Given an integer $N$, Find how many strings of length $N$ are possible, consisting only of characters A, B, C with each character occuring at least once.

Solution: Lets place A,B,C (at least once) in the first three places. They can be arranged in $3!=6$ ways. Now the remaining $N-3$ places can be arranged in $3^{N-3}$ ways [Since any of A,B,C can come in $N-3$ places]. Again, taking the first three places A,B,C as one, we can permute the string of length $N-2$ in $(N-2)!$ ways. So there would be a total of $$6 \times 3^{N-3} \times (N-2)! $$strings possible. What am I doing wrong here?


You're doing three things wrong.

The first is that you're constraining the required occurrences of the three characters to be consecutive, which leads to undercounting, since the string might be e.g. all A's except for a B and a C that are far apart.

The second is that you're counting every string multiple times, once for each consecutive string of three different characters in it, leading to overcounting.

The third is a massive overcount in that you're permuting all the $N-3$ letters even though you've already counted all possible choices for them, and the permutations are generating all those choices over again.

A correct solution would be, using inclusion-exclusion: There are $3^N$ strings in all. From these we have to subtract $3\cdot2^N$ that contain only two of the letters ($3$ because there are $3$ pairs of letters). But now to properly count the $3\cdot1^N=3$ sequences that contain only one letter, which we've counted once and subtracted twice, we have to add them back in, for a total of $3^N-3\cdot2^N+3$.

| cite | improve this answer | |
  • $\begingroup$ Yes, you're right joriki. Thanks, makes sense now. $\endgroup$ – Rain Sep 10 '15 at 8:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.