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

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

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

code-golf combinatorics recursion combinationsD
источник

4

Это то же самое, что «найти количество выражений nпар совпадающих скобок, которые содержат точно kэкземпляры ()»?

xnor

4

https://oeis.org/A001263 ?

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

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

Использует повторение , . $a_{n,1} = 1$ $a_{n,k} = \frac{n(n-1)}{k(k-1)}a_{n-1,k-1}$

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

6

Желе , 7 байт

cⱮṫ-P÷⁸

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

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

$N(n,k)=\frac{1}{n}\binom{n}{k}\binom{n}{k-1}$

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

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

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

Вычисляет:

a_{n, k} = \frac{1}{k} (\binom{n - 1}{k - 1}) (\binom{n}{k - 1}) = \frac{1}{n} (\binom{n}{k}) (\binom{n}{k - 1}) = \frac{1}{n} {(\binom{n}{k})}^{2} \times \frac{k}{n - k + 1}

$a_{n,k}=\frac{1}{k}\binom{n-1}{k-1}\binom{n}{k-1}=\frac{1}{n}\binom{n}{k}\binom{n}{k-1}=\frac{1}{n}\binom{n}{k}^2\times\frac{k}{n-k+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##)&

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

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

\frac{n! (n - 1)!}{k! (k - 1)! (n - k)! (n - k - 1)!}

$\frac{n!(n-1)!}{k!(k-1)!(n-k)!(n-k-1)!}$

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

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

Рубин , 50 байтов

->l,n{eval [[*n..l]*2*?*,l,n,[*1..l-=n]*2,l+1]*?/}

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

гигабайт
источник

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}

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

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

a_{n, k} = (\binom{n - 1}{k - 1}) \times \frac{1}{k} (\binom{n}{k - 1}) = \prod_{i = 1}^{k - 1} (\frac{n - k}{i} + 1) \times \prod_{i = 2}^{k} (\frac{n - k}{i} + 1)

$a_{n,k}=\binom{n-1}{k-1}\times\frac{1}{k}\binom{n}{k-1}=\prod_{i=1}^{k-1}(\frac{n-k}{i}+1)\times\prod_{i=2}^{k}(\frac{n-k}{i}+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+[-] @_)/[/] @_}

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

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

a_{n, k} = \frac{1}{n} {(\binom{n}{k})}^{2} \times \frac{k}{n - k + 1}

$a_{n,k}=\frac{1}{n}\binom{n}{k}^2\times\frac{k}{n-k+1}$

nwellnhof
источник

0

Желе , 8 байт

,’$c’}P:

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

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

Джонатан Аллан
источник

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
источник

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

Ответы:

Python, 40 байт

Желе , 7 байт

JavaScript (ES6), 33 30 байт

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

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

J , 17 11 байт

Объяснение:

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

Рубин , 50 байтов

Common Lisp , 76 байт

Perl 6 , 33 байта

объяснение

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

Желе , 8 байт

Stax , 9 байт

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