Endofunctions of given cycle type

Iteration of an endofunction f on a finite set X defines cycles of f. To a given set L of lengths and to a given function m:L → N0, the number of all those functions having m(l) cycles of length l ∈ L and possibly other cycles of length l 6 ∈ L will be computed. Furthermore by introducing group actions the number of patterns of these functions can be derived from the Cauchy-Frobenius Lemma. We compare these solutions with the results derived from combinatorial species theory. An endofunction on the set X is a function f with domain and range X. The term endofunction comes from species theory. See for instance [2, 3, 4, 5, 10]. Bijective endofunctions are usually called permutations. We are only dealing with endofunctions on a finite set X, so without loss of generality each n-set (i. e. a set of cardinality n) can be replaced by n: = {1, 2,..., n}. Denoting the k-th iterate of an endofunction f by fk we define f to have a cycle of length k, if and only if there is some i ∈ n such that fk(i) = i and f l(i) 6 = i for all 1 ≤ l < k, and the elements of {i, f(i),..., fk−1(i)} form a cycle of f (of length k). Furthermore f restricted to a cycle is a cyclic permutation of the elements of this cycle. It is obvious that each endofunction on a finite set must have at least one cycle. The cycle type of an endofunction f can be considered as a multi-set L: = {lm(l) | l ∈ n}, where m(l) ∈ N0 is the number of cycles of f of length l. Let s be the number of elements lying in cycles of f, then s = l∈n l ·m(l) and 1 ≤ s ≤ n. Renaming the elements of n leads to the following group action of the symmetric group Sn on the set of all endofunctions: Sn × nn → nn, (pi, f) 7 → pi ◦ f ◦ pi−1 =: pifpi−1, (1) ∗Supported by the Fonds zur Förderung der wissenschaftlichen Forschung P10189- PHY and P12642- MAT