number of monotonely increasing numbers

Question

1. Introduction to problem

I am trying to find the number of monotonely increasing numbers with a certain number of digits. A monotonely increasing number with k digits can be written as

n = a_0 a_1 ... a_k-1

where a_i <= a_(i+1) for all i in range(0, k). A more concrete example are 123 or 12234489. I am trying to create a function such that

increasing(2) = 45
increasing(3) = 165
increasing(4) = 495
increasing(5) = 1287
increasing(6) = 3003

Because there are 45 numbers with two digits that are increasing, 11, 12, ..., 22, 23, ..., 88, 89, 99. And so forth.

I saw this as a nice opportunity to use recursion. I have tried to write a code that does this, however there is something wrong with the result. My psudo-code goes like this

2. Psudo-code

• Start with the numbers [1, 2, ..., 9] loop through these numbers. Increase length by one.
• Loop over the numbers [i, ..., 9] where last_digit was the number from the previous recursion.
• If length = number of digits wanted add one to total and return else repeat the steps above.

3. Code

global total
total = 0
nums = range(1, 10)

def num_increasing(digits, last_digit = 1, length = 0):
    global total

    # If the length of the number is equal to the number of digits return
    if digits == length:
        total += 1
        return

    possible_digits = nums[last_digit-1::]

    for i in possible_digits:
        last_digit = i
        num_increasing(digits, last_digit, length + 1)
    return total

if __name__ == '__main__':

    num_increasing(6)
    print total

4. Question:

Is my psudocode correct for finding these numbers? How can one use recursion correctly to tackle this problem?

I will not ask to find the error in my code, however some pointers or an example of code that works would be much obliged.

Answer 1

This can be computed in closed form.

We have a budget of 8 units, which we can allocate to each digit or to "leftovers". A digit with n units of budget allocated to it is n greater than the digit before it; for the first digit, if we allocate n units of budget there, its value is n+1. Leftover budget does nothing.

Budget allocations are in 1-to-1 correspondence with monotonely increasing numbers, as each budget allocation produces a monotonely increasing number, and each monotonely increasing number has a corresponding budget allocation. Thus, the number of monotonely increasing numbers of length k is the number of ways to allocate 8 units of budget to k+1 buckets, one bucket per digit and one bucket of leftovers.

By the classic stars and bars result, this is (8 + k) choose 8, or (8+k)!/(8!k!):

def monotone_number_count(k):
    total = 1
    for i in xrange(k+1, k+9):
        total *= i
    for i in xrange(1, 9):
        total //= i
    return total

For monotonely decreasing numbers, the same idea can be applied. This time we have 9 units of budget, because our digits can go from 9 down to 0 instead of starting at 1 and going up to 9. A digit with n units of budget allocated to it is n lower than the previous digit; for the first digit, n units of budget gives it value 9-n. The one caveat is that this counts 0000 as a four-digit number, and similarly for other values of k, so we have to explicitly uncount this, making the result ((9 + k) choose 9) - 1:

def monotonely_decreasing_number_count(k):
    total = 1
    for i in xrange(k+1, k+10):
        total *= i
    for i in xrange(1, 10):
        total //= i
    total -= 1
    return total