Beautiful numbers

Simply, algorithm I used for this prob is -> UNIVERSE - EXCEPTION

Which is : (10C5) - (9C5) = 126

10C5 is the total number of position could obtained.

Then, 9C4 is the number of position which the 1st digit is 0. So we just need to find how to place the rest 4 digits there.

A nice computational solution is available for this problem too.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

from itertools import permutations
from re import compile

hi=compile('[5-9]+')
lo=compile('[0-4]+')

count=0
for p in permutations('9876543210'):
    n=''.join(p)
    if n.startswith('0'):
        continue
    if ''.join(hi.findall(n))=='98765':
        if ''.join(lo.findall(n))=='01234':
            count+=1

print count    

Generate each permutation of the ten digits in turn. Use regular expressions to select the parts of each permutation consisting of digits between 5 and 9 and 0 and 4 respectively. Then compare these parts against 98765 and 01234 respectively.

Solution is 8C4 + 8C3 = 126. There are 10 places. 0 cannot be in the first place, so first place has to be 9. Second place can either be 8 or 0. If second place is 0, then we are left with 4 more numbers in the sequence {0,1,2,3,4}. So we can select 4 places out of 8 in 8C4 ways. To fill the remaining 5 places there is only one way. Similarly, if second place is 8, then we need 3 places to fill the remaining numbers in the sequence {9,8,7,6,5}. This can be done in 8C3 ways. So, the total number of possible sequences are 8C4 + 8C3.

The first digit must be 9. So the problem is to arrange the other 9 numbers. Because 0,1,2,3,4 is monotonically increasing, we just have to choose 5 spot for this numbers. It is 5C9=126