Summation with Multiple Indices

Question

How would the following summation work?

$\sum_{r,s,t \ge 0_{r+s+t=n}} \binom{m_1}{r} \binom{m_2}{s} \binom{m_3}{t}$

How would you choose the value for the next integer in the series?

For example, for n=2. Either r,s, or t = 2. Or r = 1 and s = 1 (or any combination thereof)

I think the inclusion-exclusion principle would be used but I'm don't know how it would be applied.

Sorry if this is a duplicate question. I wasn't sure how to word it.

Answer 1

The more general formula for a sum is the following: $$S=\sum_{i\in A} f(i) $$ where $A$ is a set and $f:A\to \Bbb N$ is a function. For example in your case : $$A=\left\{(r,s,t)\big/r,s,t\geq 0,r+s+f=n\right\}\ \text{ and }\ \ f(r,s,t)=\binom{m_1}{r} \binom{m_2}{s} \binom{m_3}{t} $$ How to compute the sum manually, first you determine the set $A$ and then you comute $S$, for exemple if $A=\{x_1,\cdots,x_n\}$ then $$S=f(x_1)+\cdots+f(x_n)$$ The order of the elements is not important when you compute the sum and does not affect either it's value because the $A$ does not contain any order, so you choose the order you want. The most important here is to determine the completely the set $A$.

---

Evaluation of the sum

What is the coefficient of $x^n$ in $$(1+x)^{m_1+m_2+m_3}=(1+x)^{m_1}(1+x)^{m_2}(1+x)^{m_3}$$ As consequence your sum equals: $$\dbinom{m_1+m_2+m_3}{n} $$

Answer 2

If your question was specifically about simplifying this particular sum, see Elaqqad's answer for a combinatorial argument on what it is equal to. If your question is more about how to manually compute the sum and how to interpret the notation, then continue reading mine.

Capital Sigma Notation can have several different ways of writing what the set of values you sum over are.

In this case, for the summation: $\sum\limits_{r,s,t\geq 0~\text{s.t.}~r+s+t=n}$, I interpret it as summing the expression over all possible $r,s,t\in\mathbb{Z}$ such that the following conditions hold:

$$\begin{cases} r\geq 0\\ s\geq 0 \\ t\geq 0\\ r+s+t=n\end{cases}$$

In particular, there will be $\binom{n+2}{n}$ summands (seen from stars&bars). It doesn't matter in what way you choose to add the terms together (since there are a finite number of terms and addition is commutative), though if you wanted to do it by hand I would recommend Lexicographic order (a.k.a. Dictionary Order).

You would do it as: $(0,0,n), (0,1,n-1), (0,2,n-2), \dots, (0,n,0), (1,0,n-1), (1,1,n-2),\dots, (n-1,0,1), (n-1,1,0), (n,0,0)$

where you order the entries according to the the size of the earliest difference.

For an explicit example, with $n=2$ you would have

$$\binom{m_1}{0}\binom{m_2}{0}\binom{m_3}{2} + \binom{m_1}{0}\binom{m_2}{1}\binom{m_3}{1} + \binom{m_1}{0}\binom{m_2}{2}\binom{m_3}{0} + \binom{m_1}{1}\binom{m_2}{0}\binom{m_3}{1} + \binom{m_1}{1}\binom{m_2}{1}\binom{m_3}{0} + \binom{m_1}{2}\binom{m_2}{0}\binom{m_3}{0}$$