1
$\begingroup$

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!

  • 0
    The question actually refers to having both an even amount of parts, and the congruency clause.2012-10-04

2 Answers 2

2

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

  • 0
    @Overload119: You mean the bit about parts congruent to $1\bmod 5$? Because it’s irrelevant to this approach.2012-10-02
2

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.