Combinatorial counting

Question

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!

Answer 1

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.

Answer 2

First, you are trying to count increasing and decreasing numbers. They are related in that you only reverse the digits of one to get the other. The only difference is that increasing numbers cannot start with 0, but decreasing ones can end with 0. So let's just work on counting increasing ones.

How many one digit increasing numbers are there? Nine. How many one digit increasing numbers are there that end in 1? One. So make a function f(x,n) where f(x,n) is the number of n digit increasing numbers that end in x, you should be able to make a recurrence for each one. That is, (6,n)=some function of the f(x,n-1). The increasing numbers under a googol are just the sum of f(x,100) over x. Then you do the same for decreasing numbers but have to add f(0,n) to the mix.

I didn't look at the program you cite to see if it works anything like this. But this approach worked for me.

There are many counting problems that yield to techniques like this. Instead of keeping a list of all the increasing numbers (which would grow too big), just keep track of how many there are of a given size and find a recurrence to get to the next size up. The next three problems in the list can be attacked this way as well.

There is another approach. Think of a series of 101 zeros. Then all the increasing numbers can be constructed by putting up to nine "step up" marks between the digits, with one of them required to be between the first and second zeros (to avoid leading zeros). You can even make it exactly nine steps if you allow some to be at the end. I'll let somebody else make this more explicit