About ascending numbers 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$.
 A: 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.
A: 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$.
