# 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!

-

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.

-
Thus, there are ${109 \choose 10} + {108 \choose 9} - 2$ numbers that are not bouncy below $10^{100}$. However the solution given in the link states that the answer is ${110 \choose 10} + {109 \choose 9} - 1000 - 2$ (which is different). I did the calculation and I came to same result as Moron, hence I think the solution given in the link is wrong, probably due to distraction of the person writing it. –  Djaian Nov 18 '10 at 16:01
Wow, great! Thanks! The Project Euler page seems to favor the linked results though. –  Robert Jeppesen Nov 18 '10 at 23:28
Why 108 for increasing numbers? –  Robert Jeppesen Nov 18 '10 at 23:29
I think the -1000 accounts for leading zeros? –  Robert Jeppesen Nov 18 '10 at 23:29
@Robert: Yes you need to account for leading zeroes (The above answer might not), if the problem does not accept those. You also need to account for double counted numbers that are both increasing and decreasing. Like 2222. I suppose the 1000 comes from the double counting. –  Aryabhata Nov 18 '10 at 23:49