# how to solve generating function for odd number?

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

## 1 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.

• I do not think equation (2) is valid. Multiplication corresponds to convolution which is not the case in equation (2). – Trismegistos Mar 4 '15 at 16:39
• @Trismegistos: $(2)$ is correct: I am talking about the terms before they are collected. – Brian M. Scott Mar 4 '15 at 21:43
• @Trismegistos: In case the previous comment wasn’t clear: $(2)$ correctly describes each term of the product before terms of the same degree $n$ are collected into a single term whose coefficient is the total number of compositions of $n$ into $k$ odd parts. That’s a matter of basic algebra that has nothing to do with the combinatorial significance of any of this. And the power expression is definitely correct. – Brian M. Scott Mar 4 '15 at 22:22