(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$).

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

| cite | improve this answer | |

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.