[This is a follow-up post to AAAAA.]

In the previous post, I didn't come up with a nice formula. However, a friend recently brought up a similar problem that they solved (with a formula), and it generated some interesting discussion.

How many 5-character bitstrings contain 000?

Essentially, this version only allows two characters, and we are only searching for strings that contain 000.

The Solution

It's actually easier to create strings that don't contain 000, and then to subtract that from the total number of 5-character bitstrings. We can create these strings using a recursive algorithm.

Theorem:

Given a string without 000, we can create a longer string without 000 by appending any of 1, 10, and 100, any number of times.

I'm not a math major so this is true by inspection.

Now we can build up valid strings by extending base cases with these appendages.

There are 2 strings of length 1 without 000: 0 and 1.
There are 4 strings of length 2 without 000: 00, 01, 10, and 11.
There are 7 strings of length 3 without 000: 001, 010, 011, 100, 101, 110, 111.

Now we can create a string of length 4 without 000 by adding 100 to the strings of length 1, adding 10 to the strings of length 2, and 1 to the strings of length 3.¹ Letting f(N) denote the number of strings of length N without 000, we can thus say that f(4) = f(3) + f(2) + f(1) = 13. In fact, this is true for all N > 3: f(N) = f(N - 1) + f(N - 2) + f(N - 3).

Thus, f(5) = 13 + 7 + 4 = 24, so there are 24 strings of length 5 without 000. Since there are 2^5 = 32 total bitstrings of length 5, that means there are 32 - 24 = 8 of them that contain 000.

00000, 00001, 00010, 00011, 01000, 10000, 11000, 10001

Solving the original problem

Now, back to the original problem in AAAAA. First, we'll look at the possible ways we can make a string without AAA.

The possible extensions we can append are now B, C, BA, CA, BAA and CAA (any number of times).

There are 3 strings of length 1 without AAA: A, B and C.
There are 9 strings of length 2 without AAA: (all combinations)
There are 26 strings of length 3 without AAA: (all combinations) - AAA

We can create a string of length 4 without AAA by adding BAA or CAA to the strings of length 1, BA or CA to the strings of length 2, or B or C to the strings of length 3. Thus, letting g(N) denote the number of strings of length N without AAA, g(N) = 2*(g(N-1) + g(N-2) + g(N-3)).

Therefore, g(4) = 2*(3 + 9 + 26) = 76, and g(5) = 2*(76 + 26 + 9) = 222. Since there are 3^5 = 243 total strings of length 5, that means there are 243 - 222 = 21 strings with AAA.

We can then apply the same trick we used at the end to show that there must also be 21 strings with CCC. Since these strings are mutually exclusive with the ones that contain AAA, so we get the same answer: 42 strings with AAA or CCC.

Further Extensions?

We can easily extend the number of characters allowed in our string: if we are allowed X characters, then we get X strings of length 1, X^2 strings of length 2, and X^3 - 1 strings of length 3 that don't contain AAA. The recursive formula would have a multiplicative factor of X - 1.

If we wanted to include more valid strings (of the same format as AAA), then we could re-apply the trick at the end as long as they were mutually exclusive. If there were some overlaps, then we'd need to start going into inclusiion-exclusion principle and that's a bit gross.

If we wanted to make it the string longer, we'd also need to delve into inclusion-exclusion, since AAACCC and CCCAAA are now counted twice. If the valid strings became longer to prevent this (e.g. strings of length 10 with AAAAAA or CCCCCC), that would be easy to extend.

If we wanted to include more valid strings of a different format, such as ABA, I feel like this would be significantly harder and don't have a good grasp of how to extend this strategy. Maybe in a third post?