What is the flaw in this approach? Conceptually, is this approach overcounting o

Question

What is the flaw in this approach? Conceptually, is this approach overcounting or
undercounting?

Problem: How many permutations of AABBCCDDEEFFGG do not contain any consecutive
letters.
Solution: let f(n) be the solution for n pairs of matching letters. We can choose the first letter in
the permutation to be any one of the n letters. Then, we can select any of 2n-2 slots for the
second copy of that letter - anything BUT the second slot. What remains is to recursively fill in
2(n-1) slots with the remaining letters, which can be done in f(n-1) ways. Thus, we've derived the
equation:
() = (2 2)( 1)
We can quickly note that f(2) = 2 since the two valid arrangements of AABB are ABAB and
BABA.
Now, we can plug in for n = 7 to solve the given query:
(3) = 3 × 4 × (2) = 12 × 2 = 24
(4) = 4 × 6 × (3) = 24 × 24 = 576
(5) = 5 × 8 × (4) = 40 × 576 = 23040
(6) = 6 × 10 × (5) = 60 × 23040 = 1382400
(7) = 7 × 12 × (6) = 84 × 1382400 = 116121600
Thus, there are 116,121,600 permutations of AABBCCDDEEFFGG without 2 of the same letter
appearing consecutively.

Explanation / Answer

The calculation is flawed. Once a letter is chosen, then the other occurence of that letter does not follow the usual pattern.

For e.g let us say the first letter in a permutation is fixed to be A. Then the other A does not have any more replicates.

The solution assumes, that we recursively allow 2(n-1) slots for the remaining letters instead of 2n-1 as there will be a repeating letter. But there won't be any repeating letter for the second A.

Therefore the solution is an undercounting approach.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.