im working on this question and i don't know where to start
the question is:
a) Find a closed form for the generating function $c(x)$ for counting compositions with $k$ parts, where each part is an odd number (Hint: Composition is different from partitions)
b) Compute the coefficient of $x^n$ in the answer in part (a) to show that the number of compositions of $n$ into $k$ parts, where each part is an odd number, equals the following piecewise function:
$$\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 usually state what I tried, but I'm completely lost here.. Any help would be very much appreciated.. thankyou
Best Answer
Each part has to be odd, so the series whose exponents describe the possibilities for one part is
$$x+x^3+x^5+\ldots=x\sum_{n\ge 0}x^{2n}\;.\tag{1}$$
You want $k$ parts, and so you want
$$\left(x\sum_{n\ge 0}x^{2n}\right)^k\;:$$
each term of that $k$-th power is of the form $$x^{2n_1+1}x^{2n_2+1}\ldots x^{2n_k+1}\;,\tag{2}$$ where the $i$-th factor corresponds to the $i$-th part of the composition. In other words, the term $(2)$ in the power corresponds to the composition
$$(2n_1+1)+(2n_2+1)+\ldots+(2n_k+1)\tag{3}$$
of the number $n$ that is the actual sum in $(3)$.
At this point you should be able to find the closed form generating function for $(1)$ and then take its $k$-th power. When it comes to extracting the coefficient of $x^n$, you’ll probably find it useful to know the series expansion of $\frac1{(1-x)^k}$; if you don’t already know it, it can be obtained by repeated differentiation of one of the most familiar ones.