Suppose we are looking a strings of letters with only the letters
"A" and "B". The first few would be A, B, AA, AB, BA, BB, AAA, AAB,
ABA, ABB, BAA, BAB, BBA, BBB, and so on. Since each string can be
made longer by adding an A or a B the number of strings with some
number n of characters is twice as many as the number of strings with
n1 characters. The number of strings of length 1 is 2, the number of
strings of length 2 is 4, the number of strings of length 3 is 8, and
so on.
Suppose that we want to count the number of strings that never have
two B's next to one another? How many strings are there of each
length? The first few strings like this are: A, B, AA, AB, BA, AAA,
AAB, ABA, BAA, BAB, AAAA, and so on. Advanced students may want to
try to find a formula for the number of strings with n characters to
get 25 points; anyone may explain how the numbers are generated to get
15 points.
Send your answer to mathstat@uoguelph.ca
Back to Problems
