The number of ways to distribute n distinguishable objects into k…

Concept. Distributing n distinguishable objects into k distinguishable boxes with a prescribed size \(n_i\) for box i (where \(n_1+n_2+\cdots+n_k=n\)) is a multinomial-coefficient count. The boxes are filled one after another by choosing which objects go into each box, and by the product rule those successive choices multiply. Dividing by \(n_i!\) for each box removes the orderings inside that box, which do not create a new distribution.

Application. Fill the boxes in order:

1. Box 1 receives any \(n_1\) of the n objects: \(\binom{n}{n_1}\) choices.

2. Box 2 receives any \(n_2\) of the \(n-n_1\) objects that remain: \(\binom{n-n_1}{n_2}\) choices.

3. In general box i receives \(\binom{n-n_1-\cdots-n_{i-1}}{n_i}\) choices, and box k finally takes the \(n_k\) objects that are left.

4. By the product rule the total is \(\binom{n}{n_1}\binom{n-n_1}{n_2}\cdots\binom{n_k}{n_k}=\frac{n!}{n_1!\,(n-n_1)!}\cdot\frac{(n-n_1)!}{n_2!\,(n-n_1-n_2)!}\cdots\frac{n_k!}{n_k!\,0!}\).

5. Every intermediate factorial cancels telescopically, leaving \(\frac{n!}{n_1!\,n_2!\,n_3!\cdots n_k!}\), the multinomial coefficient. This is the required count.

Cross-check. Take n = 3 objects a, b, c into k = 2 boxes with \(n_1=1\) and \(n_2=2\). The formula gives \(\frac{3!}{1!\,2!}=3\), and listing the distributions confirms exactly three: (a | b, c), (b | a, c) and (c | a, b).

Contrast. The over-counting to be removed is the \(n_i!\) orderings inside each box, and all of them must be divided out at once, so the correction factor is the product \(n_1!\,n_2!\cdots n_k!\). A denominator that adds or subtracts those block factorials instead does not undo that over-counting: on the same n = 3 example with box sizes 1 and 2, \(\frac{n!}{n_1!+n_2!+\cdots+n_k!}\) returns \(6/3=2\) and \(\frac{n_1!\,n_2!\cdots n_k!}{n_1!-n_2!-n_3!\cdots-n_k!}\) returns \(2/(1-2)=-2\), while the number of distributions is 3. The ratio \(\frac{n_1!+n_2!+\cdots+n_k!}{n_1!\,n_2!\cdots n_k!}\) returns \(3/2\) there, which is not even a whole number.