N3buchadnezzar - 1 year ago 124

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.

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

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

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**