This problem concerns lists made from the symbols ABCDEFGHI

This problem concerns lists made from the symbols A,B,C,D,E,F,G,H,I.

(a) How many length-5 lists can be made if repetition is not allowed and the list is in alphabetical order? (Example: BDEFI or ABCGH, but not BACGH.)

(b) How many length-5 lists can be made if repetition is not allowed and the list is not in alphabetical order?

Solution

This problem concerns lists made from the symbols A,B,C,D,E,F,G,H,I.

assume this as 1,2,3,4,5,6,7,8,9

consider digits 1-9, the following digit must be greater than the one to the left.
The first digit can\'t be 6-9 because then you wouldn\'t get a 5 digit string.
The second digit can\'t be 1 or 7-9
The third digit can\'t be 1 or 2 or 8-9
The 4th digit can\'t be 1,2, or 3 or 9
The 5th digit can\'t be 1,2,3 or 4

Working the possible \"numbers\" backwards
5,6,7,8,9
4-5, 4-6, 4-7, 4-8, 4-9, 5-6, 5-7, 5-8, 5-9, 6-7, 6-8, 6-9, 7-8, 7-9, 8-9
3-x-x (15), 4-x-x (10), 5-x-x (6), 6-x-x (3) , 7-x-x (1)
2-x-x-x (35), 3-x-x-x (20), 4-x-x-x (10), 5-x-x-x (4), 6-x-x-x (1)
1-x-x-x-x (70), 2-x-x-x-x (35), 3-x-x-x-x (15), 4-x-x-x-x (5), 5-x-x-x-x (1)

126 possibilities (which is 9 choose 5 which just blew my mind)

for b its 9*8*7*6*5=15120-126=14994

b)
the 6th position is fixed
and if you need at least one O, fix another position
that leaves 4^5 possible combinations
but that O can be in any position 1-5
so 5*4^5=5120