“Elegant” way to assign 4 distinct objects into 4 bins

combinationscombinatoricspermutations

Suppose you have four objects to distribute among four people. Suppose people can carry any number of objects (none, one, two, three, or all four objects) at once. In how many ways can the four objects be distributed?

My solution

Let the four people be named A,B,C,D.

Distribution type 1

If each person gets exactly one object, the distribution looks like

A B C D
1 1 1 1

of which there are $4!=4\cdot 3 \cdot 2 \cdot 1 = 24$ distinct ways (since the objects are distinct).

Distribution type 2

If one person gets 2 objects and two others get 1 object, the possible distributions look like

A B C D
2 1 1 0
2 1 0 1
2 0 1 1
1 2 1 0
1 2 0 1
0 2 1 1
1 1 2 0
1 0 2 1
0 1 2 1
1 1 0 2
1 0 1 2
0 1 1 2

and for each of the above distributions, there are $12$ distinct ways to distribute the distinct objects.

Distribution type 3

If two people get 2 objects, the possible distributions look like

A B C D
2 2 0 0
2 0 2 0
2 0 0 2
0 2 2 0
0 2 0 2
0 0 2 2

and for each of the above distributions, there are $6$ distinct ways to distribute the distinct objects.

Distribution type 4

If one person gets 3 objects and another person gets 1 object, the possible distributions look like

A B C D
3 1 0 0
3 0 1 0
3 0 0 1
1 3 0 0
0 3 1 0
0 3 0 1
1 0 3 0
0 1 3 0
0 0 3 1
1 0 0 3
0 1 0 3
0 0 1 3

and for each of the above distributions, there are $4$ distinct ways to distribute the distinct objects.

Distribution type 5

If one person gets all 4 objects, the possible distributions look like

A B C D
4 0 0 0
0 4 0 0
0 0 4 0
0 0 0 4

for each of the above distributions, there is only $1$ distinct way to distribute the distinct objects.

Totaling the ways

The total number of ways is then

\begin{align}
&\textrm{ type 1 + type 2 + type 3 + type 4 + type 5 }\\
=& 1(24) + 12(12) + 6(6) + 12(4) + 4(1) \\
=& 24 + 144 + 36 + 48 + 4 \\
=& 256\textrm{ ways }
\end{align}

My questions

I have 3 questions:

  1. Is there a more elegant way (using $_n P_k$ or $_n C_k$ notation) of counting the amount of each distribution type (the numbers 1, 12, 6, 12, 4) that appear in the final calculation?

  2. Is there a more elegant way (using $_n P_k$ or $_n C_k$ notation) of counting the number of ways for each distribution type (the numbers 24, 12, 6, 4, 1) that appear in the final calculation in parentheses? (Clearly the 24 is just $_4 P_4$, but what about the others?)

  3. Why is all of this just equal to $4^4$? This isn't immediately obvious to me.

Best Answer

  1. Breaking it up a little differently, the number of ways with $k = 0,1,2,3$ of them getting $0$ is $_4C_k \cdot {}_3C_{3-k}$, which gives the sequence $1, 12, 18 = 6 + 12, 4$. Where the difference is that you had the $6$ ways of $2,2,0,0$ and the $12$ ways of $3,1,0,0$ separately. Those are $\frac{4!}{2!2!}$ and $\frac{4!}{1!1!2!}$, respectively.
  2. For the arrangements, you are looking at the multinomial coefficients: $\frac{4!}{1!1!1!1!} = 24, \frac{4!}{2!1!1!0!} = 12, \frac{4!}{2!2!0!0!} = 6, \frac{4!}{3!1!0!0!} = 4, \frac{4!}{4!0!0!0!} = 1$
  3. Instead of focusing on the people and which objects they get, look at the objects and who they are given to. Each object can be given to any of the four people, without restriction. That means there are $4$ options for the first object, $4$ for the second, and so on, so the total is $4^4$.
Related Question