Problem Solving

Here's the question I've been trying to get a handle on:

In how many different ways can the letters A, A, B, B, B, C, D, E be arranged if the letter C must be to the right of the letter D?

A. 1,680
B. 2,160
C. 2,520
D. 3,240
E. 3,360

I understand what I considered the first step of the problem where we would have to de-duplicate the repeating terms by division.

So 8!/(2!)(3!) or 8*7*6*5*4*3*2*1 / (2*1)*(3*2*1)

I become lost, however, when attempting to apply the restriction limiting C's placement to the right of the letter D.

The resource from which I took this problem suggests approaching the restrictive element by dividing again by two, so 8!/(2!)(3!)(2).

The premise for this, the explanation goes on, is that "For any specified locations of the letter C and the letter D, there are the same number of arrangements for the other 6 letters when C is to the right of D and D is to the right of C. So we must divide the number of possible arrangements of all the letters by 2."

This is the part I don't quite understand and I would really appreciate any insight into how to resolve the part of the problem involving the restriction on the order of C & D as well as any other restriction related pearls of wisdom you may willing to impart.

Ryan Ziemba wrote:Here's the question I've been trying to get a handle on:

In how many different ways can the letters A, A, B, B, B, C, D, E be arranged if the letter C must be to the right of the letter D?

A. 1,680
B. 2,160
C. 2,520
D. 3,240
E. 3,360

I understand what I considered the first step of the problem where we would have to de-duplicate the repeating terms by division.

So 8!/(2!)(3!) or 8*7*6*5*4*3*2*1 / (2*1)*(3*2*1)

I become lost, however, when attempting to apply the restriction limiting C's placement to the right of the letter D.

The resource from which I took this problem suggests approaching the restrictive element by dividing again by two, so 8!/(2!)(3!)(2).

The premise for this, the explanation goes on, is that "For any specified locations of the letter C and the letter D, there are the same number of arrangements for the other 6 letters when C is to the right of D and D is to the right of C. So we must divide the number of possible arrangements of all the letters by 2."

This is the part I don't quite understand and I would really appreciate any insight into how to resolve the part of the problem involving the restriction on the order of C & D as well as any other restriction related pearls of wisdom you may willing to impart.

In all of the possible permutations, the letter C is to the right of the letter D in as many cases as are the cases in which the letter D is to the right of the letter C. Hence, the answer must be half of all the permutations with the letters A, A, B, B, B, C, D, E in hand.

ANSWER = ½ × 8!/ (2! × 3!) = [spoiler]1680.

A[/spoiler]

Both very helpful. Thanks and I appreciate the additional problem.

Hi All/Ian,


Am really week in Permutations/Combinations problem - and in the below mentioned problem - i am not able to understand why we used 8!/3!*2! ( i understand division by 2 conscept) .

Can you please help in understanding the logic behind that...i was taking up this problem as -

total way of arranging these elements shd be 8!
But we have A,A and B,B,B elemts (duplicates ) So can take A,A -> one entity and B,B,B --> one entity No we have 5 entities

so 5! -- but we can arrange A,A in 2! ways and B,B,B in 3! ways So a total of 5!*2!*3! -- but that is not correct ..

Can you please help in undertanding the concept here.

puneetdua wrote:Hi All/Ian,


Am really week in Permutations/Combinations problem - and in the below mentioned problem - i am not able to understand why we used 8!/3!*2! ( i understand division by 2 conscept) .

Can you please help in understanding the logic behind that...i was taking up this problem as -

total way of arranging these elements shd be 8!
But we have A,A and B,B,B elemts (duplicates ) So can take A,A -> one entity and B,B,B --> one entity No we have 5 entities

so 5! -- but we can arrange A,A in 2! ways and B,B,B in 3! ways So a total of 5!*2!*3! -- but that is not correct ..

Can you please help in undertanding the concept here.

You could only count AAA as one entity if all of the As had to be together. Since the As can be split up, you have to treat them separately.

Let's illustrate with a simpler example:

How many ways can the letters AAA be arranged?

Using your method, we treat the 3 As as one entity, and then you want to multiply by 3! for the 3 As, so the answer would be 1!3! = 3.

However, common sense tells us that there's only one unique arrangement.

When arranging items some of which are identical, you use a specialized formula:

n!/r!s!t!...

in which n is the total number of items and r, s, t, ... represent the number of duplicates. We treat each item as an individual when counting the total number of terms, but we divide by the number of duplicates to avoid double (or triple) counting.

