I need Vandermonde's formula in multi-set form. I modified the original formula but I get a mess with too many letters everywhere, is there a nice representation?
Here's the original:
$$ \sum_{j=0}^{k}{{m \choose j}{n \choose k-j}={m+n \choose k}} .$$
I get, $$ \def\multiset#1#2{\left(\!\left({#1\atopwithdelims..#2}\right)\!\right)} \sum_{j=0}^{k} \multiset{m+k+1}{k}\multiset{n+k-j+1}{k-j}=\multiset{m+n+k+1}{k} .$$ Is there a less cumbersome way of writing this?
Vandermonde's identity holds true with multisets as well.
A direct way to prove is by using convolution of generating functions.
In case of binomials, we need to get $[x^k]$ from $\left(1+x\right)^m\left(1+x\right)^n$.
For your question, the gf of $$a_k = \multiset{m}{k} = \binom{m+k-1}{k}$$ is \begin{align*} G(x) &= \sum_{k\ge 0} a_k x^k = \frac{1}{(1-x)^m} \end{align*} and the gf of $$b_k = \multiset{n}{k} = \binom{n+k-1}{k}$$ is \begin{align*} H(x) &= \sum_{k\ge 0} b_k x^k = \frac{1}{(1-x)^n} \end{align*} and we need to get $[x^k]$ from $G(x)\cdot H(x)$, hence, \begin{align*} G(x)\cdot H(x) &= \sum_{k\ge 0} \left(\sum_{j=0}^k a_j b_{k-j} \right)x^k \\ &= \frac{1}{(1-x)^{m+n}} \\ &= \sum_{k\ge 0} \binom{m+n+k-1}{k} x^k \end{align*} or in other words \begin{align*} \sum_{j=0}^k \multiset{m}{j}\multiset{n}{k-j} &= \multiset{m+n}{k} \end{align*}