Problem 45193. Fun with permutations

Created by William

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?><w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>input: N, the range of the integers, output: The number of permutations of 1:N for which isequal(p,j)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>HINT: For N &lt; 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.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

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 &lt; 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.

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.

Solve

Solution Stats

11 Solutions
4 Solvers

Last Solution submitted on Aug 09, 2021

Last 200 Solutions

Problem Comments

2 Comments

2 Comments

ChrisR on 6 Jan 2021

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.

Christian Schröder 1 hour and 12 minutes ago

I'm confused about the values in the test suite as well. As far as I can tell, this problem is asking about self-inverse permutations of 1:n, the number of is given in A000085 on the OEIS; the numbers given there differ from the values in the test suite, but they do match the output of my code. Some clarification would be nice.

Problem Recent Solvers4

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 45193. Fun with permutations

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers4

Suggested Problems

More from this Author2

Problem Tags

Community Treasure Hunt

Problem 45193. Fun with permutations

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers4

Suggested Problems

More from this Author2

Problem Tags

Community Treasure Hunt

Players