9

Problem

Biorąc pod uwagę wartość n, wyobraź sobie górski krajobraz wpisany w odniesienie (0, 0) do (2n, 0). Pomiędzy zboczami nie może być białych przestrzeni, a góra nie może schodzić poniżej osi x. Problem do rozwiązania to: biorąc pod uwagę n (który określa rozmiar krajobrazu) i liczbę k szczytów (k zawsze mniejszych lub równych n), ile kombinacji gór jest możliwych z k szczytów?

Wejście

n, który reprezentuje szerokość krajobrazu, a k jest liczbą pików.

Wynik

Tylko liczba możliwych kombinacji.

Przykład

Biorąc pod uwagę n = 3 i k = 2 odpowiedzią są 3 kombinacje.

Aby dać wizualny przykład, są to:

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

to 3 kombinacje możliwe przy użyciu 6 (3 * 2) pozycji i 2 pików.

Edycja: - więcej przykładów -

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

Warunki wygranej

Standard golf-golfobowiązują zasady. Najkrótsze przesłanie w bajtach wygrywa.

code-golf combinatorics recursion

— kombinacje D
źródło

4

Czy to to samo, co: „znaleźć liczbę wyrażeń ndopasowanych par nawiasów, które zawierają dokładnie kwystąpienia ()”?

— xnor

4

https://oeis.org/A001263 ?

— xnor

@ xnor tak to jest.

— Jonathan Allan

4

Możesz zaktualizować wyzwanie o bardziej jednoznaczny tytuł, taki jak Obliczanie liczb Narayana .

— Arnauld

Czy możesz potwierdzić, czy wejście z kzerą musi być obsługiwane? Jeśli tak, to czy należy obsługiwać dane wejściowe nrówne zeru (z kdefinicji również zero)?

— Jonathan Allan

7

Python, 40 bajtów

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

Wypróbuj online!

Korzysta z nawrotu $a_{n,1} = 1$ , $a_{n,k} = \frac{n(n-1)}{k(k-1)}a_{n-1,k-1}$ .

— Anders Kaseorg
źródło

6

Galaretka , 7 bajtów

cⱮṫ-P÷⁸

Wypróbuj online!

Pobiera dane jak nwtedy k. Używa wzoru

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

które znalazłem na Wikipedii .

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 bajtów

Każda linia działa samodzielnie.

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

Pobiera dane jak kwtedy n.

7 bajtów

cⱮ×ƝṪ÷⁸

Podziękowania dla Jonathana Allana za ten.

— dylnan
źródło

Czekaj ... ogon jest automatycznie definiowany jako 2 liczby? (W ogóle nie znam Galaretki, tylko głupie pytanie)

— Quintec

@Quintec Istnieją dwie funkcje ogona. Jeden ( Ṫ), który bierze tylko ostatni element pojedynczego argumentu i ten, którego użyłem ( ṫ), który przyjmuje dwa argumenty. Pierwszy argument to lista, a drugi to liczba (w moim przypadku -1reprezentowana przez -w kodzie), która mówi, ile elementów należy zapisać. Mając -1otrzymując dwa elementy był golfiest sposobem definiowaniaṫ

— dylnan

Gotcha, dzięki! Widzę, jak zbudowano galaretkę do gry w golfa ... hehe

— Quintec

1

Kolejny wariant dla 7 f (n, k):cⱮ×ƝṪ÷⁸

— Jonathan Allan

4

JavaScript (ES6), 33 30 bajtów

Zaoszczędź 3 bajty dzięki @Shaggy

Pobiera dane wejściowe jako (n)(k).

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

Wypróbuj online!

Implementuje rekurencyjną definicję używaną przez Andersa Kaseorga .

JavaScript (ES7), 59 58 49 45 bajtów

Pobiera dane wejściowe jako (n)(k).

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

Wypróbuj online!

Oblicza:

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}$

Pochodzi z A001263 (pierwsza formuła).

— Arnauld
źródło

-3 bajty z curry.

— Shaggy

@Shaggy Doh ... Dzięki. Wersja 7 wreszcie wygląda tak, jak powinna mieć wersja 1. : p

— Arnauld

3

Wolfram Language (Mathematica) , 27 bajtów

Trzy wersje o tej samej długości:

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

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

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

