17. Aaron has to choose a three-digit code for his bike lock. The digits can be chosen from 1 to 9. To help him remember them, Aaron chooses three different digits in increasing order, for example 278.
How many such codes can be chosen?
A 779
B 504
C 168
D 84
E 9
Solution
D
Method 1
We count the number of ways in which Aaron can choose three digits in increasing order.
We first consider the case when the first digit Aaron chooses is 1 .
If the second digit he chooses is 2 , he has 7 remaining choices for the third digit, namely any of the digits from 3 to 9 , inclusive. If the second digit Aaron chooses is 3 , he has 6 remaining choices for the third digit, namely any of the digits from 4 to 9 , inclusive, and so on. Finally, we see that if the second digit Aaron chooses is 8 , he has just one choice, 9 , for the third digit. He cannot choose 9 as the second digit, as that would leave no choice for the third digit.
Therefore, the number of different codes with first digit 1 that Aaron can choose is $7+6+5+$ $4+3+2+1$, that is, 28 .
Similarly, the number of different codes with first digit 2 , that Aaron can choose is $6+5+4+3+2+1$, that is, 21 .

And so on, until finally, if the first digit Aaron chooses is 7, he has just one choice of code, namely 789 .

Therefore the total number of codes that Aaron can choose is $28+21+15+10+6+3+1$, that is, 84 .

METHOD 2
This method assumes some previous knowledge of binomial coefficients (see the note below).
Given any three different non-zero digits, there is only one way in which Aaron can use them to make a code, as he wishes to arrange them in increasing order.
Therefore the number of different codes that Aaron can choose is the number of different ways in which Aaron can choose 3 digits from the 9 non-zero digits. This number, ' 9 choose 3 ', is written $\binom{9}{3}$ or sometimes ${ }_{9} C_{3}$ or ${ }^{9} C_{3}$. The number $\binom{9}{3}$ is the coefficient of $x^{3}$ in the expansion of $(1+x)^{9}$. It is what is called a binomial coefficient.
The general formula for the binomial coefficients is given by $\binom{n}{r}=\frac{n!}{r!(n-r)!}$. Therefore the number of different codes that Aaron can choose is
$$
\binom{9}{3}=\frac{9!}{3!6!}=\frac{9 \times 8 \times 7}{3 \times 2 \times 1}=84
$$