0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I have counted every item two times and obtained 10. How many items were there? $\endgroup$
    – user
    May 2 '20 at 19:37
  • $\begingroup$ @user 5*2 = 10. So, 5 items were there? I understand my question also has some similar argument. But cannot put it in clear thoughts. $\endgroup$
    – user701723
    May 2 '20 at 20:04
  • $\begingroup$ Exactly. You count several times the same item. If you know how many times you have counted it, you determine the number of items by division, not by subtraction. $\endgroup$
    – user
    May 2 '20 at 20:09
  • $\begingroup$ @user: okay, now I see point of your question. and getting somewhere: If I count one item n1! times, I have to divide it by n1!. Is that right way to think? $\endgroup$
    – user701723
    May 2 '20 at 20:10
  • $\begingroup$ Absolutely correct. $\endgroup$
    – user
    May 2 '20 at 20:10
0
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.