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 CommentsShow comments
Problem Recent Solvers6