Different combinations possible

Question

Problem

Given a value n, imagine a mountain landscape inscribed in a reference (0, 0) to (2n, 0). There musn't be white spaces between slopes and also the mountain musn't descend below the x axis. The problem to be solved is: given n (which defines the size of the landscape) and the number k of peaks (k always less than or equal to n), how many combinations of mountains are possible with k peaks?

Input

n who represents the width of the landscape and k which is the number of peaks.

Output

Just the number of combinations possible.

Example

Given n=3 and k=2 the answer is 3 combinations.

Just to give a visual example, they are the following:

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

are the 3 combinations possible using 6 (3*2) positions and 2 peaks.

Edit: - more examples -

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

Winning condition

Standard code-golf rules apply. The shortest submission in bytes wins.

Answer 1

Python, 40 bytes

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

Try it online!

Uses the recurrence \$a_{n,1} = 1\$, \$a_{n,k} = \frac{n(n-1)}{k(k-1)}a_{n-1,k-1}\$.

Answer 2

Jelly, 7 bytes

cⱮṫ-P÷⁸

Try it online!

Takes input as n then k. Uses the formula

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

which I found on 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 bytes

Each line works on it's own.

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

Takes input as k then n.

7 bytes

cⱮ×ƝṪ÷⁸

• Thanks to Jonathan Allan for this one.

Answer 3

JavaScript (ES6), 33 30 bytes

Saved 3 bytes thanks to @Shaggy

Takes input as (n)(k).

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

Try it online!

Implements the recursive definition used by Anders Kaseorg.

---

JavaScript (ES7), 59 58 49 45 bytes

Takes input as (n)(k).

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

Try it online!

Computes:

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

Derived from A001263 (first formula).

Answer 4

Wolfram Language (Mathematica), 27 bytes

Three versions, all the same length:

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

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

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

Try it online! (Just the first version, but you can copy and paste to try the others.)

All of these are some sort of variant on $$\frac{n!(n-1)!}{k!(k-1)!(n-k)!(n-k-1)!}$$ which is the formula that's been going around. I was hoping to get somewhere with the Beta function, which is a sort of binomial reciprocal, but then there was too much division happening.

Answer 5

J, 17 11 bytes

]%~!*<:@[!]

Try it online!

Takes n as the right argument, k as the left one. Uses the same formula as dylnan's Jelly answer and Quintec's APL solution.

Explanation:

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

Answer 6

APL(Dyalog), 19 18 16 12 bytes

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

Thanks to @Galen Ivanov for -4 bytes

Uses the identity in the OEIS sequence. Takes k on the left and n on the right.

TIO

Answer 7

Ruby, 50 bytes

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

Try it online!

Answer 8

Common Lisp, 76 bytes

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

Try it online!

Answer 9

Perl 6, 33 bytes

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

Try it online!

Uses the formula

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

Explanation

{[*]                            }  # 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+[-] @_)/[/] @_}

Try it online!

Uses the formula from Arnauld's answer:

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

Answer 10

Jelly, 8 bytes

,’$c’}P:

A dyadic Link accepting n on the left and k on the right which yields the count.

Try it online!

Answer 11

Stax, 9 bytes

ÇäO╪∙╜5‼O

Run and debug it

I'm using dylnan's formula in stax.

Unpacked, ungolfed, and commented the program looks like this.

        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

Run this one

Answer 12

APL(NARS), 17 chars, 34 bytes

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

test:

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