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 solution by Charlie)

The cases were supposed to show all combinations of 5, 4, 2 and 1 that add up to 7, but one was left out: 4, 1, 1, 1. It was found by the following:

FOR no5s = 0 TO 1
FOR no4s = 0 TO (7 - 5 * no5s) / 4
FOR no2s = 0 TO (7 - 5 * no5s - 4 * no4s) / 2
  no1s = 7 - 5 * no5s - 4 * no4s - 2 * no2s
  FOR i = 1 TO no5s: PRINT "5, "; : NEXT
  FOR i = 1 TO no4s: PRINT "4, "; : NEXT
  FOR i = 1 TO no2s: PRINT "2, "; : NEXT
  FOR i = 1 TO no1s: PRINT "1, "; : NEXT
  PRINT
NEXT
NEXT
NEXT

whose output was:

1, 1, 1, 1, 1, 1, 1,
2, 1, 1, 1, 1, 1,
2, 2, 1, 1, 1,
2, 2, 2, 1,
4, 1, 1, 1,
4, 2, 1,
5, 1, 1,
5, 2,

The contribution of 4, 1, 1, 1 is given as follows:

There are C(7,4)= 35 ways of choosing the participants in the cycle of 4. Again, any cycle of 4 can done in 6 different ways, as the lowest of the four can go to any of 3 numbers, and that number can go to either of 2 numbers.

So this accounts for 35*6=210 functions.

Added to the 1870 functions (permutations) found previously, this brings the total to 2080, in fact the same 2080 as in the title.

Posted by Charlie on 2007-08-20 10:36:24