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:
1,1,1,1,1,1,1 (identity mapping)
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.
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.
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.
This merely consists of determining the pair to be switched: C(7,2)= 21.
This accounts for 21 functions.
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.
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.
As this is just the identity function, it counts as only 1 function.
105 + 105 + 630 + 21 + 504 + 504 + 1 = 1870
Posted by Charlie
on 2007-08-17 15:34:40