0
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Isn't there exactly $1$ strictly decreasing number with $10$ digits?, namely $9876543210$? $\endgroup$ Commented Oct 17, 2017 at 21:03
  • $\begingroup$ Yes indeed but I mentioned the total number of strictly decreasing numbers. $\endgroup$ Commented Nov 8, 2017 at 12:21
  • $\begingroup$ oeis.org/A035927 (“Number of distinct n-digit numbers up to permutations of digits.”) $\endgroup$ Commented Feb 4, 2018 at 0:00
  • $\begingroup$ @JustvanderVeeken you may better accept the other answer it's just a simplified form of mine. $\endgroup$ Commented Feb 6, 2018 at 0:25

2 Answers 2

Reset to default
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ you chose addition sign to represent runs of latter digit, genuine! how could this trick skip my imagination! $\endgroup$ Commented Feb 4, 2018 at 0:08
1
$\begingroup$
  • Well i guess this solution is less tricky then the other:

On the basis that choosing random $k$ digits are constrained to be rowed in one specific order. Let's denote:

$C_i$ how many ways of choosing $i$ from $10$ digits.

Using stars&bars as a mean to repartition sets of distinct repetitive streams of digits. Let's denote St(i) the configurations of $i$ bars amongst $10$ stars.

$F_i$ the number of possibilities of forming decreasing numbers with exactly $i$ digits.

$F_1=C(1)*St(0)=\binom{10}{1}*\binom{9}{0}$

$F_2=C(2)*St(1)=\binom{10}{2}*\binom{9}{1}$

$F_3=C(3)*St(2)=\binom{10}{3}*\binom{9}{2}$

...

$F_10=\binom{10}{10}*\binom{9}{9}=1$ obviously.

$$S=\sum{F_i}=\sum{\binom{10}{i}*\binom{9}{i-1}}=\sum_{i=1}{\binom{10}{i}^2*\frac{i}{10}}$$

Since runs of 0's are not counted, solution is S-1=92377 .

$\endgroup$
2
  • $\begingroup$ In your explanation, you wrote $F_2$ when you meant $F_1$ in your list of cases. Also, you should explain that $\binom{10}{i}$ is the way of selecting $i$ of the $10$ digits to be included in the number and $\binom{9}{i - i}$ is the number of ways of choosing which $i - 1$ of the $9$ possible transition points are used to jump from a smaller digit to the next larger one. That said, it is a nice approach. $\endgroup$ Commented Feb 4, 2018 at 0:15
  • $\begingroup$ done; it's amazing how coincidently happened that this sum is just a deployment of Vandermonde's identity you stated above! $\endgroup$ Commented Feb 4, 2018 at 0:29

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.