"Elegant" way to assign 4 distinct objects into 4 bins

Question

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.

Answer 1

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

Answer 2

Let the objects choose the people . . .

Each object has $4$ choices, and each object's choices are independent of the choices made by the other objects, hence there are $4^4$ ways for the objects to choose the people.

Alternatively, using your cases . . .

• For distribution type $1$, the number of ways is $$4!=24$$ Explanation:
  If we have the people line up to choose, then person $1$ has $4$ choices, person $2$ has $3$ choices, person $3$ has $2$ choices, and person $4$ has $1$ choice.

• For distribution type $2$, the number of ways is $$\binom{4}{1}\binom{4}{2}\binom{3}{2}2!=144$$ Explanation:
  • Choose the person who gets two objects:$\;{\large{\binom{4}{1}}}\;$choices.
  • Choose the two objects for that person:$\;{\large{\binom{4}{2}}}\;$choices.
  • Choose the two people to get the two remaining objects:$\;{\large{\binom{3}{2}}}\;$choices.
  • Distribute the two remainining objects, one to each of the two chosen people:$\;2!\;$choices.

• For distribution type $3$, the number of ways is $$\binom{4}{2}\binom{2}{1}\binom{3}{1}=36$$ Explanation:
  • Choose the two people who get two objects:$\;{\large{\binom{4}{2}}}\;$choices.
  • Choose the person who gets the object labeled #$1$ plus one other object:$\;{\large{\binom{2}{1}}}\;$choices.
  • Choose the other object for that person:$\;{\large{\binom{3}{1}}}\;$choices.

• For distribution type $4$, the number of ways is $$\binom{4}{1}\binom{4}{3}\binom{3}{1}=48$$ Explanation:
  • Choose the person who gets three objects:$\;{\large{\binom{4}{1}}}\;$choices.
  • Choose the three objects for that person:$\;{\large{\binom{4}{3}}}\;$choices.
  • Choose the person to get the one remaining object:$\;{\large{\binom{3}{1}}}\;$choices.

• For distribution type $5$, the number of ways is $$\binom{4}{1}=4$$ Explanation:$\;$Choose the person who gets all four objects:$\;{\large{\binom{4}{1}}}\;$choices.

$\;\;\;$Summing the counts for the cases, the total number of ways is $$24+144+36+48+4=256$$