So, in the above very simple example, the answer would be:

3!/3! = 1.

In the originally posted question, we have:

8 total letters
2*A; 3*B

so, (ignoring the C/D restriction), the number of unique arrangements is:

8!/2!3!

The reason why we divide by the number of duplicates factorial is because that's the number of ways of arranging those items within their own designated slots.

Let's go back to AAA and instead call the 3 letters A1, A2 and A3.

If we just do 3!, we've counted:

A1 A2 A3
A1 A3 A2
A2 A1 A3
A2 A3 A1
A3 A1 A2
A3 A2 A1

as 6 different arrangements, even though all 6 are identical.

Similarly, if we have 2 Bs (B1 and B2) and just used 2!, we've counted:

B1 B2
B2 B1

as 2 different arrangements, even though both are identical.

@Stuart and @Ian
I have a question on a similar problem :

How many ways can I arrange the letters 1) A A B C 2) A A B B ? The answer to the first question is 6. The answer to the second question is 3.

Method 1 : Permutation First, I applied the method n!/a! b! .... where a and b are repetitions....

Therefore, 1) => 4!/2! = 4*3*2/2 = 12 NOT CORRECT
for 2) => 4!/2!*2! = 6 NOT CORRECT. I am not sure why.

Second Method - If I think of this example as that of a combination problem as opposed to permutation (Method 1) problem, here's what i Got

for 1) it's nothing but I am asked to choose two letters out of 4 letters => 4C2 = 6.
for 2) it's nothing but I am asked to find combinations with repetitions. Hence, n=2, r=2. Therefore, total number of combinations = (n+r-1,r) = (3,2) = 3 CORRECT.

My question is: (i) What's wrong with method 1 ?
(ii) Is my understanding correct for Method 2 ?

I have a bad feeling that I am missing an important concept.

Any help is greatly appreciated.

thanks
Voodoo

Sure, Ian. You are right. We need to look at the complete question to understand whether the answer is correct or not.


HEre's the question:

Question - Bill has a small deck of 12 playing cards made up of only 2 suits of 6 cards each. Each of the 6 cards within a suit has a different value from 1 to 6; thus, for each value from 1 to 6, there are two cards in the deck with that value. Bill likes to play a game in which he shuffles the deck, turns over 4 cards, and looks for pairs of cards that have the same value. What is the chance that Bill finds at least one pair of cards that have the same value?


8/33
62/165
17/33
103/165


Frankenstein and I were discussing this problem. I know an easy method to solve it but I thought of doing it the "lengthy" way just to test my understanding of the probability theory i.e. by calculating the probability of a pair and then two pairs.


My approach to solve the question :

We have four cards that are drawn. Let's call them A B C D

Now we can only have two pairs at max because four cards are drawn.

Option (i) Two cards = 1 pair : => A and B are same. C and D are different
The first card can be drawn in 12 ways.
The second card can be drawn in only 1 way because we need a pair and I am assuming that A = B
The third and the fourth can be drawn in 10, 8 ways respectively.

Therefore, total number of combinations for 1 pair = X *12*1*10*8 {where X = arrangement of letters A, B and C in AABC = 4!/2! = 12; Assuming my sequence is AABC; I have two 2 A's }.......(U)


Option (ii) 2 pairs : A and B are same. C and D are same too.... But, A != C
Using the same logic as above A B C D = 12*1*10*1 * Y .............(V) {where Y = arrangement of letters A and B in AABB = 4!/(2!*2!) = 6}

Total number of combinations = 12*11*10*9 ................(W)

Therefore, probability = (U+V)/W = 17*2/33 > 1 Not possible.

Frankenstein told me that X should be 6 and Y should be 3 because I will have duplicates in both the equations above and hence, I will have to divide U AND V by 2. I see his point. I have worked it out and he is correct. But, I am not able to understand how can I derive this result mathematically in terms of formula.


Here's what I tried as my next step :

X = 4C2 because AABC can be thought of as choosing two cards from a deck of 4 cards. secondly, order doesn't matter. Works.
For Y, I thought of applying the concept of repetition for combinations (becuase order doesnt matter and we have two A's and B's ) ie (n,r)=(2 letters, 2 choices) . Therefore, Y= (n+r-1,r) = (3,2) = 3 works. But I am not able to understand why I am required to apply two different concept for the same problem.

Any help is greatly appreciated. I have a bad feeling that I am missing an important concept.

Thanks
Voodoo