← All problems

Strings with Paired Letters

Combinatorics · 29th PMO Qualifying Stage 1375
A string is called good if every character is either A or B, and every occurrence of A is immediately adjacent to at least one other A. Thus, BBBB and BAAB are good strings of length 4, but not AABA. How many good strings of length 9 are there?
A$114$ B$128$ C$135$ D$149$