Massachusetts Institute of Technology Handout 37 6.042J/18.062J: Mathematics for Computer Science November 3, 2000 Professors Nancy Lynch and Srinivas Devadas

Mini-Quiz 8

1. Write your name:

2. How many strings are there of lowercase letters of length 4 or less?

Solution: Assuming that we are dealing with the English language, there are 26 letters to choose from. We need to figure out how many different strings there are of lenght 0, 1, 2, 3, and 4.

• Strings of length 0: 1 (the empty string)

• Strings of length 1: 26^{1} = 26.

• Strings of length 2: 26^{2} = 676.

• Strings of length 3: 26^{3} = 17576.

• Strings of length 4: 26^{4} = 456976.

• Grand total: 475, 255 different strings, that is, ∑_{i=0}^{4} 26^{i}