About ascending numbers

Question

I have that a positive integer d is said to be ascending if in its decimal representation: $$d=d_md_{m-1}\cdots d_2d_1$$ we have $$0<d_m\leq d_{m-1}\leq \cdots \leq d_2\leq d_1.$$ How can I find the number of ascending integers which are less that $10^9$.

Answer 1

First note that you can assume that $m=9$: if $d_3d_2d_1$, say, is ascending, the representation $000000d_3d_2d_1$ still satisfies the condition that $d_9\le d_8\le\ldots\le d_1$. Thus, you’re really looking for the number of non-decreasing sequences of $9$ digits.

Let $x_1=d_9$, $x_2=d_8-d_9$, $x_3=d_7-d_8$, and in general $x_k=d_{10-k}-d_{11-k}$ for $k=2,\dots,9$; clearly each $x_k\ge 0$, and it’s not hard to check that $x_1+\ldots+x_9=d_1$. Conversely, if $x_1,\dots,x_9$ are non-negative integers whose sum is at most $9$, we can set $d_9=x_1$, $d_8=x_1+x_2$, and in general $d_k=x_1+x_2+\ldots+x_{10-k}$ to get a non-decreasing sequence of $9$ digits. Thus, the problem is almost reduced to counting the solutions in non-zero integers to the inequality

$$x_1+x_2+\ldots+x_9\le 9\tag{1}\;.$$

The almost is because we don’t want the one solution $x_1=x_2=\ldots=x_9=0$: it doesn’t correspond to the decimal representation of a positive integer. But that’s okay; we’ll count it for now, because it makes things simpler, and then subtract $1$ at the end.

The inequality is a bit difficult to work with, so we add an extra variable to take up the slack between $x_1+\ldots+x_9$ and $9$ and replace $(1)$ with the equation

$$x_0+x_1+x_2+\ldots+x_9=9\tag{2}\;:$$

every solution to $(2)$ in non-negative integers corresponds to a unique solution to $(1)$ in non-negative integers and vice versa, so we need only count the solutions to $(2)$ in non-negative integers and subtract $1$. This is a standard stars-and-bars problem; the link gives both a formula for the answer and a pretty decent explanation of why that formula is correct, but if it’s not clear, feel free to leave a comment.

Answer 2

Hint: the number of base-$b$ ascending integers less than $b^m$ is the number of ordered $m$-tuples $(s_1,\ldots,s_m)$ of nonnegative integers with $\sum s_j \le b-1$. Find a recurrence for the number with sum $k$.

Answer 3

First of all, sorry for being too lengthy.

$(1)$For single digit number we have $9[1-9]$ of them

$(2)$For $2$ digit numbers observe that

$\in[10,19]$ there are $9[11-19]$ of them

$\in[20,29]$ there are $8[22-29]$ of them

$\cdots$

$\in[80,89]$ there are $2[88-89]$ of them

$\in[90,99]$ there are $1[99]$ of them

So, $\in[10-99]$ there are $1+2+\cdots+8+9=\sum_{1\le r\le 9}\frac{r(r+1)}2=45$ of them

Similarly,

$(3a)$

Observe that $[10,99]$ and $[100,199]$ have same numbers of such elements

So, $\in[100-199]$ there are $1+2+\cdots+8+9=\sum_{1\le r\le 9}\frac{r(r+1)}2=45$ of them

$(3b)$

$\in[200,219]$ there are $0[]$ of them

$\in[220,129]$ there are $8[222-229]$ of them

$\cdots$

$\in[280,289]$ there are $2[288-289]$ of them

$\in[290,299]$ there are $1[299]$ of them

So, $\in[200-299]$ there are $1+2+\cdots+8=\sum_{1\le r\le 8}\frac{r(r+1)}2=36$ of them

$\cdots$

So, $\in[100,999]$ there are $\sum_{1\le r\le 9}\frac{r(r+1)}2$ of them

Now, $\sum_{1\le r\le n}\frac{r(r+1)}2=\frac12 (\sum_{1\le r\le n}r+\sum_{1\le r\le n}r^2)=\frac12\{\frac {n(n+1)}2+\frac {n(n+1)(2n+1)}6\}=\frac{n(n+1)(n+2)}{2\cdot3}$

So, $\in[100,999]$ there are $=\frac{9(9+1)(9+2)}{2\cdot3}=165$ of them

$(4a)$ Observe that $[100,999]$ and $[1000,1999]$ have same numbers of such elements

Similarly, $\in[1000,1999]$ there will be $\frac{9(9+1)(9+2)}{2\cdot3}=165$ of them which is due to $$(1+2+\cdots+9)+(1+2+\cdots+8)+(1+2+\cdots+7)+\cdots+(1+2)+1$$

Following this method $\in[2000,2999]$ we find the number of such elements to be $\frac{n(n+1)(n+2)}{2\cdot3}$ with $n=10-2=8$

So, $\in[1000,9000]$ there will be $\sum_{1\le r\le 9}\frac{r(r+1)(r+2)}{2\cdot3}$ of them

Can you recognize the pattern?