# Strictly increasing numbers

A number can be described as strictly monotonically increasing if each digit (when reading left to right), is larger than the one before it.

*e.g.*123, 1789, 23689, 4589

are all strictly increasing, but

*e.g.*666, 4807, 71244, 981

are all

__not__.Question: How many five digit strictly monotonically increasing numbers are possible?

How many five digit strictly monotonically increasing numbers are possible?

Advertisement:

## Solution

First of all, it should be obvious that zero can’t occur anywhere in the solution (The only place it could possibly occur would be the leading digit, but that would mean the number would be four digits, and not five!)

For the remaining digits {1,2,3,4,5,6,7,8,9}, it’s also clear that each digit can only be used

*once*(if any digit is repeated then the second occurrence cannot be greater).We can represent the number by a binary representation of the nine digits, where a ‘1’ represents that digit is used, and a ‘0’ represents that digit is not used

*e.g.*010101110 to represent 24678

*e.g.*100111001 to represent 14569

For a number to have five digits, there will need to be exactly five 1’s in the binary string.

There are 9

*C*5 = 126 ways to select five bits from nine, so there are exactly 126 five digit strictly increasing numbers.There are 126 five digit strictly increasing numbers.