Different combinations possible
Clash Royale CLAN TAG#URR8PPP
up vote
9
down vote
favorite
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.
code-golf combinatorics recursion
edited Oct 1 at 0:01
Bubbler
3,837541
asked Sep 30 at 20:10
combinationsD
462
New contributor
combinationsD is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
9
down vote
favorite
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.
code-golf combinatorics recursion
edited Oct 1 at 0:01
Bubbler
3,837541
asked Sep 30 at 20:10
combinationsD
462
New contributor
combinationsD is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
4
Is this the same as, "find the number of expressions ofnmatched parentheses pairs that contain exactlykinstances of()"?
– xnor
Sep 30 at 20:36
4
https://oeis.org/A001263?
– xnor
Sep 30 at 20:40
@xnor yes it is.
– Jonathan Allan
Sep 30 at 21:30
4
You may want to update the challenge with a more explicit title such as Compute Narayana Numbers.
– Arnauld
Oct 1 at 9:16
Could you confirm whether or not an input withkof zero must be handled? If so must an input withnequal to zero (withkalso zero by definition) be handled?
– Jonathan Allan
Oct 1 at 11:28
add a comment |Â
up vote
9
down vote
favorite
up vote
9
down vote
favorite
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.
code-golf combinatorics recursion
edited Oct 1 at 0:01
Bubbler
3,837541
asked Sep 30 at 20:10
combinationsD
462
New contributor
combinationsD is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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.
code-golf combinatorics recursion
code-golf combinatorics recursion
edited Oct 1 at 0:01
Bubbler
3,837541
asked Sep 30 at 20:10
combinationsD
462
New contributor
combinationsD is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Oct 1 at 0:01
Bubbler
3,837541
asked Sep 30 at 20:10
combinationsD
462
New contributor
combinationsD is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Oct 1 at 0:01
Bubbler
3,837541
edited Oct 1 at 0:01
Bubbler
3,837541
edited Oct 1 at 0:01
Bubbler
3,837541
3,837541
asked Sep 30 at 20:10
combinationsD
462
New contributor
combinationsD is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Sep 30 at 20:10
combinationsD
462
asked Sep 30 at 20:10
combinationsD
462
462
New contributor
combinationsD is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
combinationsD is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
combinationsD is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
4
Is this the same as, "find the number of expressions ofnmatched parentheses pairs that contain exactlykinstances of()"?
– xnor
Sep 30 at 20:36
4
https://oeis.org/A001263?
– xnor
Sep 30 at 20:40
@xnor yes it is.
– Jonathan Allan
Sep 30 at 21:30
4
You may want to update the challenge with a more explicit title such as Compute Narayana Numbers.
– Arnauld
Oct 1 at 9:16
Could you confirm whether or not an input withkof zero must be handled? If so must an input withnequal to zero (withkalso zero by definition) be handled?
– Jonathan Allan
Oct 1 at 11:28
add a comment |Â
4
Is this the same as, "find the number of expressions ofnmatched parentheses pairs that contain exactlykinstances of()"?
– xnor
Sep 30 at 20:36
4
https://oeis.org/A001263?
– xnor
Sep 30 at 20:40
@xnor yes it is.
– Jonathan Allan
Sep 30 at 21:30
4
You may want to update the challenge with a more explicit title such as Compute Narayana Numbers.
– Arnauld
Oct 1 at 9:16
Could you confirm whether or not an input withkof zero must be handled? If so must an input withnequal to zero (withkalso zero by definition) be handled?
– Jonathan Allan
Oct 1 at 11:28
4
4
Is this the same as, "find the number of expressions of
n matched parentheses pairs that contain exactly k instances of ()"?– xnor
Sep 30 at 20:36
Is this the same as, "find the number of expressions of
n matched parentheses pairs that contain exactly k instances of ()"?– xnor
Sep 30 at 20:36
4
4
https://oeis.org/A001263?
– xnor
Sep 30 at 20:40
https://oeis.org/A001263?
– xnor
Sep 30 at 20:40
@xnor yes it is.
– Jonathan Allan
Sep 30 at 21:30
@xnor yes it is.
– Jonathan Allan
Sep 30 at 21:30
4
4
You may want to update the challenge with a more explicit title such as Compute Narayana Numbers.
– Arnauld
Oct 1 at 9:16
You may want to update the challenge with a more explicit title such as Compute Narayana Numbers.
– Arnauld
Oct 1 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?– Jonathan Allan
Oct 1 at 11:28
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?– Jonathan Allan
Oct 1 at 11:28
add a comment |Â
12 Answers
12
active
oldest
votes
up vote
7
down vote
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 = fracn(n-1)k(k-1)a_n-1,k-1$.
answered Sep 30 at 22:28
Anders Kaseorg
25.2k14290
add a comment |Â
up vote
6
down vote
Jelly, 7 bytes
cⱮṫ-P։¸
Try it online!
Takes input as n then k. Uses the formula
$N(n,k)=frac1nbinomnkbinomnk-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.
answered Sep 30 at 21:31
dylnan
3,9982529
Wait... tail is automatically defined as 2 numbers? (Don't know Jelly at all, just a silly question)
– Quintec
Sep 30 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-1represented by a-in the code) which tells you how many elements to save. Having-1give two elements was the golfiest way to defineṫ
– dylnan
Sep 30 at 21:56
Gotcha, thanks! I see how jelly was built for golf... hehe
– Quintec
Sep 30 at 21:59
1
Another variant for 7 f(n,k):câ±®×ÆÂṪ÷â¸
– Jonathan Allan
Sep 30 at 22:14
add a comment |Â
up vote
4
down vote
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=frac1kbinomn-1k-1binomnk-1=frac1nbinomnkbinomnk-1=frac1nbinomnk^2timesfrackn-k+1$$
Derived from A001263 (first formula).
answered Sep 30 at 21:31
Arnauld
66k583278
-3 bytes with currying.
– Shaggy
Sep 30 at 22:55
@Shaggy Doh... Thanks. Revision #7 finally looks like revision #1 should have. :p
– Arnauld
Sep 30 at 22:59
add a comment |Â
up vote
3
down vote
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
answered Oct 1 at 9:05
Galen Ivanov
5,0171929
add a comment |Â
up vote
3
down vote
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 $$fracn!(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.
answered Oct 1 at 15:49
Misha Lavrov
3,407320
add a comment |Â
up vote
2
down vote
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
answered Sep 30 at 21:41
Quintec
855517
⊢÷â¨!×⊢!⨯1+⊣for 12 bytes, argument reversed
– Galen Ivanov
Oct 1 at 10:38
@GalenIvanov Thanks, my tacit APL is extremely weak
– Quintec
Oct 1 at 12:51
My APL as not good, I just took the opportunity to give it a try, after my J solution :)
– Galen Ivanov
Oct 1 at 12:53
add a comment |Â
up vote
1
down vote
Ruby, 50 bytes
->l,neval [[*n..l]*2*?*,l,n,[*1..l-=n]*2,l+1]*?/
Try it online!
answered Oct 1 at 6:34
G B
6,8371325
add a comment |Â
up vote
1
down vote
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!
answered Oct 1 at 12:14
JRowan
1414
You can save 2 bytes by removing the spaces after and after x
– Galen Ivanov
Oct 1 at 12:21
1
Just updated thanks
– JRowan
Oct 1 at 12:24
add a comment |Â
up vote
1
down vote
Perl 6, 33 bytes
[*] ($^n-$^k X/(2..$k X-^2))X+1
Try it online!
Uses the formula
$$a_n,k=binomn-1k-1timesfrac1kbinomnk-1=prod_i=1^k-1(fracn-ki+1)timesprod_i=2^k(fracn-ki+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
@_)²/(1+[-] @_)/[/] @_
Try it online!
Uses the formula from Arnauld's answer:
$$a_n,k=frac1nbinomnk^2timesfrackn-k+1$$
answered Oct 1 at 11:22
nwellnhof
4,028715
add a comment |Â
up vote
0
down vote
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!
answered Sep 30 at 21:29
Jonathan Allan
48.8k534161
add a comment |Â
up vote
0
down vote
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
Â
up vote
1
down vote
Perl 6, 33 bytes
[*] ($^n-$^k X/(2..$k X-^2))X+1
Try it online!
Uses the formula
$$a_n,k=binomn-1k-1timesfrac1kbinomnk-1=prod_i=1^k-1(fracn-ki+1)timesprod_i=2^k(fracn-ki+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
@_)²/(1+[-] @_)/[/] @_
Try it online!
Uses the formula from Arnauld's answer:
$$a_n,k=frac1nbinomnk^2timesfrackn-k+1$$
answered Sep 30 at 21:29
Jonathan Allan
48.8k534161
add a comment |Â
up vote
0
down vote
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!
answered Sep 30 at 21:29
Jonathan Allan
48.8k534161
add a comment |Â
up vote
0
down vote
up vote
0
down vote
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!
answered Sep 30 at 21:29
Jonathan Allan
48.8k534161
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!
answered Sep 30 at 21:29
Jonathan Allan
48.8k534161
answered Sep 30 at 21:29
Jonathan Allan
48.8k534161
answered Sep 30 at 21:29
Jonathan Allan
48.8k534161
answered Sep 30 at 21:29
Jonathan Allan
48.8k534161
48.8k534161
add a comment |Â
add a comment |Â
up vote
0
down vote
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
answered Oct 1 at 16:18
recursive
4,4961220
add a comment |Â
up vote
0
down vote
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
answered Oct 1 at 16:18
recursive
4,4961220
add a comment |Â
up vote
0
down vote
up vote
0
down vote
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
answered Oct 1 at 16:18
recursive
4,4961220
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
answered Oct 1 at 16:18
recursive
4,4961220
answered Oct 1 at 16:18
recursive
4,4961220
answered Oct 1 at 16:18
recursive
4,4961220
answered Oct 1 at 16:18
recursive
4,4961220
4,4961220
add a comment |Â
add a comment |Â
up vote
0
down vote
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
answered Oct 2 at 6:47
RosLuP
1,540514
add a comment |Â
up vote
0
down vote
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
answered Oct 2 at 6:47
RosLuP
1,540514
add a comment |Â
up vote
0
down vote
up vote
0
down vote
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
answered Oct 2 at 6:47
RosLuP
1,540514
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
answered Oct 2 at 6:47
RosLuP
1,540514
answered Oct 2 at 6:47
RosLuP
1,540514
answered Oct 2 at 6:47
RosLuP
1,540514
answered Oct 2 at 6:47
RosLuP
1,540514
1,540514
add a comment |Â
add a comment |Â
combinationsD is a new contributor. Be nice, and check out our Code of Conduct.
combinationsD is a new contributor. Be nice, and check out our Code of Conduct.
combinationsD is a new contributor. Be nice, and check out our Code of Conduct.
combinationsD is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f173081%2fdifferent-combinations-possible%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
4
Is this the same as, "find the number of expressions of
nmatched parentheses pairs that contain exactlykinstances of()"?– xnor
Sep 30 at 20:36
4
https://oeis.org/A001263?
– xnor
Sep 30 at 20:40
@xnor yes it is.
– Jonathan Allan
Sep 30 at 21:30
4
You may want to update the challenge with a more explicit title such as Compute Narayana Numbers.
– Arnauld
Oct 1 at 9:16
Could you confirm whether or not an input with
kof zero must be handled? If so must an input withnequal to zero (withkalso zero by definition) be handled?– Jonathan Allan
Oct 1 at 11:28