A permutation puzzle (Posted on 2006-09-20)

	Submitted by K Sengupta
Rating: 5.0000 (1 votes)
Solution:	(Hide)
PART A: Let Mk denote the number of permutations (p1, p2, p3,....., pk) of 1,2,...,k such that for any i lt k, (p1,p2,....,pi) is not a permutation of 1,2,..,i. Then, (n-k)Mk is the number of permutations (p1,p2,...., pn) of 1,2,..., n in which k is the least integer such that (p1,p2,...,pk) is a permutation of 1,2,...,k. Hence, Sum (Mk*(n-k)!) ; k= 1 to n-1 is the total number of permutations of (1,2,...,n) in which there is a k lt n such that (p1,p2,.., pk) is a permutation of 1,2,...,k. Hence, Mn = n! - Sum (Mk*(n-k)!); k = 1 to n-1 By the problem, it is required to evaluate M7. Now: M1 = 1 M2 = 2! -1 = 1 M3 = 3! -(2*1+ 1*1) = 3 M4 = 4! - (3+2+6) = 13 M5 = 5! - (13 + 2*3+ 6*1 + 24) = 71 M6 = 6! - ( 71+ 2*13+ 6*3 + 24*1 + 120*1) = 461 M7 = 7! - (461 +2*71 + 6*13 + 24*3 + 120*1 + 720*1 ) = 3447 HENCE THE REQUIRED NUMBER OF PERMUTATIONS IS 3447. NOTE: (i)The symbol >, symbol < , Symbol > = and symbol < = are respectivrly denoted by lt, gt, gteq and lteq. The symbol < > is denoted by neq. (ii)The factorial symbol is denoted by !, where n! = 1*2*....(n-1)*n --------------------------------------------------------------------------------- PART B max k answer 1 4320 2 4200 3 4128 4 4050 5 3908 6 3447 For an explanation, refer to the Computer Program assisted solution submitted by Charlie in this location.

	Subject	Author	Date
	re: k <= 1,2,3,4,5,6	Charlie	2020-11-24 20:36:07
	computer solution	Charlie	2020-11-24 12:44:13
	re: solution? - Nope	Old Original Oskar!	2006-09-21 13:10:13
	k <= 1,2,3,4,5,6	Steve Herman	2006-09-21 08:05:33
	solution?	bumble	2006-09-20 19:16:35
	Typo	K Sengupta	2006-09-20 14:15:33