9

Problem

Stellen Sie sich bei einem Wert n eine Berglandschaft vor, die in einer Referenz (0, 0) bis (2n, 0) eingeschrieben ist. Es darf keine Leerzeichen zwischen den Hängen geben und auch der Berg darf nicht unter die x-Achse absteigen. Das zu lösende Problem ist: Wenn n (das die Größe der Landschaft definiert) und die Anzahl k der Gipfel (k immer kleiner oder gleich n) gegeben sind, wie viele Kombinationen von Bergen sind mit k Gipfeln möglich?

Eingang

n, der die Breite der Landschaft darstellt, und k, die die Anzahl der Spitzen darstellt.

Ausgabe

Nur die Anzahl der möglichen Kombinationen.

Beispiel

Bei n = 3 und k = 2 lautet die Antwort 3 Kombinationen.

Um nur ein visuelles Beispiel zu geben, sie sind die folgenden:

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

sind die 3 möglichen Kombinationen mit 6 (3 * 2) Positionen und 2 Peaks möglich.

Bearbeiten: - weitere Beispiele -

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

Gewinnbedingung

Es gelten die Standardregeln für Code-Golf . Die kürzeste Übermittlung in Bytes gewinnt.

code-golf combinatorics recursion KombinationenD
quelle

4

Ist dies dasselbe wie "Finden Sie die Anzahl der Ausdrücke nübereinstimmender Klammerpaare, die genau kInstanzen von enthalten ()"?

xnor

4

https://oeis.org/A001263 ?

xnor

@xnor ja das ist es.

Jonathan Allan

4

Möglicherweise möchten Sie die Herausforderung mit einem expliziteren Titel wie " Narayana-Zahlen berechnen" aktualisieren .

Arnauld

Können Sie bestätigen, ob eine Eingabe mit kNull behandelt werden muss oder nicht ? Wenn ja, muss eine Eingabe ngleich Null ( kper Definition auch Null) behandelt werden?

Jonathan Allan

7

Python, 40 Bytes

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

Probieren Sie es online aus!

Verwendet die Wiederholung $a_{n,1} = 1$ , $a_{n,k} = \frac{n(n-1)}{k(k-1)}a_{n-1,k-1}$ .

Anders Kaseorg
quelle

6

Gelee , 7 Bytes

cⱮṫ-P÷⁸

Probieren Sie es online aus!

Nimmt die Eingabe wie ndamals vor k. Verwendet die Formel

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

was ich auf Wikipedia gefunden habe .

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 Bytes

Jede Zeile arbeitet für sich.

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

Nimmt die Eingabe wie kdamals vor n.

7 Bytes

cⱮ×ƝṪ÷⁸

Vielen Dank an Jonathan Allan für diesen einen.

Dylnan
quelle

Warten Sie ... Schwanz wird automatisch als 2 Zahlen definiert? (Ich kenne Jelly überhaupt nicht, nur eine dumme Frage)

Quintec

@Quintec Es gibt zwei Endfunktionen. Ein ( Ṫ), das nur das letzte Element eines einzelnen Arguments verwendet, und das von mir verwendete ( ṫ), das zwei Argumente verwendet. Das erste Argument ist eine Liste und das zweite ist eine Zahl (in meinem Fall -1durch a -im Code dargestellt), die angibt, wie viele Elemente gespeichert werden sollen. Mit -1give zwei Elementen war der golfiest zu definierenṫ

dylnan

Gotcha, danke! Ich sehe, wie Gelee für Golf gebaut wurde ... hehe

Quintec

1

Eine andere Variante für 7 f (n, k):cⱮ×ƝṪ÷⁸

Jonathan Allan

4

JavaScript (ES6), 33 30 Byte

3 Bytes dank @Shaggy gespeichert

Nimmt Eingabe als (n)(k).

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

Probieren Sie es online aus!

Implementiert die von Anders Kaseorg verwendete rekursive Definition .

JavaScript (ES7), 59 58 49 45 Byte

