9

Masalah

Diberi nilai n, bayangkan lanskap gunung yang tertulis dalam referensi (0, 0) hingga (2n, 0). Tidak ada ruang putih di antara lereng dan juga gunung tidak turun di bawah sumbu x. Masalah yang harus dipecahkan adalah: mengingat n (yang menentukan ukuran lanskap) dan jumlah k puncak (k selalu kurang dari atau sama dengan n), berapa banyak kombinasi gunung yang mungkin dengan k puncak?

Memasukkan

n yang mewakili lebar lanskap dan k yang merupakan jumlah puncak.

Keluaran

Jumlah kombinasi yang dimungkinkan.

Contoh

Diberikan n = 3 dan k = 2 jawabannya adalah 3 kombinasi.

Hanya untuk memberikan contoh visual, mereka adalah sebagai berikut:

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

adalah 3 kombinasi yang mungkin menggunakan 6 (3 * 2) posisi dan 2 puncak.

Edit: - lebih banyak contoh -

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

Kondisi menang

Aturan standar kode-golf berlaku. Pengajuan terpendek dalam byte menang.

code-golf combinatorics recursion kombinasi D
sumber

4

Apakah ini sama dengan, "temukan jumlah ekspresi npasangan kurung yang cocok yang persis sama dengan kcontoh ()"?

xnor

4

https://oeis.org/A001263 ?

xnor

@xnor ya itu.

Jonathan Allan

4

Anda mungkin ingin memperbarui tantangan dengan judul yang lebih eksplisit seperti Hitung Angka Narayana .

Arnauld

Bisakah Anda mengonfirmasi apakah input dengan knol harus ditangani? Jika demikian haruskah input dengan nsama dengan nol (dengan kjuga nol menurut definisi) ditangani?

Jonathan Allan

7

Python, 40 byte

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

Cobalah online!

Menggunakan pengulangan $a_{n,1} = 1$ , $a_{n,k} = \frac{n(n-1)}{k(k-1)}a_{n-1,k-1}$ .

Anders Kaseorg
sumber

6

Jelly , 7 byte

cⱮṫ-P÷⁸

Cobalah online!

Mengambil input saat nitu k. Menggunakan formula

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

yang saya temukan di Wikipedia .

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 byte

Setiap baris berfungsi sendiri.

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

Mengambil input saat kitu n.

7 byte

cⱮ×ƝṪ÷⁸

Terima kasih kepada Jonathan Allan untuk yang satu ini.

dylnan
sumber

Tunggu ... ekor secara otomatis didefinisikan sebagai 2 angka? (Tidak tahu Jelly sama sekali, hanya pertanyaan konyol)

Quintec

@ Quintec Ada dua fungsi ekor. Satu ( Ṫ) yang hanya mengambil elemen terakhir dari satu argumen dan yang saya gunakan ( ṫ) yang mengambil dua argumen. Argumen pertama adalah daftar dan yang kedua adalah angka (Dalam kasus saya -1diwakili oleh -dalam kode) yang memberi tahu Anda berapa banyak elemen yang harus disimpan. Setelah -1memberikan dua elemen adalah cara golf untuk mendefinisikanṫ

dylnan

Gotcha, terima kasih! Saya melihat bagaimana jeli dibangun untuk golf ... hehe

Quintec

1

Varian lain untuk 7 f (n, k):cⱮ×ƝṪ÷⁸

Jonathan Allan

4

JavaScript (ES6), 33 30 byte

Disimpan 3 byte berkat @Shaggy

Mengambil input sebagai (n)(k).

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

Cobalah online!

Menerapkan definisi rekursif yang digunakan oleh Anders Kaseorg .

JavaScript (ES7), 59 58 49 45 byte

Mengambil input sebagai (n)(k).

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

Cobalah online!

Menghitung:

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

Berasal dari A001263 (rumus pertama).

Arnauld
sumber

-3 byte dengan kari.

Shaggy

@Shaggy Doh ... Terima kasih. Revisi # 7 akhirnya terlihat seperti revisi # 1 seharusnya. : p

Arnauld

3

Bahasa Wolfram (Mathematica) , 27 byte

Tiga versi, semuanya memiliki panjang yang sama:

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

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

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

Cobalah online! (Hanya versi pertama, tetapi Anda dapat menyalin dan menempel untuk mencoba yang lain.)

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

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

Misha Lavrov
sumber

2

J , 17 11 byte

]%~!*<:@[!]

Cobalah online!

Dibawa nsebagai argumen yang benar, ksebagai argumen kiri. Menggunakan rumus yang sama dengan jawaban Jelly dylnan dan solusi APL Quintec.

Penjelasan:

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

Galen Ivanov
sumber

2

APL (Dyalog), 19 18 16 12 byte

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

Terima kasih kepada @Galen Ivanov untuk -4 byte

Menggunakan identitas dalam urutan OEIS. Mengambil k di kiri dan n di kanan.

TIO

Quintec
sumber

⊢÷⍨!×⊢!⍨¯1+⊣untuk 12 byte , argumen dibalik

Galen Ivanov

@ GalenIvanov Terima kasih, APL diam-diam saya sangat lemah

Quintec

APL saya tidak bagus, saya hanya mengambil kesempatan untuk mencobanya, setelah solusi J saya :)

Galen Ivanov

1

Ruby , 50 byte

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

Cobalah online!

GB
sumber

1

Common Lisp , 76 byte

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

Cobalah online!

JRowan
sumber

Anda dapat menyimpan 2 byte dengan menghapus spasi setelah \ dan setelah x

Galen Ivanov

1

Baru saja diperbarui, terima kasih

JRowan

Sarankan (*(1- x)x)alih-alih(* x(1- x))

ceilingcat

1

Perl 6 , 33 byte

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

Cobalah online!

Menggunakan formula

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

Penjelasan

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

Versi alternatif, 39 byte

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

Cobalah online!

Menggunakan rumus dari jawaban Arnauld:

{Sebuah}_{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
sumber

0

Jelly , 8 byte

,’$c’}P:

Tautan diad menerima ndi sebelah kiri dan kdi sebelah kanan yang menghasilkan hitungan.

Cobalah online!

Jonathan Allan
sumber

0

Stax , 9 byte

ÇäO╪∙╜5‼O

Jalankan dan debug itu

Saya menggunakan formula dylnan di stax.

Membongkar, tidak bertali, dan berkomentar programnya terlihat seperti ini

        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

Jalankan yang ini

rekursif
sumber

0

APL (NARS), 17 karakter, 34 byte

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

uji:

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

RosLuP
sumber

Kombinasi yang berbeda dimungkinkan

Jawaban:

Python, 40 byte

Jelly , 7 byte

JavaScript (ES6), 33 30 byte

JavaScript (ES7), 59 58 49 45 byte

Bahasa Wolfram (Mathematica) , 27 byte

J , 17 11 byte

Penjelasan:

APL (Dyalog), 19 18 16 12 byte

Ruby , 50 byte

Common Lisp , 76 byte

Perl 6 , 33 byte

Penjelasan

Versi alternatif, 39 byte

Jelly , 8 byte

Stax , 9 byte

APL (NARS), 17 karakter, 34 byte