Mixing
Counting configurations on a 2xn board under restrictions
Clash Royale CLAN TAG#URR8PPP
up vote
6
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 15 mins ago
Per Alexandersson
6,73973877
asked 7 hours ago
Sparsh Kedia
333
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
6
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 15 mins ago
Per Alexandersson
6,73973877
asked 7 hours ago
Sparsh Kedia
333
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
6 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
5 hours 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
5 hours ago
add a comment |Â
up vote
6
down vote
favorite
up vote
6
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 15 mins ago
Per Alexandersson
6,73973877
asked 7 hours ago
Sparsh Kedia
333
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 15 mins ago
Per Alexandersson
6,73973877
asked 7 hours ago
Sparsh Kedia
333
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 15 mins ago
Per Alexandersson
6,73973877
asked 7 hours ago
Sparsh Kedia
333
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 15 mins ago
Per Alexandersson
6,73973877
edited 15 mins ago
Per Alexandersson
6,73973877
edited 15 mins ago
Per Alexandersson
6,73973877
6,73973877
asked 7 hours ago
Sparsh Kedia
333
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 7 hours ago
Sparsh Kedia
333
asked 7 hours ago
Sparsh Kedia
333
333
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
6 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
5 hours 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
5 hours 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
6 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
5 hours 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
5 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
6 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
6 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
5 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
5 hours 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
5 hours 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
5 hours ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
7
down vote
accepted
$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 4 hours ago
T. Amdeberhan
16.4k228122
That sum may have a combinatorial proof.
– Michael Lugo
2 hours ago
That is what I anticipate. Go for it. :-)
– T. Amdeberhan
2 hours ago
So that summation can be reduced to an identity?
– Sparsh Kedia
32 mins ago
No, it can not be reduced.
– T. Amdeberhan
2 mins ago
add a comment |Â
up vote
7
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 6 hours ago
Per Alexandersson
6,73973877
Say for eg n=5,k=3 how do I use this rational function to solve the problem?
– Sparsh Kedia
5 hours ago
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
7
down vote
accepted
$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 4 hours ago
T. Amdeberhan
16.4k228122
That sum may have a combinatorial proof.
– Michael Lugo
2 hours ago
That is what I anticipate. Go for it. :-)
– T. Amdeberhan
2 hours ago
So that summation can be reduced to an identity?
– Sparsh Kedia
32 mins ago
No, it can not be reduced.
– T. Amdeberhan
2 mins ago
add a comment |Â
up vote
7
down vote
accepted
$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 4 hours ago
T. Amdeberhan
16.4k228122
That sum may have a combinatorial proof.
– Michael Lugo
2 hours ago
That is what I anticipate. Go for it. :-)
– T. Amdeberhan
2 hours ago
So that summation can be reduced to an identity?
– Sparsh Kedia
32 mins ago
No, it can not be reduced.
– T. Amdeberhan
2 mins ago
add a comment |Â
up vote
7
down vote
accepted
up vote
7
down vote
accepted
$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 4 hours ago
T. Amdeberhan
16.4k228122
$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 4 hours ago
T. Amdeberhan
16.4k228122
answered 4 hours ago
T. Amdeberhan
16.4k228122
answered 4 hours ago
T. Amdeberhan
16.4k228122
answered 4 hours ago
T. Amdeberhan
16.4k228122
16.4k228122
That sum may have a combinatorial proof.
– Michael Lugo
2 hours ago
That is what I anticipate. Go for it. :-)
– T. Amdeberhan
2 hours ago
So that summation can be reduced to an identity?
– Sparsh Kedia
32 mins ago
No, it can not be reduced.
– T. Amdeberhan
2 mins ago
add a comment |Â
That sum may have a combinatorial proof.
– Michael Lugo
2 hours ago
That is what I anticipate. Go for it. :-)
– T. Amdeberhan
2 hours ago
So that summation can be reduced to an identity?
– Sparsh Kedia
32 mins ago
No, it can not be reduced.
– T. Amdeberhan
2 mins ago
That sum may have a combinatorial proof.
– Michael Lugo
2 hours ago
That sum may have a combinatorial proof.
– Michael Lugo
2 hours ago
That is what I anticipate. Go for it. :-)
– T. Amdeberhan
2 hours ago
That is what I anticipate. Go for it. :-)
– T. Amdeberhan
2 hours ago
So that summation can be reduced to an identity?
– Sparsh Kedia
32 mins ago
So that summation can be reduced to an identity?
– Sparsh Kedia
32 mins ago
No, it can not be reduced.
– T. Amdeberhan
2 mins ago
No, it can not be reduced.
– T. Amdeberhan
2 mins ago
add a comment |Â
up vote
7
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 6 hours ago
Per Alexandersson
6,73973877
Say for eg n=5,k=3 how do I use this rational function to solve the problem?
– Sparsh Kedia
5 hours ago
add a comment |Â
up vote
7
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 6 hours ago
Per Alexandersson
6,73973877
Say for eg n=5,k=3 how do I use this rational function to solve the problem?
– Sparsh Kedia
5 hours ago
add a comment |Â
up vote
7
down vote
up vote
7
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 6 hours ago
Per Alexandersson
6,73973877
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 6 hours ago
Per Alexandersson
6,73973877
answered 6 hours ago
Per Alexandersson
6,73973877
answered 6 hours ago
Per Alexandersson
6,73973877
answered 6 hours ago
Per Alexandersson
6,73973877
6,73973877
Say for eg n=5,k=3 how do I use this rational function to solve the problem?
– Sparsh Kedia
5 hours ago
add a comment |Â
Say for eg n=5,k=3 how do I use this rational function to solve the problem?
– Sparsh Kedia
5 hours ago
Say for eg n=5,k=3 how do I use this rational function to solve the problem?
– Sparsh Kedia
5 hours ago
Say for eg n=5,k=3 how do I use this rational function to solve the problem?
– Sparsh Kedia
5 hours ago
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%2fcounting-configurations-on-a-2xn-board-under-restrictions%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
6 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
5 hours 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
5 hours ago