How does distinguishability of boxes change the number of ways to distribute n objects into separate boxes

113 Views Asked by At

I was going through problems related to distributing n distinguishable objects all into boxes, a in the first, b in the second, c in the third where a+b+c = n. The solutions I've seen usually comes to the form of $\frac{n!}{a!b!c!}$ I am wondering, for this solution to be true, are the boxes distinguishable or not distinguishable?

If a, b, c etc. are all different similar to this problem, it seems like we would need to multiply the factorial of the number of boxes to $\frac{n!}{a!b!c!...}$ if the boxes are distinguishable? What if we specify, like in the question, that the $a$, $b$ ... objects must go into specific boxes, does that make the boxes distinguishable (and yet per the solution we would suppress the 5! term)?

For this problem, the number of ways to distribute 13 cards to four people is $\frac{52!}{13!^4}$. If I split the deck into 4 specific sets of 13 (and label each set as A, B, C, D), doesn't $\frac{52!}{13!^4}$ include the combination where one person gets A, another gets B, then C, then D, as well as one person getting D, then C, then B, then A (and all other permutations of these four sets). In this case, it seems like the people are distinguishable?

Edit:

With respect to the duplicate, I have some followup questions.

For partitions of all different sizes, why does whether the ordering matter or not not change the solution of $\frac{n!}{n_1!n_2!\dots n_r!}$?

The duplicate states that if the partitions are of equal sizes, then an r! term must be in the denominator to discount for order (I assume this means the r boxes are indistinguishable?). However, in the poker problem I linked above, the number of ways to distribute 13 cards to 4 people was given as $\frac{52!}{13!^4}$ even though I don't think the people were considered distinguishable in that problem. I feel like I'm missing something?

1

There are 1 best solutions below

6
On BEST ANSWER

Consider the case of having distinguishable boxes, which we can just label $A, B, C$. We can arbitrarily decide to fill $A$ first, then $B$, then $C$.

How many ways can we put $a$ elements in box $A$? That is well-known to be $n \choose a$. Now how many ways can we put $b$ of the remaining $n-a$ elements in box $B$?. This is well-known to be $n - a \choose b$. And finally, how many ways can be put the remaining $c$ elements in box $C$? Obviously $1$.

Since these are independent, the total number of ways to do all three is their product $${n\choose a}{n - a \choose b}1 = \frac{n!}{a!(n-a)!}\frac{(n-a)!}{b!(n-a-b)!} = \frac {n!}{a!b!c!}$$

I.e., the formula $\frac {n!}{a!b!c!}$ counts the number of ways of distributing $n$ objects among distinguishable boxes (and similarly when there are more boxes).

When the boxes are indistinguishable, it becomes more complicated. But first note that if $a \ne b, b \ne c, c \ne a$, then the boxes are automatically distinguishable! $A$ is the box that will end up with $a$ elements, $B$ is the box that will end up with $b$ elements, and $C$ is the box that will end up with $c$ elements.

Now if all three of $a,b,c$ are the same (so $n=3a$), then the boxes become indistinguishable, so we have to divide by the possible arrangements of the boxes to get the count in this case: $$\frac{(3a)!}{3!a!^3}$$ If $a$ is different, but $b = c$, then $A$ is distinguishable, but $B$ and $C$ are not, so we have to divide by the possible arrangements of $B$ and $C$:

$$\frac{n!}{2!a!b!^2}$$