Count the number of strings of length 9 over the alphabet {a, b, c} subject to e
ID: 3365294 • Letter: C
Question
Count the number of strings of length 9 over the alphabet {a, b, c} subject to each of the following restrictions.
(a)
The first or the last character is a.
(b)
The string contains at least 8 consecutive a's.
(c)
The string contains at least 8 consecutive identical characters.
(d)
The first character is the same as the last character, or the last character is a, or the first character is a.
(e)
The string contains at least seven consecutive a's.
(f)
The characters in the string "abababa" appear consecutively somewhere in the 9-character string. (So "ccabababa" would be such a 9-character string, but "cababcaba" would not.)
(g)
The string has exactly 2 a's or exactly 3 b's.
(h)
The string has exactly 2 a's or exactly 2 b's or exactly 2 c's
Explanation / Answer
(a)
The first or the last character is a.
Since the first letter is a, we only need to worry about the remaining 8 letters. Each letter has 2 choices. There can be 28 = 256 strings.
(b)
The string contains at least 8 consecutive a's.
If all 9 are a's, there is only one such string. If there are exactly 8 consecutive a's, they can be at the beginning or at the end, thus giving two options.
Total number of strings = 3.
(c)
The string contains at least 8 consecutive identical characters.
The answer to this question is based on the answer for (b). For the letter a, we had 3 strings. Since there are 3 different letters a,b and c, total number of strings = 3 * 3 = 9.
(d)
The first character is the same as the last character, or the last character is a, or the first character is a.
If the first character and the last character are both a's, we need to check for the remaining 7 letters. There can be 27 = 128 strings.
This is the same for b's and c's.
In all we have 128*3 = 384 strings.
If only the first letter is a, the last letter could be b or c. There are again 27 options for the letters in between. Thus there are 2 * 27 = 256 strings. Similarly there are 256 strings such that only the last letter is a.
In all the number of strings = 384 + 256 + 256 = 896.