HMMT-Feb 2017 comb, Problem 5

Kelvin the Frog likes numbers whose digits strictly decrease, but numbers that violate this condition in at most one place are good enough. In other words, if $d_{i}$ denotes the $i$ th digit, then $d_{i} \leq d_{i+1}$ for at most one value of $i$. For example, Kelvin likes the numbers 43210, 132, and 3, but not the numbers 1337 and 123. How many 5-digit numbers does Kelvin like?

Solution: Suppose first that no digit violates the constraint; i.e. the digits are in strictly decreasing order. There are $\left(\begin{array}{c}10 \\ 5\end{array}\right)$ ways to choose the digits of the number, and each set of digits can be arranged in exactly one way, so there are $\left(\begin{array}{c}10 \\ 5\end{array}\right)$ such numbers. We now perform casework on which digit violates the constraint. If it is the final digit, the first four digits must be arranged in decreasing order, which there are $\left(\begin{array}{c}10 \\ 4\end{array}\right)$ ways to do. The final digit can then be any digit, but we have overcounted the ones in which the number is in fully decreasing order (this can happen, for example, if the first 4 digits we chose were $5,4,3$, and 2 - a last digit of 1 was already counted in the first case). Therefore, there are $\left(\begin{array}{c}10 \\ 4\end{array}\right)\left(\begin{array}{c}10 \\ 1\end{array}\right)-252$ new numbers in this case. If the offending digit is second from the right, the first 3 digits must be decreasing, as must the last 2 digits. There are $\left(\begin{array}{c}10 \\ 3\end{array}\right)\left(\begin{array}{c}10 \\ 2\end{array}\right)$ ways to do this. As before, we overcount the case where the second digit from the right is not actually an offender, so we again overcount the case where all 5 digits decrease. Hence there are $\left(\begin{array}{c}10 \\ 3\end{array}\right)\left(\begin{array}{c}10 \\ 2\end{array}\right)-252$ new numbers in this case. The case where the third digit is the offender is identical to the previous case, so there are another $\left(\begin{array}{c}10 \\ 3\end{array}\right)\left(\begin{array}{c}10 \\ 2\end{array}\right)-252$ numbers to account for. The final case is when the second digit is the offending digit, in which case there are $\left(\begin{array}{c}10 \\ 4\end{array}\right)$ ways to choose the final 4 digits, but only 9 ways to choose the opening digit (as 0 cannot be a leading digit). Accounting for the usual overcounting, our final answer is \[ 252+\left[\left(\begin{array}{c} 10 \\ 4 \end{array}\right)\left(\begin{array}{c} 10 \\ 1 \end{array}\right)-252\right]+2\left[\left(\begin{array}{c} 10 \\ 3 \end{array}\right)\left(\begin{array}{c} 10 \\ 2 \end{array}\right)-252\right]+\left[\left(\begin{array}{c} 10 \\ 4 \end{array}\right) \cdot 9-252\right] \] which is easily calculated as 14034 . $\fbox{14034}$.

Answer: 14034