There are 9 possible destination floors, namely floors 2 through 10. Since the three people make their choices independently, it is natural to count ordered triples of desired floors. The total number of such triples is \[ 9^3. \]

For exactly three consecutive buttons to be pressed, the three desired floors must be distinct, and the set of floors must look like \[ \{j,j+1,j+2\}, \quad with \ j=2,\cdots , 8. \] The smallest possible starting floor is 2 and the largest possible starting floor is 8, so there are 7 possible consecutive triples of floors. Once such a triple of floors has been chosen, the three people may be assigned to those floors in \(3!\) different orders. Thus the number of favorable ordered triples is \[ 7\cdot 3!. \] Hence the desired probability is \[ \frac {7\cdot 3!}{9^3} = \frac {42}{729} = \frac {14}{243}. \]

(a) Fred is choosing restaurants for five ordered nights, and in this part no restaurant may be repeated. There are 10 choices for Monday, then 9 choices for Tuesday, then 8 choices for Wednesday, then 7 choices for Thursday, and finally 6 choices for Friday. Therefore the number of possible dinner schedules is \[ 10\cdot 9\cdot 8\cdot 7\cdot 6 = 30240. \]

(b) Now Fred may return to a restaurant later in the week, but he may not eat at the same restaurant on two consecutive nights. Monday can be chosen in 10 ways. On each of the remaining four nights, exactly one restaurant is forbidden, namely the restaurant from the previous night. Thus each of Tuesday through Friday has 9 available choices. The number of possible schedules is \[ 10\cdot 9^4 = 65610. \]

(a) Consider a group of \(n\) people, and imagine forming a committee from this group. One way to make the committee is to decide, separately for each person, whether that person is included. Since each person has two possibilities, included or not included, the number of committees is \(2^n\).

The same committees can also be counted by their size. If the committee has \(k\) members, then it can be chosen in \(\binom {n}{k}\) ways. Since the committee may have any size from 0 to \(n\), the total number of committees is \[ \sum _{k=0}^{n}\binom {n}{k}. \] These two expressions count the same set of committees, and so \[ \sum _{k=0}^{n}\binom {n}{k}=2^n. \]

(b) Suppose there are two groups, each containing \(n\) people. We want to form a committee of size \(n\) from the combined group of \(2n\) people. If we ignore the two-group structure, this can be done in \[ \binom {2n}{n} \] ways.

Now count the same committees by the number \(k\) chosen from the first group. If \(k\) people are chosen from the first group, then \(n-k\) people must be chosen from the second group. This gives \[ \binom {n}{k}\binom {n}{n-k} \] committees. Since \(\binom {n}{n-k}=\binom {n}{k}\), the number with this value of \(k\) is \(\binom {n}{k}^2\). Summing over all possible values of \(k\) gives \[ \sum _{k=0}^{n}\binom {n}{k}^2. \] Both counts describe the same committees, and hence

(c) Again take two groups of \(n\) people each. We form a committee of size \(n\), and then choose a chair from the first group among those who are on the committee.

Count first according to the number \(k\) of committee members who come from the first group. The first group contributes \(k\) people in \(\binom {n}{k}\) ways, and the second group contributes the remaining \(n-k\) people in \(\binom {n}{n-k}=\binom {n}{k}\) ways. Once the committee has been chosen, there are \(k\) choices for the chair, since the chair must be one of the selected members from the first group. Thus this count gives \[ \sum _{k=1}^{n} k\binom {n}{k}^2. \]

There is a shorter count of the same chaired committees. Choose the chair first from the first group, which gives \(n\) choices. After the chair is chosen, we still need \(n-1\) additional committee members, and they may be chosen from the remaining \(2n-1\) people. This gives \[ n\binom {2n-1}{n-1}. \] The two counts are counting exactly the same objects, so

It is easiest to count the complement. Treat the 6 robberies as distinguishable, for instance by the order in which they occurred. Each robbery may occur in any of the 6 districts, so there are \[ 6^6 \] equally likely assignments.

The complement of the event in the problem is the event that no district had more than one robbery. Since there are 6 robberies and 6 districts, this means that each district had exactly one robbery. The number of assignments with exactly one robbery in each district is \(6!\), since the robberies must be matched one-to-one with the districts.

Therefore \[ \mathbb {P}(\text {no district had more than one robbery}) = \frac {6!}{6^6}. \] It follows that \[ \mathbb {P}(\text {some district had more than one robbery}) = 1-\frac {6!}{6^6} = 1-\frac {720}{46656} = \frac {319}{324}. \]

(a) There are \(2^n\) players at the beginning. After each round, half of the players remain. Thus the numbers of players remaining after successive rounds are \[ 2^n,\;2^{n-1},\;2^{n-2},\ldots ,2,1. \] It takes \(n\) rounds to reduce the field from \(2^n\) players to one champion.

(b) In the first round, \(2^{n-1}\) games are played. In the second round, \(2^{n-2}\) games are played. Continuing in this way, the final round has one game. The total number of games is therefore \[ 2^{n-1}+2^{n-2}+\cdots +2+1 = 2^n-1. \]

(c) There is also a very direct way to see the same number. Every game eliminates exactly one player. To finish with one champion, the tournament must eliminate all the other players. Since there are \(2^n\) players at the start, the number of eliminated players is \[ 2^n-1. \] Thus the number of games is \(2^n-1\).

There are \(6^n\) equally likely sequences of \(n\) die rolls. We want the probability that at least one of the six faces is absent.

Let \(A_j\) be the event that face \(j\) never appears. The desired event is \[ A_1\cup A_2\cup \cdots \cup A_6. \] We count this union by inclusion-exclusion. If a particular set of \(k\) faces is missing, then each roll must be one of the remaining \(6-k\) faces, so there are \[ (6-k)^n \] sequences. There are \(\binom {6}{k}\) ways to choose the missing faces. Hence, using the inclusion-exclusion principle, we have \[ \mathbb {P}(A_1\cup \cdots \cup A_6) = \frac {1}{6^n} \sum _{k=1}^{6} (-1)^{k+1}\binom {6}{k}(6-k)^n. \] Writing the expression out gives

There are \(62\) legal characters in total, namely \(26\) lowercase letters, \(26\) uppercase letters, and \(10\) digits.

(a) Count all 8-character passwords and subtract those with no lowercase letters. There are \(62^8\) passwords in total. If no lowercase letter appears, each character must be chosen from the \(26\) uppercase letters and the \(10\) digits, giving \(36^8\) such passwords. Therefore the number with at least one lowercase letter is

(b) Now the password must contain at least one lowercase letter and at least one uppercase letter. Start with all \(62^8\) passwords. Subtract the passwords with no lowercase letters and the passwords with no uppercase letters. Each of these two forbidden classes has \(36^8\) passwords. Passwords with neither lowercase nor uppercase letters use only digits, and there are \(10^8\) of them. These digit-only passwords have been subtracted twice, so they must be added back once. The desired number is

(c) Finally, require all three types of characters to appear. Again begin with \(62^8\) total passwords. Subtract the passwords missing lowercase letters, missing uppercase letters, or missing digits. These counts are \(36^8\), \(36^8\), and \(52^8\), respectively.

Now add back the passwords in which two of the three character types are missing. If lowercase and uppercase letters are both missing, only digits remain, giving \(10^8\) passwords. If lowercase letters and digits are both missing, only uppercase letters remain, giving \(26^8\) passwords. If uppercase letters and digits are both missing, only lowercase letters remain, again giving \(26^8\) passwords. Since a password cannot be missing all three character types and still have length 8, there is no further term. Thus the number of valid passwords is