A wrong understanding of Permutation and Combination

combinationspermutations

Suppose We have 10 different things that we want to distribute to P and Q where P gets 3 and Q gets 7, in how many ways can we do this ? ( order doesnt matter when P or Q gets them , ie if P gets {a,b,c} then it is same as {b,c,a} )

Now we know the answer will be $${10 \choose 3}\text{ Or } {10 \choose 7}$$
But my basic understanding is this :
The picture that alsways plays out in my mind is this

Row 1 : $\oplus$ $\oplus$ $\oplus$ $\oplus$ $\oplus$ $\oplus$ $\oplus$ $\oplus$ $\oplus$ $\oplus$

Row 2: |_______| |_______________|

       P             Q

My understanding:

  1. First we arrange the different things in row 1 ie in $10!$ ways .
  2. Then just bring the row 1 into row 2 , ie whichever balls are above P 's box come into it and the ballss above Q's box go into that box.
  3. But even in these small individual boxes there can be many permutations ( which are supposed to be treated as the same , but currently we are not)
  4. so we find the no of permutations possible in these small boxes . For P its $3!$ and for Q it is $7!$
  5. Now WE DIVIDE our initial arrangements by $3!\cdot 7!$ ( why not subtract ) and get $$\frac{10!}{3! \cdot 7!}$$
    So we got our Answer .

Now if we have 10 things out of which 3 are same (identical) , and 7 are different (non identical) ie a total of 8 species of balls, Find the number of ways you can distribute these to P and Q such that P gets 3 and Q gets 7 ?

(I don't know the actual answer but my friend told me that the answer that we were getting from logic is wrong)

By Logic :
Imagine the same picture( the two rows one with balls and other with empty boxes)

  1. First we arrange -> $\frac{10!}{3!}$ ( divided by 3! because they are same )

  2. Then we try to Find the Arrangements in those little boxes , But this time its not straightforwards , because the same balls can

    Case A : P has 3 identical and Q doesnt have any identical so we get $\frac{3!}{3!} \cdot 7! $

    Case B : P has 2 identical , Q has 1 so $ \frac{3!}{2!} \cdot 7!$

    Case C : P has 1 identical , Q has 2 so $ 3! \cdot \frac{7!}{2!}$

    Case D : P has 0 identical , Q has all 3 so $ 3! \cdot \frac{7!}{3!} $

  3. We Add them to get $$\frac{7!3!}{1}+\frac{7!3!}{3}=\frac{7!3!(4)}{3}=8!$$

  4. Now we divide the arrangements with no, of repititions ( or whatever ) and we get
    $$ \frac{10!}{2!8!}={10 \choose 2}$$

Is this Logic Correct ? Is there a shortcut logic for this ? Also why do we Divide and not subtract the repetition ( in step 5 of question 1 and Step 4 of question 2 )

Best Answer

The only reason that in the first problem, you can divide is because each single case in the $10!$ original arrangements is

  1. Equal probability
  2. With a precisely equal distribution into equivalent cases
  3. Where you actually want the count of the equivalent case-classes.

The problem with 4. in the second problem is not all of these cases have the same probability. It is far more difficult for all of the 3 identical balls to end up in P, for example.

There is no need to go about dividing the number of total arrangements. 2. does more than well enough in actually counting the different number of ways the objects can be distributed.

To do so, simply note that as a partition, choosing the objects for P completely determine the objects for Q (everything else). So:

  1. If P has 3 identical, there is precisely $\binom{7}{0}=1$ case
  2. If P has 2 identical, then you are choosing 1 of the other 7 non-identical objects, so precisely $\binom{7}{1}$ cases.
  3. If P has 1 identical, choose 2 of the other 7, for $\binom{7}{2}$ cases.
  4. If P has 0 identical, you choose $\binom{7}{3}$ ways.

The sum of these is the answer, without reference to the 10 total objects.

Related Question