Revision as of 12:48, 25 April 2012

Distinguished/Indistinguished Problem

This page is mainly discussing an interesting permutation problem in the back of the book. We have done such problems in our homework, but when I did those problems I always feel confused and overwhelmed. So that's the reason why I want to write this summary.

I will discuss this problem in detail by giving out some examples and hope this will clarify your confusion as well.

Let's first begin with the easiest one.

Problem Type A: Distinguished Boxes vs Indistinguished Items

Example1: If we have 3 distinguished boxes and 5 indistinguished items, how many ways can we distribute the items into the boxes?

This kind of problem is similar to the “fruit basket problem” we discussed in lecture. Treat the indistinguished items as stars(*) and we use bars to separate items into boxes.

So we need 5 stars and 2 bars for this example and therefore,

          #ways = C((5+2), 2) = C(7, 2) = 21.

Problem Type B: Indistinguished Boxes vs Indistinguished Items

Example2: If we have 3 indistinguished boxes and 5 indistinguished items, how many ways can we distribute the items into the boxes?

This problem seems to be easy but actually, at least for me, it's easy to make mistakes and leave out some possible combinations.

So for this kind of problem, you need to sit down and calm down and try to list every possible combinations yourself.

To make our work easier, let's simplify (x items in box1, y items in box2, z items in box3) into (x,y,z).

OK, let's begin:

        (0,0,5), (0,1,4), (0,2,3), (0,3,2), (1, 1, 3), (1, 2, 2), (1,3,1), (2,0,3) END<strike</strike>

        #ways = 5.

Problem Type C: Indistinguished Boxes vs Distinguished Items

Example3: If we have 3 distinguished boxes and 5 distinguished items, how many ways can we arrange the items into the boxes?
          Step1: You need to find out all possible box combinations. {(0,0,5), (0,5,0), (5,0,0)}, {(0,1,4), ..., (4,1,0)}, {(0,2,3), ...(3,2,0)}, {(1, 1, 3), (1,3,1), (3,1,1)},{(1, 2, 2),(2, 1, 2), (2, 2, 1)}

          We can call {...} a set.

          Step2: For each box combination set from step1, calculate the total ways of different item arrangements for one particular elements in the set:
                  #ways(x,y,z) = C(5,x)*C(5-x,y).

                  We notice that for each elements in the set, the values for #way are the same, therefore,

                  total ways of arrangement for a set = #ways*(# of elements of the set).

          Step3: Iterate step 2 for all sets and then add everything up.

          Final Calculation:

            for set1: #way(0,0,5) = C(5,0)*C(5-0,0) = 1; total ways for set1 = #way(0,0,5)*C(3,1)(choose a box for the 5 items) = 1*3 = 3;

            for set2: #way(0,1,4) = C(5,0)*C(5-0,1) = 5; total ways for set1 = #way(0,1,4)*(C(3,1)*C(2,1))(choose a box for the 0 item and then one box fore the 1 item) = 5*6 = 30;

            for set3: #way(0,2,3) = C(5,0)*C(5-0,2) = 10; total ways for set1 = #way(0,2,3)*(C(3,1)*C(2,1))(choose a box for the 0 item and then one box fore the 2 item) = 10*6 = 60;

            for set4: #way(1,1,3) = C(5,1)*C(5-1,1) = 20; total ways for set1 = #way(1,1,3)*C(3,1)(choose a box for the 3 items) = 20*3 = 60;

            for set5: #way(1,2,2) = C(5,1)*C(5-1,2) = 30; total ways for set1 = #way(1,2,2)*C(3,1)(choose a box for the 3 items) = 30*3 = 90;

            Total = 3+30+60+60+90 = 243.

Problem Type D: Indistinguished Boxes vs Distinguished Items

Example4: If we have 3 distinguished boxes and 5 distinguished items, how many ways can we arrange the items into the boxes?

The foregoing problem solutions have made a strong foundation for solving this problem.

          First we can go to problem Type B, and we will get the number of different box arrangements, which is 5.

          Then we can calculate the item arrangements for each box arrangement listed in B.

                    for(0,0,5): There is only one way of this combination;

                    for(0,1,4): #ways = C(5,1)*C(4,4) = 5;

                    for(0,2,3): #ways = C(5,2)*C(3,3) = 10;

                    for(1,1,3): #ways = C(5,1)*C(4,1) = 20;

                    WAIT!! If we compute in this way, we are treated the two boxes containing the same number of items differently,

so to get the correct number, we need to devide 20 by 2!, and then we get #ways = 20/2 = 10;

                    for(1,2,2): #ways = C(5,1)*C(5,2)/2! = 15;

                    Total = 1+5+10+20+10+15 = 41.

Pianpian Cao

[Category:MA375Spring2012Walther]