Finding generating series

Question

I am not able to figure out this problem based on Combinatorics -

How many integer compositions of n, where $n ≥ 0$, are there where every part is even, and there are at least three parts?

How should we find the generating series?

Answer 1

Hints:

• The number of all compositions of $n$ into a positive number of positive parts is $2^{n-1}$ except when $n=0$ when it is $0$ (stars and bars can show this). So find the generating function for this

• The number of compositions of $n$ into $1$ positive part is $1$ except when $n=0$ when it is $0$ (stars but no bar). So find the generating function for this

• The number of compositions of $n$ into $2$ positive parts is $n-1$ except when $n=0$ when it is $0$ (stars and one bar). So find the generating function for this

• So the generating function for the number of compositions of $n$ into $3$ or more positive parts is the first generating function above minus the second and the third

• To make sure "every part is even" involves replacing $x$ by $x^2$, so you can find the generating function for the number of compositions of $n$ into $3$ or more positive even parts

As a check, we have $8=2+2+2+2=4+2+2=2+4+2=2+2+4$, i.e. $4$ ways of making $8$, so see if your answer reproduces this for the coefficient of $x^8$ in its expansion