N3buchadnezzar - 1 year ago 68

Python Question

I am trying to find the number of monotonely increasing numbers with a certain number of digits. A monotonely increasing number with

`k`

`n = a_0 a_1 ... a_k-1`

where

`a_i <= a_(i+1)`

`i in range(0, k)`

`123`

`12234489`

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

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

- Start with the numbers loop through these numbers. Increase
`[1, 2, ..., 9]`

by one.`length`

- Loop over the numbers where
`[i, ..., 9]`

was the number from the previous recursion.`last_digit`

- If add one to
`length = number of digits wanted`

and`total`

else repeat the steps above.`return`

`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

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

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