[Math] Generating Series for the set of all compositions which have an even number of parts.

combinatorics

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!

Best Answer

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)$.