Nimmt Eingabe als (n)(k).

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

Probieren Sie es online aus!

Berechnet:

{ein}_{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}$

Abgeleitet von A001263 (erste Formel).

Arnauld
quelle

-3 Bytes mit Curry.

Shaggy

@ Shaggy Doh ... Danke. Revision Nr. 7 sieht schließlich so aus, wie es Revision Nr. 1 haben sollte. : p

Arnauld

3

Wolfram Language (Mathematica) , 27 Bytes

Drei Versionen, alle gleich lang:

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

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

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

Probieren Sie es online aus! (Nur die erste Version, aber Sie können kopieren und einfügen, um die anderen zu versuchen.)

All dies sind eine Art Variante von , Der Formel, die es gibt. Ich hatte gehofft, mit der Beta-Funktion, die eine Art binomischer Kehrwert ist, irgendwohin zu gelangen, aber dann geschah zu viel Spaltung.

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

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

Mischa Lawrow
quelle

2

J , 17 11 Bytes

]%~!*<:@[!]

Probieren Sie es online aus!

Nimmt nals rechtes Argument, kals linkes. Verwendet die gleiche Formel wie die Jelly-Antwort von Dylnan und die APL-Lösung von Quintec.

Erläuterung:

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

Galen Ivanov
quelle

2

APL (Dyalog), 19 18 16 12 Bytes

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

Vielen Dank an @Galen Ivanov für -4 Bytes

Verwendet die Identität in der OEIS-Sequenz. Nimmt k links und n rechts.

TIO

Quintec
quelle

⊢÷⍨!×⊢!⍨¯1+⊣für 12 Bytes , Argument umgekehrt

Galen Ivanov

@GalenIvanov Danke, meine stillschweigende APL ist extrem schwach

Quintec

Meine APL als nicht gut, ich habe gerade die Gelegenheit genutzt, es nach meiner J-Lösung zu versuchen :)

Galen Ivanov

1

Ruby , 50 Bytes

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

Probieren Sie es online aus!

GB
quelle

1

Common Lisp , 76 Bytes

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

Probieren Sie es online aus!

JRowan
quelle

Sie können 2 Bytes speichern, indem Sie die Leerzeichen nach \ und nach x entfernen

Galen Ivanov

1

Gerade aktualisiert danke

JRowan

Schlagen Sie (*(1- x)x)statt(* x(1- x))

Deckenkatze

1

Perl 6 , 33 Bytes

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

Probieren Sie es online aus!

Verwendet die Formel

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

Erläuterung

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

Alternative Version, 39 Bytes

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

Probieren Sie es online aus!

Verwendet die Formel aus Arnauld's Antwort:

{ein}_{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
quelle

0

Gelee , 8 Bytes

,’$c’}P:

nLinks und krechts ein dyadischer Link, der die Zählung ergibt.

Probieren Sie es online aus!

Jonathan Allan
quelle

0

Stax , 9 Bytes

ÇäO╪∙╜5‼O

Führen Sie es aus und debuggen Sie es

Ich benutze Dylnans Formel in Stax.

Ausgepackt, ungolfed und kommentiert sieht das Programm so aus.

        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

Führen Sie diesen aus

rekursiv
quelle

0

APL (NARS), 17 Zeichen, 34 Bytes

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

Prüfung:

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

RosLuP
quelle

Verschiedene Kombinationen möglich

Antworten:

Python, 40 Bytes

Gelee , 7 Bytes

JavaScript (ES6), 33 30 Byte

JavaScript (ES7), 59 58 49 45 Byte

Wolfram Language (Mathematica) , 27 Bytes

J , 17 11 Bytes

Erläuterung:

APL (Dyalog), 19 18 16 12 Bytes

Ruby , 50 Bytes

Common Lisp , 76 Bytes

Perl 6 , 33 Bytes

Erläuterung

Alternative Version, 39 Bytes

Gelee , 8 Bytes

Stax , 9 Bytes

APL (NARS), 17 Zeichen, 34 Bytes