Determine the number of permutations (p₁, p₂,...p₇) of 1,2, ...7; such that for all k 1≤k≤6, (p₁, p₂,... p_k) is not a permutation of (1,2, ...k); i.e., p₁≠1; (p₁, p₂) is not a permutation of (1,2), etc.

What would be the answer if we specify 1≤k<6 instead?

Total permutations = 7! = 5040

1 <= k <= 1
The number of permutations which start with 1 are 6! = 720.
So p1 not a permutation of (1) = 5040 - 720 = 4320

1 <= k <= 2
The number of addtional permutations where (p1,p2) is a permutation of (1,2) but p1 is not a permutation of 1:
Necessarly p2 must be 1 and p1 must be 2.  So additional permutations = 5! = 120.
The number of permutations where p₁≠1 and (p₁, p₂) is not a permutation of (1,2) = 4320 - 120 = 4200

1 <= k <= 3
The number of addtional permutations where (p1,p2,p3) is a permutation of (1,2,3) but p1 is not a permutation of 1 and (p₁, p₂) is not a permutation of (1,2):
Necessarly p3 must be 1 or 2 and (p1,p2) must be a permutation of the the other 2.  And (p4,p5,p6,p7) is a permutation of (4,5,6,7) So additional permutations = 2*2!*4! =96
.
The number of permutations where p₁≠1 and (p₁, p₂) is not a permutation of (1,2) and (p1,p2,p3) is not a permutation of (1,2,3) = 4320 - 120 = 4200 - 96 = 4104

1 <= k <= 4
Similarly, 4104 - 3*3!*3! = 4014 - 108 = 3996

1 <= k <= 5
Similarly, 3996 - 4*4!*2! = 3996 - 96 = 3900
This is my answer to the 2nd question.
Hope I didn't make a mistake

1 <= k <= 6
Similarly, 3900 - 5*5!*1! = 3900 - 600 = 3300
This is my answer to the 1st question.
Hope I didn't make a mistake

Posted by Steve Herman on 2006-09-21 08:05:33