The problem I have been trying to figure out is as follows:
Let $n-r=2k$. Show that the number $f(n,r,s)$ of compositions of $n$ with $r$ odd parts and $s$ even parts is given by $\binom{r+s}{r}\binom{r+k-1}{r+s-1}$. Give a generating function proof.
The following hint is given:
It is clear that $\displaystyle \sum_{n,r,s} f(n,r,s)x^ny^rz^s=\sum_{j\geq 0} \left( \frac{yx}{1-x^2}+\frac{zx^2}{1-x^2} \right)^j$.
I can't figure out why the hint is obvious! I have been trying to figure out how to work with the following recursion I came up with:
$f(n,r,s)=f(n-1,r-1,s)+f(n-1,r,s)$,
which comes from partitioning the set of compositions of $n$ by considering the cases when $1$ is the smallest part and when some number greater than or equal to $2$ is the smallest part. However, my calculations come out insane! Anyone have a better suggestion for how to approach this problem or could you at least give some insight about the hint?
Thank you in advance!
I’ve not had time to think much about the problem itself, but I can explain the hint. Let
$$g_{n,r,s}(x)=\frac{yx}{1-x^2}+\frac{zx^2}{1-x^2}=\sum_{k\ge 0}yx^{2k+1}+\sum_{k\ge 0}zx^{2k+2}\;.$$
The $x^n$ term in $g_{n,r,s}(x)$ is $yx^n$ if $n$ is odd and $zx^n$ if $n$ is even. In other words, this generating functions counts one odd part when $n$ is odd and one even part when $n$ is even: the coefficient of $x^ny^rz^s$ is the number of compositions of $n$ into one part such that $r$ parts are odd and $s$ are even.
Suppose that we square it; the resulting $x^n$ term is
$$\sum_{k=0}^n\Big([2\mid k]z+[2\nmid k]y\Big)\Big([2\mid n-k]z+[2\nmid n-k]y\Big)x^n\;.$$
If $n$ is even, this is
$$\Large\sum_{{0\le k\le n}\atop{k\text{ even}}}z^2x^n+\sum_{{0\le k\le n}\atop{k\text{ odd}}}y^2x^n\;;$$
if $n$ is odd, it’s
$$\Large\sum_{{0\le k\le n}\atop{k\text{ even}}}zyx^n+\sum_{{0\le k\le n}\atop{k\text{ odd}}}yzx^n=(n+1)yzx^n\;.$$
In either case the coefficient of each $x^ny^rz^s$ is the number of compositions of $n$ into two parts so that $r$ parts are odd and $s$ are even. If $n=2m$, there are $m+1$ compositions of $n$ into two even parts and $m$ compositions of $n$ into two odd parts; if $n$ is odd, there are $n+1$ compositions of $n$ into two parts, and in every case one part is odd and the other even.
In general $\big(g_{n,r,s}(x)\big)^j$ gives you the number of compositions of $n$ into $j$ parts, the exponents on $y$ and $z$ giving the the numbers of odd and even parts, respectively. This is why
$$\sum_{n,r,s}f(n,r,s)x^ny^rz^s=\sum_{j\ge 0}\left(\frac{yx}{1-x^2}+\frac{zx^2}{1-x^2}\right)^j\;.$$
Added: I’ve thought through the problem now and solved it. Unfortunately, I don’t really see how to reduce it to hints. I will mark a point part of the way through where you might want to stop reading and try to complete the argument yourself.
Recalling that $j$ is the number of parts, we can let $s=j-r$ and write
$$\begin{align*} \left(\frac{yx}{1-x^2}+\frac{zx^2}{1-x^2}\right)^j&=\frac1{(1-x^2)^j}\sum_{r=0}^j\binom{j}ry^rz^{j-r}x^{2j-r}\\ &=\frac1{(1-x^2)^j}\sum_{r=0}^j\binom{j}ry^rz^sx^{r+2s}\\ &=\frac1{(1-x^2)^j}\sum_{r+s=j}\binom{r+s}ry^rz^sx^{r+2s}\;, \end{align*}$$
where it’s understood that $r$ and $s$ are non-negative. A standard generating function is
$$\frac1{(1-x^2)^j}=\sum_{m\ge 0}\binom{j+m-1}mx^{2m}=\sum_{m\ge 0}\binom{j+m-1}{j-1}x^{2m}\;.$$
so
$$\begin{align*} \sum_{j\ge 0}\left(\frac{yx}{1-x^2}+\frac{zx^2}{1-x^2}\right)^j&=\sum_{j\ge 0}\frac1{(1-x^2)^j}\sum_{r+s=j}\binom{r+s}ry^rz^sx^{r+2s}\\ &=\sum_{j\ge 0}\sum_{m\ge 0}\sum_{r+s=j}\binom{j+m-1}m\binom{r+s}ry^rz^sx^{r+2s+2m}\;.\tag{1} \end{align*}$$
Let $n=r+2s+2m$; then $2k=n-r=2(s+m)$, $k=s+m$,
$$j+m-1=r+s+(k-s)-1=r+k-1\;,$$
and
$$\binom{j+m-1}m=\binom{j+m-1}{j-1}=\binom{r+k-1}{r+s-1}\;.$$
It’s not hard to check that with this renaming of quantities we can rewrite $(1)$ as
$$\sum_{r,s,n\ge 0}\binom{r+k-1}{r+s-1}\binom{r+s}ry^rz^sx^n\;;$$
you just have to verify $\sum_{j\ge 0}\sum_{m\ge 0}\sum_{r+s=j}\ldots$ and $\sum_{r,s,n\ge 0}\ldots$ run over the same combinations of exponents on $x,y$, and $z$.