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 function you write is the generating function for compositions with an even number of parts *and* each part $\equiv1\bmod5$.2012-09-30
  • 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
    I think you missed the composition of $0$ into $0$ parts. At least [Wikipedia](http://en.wikipedia.org/wiki/Composition_%28number_theory%29#Number_of_compositions) 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$.2012-09-30
  • 0
    @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.2012-09-30
  • 0
    How come the congruency condition wasn't mentioned anywhere in this answer?2012-10-01
  • 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.