Wypróbuj online! (Tylko pierwsza wersja, ale możesz skopiować i wkleić, aby wypróbować inne.)

Wszystkie są pewnego rodzaju wariantem

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

$\frac{n!(n-1)!}{k!(k-1)!(n-k)!(n-k-1)!}$ która jest formułą, która się kręci. Miałem nadzieję, że uda mi się gdzieś dotrzeć z funkcją Beta, która jest rodzajem dwumianowej wzajemności, ale potem nastąpiło zbyt wiele podziałów.

— Misza Ławrow
źródło

2

J , 17 11 bajtów

]%~!*<:@[!]

Wypróbuj online!

Uważa się nza właściwy argument,k za lewy. Używa tej samej formuły co odpowiedź Jelly Dylnana i rozwiązanie APL firmy Quintec.

Wyjaśnienie:

            ] - n  
           !  - choose
       <:@[   - k-1
      *       - multiplied by
     !        - n choose k
   %~         - divided by
  ]           - n

— Galen Iwanow
źródło

2

APL (Dyalog), 19 18 16 12 bajtów

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

Dzięki @Galen Iwanow za -4 bajty

Wykorzystuje tożsamość w sekwencji OEIS. Bierze k po lewej i n po prawej.

TIO

— Quintec
źródło

⊢÷⍨!×⊢!⍨¯1+⊣dla 12 bajtów , argument odwrócony

— Galen Iwanow

@GalenIvanov Dzięki, moja milcząca APL jest bardzo słaba

— Quintec

Mój APL jako niezbyt dobry, właśnie skorzystałem z okazji, aby spróbować, po moim rozwiązaniu J :)

— Galen Iwanow

1

Rubinowy , 50 bajtów

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

Wypróbuj online!

— GB
źródło

1

Common Lisp , 76 bajtów

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

Wypróbuj online!

— JRowan
źródło

Możesz zapisać 2 bajty, usuwając spacje po \ i po x

— Galen Iwanow

1

Właśnie zaktualizowane podziękowania

— JRowan

Zaproponuj (*(1- x)x)zamiast(* x(1- x))

— ceilingcat

1

Perl 6 , 33 bajtów

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

Wypróbuj online!

Używa wzoru

{za}_{n, k} = (\binom{n - 1}{k - 1}) \times \frac{1}{k} (\binom{n}{k - 1}) = \prod_{ja = 1}^{k - 1} (\frac{n - k}{ja} + 1) \times \prod_{ja = 2)}^{k} (\frac{n - k}{ja} + 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)$

Wyjaśnienie

{[*]                            }  # 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.

Alternatywna wersja, 39 bajtów

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

Wypróbuj online!

Wykorzystuje formułę z odpowiedzi Arnaulda:

{za}_{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
źródło

0

Galaretka , 8 bajtów

,’$c’}P:

Dyadyczny link akceptujący npo lewej i kpo prawej stronie, który daje wynik.

Wypróbuj online!

— Jonathan Allan
źródło

0

Stax , 9 bajtów

ÇäO╪∙╜5‼O

Uruchom i debuguj

Używam formuły Dylnana w stax.

Rozpakowany, nieprzygotowany i skomentowany program wygląda tak.

        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

Uruchom ten

— rekurencyjny
źródło

0

APL (NARS), 17 znaków, 34 bajty

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

test:

  f←{⍺÷⍨(⍵!⍺)×⍺!⍨⍵-1}
  (2 f 1)(4 f 1)(4 f 3)(5 f 2)    
1 1 6 10

— RosLuP
źródło

Możliwe różne kombinacje

Python, 40 bajtów

Galaretka , 7 bajtów

JavaScript (ES6), 33 30 bajtów

JavaScript (ES7), 59 58 49 45 bajtów

Wolfram Language (Mathematica) , 27 bajtów

J , 17 11 bajtów

Wyjaśnienie:

APL (Dyalog), 19 18 16 12 bajtów

Rubinowy , 50 bajtów

Common Lisp , 76 bajtów

Perl 6 , 33 bajtów

Wyjaśnienie

Alternatywna wersja, 39 bajtów

Galaretka , 8 bajtów

Stax , 9 bajtów

APL (NARS), 17 znaków, 34 bajty