probability /Permutation without Repitition formula

[Deep79]

Hi

 

I am confused here.

We have a formule to permute k out of n objects with indistinguishable objects in the set.

P(n,r) = n ! / n1 ! n2!...nk!

 

Is there any constraint on this formula?

 

Say i have a word 'RARR' -4 letter word .In how many ways i can permute 2 letters out of this,no repititon and .

no of indistinguishable objects=3

We have to select 2 out of 4 objects

 

P = P(4,2) / 3!= 2 answer

ut in real, ways are 3 => RR,AR,RA

 

 

I dont understand here in this case, is formula modified.

Or should no of indistinguishable objects be

[ikkokusenkin]

Hi

 

I am confused here.

We have a formule to permute k out of n objects with indistinguishable objects in the set.

P(n,r) = n ! / n1 ! n2!...nk!

 

I think you meant P(n,r)/(n₁!n₂!...n_k!) where there are k classes of indistinguishable objects and we permute r objects.

 

Is there any constraint on this formula?

 

Say i have a word 'RARR' -4 letter word .In how many ways i can permute 2 letters out of this,no repititon and .

no of indistinguishable objects=3

We have to select 2 out of 4 objects

 

P = P(4,2) / 3!= 2 answer

ut in real, ways are 3 => RR,AR,RA

 

 

I dont understand here in this case, is formula modified.

Or should no of indistinguishable objects be

 

Yes, the number of indistinguishable objects should be ≤ r. For instance, the number of ways of permuting 3 letters of 'RARR' is:

⁴P₃/3! = 4. Enumerating, we see that this is correct:

RRA

RAR

ARR

RRR

 

The idea is that ⁿP_r assumes all r objects are distinct. If some objects are the same, we need to compensate for duplicated permutations by dividing by the number of permutations of the same objects. Obviously, for this formula to work, at least one of the same objects must be in the mix at all times. For instance, in the example I just gave, there isn't a case that doesn't involve R. This is also why the formula n!/(n₁!n₂!...n_k!) always works. It is the number of permutations possible for all n objects (P(n,n) = n!). We know that n will always be ≥ number of indistinguishable objects.

 

This brings us to an interesting limitation of this formula. What if it was possible to permute r out of n objects (observing the condition that r ≥ number of indistinguishable objects) and still leave out some of the indistinguishable objects for at least some of the permutations?

 

For instance, consider 'RARBC.' The number of indistinguishable objects is 2. Let's try to permute 2 objects out of the 5 given. The P(n,r)/(n₁!n₂!...n_k!) formula gives us ⁵P₂/2! = 20/2 = 10 ways. Is this true? No! Because some of the ⁵P₂ permutations don't involve R at all! Let's enumerate permutations to confirm this hunch:

1. AB

2. BA

3. AC

4. CA

5. BC

6. CB

7. AR

8. RA

9. BR

10. RB

11. CR

12. RC

13. RR

 

The conclusion? We should qualify the formula P(n,r)/(n₁!n₂!...n_k!) by specifiying that:

1. r ≥ number of indistinguishable objects

2. the number of indistinguishable objects ≥ half the number of total objects

[saubaer]

The conclusion? We should qualify the formula P(n,r)/(n1!n2!...nk!) by specifiying that:

1. r ≥ number of indistinguishable objects

2. the number of indistinguishable objects ≥ half the number of total objects

If this is not the case, can we only solve this by systematically listing all possible permutations?

Are there any other constraints? It seems not to work if repetition is allowed.

E.g: In how many ways can the letters ABA be arranged?

In this case the above conditions are fulfilled. But the right answer is obviously not 3³/2! = 13.5 (in fact, there are 8 possible permutations) How can one solve this without writing down all options?

 

Another question: How do we handle indistinguishable objects in combination problems?

E.g: How many different 3 letter combinations are there of the set ABBBC (rep. not allowed)?

Possible combinations are ABC,ABB,BBB,BBC = 4 and not ₅C₃/2! = 5

 

One more question (from Dr. Raju's april quant update):

Given the two names JULLIE and LILLY, if one letter is picked from both simultaneously at random, what is the probability that it is the same letter?

Can we solve it like this: Probability of picking a L from both names + prob. of picking I from both names = (2/6)*(3/5) + (1/6)*(1/5) = 7/30

How would you solve this by using the combination formula? Do we have to be concerned about the indistinguishable letters?

[ikkokusenkin]

If this is not the case, can we only solve this by systematically listing all possible permutations?

Are there any other constraints? It seems not to work if repetition is allowed.

E.g: In how many ways can the letters ABA be arranged?

In this case the above conditions are fulfilled. But the right answer is obviously not 3³/2! = 13.5 (in fact, there are 8 possible permutations)

 

There are? Hmmm. I can only see three:

ABA

BAA

AAB

which is ³P₃/2!

[saubaer]

In how many ways can the letters ABA be arranged?

I meant with repetition allowed, forgot to mention it.

[ikkokusenkin]

Another question: How do we handle indistinguishable objects in combination problems?

E.g: How many different 3 letter combinations are there of the set ABBBC (rep. not allowed)?

Possible combinations are ABC,ABB,BBB,BBC = 4 and not ₅C₃/2! = 5

 

Looks like we've opened a can of worms! :D

I don't think we can frame a neat formula for combinations. If I had to guess, I'd say that part of the problem is that the ⁿC_r formula was itself built to discard repetitions from the permutations formula.

 

One more question (from Dr. Raju's april quant update):

Given the two names JULLIE and LILLY, if one letter is picked from both simultaneously at random, what is the probability that it is the same letter?

Can we solve it like this: Probability of picking a L from both names + prob. of picking I from both names = (2/6)*(3/5) + (1/6)*(1/5) = 7/30

 

Yeah, that's how I'd do it too.

 

If this is not the case, can we only solve this by systematically listing all possible permutations?

 

Hey, I list all possible permutations even when it's not required. Would be good to have to do it as correct procedure some of the time. LOL :D