XXIII OM - I - Problem 9

How many natural numbers less than $ 10^n $ have a decimal representation whose digits form a non-decreasing sequence?
Let $ A $ be the set of natural numbers less than $ 10^n $, having a decimal representation whose digits form a non-decreasing sequence. Let's agree to place as many zeros at the beginning of the representation of each number in the set $ A $ so that the representation of this number has $ n $ digits in total.
Let $ B $ be the set of natural numbers less than $ 10^{n+10} $ having a decimal representation (with zeros at the beginning), whose digits form a non-decreasing sequence and in which each of the ten digits appears.
To each representation of a number in the set $ A $, we assign a representation in which each digit $ 0, 1, 2, \ldots, 9 $ appears one more time and the digits form a non-decreasing sequence. This assignment defines a mapping $ f $ from the set $ A $ to the set $ B $. At the same time, the number $ x = \underbrace{00\ldots 0}_{n+1} 12\ldots 9 $ belonging to $ B $ does not correspond to any number in the set $ A $.
The mapping $ f \colon A \to B - \{x\} $ is bijective; the inverse mapping involves deleting one digit of each kind in the representation of a number in the set $ B - \{x\} $. Therefore, the number of elements in the set $ B $ is one greater than the number of elements in the set $ A $.
The representation of any number in the set $ B $ consists of $ n + 10 $ digits. There are thus $ n + 9 $ places between consecutive digits. Let's agree to place a dash between digits in such a representation if they are different. There are $ 9 $ such dashes, since there are $ 10 $ different digits and each of them appears in the representation of a number in the set $ B $.
To determine the number of elements in the set $ B $, note that the representation of a number in the set $ B $ is uniquely determined by any placement of $ 9 $ dashes in $ n+9 $ places. Therefore, the set $ B $ has $ \displaystyle \binom{n+9}{9} $ elements, and the set $ A $ has $ \displaystyle \binom{n+9}{9}-1 $ elements.