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$
  • 1
    $\begingroup$ Isn't there exactly $1$ strictly decreasing number with $10$ digits?, namely $9876543210$? $\endgroup$ – Bram28 Oct 17 '17 at 21:03
  • $\begingroup$ Yes indeed but I mentioned the total number of strictly decreasing numbers. $\endgroup$ – Just van der Veeken Nov 8 '17 at 12:21
  • $\begingroup$ oeis.org/A035927 (“Number of distinct n-digit numbers up to permutations of digits.”) $\endgroup$ – Steve Kass Feb 4 '18 at 0:00
  • $\begingroup$ @JustvanderVeeken you may better accept the other answer it's just a simplified form of mine. $\endgroup$ – Abr001am Feb 6 '18 at 0:25
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$
  • $\begingroup$ you chose addition sign to represent runs of latter digit, genuine! how could this trick skip my imagination! $\endgroup$ – Abr001am Feb 4 '18 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$
  • $\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$ – N. F. Taussig Feb 4 '18 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$ – Abr001am Feb 4 '18 at 0:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.