N3buchadnezzar - 6 months ago 31
Python Question

# number of monotonely increasing numbers

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

`[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`
`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)

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.

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
``````

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