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


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


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.

  • $\begingroup$ I do not think equation (2) is valid. Multiplication corresponds to convolution which is not the case in equation (2). $\endgroup$ – Trismegistos Mar 4 '15 at 16:39
  • $\begingroup$ @Trismegistos: $(2)$ is correct: I am talking about the terms before they are collected. $\endgroup$ – Brian M. Scott Mar 4 '15 at 21:43
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Mar 4 '15 at 22:22

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.