Question

# Suppose the alphabet consists of just {a,b,c,d,e}. Consider strings of letters that show repetitions. How many 4-letter strings are there that do not contain “aa"?

Probability and combinatorics
Suppose the alphabet consists of just {a,b,c,d,e}. Consider strings of letters that show repetitions. How many 4-letter strings are there that do not contain “aa"?

2021-01-20

Fundamental counting principle: If the first event could occur in m ways and the second event could occur in n ways, then the number of ways that the two events could occur in sequence is $$m \cdot n$$
Solution Number of 4-letter strings
Each letter in the string has 5 possible values (a,b,c,d).
First letter: 5 ways
Second letter: 5 ways
Third letter: 5 ways
Fourth letter: 5 ways
Use the fundamental counting principle: $$\displaystyle{5}\cdot{5}\cdot{5}\cdot{5}={5}^{{4}}={625}$$
Number of 4-letter strings containing "aa" There are three possible positions for the string aa (that is, the string is either of the form aaxx, xaax or xxaa.
Each of the letters x in the string has 5 possible values (a,b,c,d,e).
Place aa: 3 ways First letter: 5 ways Second letter: 5 ways
Use the fundamental counting principle: $$\displaystyle{3}\cdot{5}\cdot{5}={75}$$
Number of 4-letter strings not containing "aa" There are 625 4-letter strings and there are 75 4-letter strings containing "aa", thus there are then $$625-75=550$$ 4-letter strings not containing "aa"