Find the generating function for the number of compositions of $n$ into $k$ parts, each of which is odd. Apply algebraic manipulation and the formal power series expansion of some basic functions to find a formula for the coefficient of $x^n$ in the generating function.

I have that the generating function for the number of compositions comes from $$(x+x^3+x^5+...)^k=\bigg(\frac{x}{(1-x^2)}\bigg)^k=x^k\sum_{n=0}^\infty\begin{pmatrix}n+k-1\\k-1\end{pmatrix}x^{2n}$$ and I think that the formula I want to get too eventually is $$\begin{cases} 0,&\text{if }n-k\text{ is odd}\\\\ \dbinom{\frac{n+k}2-1}{\frac{n-k}2},&\text{if }n-k\text{ is even}\;. \end{cases}$$ I'm not sure how to get from the first formula to the second, any help would be appreciated!

  • 1
    $\begingroup$ In the first formula, where did the sum over $n$ come from? You're summing an expression for $n$ to infinity that doesn't depend on $n$, so this series diverges. $\endgroup$ – joriki Dec 8 '19 at 21:11

You are happy that the generating fuction is \begin{eqnarray*} \sum_{N=0}^{\infty} \binom{N+k-1}{k-1} x^{2N+k} \text{ ?} \end{eqnarray*} This means there are $ \binom{N+k-1}{k-1}$ compositions (into $k$ odd parts) of $n$ where $n=2N+k$. So $n-k$ needs to be even (& the number of ways will be zero if it is odd) ... A little bit of algebra will lead to the conclusion you require.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.