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

62.5% Correct | 37.5% Incorrect
Last Solution submitted on Jun 10, 2020

Problem Comments

Problem Recent Solvers5

Suggested Problems

More from this Author2

Problem Tags