I'm self studying combinatorics with Springer's Combinatorics and Graph Theory and am having trouble understanding the summation manipulations used to derive a formula for the generating function that represents "how many ways to select $m$ items from $n$ different items, where each item can be selected at most twice". He denotes that quantity by $t_{n,m}$, and derives it by generating functions and the binomial theorem.

$$\begin{align} G_n(x) & = (1+(x+x^2))^n \\ & = \sum_k\binom{n}{k}(x+x^2)^k \\ & = \sum_k\binom{n}{k}x^k \sum_j\binom{k}{j}x^j \\ & = \sum_k\sum_j\binom{n}{k}\binom{k}{j}x^{j+k} \\ & = \sum_m \left( \sum_j\binom{n}{m-j}\binom{m-j}{j}\right)\,x^m,\\ \end{align} $$ where we obtained the last line by substituting $m$ for $j+k$. Therefore,

$$\begin{align} t_{m,n} = \sum_{j=0}^{\lfloor{m/2}\rfloor} \binom{n}{m-j}\binom{m-j}{j} \end{align}$$

I can understand everything up to the last two lines. How can you change the outer sum index to be a function of the inner sum, when the inner sum itself is a function of k (assuming $k$ becomes $m-j$)? I tried to rework everything by writing the indexes explicitly, but couldn't work out how this $m$ was introduced.

Also on the last line, how did he introduce the $\lfloor{m/2}\rfloor$ to calculate a specific coefficient? (I assume this step will become clear if I understand the previous one)


The next to last is just applying Cauchy's product (the expression for the coefficient of the product of $\sum_{i \ge 0} a_i z^i$ and $\sum_{i \ge 0} b_i z^i$) "in reverse". To explain the $\lfloor m / 2 \rfloor$ limit in the last expression, just take the sum as an infinite sum over $j \ge 0$ (as written in the derivation), and check where the sum stops due to a binomial coefficient becoming 0 when $m$ is odd and even.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.