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?

For the first 6 numbers not to be a permutation of 1..6, then one of the numbers must be 7. So, the question is how many permutations are there where 7 isn't in the last position?

We could determine this by

total permutations - permutations ending with 7
(The permutations ending with 7 is the number of permutations of 1..6.)

7! - 6!

= 5040 - 720

= 4320

I think this generalizes to
N! - (p!.N-p!)

Where N is the maximum length of the sequence, and p is the length of the prefix that should not contain numbers  1..p.

For 1<=k<6, this gives N=7, p=5,
so
7! - (5!.2!)
= 5040 - (120 x 2)
= 4800

I'm not often on the ball with this kind of stuff so half expecting this to be wrong!

Posted by bumble on 2006-09-20 19:16:35