Example Problem:
Count the number of distinct ways in which N objects, of which n1 are indistinguishably of one type and n2 of a second type, can be accomodated in a total of N = n1 + n2 ways.
Solution argument goes like:
1st place can be occupied by any one of the N objects.
the 2nd place can be occupied by any one of the remaining (N-1) objects.
…
Nth place can be occupied only by last 1 object.
Hence all available places can be occupied in
N(N-1)(N-2)…1 = N!
possible ways.
Now since n1 objects are indistinguishable, all the n1! permutations of these objects lead to the same situation. Similarly, all the n2! permutations of objects of second kind lead to the same situation.
Final argument which I don't understand:
By dividing N! by n1!n2!, we obtain total number of distinct ways of arrangement of N objects in which n1 are of one type and n2 are of second.
My question is what is the intuitive and memorable way to visualize this. Why can't following answers be right?
a) N! – (n1!n2!)
b) N! – n1! – n2!
I can validate the right answer by taking small numbers like N = 5, n1 = 2, n2 = 3. But cannot build the general understanding why division and not subtraction.
Best Answer
First imagine all $N$ items are distinct. There are $N!$ ways to put them in order. Now designate $n1$ of them to be interchangeable. There are $n1!$ orders you could have had the items in, which are now all the same, so now there are $\frac {N!}{n1!}$ distinct orders. Repeat with the other $n2$ items. The advantage of this approach is it works if $n1+n2 \lt N$, so there are still some distinct items.