All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
A permutation puzzle (Posted on 2006-09-20) Difficulty: 3 of 5
Determine the number of permutations (p1, p2,...p7) of 1,2, ...7; such that for all k 1≤k≤6, (p1, p2,... pk) is not a permutation of (1,2, ...k); i.e., p1≠1; (p1, p2) is not a permutation of (1,2), etc.

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

No Solution Yet Submitted by K Sengupta    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution k <= 1,2,3,4,5,6 | Comment 3 of 4 |
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 p1≠1 and (p1, p2) 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 (p1, p2) 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 p1≠1 and (p1, p2) 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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information