Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm having trouble showing that the generating series for all compositions which have an even number of parts.

I'm given that each part congruent to 1 mod 5 is equal to:$$\frac{1-2x^5+x^{10}}{1-x^2-2x^5+x^{10}}$$

If you could help me out that would be great!

share|cite|improve this question
The function you write is the generating function for compositions with an even number of parts and each part $\equiv1\bmod5$. – joriki Sep 30 '12 at 8:18
The question actually refers to having both an even amount of parts, and the congruency clause. – user43646 Oct 4 '12 at 19:38
up vote 2 down vote accepted

The number of compositions of $n$ with exactly $k$ parts is $\dbinom{n-1}{k-1}$, so the generating function for the number of compositions with an even number of parts is

$$g(x)=\sum_{n\ge 0}\left(\sum_{k\ge 0}\binom{n-1}{2k-1}\right)x^n\;.\tag{1}$$

$\displaystyle\sum_{k\ge 0}\binom{n-1}{2k-1}$ is simply the number of subsets of $\{1,\dots,n-1\}$ with an odd number of elements. For $n\le 1$ that’s clearly $0$, so we can rewrite $(1)$ as

$$g(x)=\sum_{n\ge 2}\left(\sum_{k\ge 0}\binom{n-1}{2k-1}\right)x^n=x^2\sum_{n\ge 2}\left(\sum_{k\ge 0}\binom{n-1}{2k-1}\right)x^{n-2}=x^2\sum_{n\ge 0}\left(\sum_{k\ge 0}\binom{n+1}{2k-1}\right)x^n\;.$$

Now $\displaystyle\sum_{k\ge 0}\binom{n+1}{2k-1}$ is the number of subsets of $\{1,\dots,n+1\}$ having an odd number of elements, and since $n+1\ge 1$, this has a simple closed form that you should know. Let’s say that that closed form is $f(n)$. Then you have

$$g(x)=x^2\sum_{n\ge 0}f(n)x^n\;,$$

where you should be able to recognize the generating function for $\displaystyle\sum_{n\ge 0}f(n)x^n$ fairly easily.

Added: If you follow the convention that $0$ has one composition, of size $0$, then $g(x)$ should have a constant term $1$ in addition to the terms given by $(1)$.

share|cite|improve this answer
I think you missed the composition of $0$ into $0$ parts. At least Wikipedia says this is conventionally counted as a composition; in any case $\binom{n-1}{k-1}$ doesn't give the number of compositions with exactly $k$ parts for $n=0$. – joriki Sep 30 '12 at 7:57
@joriki: I didn’t learn it that way, so it didn’t occur to me. But I learned my finite combinatorics late and unsystematically, so that doesn’t mean much. Fortunately, that would just add $1$ to my $g(x)$, so it’s not a major problem. I’ll add a note to that effect in a bit. – Brian M. Scott Sep 30 '12 at 8:05
How come the congruency condition wasn't mentioned anywhere in this answer? – Overload119 Oct 1 '12 at 23:19
@Overload119: You mean the bit about parts congruent to $1\bmod 5$? Because it’s irrelevant to this approach. – Brian M. Scott Oct 2 '12 at 1:14

Here's another method. First, you should convince yourself that the generating function for compositions with $k$ parts is given by

$$(x + x^2 + x^3 + \ldots)^k.$$ This is because choosing a composition $k_1 + k_2 + \ldots + k_m$ corresponds to choosing $x^{k_1}$ in the first factor, $x^{k_2}$ in the second, and so on. This is the same way you would multiply out the power series - choosing every possible $k$-tuple of terms, one from each factor, and multiplying them, and then summing the result.

Now simplify this expression and sum this over all even $k$ - it will become a nice rational generating function.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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