In how many ways can the letters in "abcdabcd" be arranged without letting two letters which are alike come together?
a)2520
b)864
c)324
d)648
e)468
OA B
Any thoughts?
tough one - combinations
-
- Master | Next Rank: 500 Posts
- Posts: 405
- Joined: Thu Feb 10, 2011 1:44 am
- Thanked: 3 times
- Followed by:1 members
- sl750
- Master | Next Rank: 500 Posts
- Posts: 496
- Joined: Tue Jun 07, 2011 5:34 am
- Thanked: 38 times
- Followed by:1 members
Arrange the letters without any restriction. This can be done in 8!/(2!)^4 ways, as we have four-two repeating letters
Assume the letters are together, the opposite of what the question states. This allows us to club the identical letters as one unit.
Number of ways to arrange 4 letters is 4! ways
This clubbing results in 4 empty slots, we can treat this empty slots as filled by some imaginary letter, say n. In this case, we have 8!/4! ways of arranging the letters
Therefore, number of ways of arranging the letters without two identical letters being adjacent to each other is 8!/(2!)^4 - (8!/4! - 4!) = 864 . The 4! has to be subtracted from 8!/4! to avoid duplicate counting
Assume the letters are together, the opposite of what the question states. This allows us to club the identical letters as one unit.
Number of ways to arrange 4 letters is 4! ways
This clubbing results in 4 empty slots, we can treat this empty slots as filled by some imaginary letter, say n. In this case, we have 8!/4! ways of arranging the letters
Therefore, number of ways of arranging the letters without two identical letters being adjacent to each other is 8!/(2!)^4 - (8!/4! - 4!) = 864 . The 4! has to be subtracted from 8!/4! to avoid duplicate counting
- rijul007
- Legendary Member
- Posts: 588
- Joined: Sun Oct 16, 2011 9:42 am
- Location: New Delhi, India
- Thanked: 130 times
- Followed by:9 members
- GMAT Score:720
i didnt get this part of the solution..sl750 wrote:
This clubbing results in 4 empty slots, we can treat this empty slots as filled by some imaginary letter, say n. In this case, we have 8!/4! ways of arranging the letters
after clubbing all alike letters together, where did the 4 empty slots come from????
- sl750
- Master | Next Rank: 500 Posts
- Posts: 496
- Joined: Tue Jun 07, 2011 5:34 am
- Thanked: 38 times
- Followed by:1 members
As per the question, you will agree that there are a total of 8 letters. I club the a's, b's,c's, and d's respectively and treat them as abcd_ _ _ _. Imagine fusing the two a's into just one a.Do the same for the remaining letters. That is how I get four empty slotsrijul007 wrote:i didnt get this part of the solution..sl750 wrote:
This clubbing results in 4 empty slots, we can treat this empty slots as filled by some imaginary letter, say n. In this case, we have 8!/4! ways of arranging the letters
after clubbing all alike letters together, where did the 4 empty slots come from????
-
- Master | Next Rank: 500 Posts
- Posts: 385
- Joined: Fri Sep 23, 2011 9:02 pm
- Thanked: 62 times
- Followed by:6 members
could you explain say if the letters are ABCABC what the solution might be?sl750 wrote:As per the question, you will agree that there are a total of 8 letters. I club the a's, b's,c's, and d's respectively and treat them as abcd_ _ _ _. Imagine fusing the two a's into just one a.Do the same for the remaining letters. That is how I get four empty slotsrijul007 wrote:i didnt get this part of the solution..sl750 wrote:
This clubbing results in 4 empty slots, we can treat this empty slots as filled by some imaginary letter, say n. In this case, we have 8!/4! ways of arranging the letters
after clubbing all alike letters together, where did the 4 empty slots come from????
I partly was not able to understand the 8!/4! in your solution.
Thanks
user123321
- sl750
- Master | Next Rank: 500 Posts
- Posts: 496
- Joined: Tue Jun 07, 2011 5:34 am
- Thanked: 38 times
- Followed by:1 members
For ABCABCuser123321 wrote:could you explain say if the letters are ABCABC what the solution might be?sl750 wrote:As per the question, you will agree that there are a total of 8 letters. I club the a's, b's,c's, and d's respectively and treat them as abcd_ _ _ _. Imagine fusing the two a's into just one a.Do the same for the remaining letters. That is how I get four empty slotsrijul007 wrote:i didnt get this part of the solution..sl750 wrote:
This clubbing results in 4 empty slots, we can treat this empty slots as filled by some imaginary letter, say n. In this case, we have 8!/4! ways of arranging the letters
after clubbing all alike letters together, where did the 4 empty slots come from????
I partly was not able to understand the 8!/4! in your solution.
Thanks
user123321
The two A's are joined as one
The two B's are joined as one
The two C's are joined as one
ABC_ _ _
Fill the blanks with X's
ABCXXX
This can be arranged in 6!/3! ways. The 3! represents the X's
- rijul007
- Legendary Member
- Posts: 588
- Joined: Sun Oct 16, 2011 9:42 am
- Location: New Delhi, India
- Thanked: 130 times
- Followed by:9 members
- GMAT Score:720
I didnt why you did this...sl750 wrote:For ABCABCuser123321 wrote:could you explain say if the letters are ABCABC what the solution might be?sl750 wrote:As per the question, you will agree that there are a total of 8 letters. I club the a's, b's,c's, and d's respectively and treat them as abcd_ _ _ _. Imagine fusing the two a's into just one a.Do the same for the remaining letters. That is how I get four empty slotsrijul007 wrote:i didnt get this part of the solution..sl750 wrote:
This clubbing results in 4 empty slots, we can treat this empty slots as filled by some imaginary letter, say n. In this case, we have 8!/4! ways of arranging the letters
after clubbing all alike letters together, where did the 4 empty slots come from????
I partly was not able to understand the 8!/4! in your solution.
Thanks
user123321
The two A's are joined as one
The two B's are joined as one
The two C's are joined as one
ABC_ _ _
Fill the blanks with X's
ABCXXX
This can be arranged in 6!/3! ways. The 3! represents the X's
-
- Master | Next Rank: 500 Posts
- Posts: 385
- Joined: Fri Sep 23, 2011 9:02 pm
- Thanked: 62 times
- Followed by:6 members
There is still problem in your explanation.sl750 wrote:For ABCABCuser123321 wrote:could you explain say if the letters are ABCABC what the solution might be?sl750 wrote:As per the question, you will agree that there are a total of 8 letters. I club the a's, b's,c's, and d's respectively and treat them as abcd_ _ _ _. Imagine fusing the two a's into just one a.Do the same for the remaining letters. That is how I get four empty slotsrijul007 wrote:i didnt get this part of the solution..sl750 wrote:
This clubbing results in 4 empty slots, we can treat this empty slots as filled by some imaginary letter, say n. In this case, we have 8!/4! ways of arranging the letters
after clubbing all alike letters together, where did the 4 empty slots come from????
I partly was not able to understand the 8!/4! in your solution.
Thanks
user123321
The two A's are joined as one
The two B's are joined as one
The two C's are joined as one
ABC_ _ _
Fill the blanks with X's
ABCXXX
This can be arranged in 6!/3! ways. The 3! represents the X's
If it is so,
for abcabc, based on your explanation, it will be
6!/2^3 - (6!/3! - 3!) = 90 - 120 + 6 = -ve which is wrong
Maybe i am wrong in understanding the concept
user123321
Gotcha !!
I think i figured out the flaw - please correct me if I am wrong.
You say that -
************************************************************
I club the a's, b's,c's, and d's respectively and treat them as abcd_ _ _ _. Imagine fusing the two a's into just one a.Do the same for the remaining letters. That is how I get four empty slots
************************************************************
But you already did this clubbing in 8!/4!.
You avoided counting aabbccdd kind of cases when you divided 8! by 4! (the first term in your solution).
Does that help guys?
I think i figured out the flaw - please correct me if I am wrong.
You say that -
************************************************************
I club the a's, b's,c's, and d's respectively and treat them as abcd_ _ _ _. Imagine fusing the two a's into just one a.Do the same for the remaining letters. That is how I get four empty slots
************************************************************
But you already did this clubbing in 8!/4!.
You avoided counting aabbccdd kind of cases when you divided 8! by 4! (the first term in your solution).
Does that help guys?
-
- Master | Next Rank: 500 Posts
- Posts: 385
- Joined: Fri Sep 23, 2011 9:02 pm
- Thanked: 62 times
- Followed by:6 members
if you club and form four sets, then you will miss combinations aspskharche wrote:Gotcha !!
I think i figured out the flaw - please correct me if I am wrong.
You say that -
************************************************************
I club the a's, b's,c's, and d's respectively and treat them as abcd_ _ _ _. Imagine fusing the two a's into just one a.Do the same for the remaining letters. That is how I get four empty slots
************************************************************
But you already did this clubbing in 8!/4!.
You avoided counting aabbccdd kind of cases when you divided 8! by 4! (the first term in your solution).
Does that help guys?
AAbcdbcd
AABBcdcd
......
which are still valid ones to be accounted for.
I will try the hard way after office :3
I am outta brains for today
user123321
- GmatMathPro
- GMAT Instructor
- Posts: 349
- Joined: Wed Sep 28, 2011 3:38 pm
- Location: Austin, TX
- Thanked: 236 times
- Followed by:54 members
- GMAT Score:770
Notes:
1. In my opinion this is too hard for a real GMAT question.
2. The following explanation is long for the sake of clarity, but the solution doesn't take that long once you see the pattern for how to handle the double-counting.
Here is why:
The overall strategy is to count the number of ways to arrange abcdabcd with no restrictions and then subtract out any ones where adjacent letters match. I think we all agree that the first part is 8!/16 or 2520, so let's focus on counting the cases where adjacent letters match (the part in parentheses above).
First, some sequences will have exactly one pair of adjacent letters such as aabcdbcd some will have two, such as aabbcdcd, some will have 3 daabbccd, and some will have 4, aabbccdd. Let's agree to call a sequence with exactly n adjacent matching pairs Sn. So S1 will mean sequences like aabcdbcd with exactly one adjacent pair matching, up to S4 which will represent cases like aabbccdd where exactly 4 adjacent pairs are matching. The trick is not double counting any of them when you count up how many there are of each.
We can count the ones that have at least one match as follows:
1. Choose one of the four letters a,b,c,d, and merge or "club" the two letters together. If you choose a, it would be like Abbccdd, with capital A representing the grouping of two lowercase a's. We can arrange this 7!/(2!2!2!) ways, with the 2!2!2! there to divide out the repeats. There are 4C1 ways to choose the letter treat as one, so there are 4C1(7!/(2!^3)) ways. This explains the first term within the parentheses. But note that this counts some of the sequences multiple times. For example, when you club the a's, you will count sequences such as aabbcdcd, but you will also count this sequence when you club the b's. Something like daabbccd will get counted three times because it will get counted once each time you club the a's b's and c's. With this logic, the number of time's we're counting the S1,S2,S3,S4 is as follows:
S1=1
S2=2
S3=3
S4=4
but we only want to count each of these once. So we need to subtract.
2. Count how many ways you can have two or more adjacent matching pairs:
By similar logic to above, we can choose the 2 letters in 4C2 ways, and then there will be 6!/2!^2 ways to arrange the letters. so 4C2*6!/2!^2 ways to have at least two adjacent matching pairs. This will count the S3's 3 times each and the S4's 6 times each. To see why, note that each S4 will be counted for any two letters you club together, so each one gets counted 4C2=6 ways total. Likewise, the S3's get counted 3C2=3 ways. Because, for example something like daabbccd gets counted when you club 1. a's and b's, 2. b's and c's, and 3. a's and c's as 1. dABccd 2. daaBCd 3. dAbbCd respectively. So, if we subtract out the ones with at least 2, we now have the following count:
S1=1
S2=1
S3=0
S4=-2
So we're making progress, but now S3's arent counted at all and S4's are being counted negative times. So we need to add some stuff in.
3. Count the number of ways to have at least 3 matches: 4C3*5!/2!. This counts The number of S3's one time and the number of S4's 4 times. Add this number in and we have the following count:
S1=1
S2=1
S3=1
S4=2
Now we're just about done, but we need to subtract the number of ways to have 4 matching pairs which is just 4!, and our count is perfect:
S1=1
S2=1
S3=1
S4=1
So we start with the term from number 1, subtract the term from number 2, add the term from number 3, and subtract the term from number 4 to get the number of unique sequences that have at least one adjacent matching pair. subtract this from 2520 to get 864.
1. In my opinion this is too hard for a real GMAT question.
2. The following explanation is long for the sake of clarity, but the solution doesn't take that long once you see the pattern for how to handle the double-counting.
Here is why:
The overall strategy is to count the number of ways to arrange abcdabcd with no restrictions and then subtract out any ones where adjacent letters match. I think we all agree that the first part is 8!/16 or 2520, so let's focus on counting the cases where adjacent letters match (the part in parentheses above).
First, some sequences will have exactly one pair of adjacent letters such as aabcdbcd some will have two, such as aabbcdcd, some will have 3 daabbccd, and some will have 4, aabbccdd. Let's agree to call a sequence with exactly n adjacent matching pairs Sn. So S1 will mean sequences like aabcdbcd with exactly one adjacent pair matching, up to S4 which will represent cases like aabbccdd where exactly 4 adjacent pairs are matching. The trick is not double counting any of them when you count up how many there are of each.
We can count the ones that have at least one match as follows:
1. Choose one of the four letters a,b,c,d, and merge or "club" the two letters together. If you choose a, it would be like Abbccdd, with capital A representing the grouping of two lowercase a's. We can arrange this 7!/(2!2!2!) ways, with the 2!2!2! there to divide out the repeats. There are 4C1 ways to choose the letter treat as one, so there are 4C1(7!/(2!^3)) ways. This explains the first term within the parentheses. But note that this counts some of the sequences multiple times. For example, when you club the a's, you will count sequences such as aabbcdcd, but you will also count this sequence when you club the b's. Something like daabbccd will get counted three times because it will get counted once each time you club the a's b's and c's. With this logic, the number of time's we're counting the S1,S2,S3,S4 is as follows:
S1=1
S2=2
S3=3
S4=4
but we only want to count each of these once. So we need to subtract.
2. Count how many ways you can have two or more adjacent matching pairs:
By similar logic to above, we can choose the 2 letters in 4C2 ways, and then there will be 6!/2!^2 ways to arrange the letters. so 4C2*6!/2!^2 ways to have at least two adjacent matching pairs. This will count the S3's 3 times each and the S4's 6 times each. To see why, note that each S4 will be counted for any two letters you club together, so each one gets counted 4C2=6 ways total. Likewise, the S3's get counted 3C2=3 ways. Because, for example something like daabbccd gets counted when you club 1. a's and b's, 2. b's and c's, and 3. a's and c's as 1. dABccd 2. daaBCd 3. dAbbCd respectively. So, if we subtract out the ones with at least 2, we now have the following count:
S1=1
S2=1
S3=0
S4=-2
So we're making progress, but now S3's arent counted at all and S4's are being counted negative times. So we need to add some stuff in.
3. Count the number of ways to have at least 3 matches: 4C3*5!/2!. This counts The number of S3's one time and the number of S4's 4 times. Add this number in and we have the following count:
S1=1
S2=1
S3=1
S4=2
Now we're just about done, but we need to subtract the number of ways to have 4 matching pairs which is just 4!, and our count is perfect:
S1=1
S2=1
S3=1
S4=1
So we start with the term from number 1, subtract the term from number 2, add the term from number 3, and subtract the term from number 4 to get the number of unique sequences that have at least one adjacent matching pair. subtract this from 2520 to get 864.
-
- Master | Next Rank: 500 Posts
- Posts: 385
- Joined: Fri Sep 23, 2011 9:02 pm
- Thanked: 62 times
- Followed by:6 members
thanks for the explanation. This surely is a 800+ question, if this kind of question is not touched before gmat.
user123321
user123321
-
- Master | Next Rank: 500 Posts
- Posts: 405
- Joined: Thu Feb 10, 2011 1:44 am
- Thanked: 3 times
- Followed by:1 members
Pete, I went through almost 1/4th of your solution. However, I couldnt understand above treatment. Can you explain ?GmatMathPro wrote:Notes:
But note that this counts some of the sequences multiple times. For example, when you club the a's, you will count sequences such as aabbcdcd, but you will also count this sequence when you club the b's. Something like daabbccd will get counted three times because it will get counted once each time you club the a's b's and c's. With this logic, the number of time's we're counting the S1,S2,S3,S4 is as follows:
S1=1
S2=2
S3=3
S4=4
for S4, if I start with A,
aabbccdd
is different from starting with B,
i.e. bbaaccdd Isnt it?
I dont understand why S4=4....
Thanks in advance!