Strings with Paired Letters
Combinatorics · 29th PMO Qualifying Stage
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$