Q:

Combinatorial counting

This question is about Project Euler 113: 

Working from left-to-right if no digit
  is exceeded by the digit to its left
  it is called an increasing number; for
  example, 134468.
Similarly if no digit is exceeded by
  the digit to its right it is called a
  decreasing number; for example, 66420.
We shall call a positive integer that
  is neither increasing nor decreasing a
  "bouncy" number; for example, 155349.
As n increases, the proportion of
  bouncy numbers below n increases such
  that there are only 12951 numbers
  below one-million that are not bouncy
  and only 277032 non-bouncy numbers
  below 10^10.
How many numbers below a googol
  (10 pow 100) are not bouncy?

This is obviously not something you can brute force. I found a mathematical solution that does the trick in no time, the problem is, I don't understand it! 
Can someone point me in the right direction? Not having a math background, I'm not even sure where to begin! 

A:

Suppose you wanted to find the number of decreasing numbers of exactly $\displaystyle k$ digits.
Now if you knew that the digits were distinct, you chould choose k distinct digits and sort them, giving you 10 choose k  = $\displaystyle {10 \choose k}$ numbers. If the number was in base $n$, the corresponding number would be $\displaystyle {n \choose k}$.
Now given a non-decreasing number like
5543220
We can construct a "sorted" number with distinct digits in a different base, by adding 0 to the rightmost digit, adding 1 to the digit to the left of it, 2 to the digit to the left of that, and so on.
For instance:
5543220 becomes BA86430 in base 10 + 6 = 16.
A decreasing number with $\displaystyle k$ digits correponds in a 1-1 fashion to a sorted number of $k$ digits, in base $\displaystyle 10+k-1 = 9+k$.
As we saw earlier the number of "sorted" numbers of $\displaystyle k$ digits in base $\displaystyle n$ is $\displaystyle {n \choose k}$.
Thus the number of decreasing numbers is $\displaystyle {9+k \choose k}  = {9+k \choose 9}$.
So the total number of decreasing numbers $\displaystyle \lt 10^{100}$ is
$\displaystyle \sum_{k=1}^{99} {9+k \choose 9}$
Using $\displaystyle {n \choose r} - {n-1 \choose r} = {n-1 \choose r-1}$
the above becomes
$\displaystyle \sum_{k=1}^{99} {10+k \choose 10} - {9+k \choose 10}$
which is a telescoping sum and becomes
$\displaystyle  = {10+99 \choose 10} - {9+1 \choose 10} = {109 \choose 10} - 1$
Do something similar for the increasing numbers.

