Counting configurations on a 2xn board under restrictions

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
6
down vote

favorite
2












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?











share|cite|improve this question









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














up vote
6
down vote

favorite
2












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?











share|cite|improve this question









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












up vote
6
down vote

favorite
2









up vote
6
down vote

favorite
2






2





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?











share|cite|improve this question









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






share|cite|improve this question









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.











share|cite|improve this question









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.









share|cite|improve this question




share|cite|improve this question








edited 15 mins ago









Per Alexandersson

6,73973877




6,73973877






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




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
















  • @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










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






share|cite|improve this answer




















  • 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

















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.






share|cite|improve this answer




















  • Say for eg n=5,k=3 how do I use this rational function to solve the problem?
    – Sparsh Kedia
    5 hours ago










Your Answer




StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "504"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);






Sparsh Kedia is a new contributor. Be nice, and check out our Code of Conduct.









 

draft saved


draft discarded


















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






























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






share|cite|improve this answer




















  • 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














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






share|cite|improve this answer




















  • 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












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






share|cite|improve this answer












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







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










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
















  • 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










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.






share|cite|improve this answer




















  • Say for eg n=5,k=3 how do I use this rational function to solve the problem?
    – Sparsh Kedia
    5 hours ago














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.






share|cite|improve this answer




















  • Say for eg n=5,k=3 how do I use this rational function to solve the problem?
    – Sparsh Kedia
    5 hours ago












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.






share|cite|improve this answer












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.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










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
















  • 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










Sparsh Kedia is a new contributor. Be nice, and check out our Code of Conduct.









 

draft saved


draft discarded


















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.













 


draft saved


draft discarded














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













































































Comments

Popular posts from this blog

What does second last employer means? [closed]

Installing NextGIS Connect into QGIS 3?

One-line joke