$\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$).
 A: 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:


*

*Note first that since $n<m$, we will be using at most $n$ of the $m$ boxes.

*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$.

*Fix such a $k$ now.  There are exactly $\binom{m}{k}$ ways to choose $k$ boxes among the $m$.  

*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$.

*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.
A: Suppose you need to produce n numbers, c_1,..., c_n, each between 1 and m.
You can do it in this way -


*

*Select k, number of distinct integers in the list

*Choose k distinct numbers between 1 and m

*Select number of times a_i those numbers will appear

*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

*Choose positions for all these k numbers


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