" name="description" /> Cambridge Journals Online - Combinatorics, Probability and Computing - Abstract - Period Lengths for Iterated Functions

Combinatorics, Probability and Computing

Table of Contents - March 2011 - Volume 20, Issue 02  

Paper

Period Lengths for Iterated Functions

ERIC SCHMUTZa1

a1 Mathematics Department, Drexel University, 3401 Market Street, Philadelphia, Pa., 19104, USA (e-mail: Eric.Jonathan.Schmutz@drexel.edu)

Abstract

Let Ωn be the nn-element set consisting of all functions that have {1, 2, 3, . . ., n} as both domain and codomain. Let T(f) be the order of f, i.e., the period of the sequence f, f(2), f(3), f(4) . . . of compositional iterates. A closely related number, B(f) = the product of the lengths of the cycles of f, has previously been used as an approximation for T. This paper proves that the average values of these two quantities are quite different. The expected value of T is

\[ \frac{1}{n^{n}}\sum\glimits_{f\in \Omega_{n}}{\bf T}(f)=\exp\biggl(k_{0}\sqrt[3]{\frac{n}{\log^{2}n}}\bigl(1+o(1)\bigr)\biggr), \]

where k0 is a complicated but explicitly defined constant that is approximately 3.36. The expected value of B is much larger:
\[ \frac{1}{n^{n}}\sum\glimits_{f\in \Omega_{n}}{\bf B}(f)=\exp\biggl(\frac{3}{2}\sqrt[3]{n}\bigl(1+o(1)\bigr)\biggr). \]

(Received November 02 2007)

(Revised August 06 2010)

(Online publication September 16 2010)