Determine the number of permutations (p
_{1}, p
_{2},...p
_{7}) of 1,2, ...7; such that for all k 1≤k≤6, (p
_{1}, p
_{2},... p
_{k})
is not a permutation of (1,2, ...k); i.e., p
_{1}≠1; (p
_{1}, p
_{2}) 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!.Np!)
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 20060920 19:16:35 