1. Prove that the set P of legal positions in a chess game satisfies |P| ≤ XXXXXXXXXXHint: Define a one-to-one function from {1, 2, . . . , 13} 64 to P.) 2. How many strings of length n over the...

1. Prove that the set P of legal positions in a chess game satisfies |P| ≤ 1364 . (Hint: Define a one-to-one function from {1, 2, . . . , 13} 64 to P.)

2. How many strings of length n over the alphabet {A, B, . . . , Z, ␣} are there? How many contain exactly 2 “words” (that is, contain exactly one space ␣ that is not in the first or last position)?