a tough sum of binomial coefficients

Question

Find the sum: $$\sum_{i=0}^{2}\sum_{j=0}^{2}\binom{2}{i}\binom{2}{j}\binom{2}{k-i-j}\binom{4}{k-l+i+j},\space\space 0\leq k,l\leq 6$$

I know to find $\sum_{i=0}^{2}\binom{2}{i}\binom{2}{2-i}$, I need to find the coefficient of $x^2$ of $(1+x)^4$ (which is $\binom{4}{2}$). But I failed to use that trick here. Any help appreciated!

Answer 1

Here is a variant which could be seen as generalisation of OP's example. We use the coefficient of operator $[z^k]$ to denote the coefficient of $z^n$ in a series. This way we can write for instance \begin{align*} [z^k](1+z)^n=\binom{n}{k} \end{align*} and we also use Iverson brackets which are defined as \begin{align*} [[P(z)]]=\begin{cases} 1&\qquad P(z) \ \text{ true}\\ 0&\qquad P(z) \ \text{ false} \end{cases} \end{align*}

We obtain for $0\leq k,l\leq 6$: \begin{align*} \color{blue}{\sum_{i=0}^2}&\color{blue}{\sum_{j=0}^2\binom{2}{i}\binom{2}{j}\binom{2}{k-i-j}\binom{4}{k-l+i+j}}\\ &=\sum_{i=0}^2\binom{2}{i}\sum_{j=0}^2\binom{2}{j}[z^{k-i-j}](1+z)^2[u^{k-l+i+j}](1+u)^4\tag{1}\\ &=[z^k][u^{k-l}](1+z)^2(1+u)^4\sum_{i=0}^2\binom{2}{i}\left(\frac{z}{u}\right)^i\sum_{j=0}^2\binom{2}{j}\left(\frac{z}{u}\right)^j\tag{2}\\ &=[z^k][u^{k-l}](1+z)^2(1+u)^4\left(1+\frac{z}{u}\right)^4\tag{3}\\ &=[u^{k-l}]\left([z^k]+2[z^{k-1}]+[z^{k-2}]\right)\left(1+\frac{z}{u}\right)^4(1+u)^4\tag{4}\\ &=[u^{k-l}]\left(\binom{4}{k}u^{-k}+2\binom{4}{k-1}[[k\geq 1]]u^{1-k}\right.\\ &\qquad\qquad\quad\left.+\binom{4}{k-2}[[k\geq 2]]u^{2-k}\right)(1+u)^4\tag{5}\\ &=\left(\binom{4}{k}[u^{2k-l}]+2\binom{4}{k-1}[[k\geq 1]][u^{2k-l-1}]\right.\\ &\qquad\qquad\quad\left.+\binom{4}{k-2}[[k\geq 2]][u^{2k-l-2}]\right)(1+u)^4\\ &\,\,\color{blue}{=\binom{4}{k}\binom{4}{2k-l}[[2k\geq l]]+2\binom{4}{k-1}\binom{4}{2k-l-1}[[k\geq 1]][[2k\geq l+1]]}\\ &\qquad\qquad\quad\color{blue}{+\binom{4}{k-2}\binom{4}{2k-l-2}[[k\geq 2]][[2k\geq l+2]]} \end{align*}

Comment:

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

• In (2) we use the linearity of the coefficient of operator and apply the rule $[z^{p-q}]A(x)=[z^p]z^qA(z)$.

• In (3) we apply the binomial theorem twice.

• In (4) we expand $(1+z)^2$ and select the coefficient of $[z^k]$. \begin{align*} [z^k]&(1+z)^2\left(1+\frac{z}{u}\right)^4\\ &=[z^k](1+2z+z^2)\left(1+\frac{z}{u}\right)^4\\ &=\left([z^k]+2[z^{k-1}]+[z^{k-2}]\right)\left(1+\frac{z}{u}\right)^4\\ &=\left([z^k]+2[z^{k-1}]+[z^{k-2}]\right)\sum_{j=0}^4\binom{4}{j}\left(\frac{z}{u}\right)^j\\ &=[z^k]\sum_{j=0}^4\binom{4}{j}\left(\frac{z}{u}\right)^j +2[z^{k-1}]\sum_{j=0}^4\binom{4}{j}\left(\frac{z}{u}\right)^j +[z^{k-2}]\sum_{j=0}^4\binom{4}{j}\left(\frac{z}{u}\right)^j\\ \end{align*}

