# Different combinations possible

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 rules apply. The shortest submission in bytes wins.

• Is this the same as, "find the number of expressions of n matched parentheses pairs that contain exactly k instances of ()"?
– xnor
Sep 30, 2018 at 20:36
• – xnor
Sep 30, 2018 at 20:40
• @xnor yes it is. Sep 30, 2018 at 21:30
• You may want to update the challenge with a more explicit title such as Compute Narayana Numbers. Oct 1, 2018 at 9:16
• Could you confirm whether or not an input with k of zero must be handled? If so must an input with n equal to zero (with k also zero by definition) be handled? Oct 1, 2018 at 11:28

# 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}\$$.

# 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. • Wait... tail is automatically defined as 2 numbers? (Don't know Jelly at all, just a silly question) Sep 30, 2018 at 21:51 • @Quintec There are two tail functions. One (Ṫ) that just takes the last element of a single argument and the one I used (ṫ) which takes two arguments. The fist argument is a list and the second one is a number (In my case -1 represented by a - in the code) which tells you how many elements to save. Having -1 give two elements was the golfiest way to define ṫ Sep 30, 2018 at 21:56 • Gotcha, thanks! I see how jelly was built for golf... hehe Sep 30, 2018 at 21:59 • Another variant for 7 f(n,k): cⱮ×ƝṪ÷⁸ Sep 30, 2018 at 22:14 # 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), 595849 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). • -3 bytes with currying. Sep 30, 2018 at 22:55 • @Shaggy Doh... Thanks. Revision #7 finally looks like revision #1 should have. :p Sep 30, 2018 at 22:59 # 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. # 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  # APL(Dyalog), 191816 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 • ⊢÷⍨!×⊢!⍨¯1+⊣ for 12 bytes, argument reversed Oct 1, 2018 at 10:38 • @GalenIvanov Thanks, my tacit APL is extremely weak Oct 1, 2018 at 12:51 • My APL as not good, I just took the opportunity to give it a try, after my J solution :) Oct 1, 2018 at 12:53 # Ruby, 50 bytes ->l,n{eval [[*n..l]*2*?*,l,n,[*1..l-=n]*2,l+1]*?/}  Try it online! # 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! • You can save 2 bytes by removing the spaces after \ and after x Oct 1, 2018 at 12:21 • Just updated thanks Oct 1, 2018 at 12:24 • Suggest (*(1- x)x) instead of (* x(1- x)) Oct 18, 2018 at 4:26 # 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}$$ # 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!

# 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

# 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