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\$
  • 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 '18 at 20:36
  • 4
    \$\begingroup\$ https://oeis.org/A001263? \$\endgroup\$ – xnor Sep 30 '18 at 20:40
  • \$\begingroup\$ @xnor yes it is. \$\endgroup\$ – Jonathan Allan Sep 30 '18 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 '18 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\$ – Jonathan Allan Oct 1 '18 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\$
  • \$\begingroup\$ Wait... tail is automatically defined as 2 numbers? (Don't know Jelly at all, just a silly question) \$\endgroup\$ – Quintec Sep 30 '18 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 '18 at 21:56
  • \$\begingroup\$ Gotcha, thanks! I see how jelly was built for golf... hehe \$\endgroup\$ – Quintec Sep 30 '18 at 21:59
  • 1
    \$\begingroup\$ Another variant for 7 f(n,k): cⱮ×ƝṪ÷⁸ \$\endgroup\$ – Jonathan Allan Sep 30 '18 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\$
  • \$\begingroup\$ -3 bytes with currying. \$\endgroup\$ – Shaggy Sep 30 '18 at 22:55
  • \$\begingroup\$ @Shaggy Doh... Thanks. Revision #7 finally looks like revision #1 should have. :p \$\endgroup\$ – Arnauld Sep 30 '18 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\$
  • \$\begingroup\$ ⊢÷⍨!×⊢!⍨¯1+⊣ for 12 bytes, argument reversed \$\endgroup\$ – Galen Ivanov Oct 1 '18 at 10:38
  • \$\begingroup\$ @GalenIvanov Thanks, my tacit APL is extremely weak \$\endgroup\$ – Quintec Oct 1 '18 at 12:51
  • \$\begingroup\$ My APL as not good, I just took the opportunity to give it a try, after my J solution :) \$\endgroup\$ – Galen Ivanov Oct 1 '18 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\$
  • \$\begingroup\$ You can save 2 bytes by removing the spaces after \ and after x \$\endgroup\$ – Galen Ivanov Oct 1 '18 at 12:21
  • 1
    \$\begingroup\$ Just updated thanks \$\endgroup\$ – JRowan Oct 1 '18 at 12:24
  • \$\begingroup\$ Suggest (*(1- x)x) instead of (* x(1- x)) \$\endgroup\$ – ceilingcat Oct 18 '18 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
\$\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.