Journal article
Period Lengths for Iterated Functions
Combinatorics, probability & computing, v 20(2), pp 289-298
Mar 2011
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).
\]
Metrics
Details
- Title
- Period Lengths for Iterated Functions
- Creators
- ERIC SCHMUTZ - Drexel University, Mathematics
- Publication Details
- Combinatorics, probability & computing, v 20(2), pp 289-298
- Publisher
- Cambridge University Press; Cambridge, UK
- Number of pages
- 10
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- [Retired Faculty]; Mathematics
- Web of Science ID
- WOS:000287608000008
- Scopus ID
- 2-s2.0-79957500547
- Other Identifier
- 991014877916004721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Web of Science research areas
- Computer Science, Theory & Methods
- Mathematics
- Statistics & Probability