Возможны разные комбинации

9

проблема

Учитывая значение n, представьте горный пейзаж, вписанный в ссылку (0, 0) - (2n, 0). Между склонами не должно быть пробелов, а гора не должна опускаться ниже оси x. Задача, которая должна быть решена: при заданном n (который определяет размер ландшафта) и числе k пиков (k всегда меньше или равно n), сколько комбинаций гор возможно с k пиками?

вход

n, который представляет ширину ландшафта и k, который является числом пиков.

Вывод

Просто количество возможных комбинаций.

пример

При n = 3 и k = 2 ответом является 3 комбинации.

Просто для наглядного примера, они следующие:

   /\     /\      /\/\
/\/  \   /  \/\  /    \

возможны 3 комбинации с использованием 6 (3 * 2) позиций и 2 пиков.

Изменить: - больше примеров -

n  k  result
2  1  1
4  1  1
4  3  6
5  2  10

Выигрышное условие

стандарт правила применяются. Самая короткая подача в байтах побеждает.

combinationsD
источник
4
Это то же самое, что «найти количество выражений nпар совпадающих скобок, которые содержат точно kэкземпляры ()»?
xnor
@ xnor да, это так.
Джонатан Аллан
4
Возможно, вы захотите обновить задачу с более явным названием, например, Compute Narayana Numbers .
Арно
Не могли бы вы подтвердить, kдолжен ли обрабатываться ввод с нулем? Если да, то должен ли обрабатываться вход с nнулем (с kнулем по определению)?
Джонатан Аллан

Ответы:

7

Python, 40 байт

f=lambda n,k:k<2or~-n*n*f(n-1,k-1)/~-k/k

Попробуйте онлайн!

Использует повторение , .an,1=1an,k=n(n1)k(k1)an1,k1

Андерс Касеорг
источник
6

Желе , 7 байт

cⱮṫ-P÷⁸

Попробуйте онлайн!

Принимает входные данные как nтогда k. Использует формулу

N(n,k)=1n(nk)(nk1)

который я нашел в Википедии .

cⱮṫ-P÷⁸
c        Binomial coefficient of n and...
 Ɱ       each of 1..k
  ṫ-     Keep the last two. ṫ is tail, - is -1.
    P    Product of the two numbers.
     ÷   Divide by
      ⁸  n.

7 байт

Каждая строка работает самостоятельно.

,’$c@P÷
c@€ṫ-P÷

Принимает входные данные как kтогда n.

7 байт

cⱮ×ƝṪ÷⁸
  • Спасибо Джонатану Аллану за это.
