Problem 45193. Fun with permutations
There are factorial(N) permutations of the numbers from 1 to N. For each of these permutations, we can find the set of indexes j that will return the numbers to their original order, 1:N. For example, if we generate a random permutation p with p = randperm(1:N) then the set of indices j that will return p to the original order p(j) = 1:N may be found by [~,j] = sort(p).
It sometimes happens that this set of indices j and the corresponding permutation p are the same. For example, if p = 1:N, then j = 1:N as well; and if p = N:-1:1, then j is also N:-1:1. However, for N = 3, there are 6 permutations in all, and it happens that only 4 of them have this property.
Your task is to determine, given the value of N, the number of permutations p of the array 1:N for which the permutation p and the indexes j are the same.
input: N, the range of the integers, output: The number of permutations of 1:N for which isequal(p,j)
HINT: For N < 12, you can probably solve this by checking each of the individual permutations, but for larger N this may prove to be too time-consuming.
Solution Stats
Problem Comments
-
3 Comments
I couldn't figure out why my numbers were larger than the answers in the test suite and finally realized that most of those answers were products of the unique factors of the numbers of permutations.
I can assume William has done so as to prevent hard-coded solutions, and add a flair to the test suite while maintaining a simple method to check the solutions as well.
@Dyuman you're right, of course. Leave it to me to solve a problem after midnight, and not realize that the test suite is not in fact checking for exact equality.
I'll delete my previous comment so as to not give too many hints.
Solution Comments
Show commentsProblem Recent Solvers7
Suggested Problems
-
Which values occur exactly three times?
5078 Solvers
-
2239 Solvers
-
Project Euler: Problem 3, Largest prime factor
1412 Solvers
-
Solve the set of simultaneous linear equations
417 Solvers
-
Removing rows from a matrix is easy - but what about inserting rows?
209 Solvers
More from this Author2
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!