Mixing
Combinatorics and Counting
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
Find the number of ways of selecting k cells from a $(2times n)$-board such that no two selected cells share a side (non-adjacent).
For $n=3$ and $k=2$, the answer is $8$; for $n=5$ and $k=3$, the answer is $38$.
Counting manually works for small numbers.
Question. Is there any formula that can be derived for large numbers?
nt.number-theory co.combinatorics
edited 1 hour ago
T. Amdeberhan
16.3k228122
asked 2 hours ago
Sparsh Kedia
212
New contributor
Sparsh Kedia 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
4
down vote
favorite
Find the number of ways of selecting k cells from a $(2times n)$-board such that no two selected cells share a side (non-adjacent).
For $n=3$ and $k=2$, the answer is $8$; for $n=5$ and $k=3$, the answer is $38$.
Counting manually works for small numbers.
Question. Is there any formula that can be derived for large numbers?
nt.number-theory co.combinatorics
edited 1 hour ago
T. Amdeberhan
16.3k228122
asked 2 hours ago
Sparsh Kedia
212
New contributor
Sparsh Kedia is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
@JoeSilverman: I was about to suggest that too, however, this is quite specialized, I'd say. But routine for those who have done it before...
– Per Alexandersson
2 hours ago
For small values of k you can use N(n,1)=2n and the recursion N(n,k)=N(n-1,k)+2*N(n-1,k-1). This is like Per's solution, using top-bottom symmetry, but hides some detail (and I left out a piece for you to find). This would be a good exercise for a beginning combinatorics class. If you can fully explain the recursion above, you have solved the exercise. Gerhard "Do I Get An Apple?" Paseman, 2018.10.12.
– Gerhard Paseman
1 hour ago
Oops. I miscounted. N(n,k)=N(n-1,k-1)+N(n-1,k). The full explanation of the previous recursion becomes a bonus problem. Gerhard "Always, ALWAYS Check Your Work" Paseman, 2018.10.12.
– Gerhard Paseman
1 hour ago
add a comment |Â
up vote
4
down vote
favorite
up vote
4
down vote
favorite
Find the number of ways of selecting k cells from a $(2times n)$-board such that no two selected cells share a side (non-adjacent).
For $n=3$ and $k=2$, the answer is $8$; for $n=5$ and $k=3$, the answer is $38$.
Counting manually works for small numbers.
Question. Is there any formula that can be derived for large numbers?
nt.number-theory co.combinatorics
edited 1 hour ago
T. Amdeberhan
16.3k228122
asked 2 hours ago
Sparsh Kedia
212
New contributor
Sparsh Kedia is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Find the number of ways of selecting k cells from a $(2times n)$-board such that no two selected cells share a side (non-adjacent).
For $n=3$ and $k=2$, the answer is $8$; for $n=5$ and $k=3$, the answer is $38$.
Counting manually works for small numbers.
Question. Is there any formula that can be derived for large numbers?
nt.number-theory co.combinatorics
nt.number-theory co.combinatorics
edited 1 hour ago
T. Amdeberhan
16.3k228122
asked 2 hours ago
Sparsh Kedia
212
New contributor
Sparsh Kedia is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 1 hour ago
T. Amdeberhan
16.3k228122
asked 2 hours ago
Sparsh Kedia
212
New contributor
Sparsh Kedia is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 1 hour ago
T. Amdeberhan
16.3k228122
edited 1 hour ago
T. Amdeberhan
16.3k228122
edited 1 hour ago
T. Amdeberhan
16.3k228122
16.3k228122
asked 2 hours ago
Sparsh Kedia
212
New contributor
Sparsh Kedia is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 2 hours ago
Sparsh Kedia
212
asked 2 hours ago
Sparsh Kedia
212
212
New contributor
Sparsh Kedia is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Sparsh Kedia is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Sparsh Kedia is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
@JoeSilverman: I was about to suggest that too, however, this is quite specialized, I'd say. But routine for those who have done it before...
– Per Alexandersson
2 hours ago
For small values of k you can use N(n,1)=2n and the recursion N(n,k)=N(n-1,k)+2*N(n-1,k-1). This is like Per's solution, using top-bottom symmetry, but hides some detail (and I left out a piece for you to find). This would be a good exercise for a beginning combinatorics class. If you can fully explain the recursion above, you have solved the exercise. Gerhard "Do I Get An Apple?" Paseman, 2018.10.12.
– Gerhard Paseman
1 hour ago
Oops. I miscounted. N(n,k)=N(n-1,k-1)+N(n-1,k). The full explanation of the previous recursion becomes a bonus problem. Gerhard "Always, ALWAYS Check Your Work" Paseman, 2018.10.12.
– Gerhard Paseman
1 hour ago
add a comment |Â
@JoeSilverman: I was about to suggest that too, however, this is quite specialized, I'd say. But routine for those who have done it before...
– Per Alexandersson
2 hours ago
For small values of k you can use N(n,1)=2n and the recursion N(n,k)=N(n-1,k)+2*N(n-1,k-1). This is like Per's solution, using top-bottom symmetry, but hides some detail (and I left out a piece for you to find). This would be a good exercise for a beginning combinatorics class. If you can fully explain the recursion above, you have solved the exercise. Gerhard "Do I Get An Apple?" Paseman, 2018.10.12.
– Gerhard Paseman
1 hour ago
Oops. I miscounted. N(n,k)=N(n-1,k-1)+N(n-1,k). The full explanation of the previous recursion becomes a bonus problem. Gerhard "Always, ALWAYS Check Your Work" Paseman, 2018.10.12.
– Gerhard Paseman
1 hour ago
@JoeSilverman: I was about to suggest that too, however, this is quite specialized, I'd say. But routine for those who have done it before...
– Per Alexandersson
2 hours ago
@JoeSilverman: I was about to suggest that too, however, this is quite specialized, I'd say. But routine for those who have done it before...
– Per Alexandersson
2 hours ago
For small values of k you can use N(n,1)=2n and the recursion N(n,k)=N(n-1,k)+2*N(n-1,k-1). This is like Per's solution, using top-bottom symmetry, but hides some detail (and I left out a piece for you to find). This would be a good exercise for a beginning combinatorics class. If you can fully explain the recursion above, you have solved the exercise. Gerhard "Do I Get An Apple?" Paseman, 2018.10.12.
– Gerhard Paseman
1 hour ago
For small values of k you can use N(n,1)=2n and the recursion N(n,k)=N(n-1,k)+2*N(n-1,k-1). This is like Per's solution, using top-bottom symmetry, but hides some detail (and I left out a piece for you to find). This would be a good exercise for a beginning combinatorics class. If you can fully explain the recursion above, you have solved the exercise. Gerhard "Do I Get An Apple?" Paseman, 2018.10.12.
– Gerhard Paseman
1 hour ago
Oops. I miscounted. N(n,k)=N(n-1,k-1)+N(n-1,k). The full explanation of the previous recursion becomes a bonus problem. Gerhard "Always, ALWAYS Check Your Work" Paseman, 2018.10.12.
– Gerhard Paseman
1 hour ago
Oops. I miscounted. N(n,k)=N(n-1,k-1)+N(n-1,k). The full explanation of the previous recursion becomes a bonus problem. Gerhard "Always, ALWAYS Check Your Work" Paseman, 2018.10.12.
– Gerhard Paseman
1 hour ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
5
down vote
Let $P_n(q)$ be the polynomial such that the coefficient of $q^k$ is the number of $2times n$-strips with $k$ selected boxes.
Furthermore, let $A_n(q)$, $B_n(q)$ and $C_n(q)$ be the same sequences but with restriction that the strip ends with A) one selected square at the top,
B) one selected square at the bottom, and C) no selected squares.
We have due to symmetry that $A_n(q)=B_n(q)$.
Also, $A_1(q)=q$, $C_1(q)=0$.
We can then quite easily see that
$$
A_n(q) = q B_n-1(q)+qC_n-1(q), B_n(q) =A_n-1(q)+ B_n-1(q)+C_n-1(q)
$$
or
$$
A_n(q) = q B_n-1(q)+q A_n-1(q), B_n(q) =2A_n-1(q)+ B_n-1(q).
$$
From this, (with some algebra) we can then conclude that
$$
A_n(q) = (q+1)A_n-1(q) + q A_n-2(q) qquad (ast)
$$
and
$$
B_n(q)= (2+1/q)A_n-1+A_n-2
$$
so if we can solve the recursion in $(ast)$, we are done.
With some generating functions, you can see that
$$
sum_j=0^infty A_j(q)t^j = fracq t1-(q+1)t-qt^2
quad
sum_j=0^infty B_j(q)t^j = fracq t^2+t1-(q+1)t-qt^2.
$$
It follows that the series you seek is
$$
sum_j=0^infty t^jP_j(q) = frac2 q t + q t^2 + t1 - (q + 1) t - q t^2.
$$
So, the answer to your original question is therefore
$$
frac2 q t + q t^2 + t1 - (q + 1) t - q Bigvert_t^nq^k
$$
so that the number of $2times n$-strips with $k$ selected squares is the coefficient of $t^nq^k$ in the above rational function.
answered 2 hours ago
Per Alexandersson
6,71973877
Say for eg n=5,k=3 how do I use this rational function to solve the problem?
– Sparsh Kedia
1 hour ago
add a comment |Â
up vote
2
down vote
$dots$ continued from above: to find the coefficient of $t^nq^k$, rewrite the generating function as
beginalignG(t,q):=fract+(2t+t^2)q1-t-(t+t^2)q
&=fract+(2t+t^2)q1-tcdotfrac11-left(fract+t^21-tright)q \
&=fract+(2t+t^2)q1-tsum_jgeq0left(fract+t^21-tright)^jq^j \
&=sum_kgeq0left(frac2t^k(1+t)^k-1(1-t)^k+1right)q^k.
endalign
Further calculation reveals that
$$frac2t^k(1+t)^k-1(1-t)^k+1
=sum_ngeq0left(2sum_r=0^n-kbinomn-rkbinomk-1rright)t^n.$$
In summary, the enumeration you seek becomes the coefficient of $t^nq^k$ given by
$$2sum_r=0^n-kbinomn-rkbinomk-1r.$$
This confirms your calculations: if $n=3, k=2$ then you get $8$; if $n=5, k=3$ then you get $38$.
answered 20 mins ago
T. Amdeberhan
16.3k228122
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
Let $P_n(q)$ be the polynomial such that the coefficient of $q^k$ is the number of $2times n$-strips with $k$ selected boxes.
Furthermore, let $A_n(q)$, $B_n(q)$ and $C_n(q)$ be the same sequences but with restriction that the strip ends with A) one selected square at the top,
B) one selected square at the bottom, and C) no selected squares.
We have due to symmetry that $A_n(q)=B_n(q)$.
Also, $A_1(q)=q$, $C_1(q)=0$.
We can then quite easily see that
$$
A_n(q) = q B_n-1(q)+qC_n-1(q), B_n(q) =A_n-1(q)+ B_n-1(q)+C_n-1(q)
$$
or
$$
A_n(q) = q B_n-1(q)+q A_n-1(q), B_n(q) =2A_n-1(q)+ B_n-1(q).
$$
From this, (with some algebra) we can then conclude that
$$
A_n(q) = (q+1)A_n-1(q) + q A_n-2(q) qquad (ast)
$$
and
$$
B_n(q)= (2+1/q)A_n-1+A_n-2
$$
so if we can solve the recursion in $(ast)$, we are done.
With some generating functions, you can see that
$$
sum_j=0^infty A_j(q)t^j = fracq t1-(q+1)t-qt^2
quad
sum_j=0^infty B_j(q)t^j = fracq t^2+t1-(q+1)t-qt^2.
$$
It follows that the series you seek is
$$
sum_j=0^infty t^jP_j(q) = frac2 q t + q t^2 + t1 - (q + 1) t - q t^2.
$$
So, the answer to your original question is therefore
$$
frac2 q t + q t^2 + t1 - (q + 1) t - q Bigvert_t^nq^k
$$
so that the number of $2times n$-strips with $k$ selected squares is the coefficient of $t^nq^k$ in the above rational function.
answered 2 hours ago
Per Alexandersson
6,71973877
Say for eg n=5,k=3 how do I use this rational function to solve the problem?
– Sparsh Kedia
1 hour ago
add a comment |Â
up vote
5
down vote
Let $P_n(q)$ be the polynomial such that the coefficient of $q^k$ is the number of $2times n$-strips with $k$ selected boxes.
Furthermore, let $A_n(q)$, $B_n(q)$ and $C_n(q)$ be the same sequences but with restriction that the strip ends with A) one selected square at the top,
B) one selected square at the bottom, and C) no selected squares.
We have due to symmetry that $A_n(q)=B_n(q)$.
Also, $A_1(q)=q$, $C_1(q)=0$.
We can then quite easily see that
$$
A_n(q) = q B_n-1(q)+qC_n-1(q), B_n(q) =A_n-1(q)+ B_n-1(q)+C_n-1(q)
$$
or
$$
A_n(q) = q B_n-1(q)+q A_n-1(q), B_n(q) =2A_n-1(q)+ B_n-1(q).
$$
From this, (with some algebra) we can then conclude that
$$
A_n(q) = (q+1)A_n-1(q) + q A_n-2(q) qquad (ast)
$$
and
$$
B_n(q)= (2+1/q)A_n-1+A_n-2
$$
so if we can solve the recursion in $(ast)$, we are done.
With some generating functions, you can see that
$$
sum_j=0^infty A_j(q)t^j = fracq t1-(q+1)t-qt^2
quad
sum_j=0^infty B_j(q)t^j = fracq t^2+t1-(q+1)t-qt^2.
$$
It follows that the series you seek is
$$
sum_j=0^infty t^jP_j(q) = frac2 q t + q t^2 + t1 - (q + 1) t - q t^2.
$$
So, the answer to your original question is therefore
$$
frac2 q t + q t^2 + t1 - (q + 1) t - q Bigvert_t^nq^k
$$
so that the number of $2times n$-strips with $k$ selected squares is the coefficient of $t^nq^k$ in the above rational function.
answered 2 hours ago
Per Alexandersson
6,71973877
Say for eg n=5,k=3 how do I use this rational function to solve the problem?
– Sparsh Kedia
1 hour ago
add a comment |Â
up vote
5
down vote
up vote
5
down vote
Let $P_n(q)$ be the polynomial such that the coefficient of $q^k$ is the number of $2times n$-strips with $k$ selected boxes.
Furthermore, let $A_n(q)$, $B_n(q)$ and $C_n(q)$ be the same sequences but with restriction that the strip ends with A) one selected square at the top,
B) one selected square at the bottom, and C) no selected squares.
We have due to symmetry that $A_n(q)=B_n(q)$.
Also, $A_1(q)=q$, $C_1(q)=0$.
We can then quite easily see that
$$
A_n(q) = q B_n-1(q)+qC_n-1(q), B_n(q) =A_n-1(q)+ B_n-1(q)+C_n-1(q)
$$
or
$$
A_n(q) = q B_n-1(q)+q A_n-1(q), B_n(q) =2A_n-1(q)+ B_n-1(q).
$$
From this, (with some algebra) we can then conclude that
$$
A_n(q) = (q+1)A_n-1(q) + q A_n-2(q) qquad (ast)
$$
and
$$
B_n(q)= (2+1/q)A_n-1+A_n-2
$$
so if we can solve the recursion in $(ast)$, we are done.
With some generating functions, you can see that
$$
sum_j=0^infty A_j(q)t^j = fracq t1-(q+1)t-qt^2
quad
sum_j=0^infty B_j(q)t^j = fracq t^2+t1-(q+1)t-qt^2.
$$
It follows that the series you seek is
$$
sum_j=0^infty t^jP_j(q) = frac2 q t + q t^2 + t1 - (q + 1) t - q t^2.
$$
So, the answer to your original question is therefore
$$
frac2 q t + q t^2 + t1 - (q + 1) t - q Bigvert_t^nq^k
$$
so that the number of $2times n$-strips with $k$ selected squares is the coefficient of $t^nq^k$ in the above rational function.
answered 2 hours ago
Per Alexandersson
6,71973877
Let $P_n(q)$ be the polynomial such that the coefficient of $q^k$ is the number of $2times n$-strips with $k$ selected boxes.
Furthermore, let $A_n(q)$, $B_n(q)$ and $C_n(q)$ be the same sequences but with restriction that the strip ends with A) one selected square at the top,
B) one selected square at the bottom, and C) no selected squares.
We have due to symmetry that $A_n(q)=B_n(q)$.
Also, $A_1(q)=q$, $C_1(q)=0$.
We can then quite easily see that
$$
A_n(q) = q B_n-1(q)+qC_n-1(q), B_n(q) =A_n-1(q)+ B_n-1(q)+C_n-1(q)
$$
or
$$
A_n(q) = q B_n-1(q)+q A_n-1(q), B_n(q) =2A_n-1(q)+ B_n-1(q).
$$
From this, (with some algebra) we can then conclude that
$$
A_n(q) = (q+1)A_n-1(q) + q A_n-2(q) qquad (ast)
$$
and
$$
B_n(q)= (2+1/q)A_n-1+A_n-2
$$
so if we can solve the recursion in $(ast)$, we are done.
With some generating functions, you can see that
$$
sum_j=0^infty A_j(q)t^j = fracq t1-(q+1)t-qt^2
quad
sum_j=0^infty B_j(q)t^j = fracq t^2+t1-(q+1)t-qt^2.
$$
It follows that the series you seek is
$$
sum_j=0^infty t^jP_j(q) = frac2 q t + q t^2 + t1 - (q + 1) t - q t^2.
$$
So, the answer to your original question is therefore
$$
frac2 q t + q t^2 + t1 - (q + 1) t - q Bigvert_t^nq^k
$$
so that the number of $2times n$-strips with $k$ selected squares is the coefficient of $t^nq^k$ in the above rational function.
answered 2 hours ago
Per Alexandersson
6,71973877
answered 2 hours ago
Per Alexandersson
6,71973877
answered 2 hours ago
Per Alexandersson
6,71973877
answered 2 hours ago
Per Alexandersson
6,71973877
6,71973877
Say for eg n=5,k=3 how do I use this rational function to solve the problem?
– Sparsh Kedia
1 hour ago
add a comment |Â
Say for eg n=5,k=3 how do I use this rational function to solve the problem?
– Sparsh Kedia
1 hour ago
Say for eg n=5,k=3 how do I use this rational function to solve the problem?
– Sparsh Kedia
1 hour ago
Say for eg n=5,k=3 how do I use this rational function to solve the problem?
– Sparsh Kedia
1 hour ago
add a comment |Â
up vote
2
down vote
$dots$ continued from above: to find the coefficient of $t^nq^k$, rewrite the generating function as
beginalignG(t,q):=fract+(2t+t^2)q1-t-(t+t^2)q
&=fract+(2t+t^2)q1-tcdotfrac11-left(fract+t^21-tright)q \
&=fract+(2t+t^2)q1-tsum_jgeq0left(fract+t^21-tright)^jq^j \
&=sum_kgeq0left(frac2t^k(1+t)^k-1(1-t)^k+1right)q^k.
endalign
Further calculation reveals that
$$frac2t^k(1+t)^k-1(1-t)^k+1
=sum_ngeq0left(2sum_r=0^n-kbinomn-rkbinomk-1rright)t^n.$$
In summary, the enumeration you seek becomes the coefficient of $t^nq^k$ given by
$$2sum_r=0^n-kbinomn-rkbinomk-1r.$$
This confirms your calculations: if $n=3, k=2$ then you get $8$; if $n=5, k=3$ then you get $38$.
answered 20 mins ago
T. Amdeberhan
16.3k228122
add a comment |Â
up vote
2
down vote
$dots$ continued from above: to find the coefficient of $t^nq^k$, rewrite the generating function as
beginalignG(t,q):=fract+(2t+t^2)q1-t-(t+t^2)q
&=fract+(2t+t^2)q1-tcdotfrac11-left(fract+t^21-tright)q \
&=fract+(2t+t^2)q1-tsum_jgeq0left(fract+t^21-tright)^jq^j \
&=sum_kgeq0left(frac2t^k(1+t)^k-1(1-t)^k+1right)q^k.
endalign
Further calculation reveals that
$$frac2t^k(1+t)^k-1(1-t)^k+1
=sum_ngeq0left(2sum_r=0^n-kbinomn-rkbinomk-1rright)t^n.$$
In summary, the enumeration you seek becomes the coefficient of $t^nq^k$ given by
$$2sum_r=0^n-kbinomn-rkbinomk-1r.$$
This confirms your calculations: if $n=3, k=2$ then you get $8$; if $n=5, k=3$ then you get $38$.
answered 20 mins ago
T. Amdeberhan
16.3k228122
add a comment |Â
up vote
2
down vote
up vote
2
down vote
$dots$ continued from above: to find the coefficient of $t^nq^k$, rewrite the generating function as
beginalignG(t,q):=fract+(2t+t^2)q1-t-(t+t^2)q
&=fract+(2t+t^2)q1-tcdotfrac11-left(fract+t^21-tright)q \
&=fract+(2t+t^2)q1-tsum_jgeq0left(fract+t^21-tright)^jq^j \
&=sum_kgeq0left(frac2t^k(1+t)^k-1(1-t)^k+1right)q^k.
endalign
Further calculation reveals that
$$frac2t^k(1+t)^k-1(1-t)^k+1
=sum_ngeq0left(2sum_r=0^n-kbinomn-rkbinomk-1rright)t^n.$$
In summary, the enumeration you seek becomes the coefficient of $t^nq^k$ given by
$$2sum_r=0^n-kbinomn-rkbinomk-1r.$$
This confirms your calculations: if $n=3, k=2$ then you get $8$; if $n=5, k=3$ then you get $38$.
answered 20 mins ago
T. Amdeberhan
16.3k228122
$dots$ continued from above: to find the coefficient of $t^nq^k$, rewrite the generating function as
beginalignG(t,q):=fract+(2t+t^2)q1-t-(t+t^2)q
&=fract+(2t+t^2)q1-tcdotfrac11-left(fract+t^21-tright)q \
&=fract+(2t+t^2)q1-tsum_jgeq0left(fract+t^21-tright)^jq^j \
&=sum_kgeq0left(frac2t^k(1+t)^k-1(1-t)^k+1right)q^k.
endalign
Further calculation reveals that
$$frac2t^k(1+t)^k-1(1-t)^k+1
=sum_ngeq0left(2sum_r=0^n-kbinomn-rkbinomk-1rright)t^n.$$
In summary, the enumeration you seek becomes the coefficient of $t^nq^k$ given by
$$2sum_r=0^n-kbinomn-rkbinomk-1r.$$
This confirms your calculations: if $n=3, k=2$ then you get $8$; if $n=5, k=3$ then you get $38$.
answered 20 mins ago
T. Amdeberhan
16.3k228122
answered 20 mins ago
T. Amdeberhan
16.3k228122
answered 20 mins ago
T. Amdeberhan
16.3k228122
answered 20 mins ago
T. Amdeberhan
16.3k228122
16.3k228122
add a comment |Â
add a comment |Â
Sparsh Kedia is a new contributor. Be nice, and check out our Code of Conduct.
Sparsh Kedia is a new contributor. Be nice, and check out our Code of Conduct.
Sparsh Kedia is a new contributor. Be nice, and check out our Code of Conduct.
Sparsh Kedia 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%2fmathoverflow.net%2fquestions%2f312679%2fcombinatorics-and-counting%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
@JoeSilverman: I was about to suggest that too, however, this is quite specialized, I'd say. But routine for those who have done it before...
– Per Alexandersson
2 hours ago
For small values of k you can use N(n,1)=2n and the recursion N(n,k)=N(n-1,k)+2*N(n-1,k-1). This is like Per's solution, using top-bottom symmetry, but hides some detail (and I left out a piece for you to find). This would be a good exercise for a beginning combinatorics class. If you can fully explain the recursion above, you have solved the exercise. Gerhard "Do I Get An Apple?" Paseman, 2018.10.12.
– Gerhard Paseman
1 hour ago
Oops. I miscounted. N(n,k)=N(n-1,k-1)+N(n-1,k). The full explanation of the previous recursion becomes a bonus problem. Gerhard "Always, ALWAYS Check Your Work" Paseman, 2018.10.12.
– Gerhard Paseman
1 hour ago