dylnan
источник
Подождите ... хвост автоматически определяется как 2 числа? (
Вообще
@ Quintec Есть две функции хвоста. Один ( ), который просто принимает последний элемент одного аргумента, и тот, который я использовал ( ), который принимает два аргумента. Первый аргумент - это список, а второй - число (в моем случае это -1обозначено -в коде символом a ), которое указывает, сколько элементов нужно сохранить. Имея -1ДАЙ два элемента был golfiest способ определить
dylnan
Попался, спасибо! Я вижу, как желе было построено для гольфа ... хе-хе
Quintec
1
Другой вариант для 7 f (n, k):cⱮ×ƝṪ÷⁸
Джонатан Аллан
4

JavaScript (ES6), 33 30 байт

Сохранено 3 байта благодаря @Shaggy

Принимает вход как (n)(k).

n=>g=k=>--k?n*--n/-~k/k*g(k):1

Попробуйте онлайн!

Реализует рекурсивное определение, используемое Anders Kaseorg .


JavaScript (ES7), 59 58 49 45 байт

Принимает вход как (n)(k).

n=>k=>k/n/(n-k+1)*(g=_=>k?n--/k--*g():1)()**2

Попробуйте онлайн!

Вычисляет:

an,k=1k(n1k1)(nk1)=1n(nk)(nk1)=1n(nk)2×knk+1

Получено из A001263 (первая формула).

Arnauld
источник
-3 байта с каррированием.
Лохматый
@ Shaggy Doh ... Спасибо. Версия №7, наконец, выглядит так, как должна быть версия № 1. : p
Арнаулд
3

Wolfram Language (Mathematica) , 27 байтов

Три версии одинаковой длины:

(b=Binomial)@##b[#,#2-1]/#&

Binomial@##^2#2/(#-#2+1)/#&

1/(Beta[#2,d=#-#2+1]^2d##)&

Попробуйте онлайн! (Только первая версия, но вы можете скопировать и вставить, чтобы попробовать другие.)

Все они являются своего рода вариантом для Которая является формулой, которая используется. Я надеялся попасть куда-нибудь с бета-функцией, которая является своего рода биномиальной взаимностью, но потом произошло слишком много делений.

n!(n1)!k!(k1)!(nk)!(nk1)!

Миша лавров
источник
2

J , 17 11 байт

]%~!*<:@[!]

Попробуйте онлайн!

Принимает nза правый аргумент, kза левый. Используется та же формула, что и в ответе на желе от Dylnan и в решении APL от Quintec.

Объяснение:

            ] - n  
           !  - choose
       <:@[   - k-1
      *       - multiplied by
     !        - n choose k
   %~         - divided by
  ]           - n   
Гален Иванов
источник
2

APL (Dyalog), 19 18 16 12 байтов

⊢÷⍨!×⊢!⍨¯1+⊣

Спасибо @Galen Иванову за -4 байта

Использует идентификатор в последовательности OEIS. Принимает k слева и n справа.

TIO

Quintec
источник
⊢÷⍨!×⊢!⍨¯1+⊣для 12 байтов , аргумент полностью изменен
Гален Иванов
@GalenIvanov Спасибо, мой молчаливый APL очень слабый
Quintec
Мой APL не очень хороший, я просто воспользовался возможностью, чтобы попытаться, после моего решения J :)
Гален Иванов
1

Common Lisp , 76 байт

(defun x(n k)(cond((= k 1)1)(t(*(/(* n(1- n))(* k(1- k)))(x(1- n)(1- k))))))

Попробуйте онлайн!

JRowan
источник
Вы можете сэкономить 2 байта, удалив пробелы после \ и после x
Гален Иванов
1
Только что обновил спасибо
JRowan
Предлагаю (*(1- x)x)вместо(* x(1- x))
floorcat
1

Perl 6 , 33 байта

{[*] ($^n-$^k X/(2..$k X-^2))X+1}

Попробуйте онлайн!

Использует формулу

an,k=(n1k1)×1k(nk1)=i=1k1(nki+1)×i=2k(nki+1)

объяснение

{[*]                            }  # Product of
     ($^n-$^k X/                   # n-k divided by
                (2..$k X-^2))      # numbers in ranges [1,k-1], [2,k]
                             X+1   # plus one.

Альтернативная версия, 39 байт

{combinations(|@_)²/(1+[-] @_)/[/] @_}

Попробуйте онлайн!

Использует формулу из ответа Арно:

an,k=1n(nk)2×knk+1

nwellnhof
источник
0

Stax , 9 байт

ÇäO╪∙╜5‼O

Запустите и отладьте его

Я использую формулу Дилнана в Stax.

Распакованная, разархивированная и прокомментированная программа выглядит следующим образом.

        program begins with `n` and `k` on input stack
{       begin block for mapping
  [     duplicate 2nd element from top of stack (duplicates n)
  |C    combinatorial choose operation
m       map block over array, input k is implicitly converted to [1..k]
O       push integer one *underneath* mapped array
E       explode array onto stack
*       multiply top two elements - if array had only element, then the pushed one is used
,/      pop `n` from input stack and divide

Запустите этот

рекурсивный
источник
0

APL (NARS), 17 символов, 34 байта

{⍺÷⍨(⍵!⍺)×⍺!⍨⍵-1}

тестовое задание:

  f←{⍺÷⍨(⍵!⍺)×⍺!⍨⍵-1}
  (2 f 1)(4 f 1)(4 f 3)(5 f 2)    
1 1 6 10 
RosLuP
источник