For the identity of binomials below, we have a combinatorial view.
$$\sum_{k=0}^n \binom{n}{k} k(n-k)=\binom{n}{2}2^{n-1}$$
For the left-hand side: Choose $k$ balls from n balls and paint them in red, then paint rest $(n-k)$ balls in blue. Finally, choose one red ball and one blue ball.
For the right-hand side: Choose $2$ balls from $n$ balls and paint one ball in red and the other in blue. And paint rest $n-2$ balls freely in red and blue.
Then, can you find the combinatorial view of the identity below? (I found this formula counting the number of a path in the grid. link).
$$\sum_{i=0}^{\min(x,y)}\binom{x}{i}\binom{y}{i}2^{x+y-(i+1)}=\sum_{i=0}^{\min(x,y)}2^{x+y-(i+1)} (-1)^i \frac{(x+y-i)!}{(x-i)!(y-i)!i!}$$
This seems to have something to do with the inclusion-exclusion principle. However, I cannot come up with a combinatorial view.
Best Answer
Left hand side count the way to put $i$ blocks of $\rightarrow\ldots\rightarrow\uparrow\ldots\uparrow$.
Right hand side count the way to put $i$ blocks of $\rightarrow\ldots\rightarrow\uparrow\ldots\uparrow$ incoherently in the block. Then arranging them using inclusion-exclusion principle.