• In (5) we select the coefficients of $[z^{k-a}]$ in $\left(1+\frac{z}{u}\right)^4$ with $0\leq a\leq 2$. We use Iverson brackets to set terms to zero if the lower part of binomial coefficients is less than zero. We do a similar job with $[u^{k-l}]$ in the following lines.

Answer 2

Computing the generating function: $$ \begin{align} &\sum_k\sum_l\sum_i\sum_j\binom{2}{i}\binom{2}{j}\binom{2}{k-i-j}\binom{4}{k-l+i+j}x^ly^k\\ &=\sum_k\color{#C00}{\sum_l}\sum_i\sum_j\binom{2}{i}\binom{2}{j}\binom{2}{k-i-j}\color{#C00}{\binom{4}{k-l+i+j}x^{l+4-k-i-j}}x^{k+i+j-4}y^k\\ &=\color{#C00}{(1+x)^4}\sum_k\sum_i\sum_j\binom{2}{i}\binom{2}{j}\binom{2}{k-i-j}x^{k+i+j-4}y^k\\ &=(1+x)^4\color{#090}{\sum_k}\sum_i\sum_j\binom{2}{i}\binom{2}{j}\color{#090}{\binom{2}{k-i-j}x^{k-i-j}y^{k-i-j}}x^{2i+2j-4}y^{i+j}\\ &=(1+x)^4\color{#090}{(1+xy)^2}\color{#00F}{\sum_i\sum_j\binom{2}{i}\binom{2}{j}x^{2i+2j-4}y^{i+j}}\\ &=\frac{(1+x)^4(1+xy)^2\color{#00F}{(1+x^2y)^4}}{\color{#00F}{x^4}}\\ &=\color{#CCC}{\frac1{x^4}+\frac{4+2y}{x^3}+\frac{6+12y+y^2}{x^2}+\frac{4+28y+12y^2}x}\\ &+\left(1+32y+44y^2+4y^3\right)+x\left(18y+76y^2+28y^3\right)+x^2\left(4y+69y^2+76y^3+6y^4\right)\\ &+x^3\left(32y^2+104y^3+32y^4\right)+x^4\left(6y^2+76y^3+69y^4+4y^5\right)\\ &+x^5\left(28y^3+76y^4+18y^5\right)+x^6\left(4y^3+44y^4+32y^5+y^6\right)\\ &\color{#CCC}{+x^7\left(12y^4+28y^5+4y^6\right)+x^8\left(y^4+12y^5+6y^6\right)+x^9\left(2y^5+4y^6\right)+x^{10}y^6} \end{align} $$ where the terms not in the requested range have been grayed out.

Answer 3

I would add some comments following the given solution. First at all we need a variable change $l'=l+4$ to bring the GF into the real world.

Suppose we have to fill the structure above with $l'$ identical white balls and $k$ identical black balls, white in the upper row, black in the lower row. Then there is a rule that says every structured bin either is empty or is full.

Thus we get $\binom2i$ for filling the first section, $\binom2j$ for the second, $\binom2{k-i-j}$ for the green section. For the fourth section, we have $l'-2i -2j - (k-i-j) = l'-i-j-k = l + 4 - i-j-k$ hence the binomial $\binom4 {i+j+k-l} $

here are my comments :

• such structures that could be named ''partial surjective function'' missed the twelve-fold Rota way train or other expansions and they are less studied.

• the blue summamnds could be grouped in only one section with only one parameter, but the section is split.

• the l' parameter is shifted from reality exactly with 4 as to be well hidden in the binomial expression.

• then we have a range for l', to place 4..10 balls in 14 slots.

Gives these I would say, someone have done his mile to produce this tough structure and problem.