Compositions of $n$ with $r$ odd parts and $s$ even parts 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!
 A: 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*}$$


At this point you could try to finish on your own.


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