I have met the following question: consider the set of compositions with any number of parts where each odd part is equal to 1. E.g $(1,2,1,3,1,4,1,\ldots)$. Then I am asked to find the generating function for this set. The hint is that for $k\ge0$, first find the generating function for the set of such compositions of at most $k$ parts.
I think I am pretty confused about generating functions. My understanding is that the generating functions depends on which value we can choose and how many parts of the composition. So for example: choose from $\{1,2\}$ and of part $3$, the GF is simple $(x^1+x^2)^3$…But in case, what is the set of values? Is it $\{1,\ldots,1,2,3,\ldots\}$? So does it mean that the generating function is (assume $k$ is even for now) $$x^{k/2}+\left(\sum_{i=2}^\infty x^i\right)^k?$$
Thanks!!!
Best Answer
Call compositions of the desired type good. Let $a_n$ be the number of good compositions of $n$. Direct calculation shows that $a_1=a_2=1$, $a_3=2$, $a_4=3$, $a_5=5$, and $a_6=8$. These are the Fibonacci numbers and suggest that perhaps $a_n=a_{n-1}+a_{n-2}$ for $n\ge 3$. A bit of thought verifies this. There is an obvious bijection between good compositions of $n$ that end in $1$ and compositions of $n-1$, and there is also a bijection between good compositions of $n$ that end in a number greater than $1$ and compositions of $n-2$: just subtract $2$ from the last part. (It may take a little thought to verify that this really is a bijection.) $0$ has no compositions, so $a_0=0=F_0$, and we already saw that $a_1=1=F_1$, so $a_n=F_n$ for each $n\ge 0$. Thus, the desired generating function is the same as for the Fibonacci numbers and is therefore
$$g(x)=\frac{x}{1-x-x^2}\,.$$
This can of course be found by standard methods from the recurrence and initial conditions if you don’t already know it.
Added: The good compositions of $n$ into $2k$ parts are just compositions of $n-k$ into $k$ parts, with a $1$ inserted before each of the $k$ parts, so there are $\binom{n-k-1}{k-1}$ of them. Similarly, the good compositions of $n$ into $2k+1$ parts are just compositions of $n-k-1$ into $k$ parts, so there are $\binom{n-k-2}{k-1}$ of them. Thus, if $g_k$ is the generating function for the number of good compositions into $k$ parts, we have
$$g_{2k}(x)=\sum_{n\ge 0}\binom{n-k-1}{k-1}x^n$$
and
$$g_{2k+1}(x)=\sum_{n\ge 0}\binom{n-k-2}{k-1}x^n\,.$$
From these we can extract the actual functions without too much trouble. For instance,
$$\begin{align*} \sum_{n\ge 0}\binom{n-k-1}{k-1}x^n&=\sum_{n\ge 0}\binom{n-k-1}{n-2k}x^n\\ &=\sum_{n\ge 2k}\binom{n-k-1}{n-2k}x^n\\ &=\sum_{n\ge 0}\binom{n+k-1}nx^{n+2k}\\ &=x^{2k}\sum_{n\ge 0}\binom{n+k-1}nx^n\\ &=\frac{x^{2k}}{(1-x)^k}\,. \end{align*}$$
The calculation for $g_{2k+1}(x)$ is very similar.