A friend of mine asked this question about 6 years ago in a shared server:
Let's say a four character code is generated and the characters available are A, B, and C. Is there a simple way to calculate the number of permutations where either AAA or CCC show up? So CCAC would be illegal and BCCC would be legal.
What about a five-character code containing AAA or CCC?
I'm not particularly good at math, so I wasn't able to come up with a nice formula. But I still got the answer, which is the important part, right?
1. The 4-Character Code
We can first imagine AAA / CCC to be one "block", such that the code is yXXX or XXXy. Then the number of combinations seems to be 2 * 2 * 3 = 12.
2 is either X = A or C.
3 is either y = A, B, or C.
2 is either yXXX or XXXy.
Since we can have any combination of the above options, we need to multiply these together.
But this counts both AAAA and CCCC twice; there are only 10 actual codes. If we think of this case, we can simply subtract the duplicates to get the answer, but this is harder for larger codes.
2. The 5-Character Code
In the case of 5-letter strings, we can split it into the cases of "3 A's", "4 A's" and "5 A's".
First, there are 3 * 2 * 2 = 12 codes with 3 A's.
3 is _ AAA _ , _ _ AAA and AAA _ _.
2 is for the first slot being B or C.
2 is for the second slot being B or C.
BBAAA BAAAB AAABB
BCAAA BAAAC AAABC
CBAAA CAAAB AAACB
CCAAA CAAAC AAACC (proof of the 12 strings)
Next, there are 4 + 4 = 8 codes with 4 A's.
One group of such codes is a 4-group _ AAAA. There are 2 * 2 = 4 codes.
2 is for _ AAAA and AAAA _.
2 is for the slot being B or C.
The second group of codes with 4 A's is a 3-group and an isolated A. There are 2 * 2 = 4 codes.
2 is for A _ AAA and AAA _ A.
2 is for the slot being B or C.
Finally, for 5 A's there's only 1 possibility. AAAAA
Therefore, there are 12 + 8 + 1 = 21 codes containing AAA. We can use the above arguments to show that there are also 21 codes containing CCC. Since AAA and CCC cannot be in the same string (i.e. they are mutually exclusive), the combinations can simply be added up for 21 + 21 = 42 codes with either AAA or CCC.