4
$\begingroup$

Here's the problem statement

In how many ways can we arrange $5$ $A$s, $7$ $B$s and $4$ $C$s into a $16$-letter word such that there are atleast three $CA$ pairs occurring in a word

The solution mentioned proceeds to calculate the number of words containing exactly four $CA$ pairs and then the number of words containing exactly three $CA$ pairs (which it does by calculating number of ways of inserting $2$ $A$s in $11$ out of $12$ gaps (blank group allowed) of a string containing $3$ $CA$ pairs, $7$ $B$s and one $C$. I agree with this solution, however I cannot figure out why my method fails.

I think calculating number of words that contain $3$ $CA$s pairs and their permutations should suffice, because their permutations do include the cases where another $CA$ pair is formed (so that accounts for $4$ $CA$ pairs formed) and when $C$ does not precedes any of the $A$s, it accounts for the words containing $3$ $CA$ pairs. So, number of words should be $$\frac{13!}{7! \times 3! \times 2!} =102960$$ whereas, according to solution 1 $$\frac{12!}{7! \times 4!} + \frac{11!}{7! \times 3!} \times {12\choose10} = 3960 + 87120 = 91080$$ can someone point out my mistake

$\endgroup$
10
  • 1
    $\begingroup$ Beware overcounting. For example, consider the sequence that starts CACACACA.... If you are counting any string with at least $3$ CA pairs, then you will count the above prefix $(4)$ times, instead of just once. Your approach, with some gymnastics, can be made to work. However, it is not advisable. The standard approach is to consider exactly $3$ pairs, and exactly $4$ pairs, separately. This avoids the whole overcounting issue. $\endgroup$
    – user2661923
    Commented Feb 8, 2022 at 7:48
  • $\begingroup$ Actually, I did not read your posting that closely. Therefore, I may have misinterpreted your work. However, when I got wind of your approach, and then glanced at your math, I asked myself: How is he preventing overcounting? $\endgroup$
    – user2661923
    Commented Feb 8, 2022 at 7:49
  • $\begingroup$ hmm, I understand, so subtracting $3$ times the number of words containing $4$ $CA$ pairs should fix this. Thanks! $\endgroup$
    – AlastorMoody
    Commented Feb 8, 2022 at 7:58
  • $\begingroup$ That would be my guess. Also, it would certainly be worth exploring, to see if you then get the purported right answer. However, going forward for problems like this, the choice of the best strategy can be very tricky. The Direct Approach (which you and the standard answer apparently used different varieties of), recursion, and Inclusion-Exclusion. It would be very educational for you to embrace the methodology of the standard answer, achieve that answer with your approach, and then rinse and repeat with Inclusion-Exclusion. Then, rinse and repeat with recursion. $\endgroup$
    – user2661923
    Commented Feb 8, 2022 at 8:01
  • $\begingroup$ so, subtracting $3$ times works as $102960 - 3\times 3960$ $=$ $91080$. My guess for the inclusion-exclusion method would be subtracting number of words containing $0,1$ and $2$ $CA$ pairs from total number of words (is this the method you're stating above?): bit.ly/3owOY7k (calculations). Still, how do you solve this using recursions? $\endgroup$
    – AlastorMoody
    Commented Feb 8, 2022 at 8:46

1 Answer 1

Reset to default
2
$\begingroup$

Your approach overcounts four-pair cases, as noted in comments, and fixing it leads to the inclusion/exclusion approach. Forming four CA pairs leaves one As and seven Bs for an initial total of $$\binom{12}{4,1,7}=3960$$ We counted the four-pair cases four times, for there are four CA pairs and we must pick one to split to get a three-pair case, and we only want to count them once, so we subtract three times this number from $102960$ to get the correct answer of $91080$.

This problem is simple enough to be solved additively and subtractively (through inclusion/exclusion) that recursion is totally unsuitable.

$\endgroup$
1
  • $\begingroup$ Agreed that recursion is the wrong approach for this problem. However, this is a good problem to learn recursion on, to see how different methods reach the same answer. This potentially puts an additional Combinatorics weapon in the OP's (i.e. original poster's) arsenal. $\endgroup$
    – user2661923
    Commented Feb 8, 2022 at 10:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .