STSSTTTSST is a string of letters which does not include the consecutive letters STTS. How many more strings of ten letters that do not include the consecutive letter STTS?

Answer 1

I got 393 records with the STTS sequence. I did this using brute force - I looked at all 2^10 combinations, and then found one way to avoid counting as shown below.

A way to calculate this via the inclusion exclusion method:

If we have a particular 4 character string within 10 characters, there are 7 locations, 1-4 through 7-10, for the 4 characters, and 2^6 possibilities for the other 6 positions. Then, for the double counts, we can either have the strings connected, 1-7, 2-8, 3-9, and 4-10, with 2^3 other values, equals 4*8=32, or have the strings separated, 1-4 and 5-8, 6-9,7-10, 2-5 and 6-9, 7-10, or 3-6,7-10, equals 6, and 2^2 = 4 others for 6*4 = 24, and one 10 character sequence that had the pattern 3 times. STTSTTSTTS.

448 - (32 + 24) + 1 = 393.

Then, 1024 - 393 = 631

This means 631 - 1 = 630 others.