Find the number of functions Ο mapping the set A={1,2,3,4,5,6} onto A such that for every aβA,
Ο(Ο(Ο(Ο(Ο(Ο(a))))))=a.
Announcement
Random Math Together Program - Free for USA(J)MO Qualifiers
Our together program brings together high-achieving students nationwide for team-based problem solving and to prepare for competitions such as HMMT, PUMaC, and more.
Eligibility: USA(J)MO qualifiers β’ Spots limited
The function must be a surjection, meaning that for every yβ{1,2,3,4,5,6} there must be some x such that Ο(x)=y. To see this, suppose without loss of generality that there exists no x such that Ο(x)=1. Then Ο(Ο(Ο(Ο(Ο(Ο(1)))))) will never be able to equal 1. Note that this implies that Ο must be a permutation.
Consider the cycle decomposition of the permutation. For example if Ο(x)=7βx, then the cycle decomposition would look like:
(16)(25)(34)
because we have 1β6β1, 2β5β2, and 3β4β3, where the arrows denote applications of the function Ο. The condition that 6 applications of Ο returns every number to themselves is equivalent to stating that there are no cycles of length 4 or 5.
So, we count the complement. Note that there are (nβ1)! possible cycles of length n. The only possible cycle decompositions involving cycles of length 4 or 5 are : 4,1,1; 4,2; and 5,1. Casing on each gives:
720β((46β)β
3!β
0!β
0!+(46β)β
3!β
1!+(56β)β
4!β
1!)=396β
The problems on this page are the property of the MAA's American Mathematics Competitions