Let S = {1; 2; 3; 4; 5; 6; 7}

Analytically determine the number of maps f from S to S such that f²⁰⁸⁰(x) = x for every x belonging to S.

Note: The iteration is denoted by the superscript, such that f¹(x) = f(x) and
fⁿ(x) = f(f^n-1(x)) for all n > 1.

(In reply to re: solution by Federico Kereki)

What I was saying was that the individual cycles could not be greater than 7, not that the resulting interplay, or beating, or combination of the cycles cannot exceed 7. Indeed, one of my cases had a 2-cycle and a 5-cycle for a total cycle length of 10. What you can't have is, say, a 5-cycle and a 13-cycle, as a 13-cycle can't exist with only 7 items to permute. And a 10-cycle can only exist as a 2-cycle and a 5-cycle, not as a case where a goes to b, b goes to c, c goes to d, ... , i goes to j, j goes to a, because h, i and j do not exist within the set being permuted.

The cycle lengths making up the complete cycle have to add up to seven (counting the 1-cycles which stay the same), and they're all positive, so none can be larger than 7.

The total cycle length of 12 does not work in the case presented as 2080 is not divisible by 12, which, further, is the case as 2080 is not divisible by 3.

I believe I presented all cycles that are made up of subcycles not exceeding 7. Only one of those overall cycles exceeds 7--the one made up of 2 and 5. But it's irrelevant whether the compound cycle exceeds 7 or not.

Posted by Charlie on 2007-08-18 01:14:24