# $\sum_{k=1}^n \binom{n}{a_1,a_2, \cdots , a_k} \binom mk \binom{k}{b_1,b_2, \cdots , b_l}= m^n,$

(Own) Let $n,m$ be positive integers such that $m>n$. Prove that $$\sum_{k=1}^n \sum_{a_1+a_2 + \cdots +a_k=n} \binom{n}{a_1,a_2, \cdots , a_k} \binom mk \binom{k}{b_1,b_2, \cdots , b_l}= m^n,$$ where $1 \le a_i \; (1 \le i \le k)$ and $a_1+a_2+ \cdots + a_k=n$. In here, $b_i$ is the number of $a_x \; (1 \le x \le k)$ that have the same value. For example, if $n=6$ and $6=3+1+1+1$ then $b_i$ are $1$ (one number $3$) and $3$ (three numbers $1$).

• just for the fun of it: $6=3+1+1+1$ :-) – Math-fun Jul 2 '15 at 7:20
• So sorry, I have edited that. – Tengu Jul 2 '15 at 11:00
• For every $k$, the sum is further taken over all possible partitions of $n$ into $k$ integers $a_1, \ldots, a_k$? – Pierre-Guy Plamondon Jul 2 '15 at 11:28
• Yes, yes it is. – Tengu Jul 2 '15 at 13:31

We can prove this equality by reducing it to a counting problem, namely: In how many ways can we put $n$ distinct objects in $m$ distinct boxes?

This number is obviously equal to $m^n$. Now, we can find the left-hand side of the equality by using the following counting strategy:

1. Note first that since $n<m$, we will be using at most $n$ of the $m$ boxes.
2. For each $k\in\{1,\ldots, n\}$, let us count the number of ways to arrange the $n$ objects using exactly $k$ of the boxes. We will then sum over all possible $k$.
3. Fix such a $k$ now. There are exactly $\binom{m}{k}$ ways to choose $k$ boxes among the $m$.
4. For every choice of $k$ boxes, we must now count the number of ways to arrange the $n$ objects inside these boxes. We first choose how many objects there will be in each of the $k$ boxes: say $c_1$ in box $1$, ..., $c_k$ in box $k$. Thus we have $c_1+\ldots+c_k = n$, with each $c_i>1$. The number of ways to arrange the objects in these $k$ boxes is then $\binom{n}{c_1,\ldots, c_k}$. We take the sum of these numbers over all possible ordered partitions $c_1, \ldots, c_k$ of $n$.
5. Finally, we rewrite this last sum as follows. Instead of taking the sum over all ordered partitions, we will take it over all non-ordered partitions $a_1, \ldots, a_k$ of $n$, and multiply by the number of ways to order it. This number, using the notations of the question, is exactly $\binom{k}{b_1, \ldots, b_\ell}$.

Putting all of this together, we get that the number of ways to put $n$ distinct objects into $m$ distinct boxes is $$\sum_{i=1}^n \sum_{a_1+\ldots + a_k=n} \binom{m}{k}\binom{n}{a_1, \ldots, a_k}\binom{k}{b_1, \ldots, b_\ell},$$ where the second sum is taken over all non-ordered partitions of $n$ into exactly $k$ positive integers $a_1, \ldots, a_k$. This finishes the proof.

Suppose you need to produce n numbers, c_1,..., c_n, each between 1 and m.

You can do it in this way -

1. Select k, number of distinct integers in the list
2. Choose k distinct numbers between 1 and m
3. Select number of times a_i those numbers will appear
4. Choose a matching of the counts a_i to the k numbers, by observing that we need to match for distinct counts - choose b_i numbers out of the k for each distinct count
5. Choose positions for all these k numbers

This is the lhs.

Also the number of ways is m^n, which is the rhs.

• This is exactly my solution, replacing "putting $n$ objects in $m$ boxes" by "choosing $n$ integers between $1$ and $m$. – Pierre-Guy Plamondon Jul 2 '15 at 14:49
• Yes... I saw your solution later :) – KalEl Jul 3 '15 at 17:09
• Simultaneous solutioning ! :-) – Pierre-Guy Plamondon Jul 3 '15 at 20:09