9
\$\begingroup\$

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.

\$\endgroup\$
5
  • 4
    \$\begingroup\$ Is this the same as, "find the number of expressions of n matched parentheses pairs that contain exactly k instances of ()"? \$\endgroup\$
    – xnor
    Sep 30, 2018 at 20:36
  • 4
    \$\begingroup\$ https://oeis.org/A001263? \$\endgroup\$
    – xnor
    Sep 30, 2018 at 20:40
  • \$\begingroup\$ @xnor yes it is. \$\endgroup\$ Sep 30, 2018 at 21:30
  • 4
    \$\begingroup\$ You may want to update the challenge with a more explicit title such as Compute Narayana Numbers. \$\endgroup\$
    – Arnauld
    Oct 1, 2018 at 9:16
  • \$\begingroup\$ 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? \$\endgroup\$ Oct 1, 2018 at 11:28

12 Answers 12

7
\$\begingroup\$

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

\$\endgroup\$
6
\$\begingroup\$

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.
\$\endgroup\$
4
  • \$\begingroup\$ Wait... tail is automatically defined as 2 numbers? (Don't know Jelly at all, just a silly question) \$\endgroup\$
    – Quintec
    Sep 30, 2018 at 21:51
  • \$\begingroup\$ @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 \$\endgroup\$
    – dylnan
    Sep 30, 2018 at 21:56
  • \$\begingroup\$ Gotcha, thanks! I see how jelly was built for golf... hehe \$\endgroup\$
    – Quintec
    Sep 30, 2018 at 21:59
  • 1
    \$\begingroup\$ Another variant for 7 f(n,k): cⱮ×ƝṪ÷⁸ \$\endgroup\$ Sep 30, 2018 at 22:14
4
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ -3 bytes with currying. \$\endgroup\$
    – Shaggy
    Sep 30, 2018 at 22:55
  • \$\begingroup\$ @Shaggy Doh... Thanks. Revision #7 finally looks like revision #1 should have. :p \$\endgroup\$
    – Arnauld
    Sep 30, 2018 at 22:59
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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   
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ ⊢÷⍨!×⊢!⍨¯1+⊣ for 12 bytes, argument reversed \$\endgroup\$ Oct 1, 2018 at 10:38
  • \$\begingroup\$ @GalenIvanov Thanks, my tacit APL is extremely weak \$\endgroup\$
    – Quintec
    Oct 1, 2018 at 12:51
  • \$\begingroup\$ My APL as not good, I just took the opportunity to give it a try, after my J solution :) \$\endgroup\$ Oct 1, 2018 at 12:53
1
\$\begingroup\$

Ruby, 50 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
3
  • \$\begingroup\$ You can save 2 bytes by removing the spaces after \ and after x \$\endgroup\$ Oct 1, 2018 at 12:21
  • 1
    \$\begingroup\$ Just updated thanks \$\endgroup\$
    – JRowan
    Oct 1, 2018 at 12:24
  • \$\begingroup\$ Suggest (*(1- x)x) instead of (* x(1- x)) \$\endgroup\$
    – ceilingcat
    Oct 18, 2018 at 4:26
1
\$\begingroup\$

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

\$\endgroup\$
0
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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 
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.