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.

Since f iterated eventually reproduces all elements of S, it must be "onto". Therefore it constitutes a permutation of the elements of S.

Permutations can be represented as cycles or combinations of cycles, of, say, a replaces b, b replaces c and c replaces a, where a, b and c represent the first three elements, or in this instance, 1, 2 and 3.

The cycles in this case must all have a length that is a factor of 2080, so as to get every number back to its original. For example, if 1 goes to 2 and 2 goes to 1, that's acceptable, as 2080 is an even number.  If 1 goes to 2; 2 goes to 3 and 3 goes to 1, that's unacceptable, as 2080 is not a multiple of 3.

The number 2080 = 2^5 * 5 * 13.  But no cycle length can exceed 7, so possible cycle lengths are 2, 4 and 5. Of course a number can be mapped to itself and be considered a cycle of 1. In fact, if one does so, the cycle lengths have to add to 7.

The following sets add to 7:

2,2,2,1
2,2,1,1,1
2,4,1
2,1,1,1,1,1
2,5
5,1,1
1,1,1,1,1,1,1 (identity mapping)

Case 2,2,2,1:

There are 7 choices for the singlet. The lowest of the remaining numbers can be paired with any of 5 other numbers. The lowest of the remaining four numbers can be paired with any of the remaining 3 numbers. The two that are left must be paired with each other.

Therefore this case accounts for 7*5*3 = 105 functions.

Case 2,2,1,1,1:

There are C(7,4)= 35 ways of choosing the participants for the pairings.  Then the lowest of these four can be paired with any one of 3 others. The remaining two are then forced.

Therefore this case accounts for 35*3=105 functions also.

Case 2,4,1:

There are C(7,2)= 21 ways of choosing the mutual pair, and once this is done, C(5,4)= 5 ways of choosing the participants in the cycle of 4. However, 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 case accounts for 21*5*6=630 functions.

Case 2,1,1,1,1,1:

This merely consists of determining the pair to be switched: C(7,2)= 21.

This accounts for 21 functions.

Case 2,5:

There are C(7,2)=C(7,5)= 21 ways of deciding which numbers are in the pair and which in the group of 5. The pair is just a mutual swap. The lowest of the group of 5 can go to any of the other 4; that one can go to any of the other 3, etc., and so each group of 5 accounts for 4!=24 functions.

So this case accounts for 21*24=504 functions.

Case 5,1,1:

There are C(7,5)=21 ways of choosing the 5 and 4!=24 ways the 5 can be rearranged.

So again, this case accounts for 21*24=504 functions.

Case 1,1,1,1,1,1,1:

As this is just the identity function, it counts as only 1 function.

The total:

105 + 105 + 630 + 21 + 504 + 504 + 1 = 1870

 

 

Posted by Charlie on 2007-08-17 15:34:40