Stuck at finding coefficients of generating functions.

combinatoricsgenerating-functions

Problem statement:

Show that the number of r-combinations of specification $2^m1^{n-2m}$ is $$\sum_k {{m}\choose {k}}{{n-m-k}\choose{r-2k}}$$

I have found the generating function which is $(1+t+t^2)^m(1+t)^{n-2m}$, but I cannot proceed further to find the general coefficient.

I know the combinatorial proof for this question, I am specifically wanting to practice using generating functions. Any hint will also suffice.

I have tried using the geometric series formula and then Taylor expansion but could not proceed further.

Edit: The particular specification given here means there are objects of m kind with 2 of each kind and (n-2m) remaining objects that are distinct.

Best Answer

Here we use the coefficient of operator $[x^r]$ which denotes the coefficient of $x^r$ of a series. This way we can write for instance \begin{align*} \binom{n}{r}=[x^r](1+x)^n \end{align*}

We obtain for non-negative integers $n\geq 2m$ and $r\geq 0$: \begin{align*} \color{blue}{\sum_{k=0}^m}&\color{blue}{\binom{m}{k}\binom{n-m-k}{r-2k}}\\ &=\sum_{k=0}^m\binom{m}{k}[x^{r-2k}](1+x)^{n-m-k}\tag{1}\\ &=[x^r](1+x)^{n-m}\sum_{k=0}^m\binom{m}{k}\left(\frac{x^2}{1+x}\right)^k\tag{2}\\ &=[x^r](1+x)^{n-m}\left(1+\frac{x^2}{1+x}\right)^m\tag{3}\\ &\,\,\color{blue}{=[x^r](1+x)^{n-2m}\left(1+x+x^2\right)^m} \end{align*} and we conclude \begin{align*} \sum_{r=0}^\infty\left(\sum_{k=0}^m\binom{m}{k}\binom{n-m-k}{r-2k}\right)x^r =(1+x)^{n-2m}\left(1+x+x^2\right)^m \end{align*}

Comment:

  • In (1) we apply the coefficient of operator.

  • In (2) we factor out terms independent of $k$ by using the linearity of the coefficient of operator and applying the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$.

  • In (3) we apply the binomial theorem.

Related Question