I've come across this problem and I cannot seem to find the answer.
Let us call a number decreasing if its digits form a decreasing sequence (each digit is not larger than the preceding one). This means for example that 1, 22221111 and 888333300000 are decreasing numbers.
I know there exist infinitely many decreasing numbers as it does not many how many for example numbers 2 you take its digits still form a decreasing sequence and therefore a decreasing number. The problem I ran into is when we want to calculate how many decreasing numbers of ten digits there are.
I understand the total number of strictly decreasing numbers(so each digit is less than the preceding one) is equal to 1275 as that just is the sum of 10c1 , 10c2 up till 10c10. However I don't understand how to calculate the other number of possibilities we have to add to this number in order to account for the decreasing numbers.
I hope I explained my problem well enough, if not feel free to ask me to clearify some things.
Best Answer
Let $x_k$, $0 \leq k \leq 9$, be the number of times the digit $k$ appears in a ten-digit number with non-increasing digits. Then $$x_0 + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 = 10 \tag{1}$$ Since the digits are non-increasing, choosing how many times each digit appears completely determines the number. For instance, the solution $$x_0 = 1, x_1 = 2, x_3 = 0, x_4 = 1, x_5 = 3, x_6 = 1, x_7 = 2, x_8 = 0, x_9 = 0$$ corresponds to the ten-digit number $7765554110$. Therefore, the number of non-increasing ten-digit numbers is the number of solutions of equation 1 in the nonnegative integers, except that we have to exclude the solution $$x_0 = 10, x_1 = x_2 = x_3 = x_4 = x_5 = x_6 = x_7 = x_8 = x_9 = 0$$ since the leading digit cannot be zero. A particular solution of equation 1 corresponds to the placement of nine addition signs in a row of $10$ ones. For instance, in the example $7765554110$, the solution corresponds to the following string of ones and addition signs. $$1 + 1 1 + + 1 + 1 1 1 + 1 + 1 1 + +$$ Hence, the number of solutions of equation 1 in the nonnegative integers is $$\binom{10 + 9}{9} = \binom{19}{9}$$ since we must choose which nine of the nineteen positions required for ten ones and nine addition signs will be filled with addition signs. Since the leading digit cannot be zero, we must eliminate the solution mentioned above. Therefore, there are $$\binom{19}{9} - 1$$ ten-digit positive integers with non-increasing digits.