Let S = {1, 2,..., n} be a set of positive integers. A permutation on S is a function that takes each element of S to a distinct element of S (i.e., it is one-to-one). The identity permutation takes each element of S to itself. Given a permutation f on S, we can ask how many times f must be applied until we arrive at the identity permutation. The smallest such positive value is called the order of f (i.e., the smallest positive k such that f^k = identity). For example, suppose f behaves as follows (for n=3):
1->2, 2->1, 3->3
Then applying f twice results in the identity permutation, since every element is taken to itself:
1->2->1, 2->1->2, 3->3->3
Since applying f once is not the identity permutation, the order of f is 2. Considering all permutations on S, return how many possible orders there are. |