## Increasing Digits

#### Problem

Working from left to right in a number, if the next digit is greater in value than the preceeding digit, we say that the digits are strictly increasing: 15689, 35679, and 13478 are examples of 5-digit numbers with this property.

Given a number has strictly increasing digits, what is the probability that it contains 5-digits?

#### Solution

Each non-empty subset taken from {1,2,3,4,5,6,7,8,9} represents each of the possible numbers with strictly increasing digits, and in turn each of these subsets can be represented by a 9-digit binary string. For example, 124789 has strictly increasing digits and can be represented by the string 110100111.

In this way we can see that there are 2^{9}=512 binary strings, but as one of these strings would be the empty set, there are 511 numbers containing strictly increasing digits that exist in total.

Next we note that a 5-digit number with strictly increasing digits can be represented by selecting a subset of size 5 from {1,2,3,4,5,6,7,8,9}; there are ^{9}C_{5} = 126 ways this can be done.

Hence the probability of a number with strictly increasing digits containing exactly 5-digits is 126/511=18/73.

Check out the related Never Decreasing Digits problem.