Permutations with indistinguishable objects vs Distinguishable objects and distinguishable boxes.

balls-in-binscombinatorics

When we consider permutation with indistinguishable objects (I assume without repetiton), the formula for the total number of permuations is:

$\frac{n!}{n_1!n_2!…n_k!}$.

(The number of different permutations of n objects, where there are
n_1 indistinguishable objects of type 1, n_2 indistinguishable objects of type 2, …., and n_k indistinguishable objects of type k, is:)

For Distinguishable objects and distinguishable boxes we have:

$\frac{n!}{n_1!n_2!…n_k!}$.

(distributing n distinguishable objects into k distinguishable boxes.)

How is this possible? In the first case the objects are indistinguishable while in the second Distinguishable. How is it that the case of Distinguishable objects and distinguishable boxes represents permutation with indistinguishable objects (I assume it does, since the formula is the same).

EDIT:

Let's say all the objects (distinguishable ) are put in the same box (distinguishable ). How is this translated to a permutation??

Best Answer

Your first part where you are talking of "indistinguishable" objects, the objects are not really indistinguishable, as they are divided into distinguishable types.

In fact, both the (identical) formulas you have written are simply the multinomial coefficient, which has various interpretations.

  • distinct objects into distinct boxes with $n_1$ in box $1$ (not $n_1$ in any box), $n_2$ in box $2$, $n_3$ in box $3$ etc
  • dividing people into teams, with the people getting labeled according to the team they are put in
  • permutations of distinct objects where some elements are repeated

The formulas for all three are equivalent, viz $$\binom{10}{2,3,3,2} \equiv \binom{10}2\binom83\binom53\binom22 \equiv \frac{10!}{2!3!3!2!}$$

The multinomial coefficient does not give all ways of dividing distinct objects into distinct boxes, eg for the simple case with $3$ distinct objects and $2$ boxes,

$\large\binom{3}{3,0} = 1,\;\; \binom{3}{2,1} = 3,\;\; \binom{3}{1,2} = 3,\;\; \binom{3}{0,3} = 1$

Total arrangements $=8 = 2^3$, as it should be

Related Question