Combinatorics and Counting

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











up vote
4
down vote

favorite
1












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














up vote
4
down vote

favorite
1












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












up vote
4
down vote

favorite
1









up vote
4
down vote

favorite
1






1





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 1 hour ago









T. Amdeberhan

16.3k228122




16.3k228122






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




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
















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










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.






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
    1 hour ago

















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






share|cite|improve this answer




















    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%2fcombinatorics-and-counting%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
    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.






    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
      1 hour ago














    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.






    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
      1 hour ago












    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.






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
















    • 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










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






    share|cite|improve this answer
























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






      share|cite|improve this answer






















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






        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 20 mins ago









        T. Amdeberhan

        16.3k228122




        16.3k228122




















            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%2fcombinatorics-and-counting%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