No CrossRef data available.
Article contents
Period Lengths for Iterated Functions
Published online by Cambridge University Press: 16 September 2010
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
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),
\]](https://static.cambridge.org/content/id/urn%3Acambridge.org%3Aid%3Aarticle%3AS0963548310000337/resource/name/S0963548310000337_eqnU1.gif?pub-status=live)
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).
\]](https://static.cambridge.org/content/id/urn%3Acambridge.org%3Aid%3Aarticle%3AS0963548310000337/resource/name/S0963548310000337_eqnU2.gif?pub-status=live)
Information
- Type
- Paper
- Information
- Copyright
- Copyright © Cambridge University Press 2010
References
[1]Abramowitz, M. and Stegun, I. A. (1964) Handbook of Mathematical Functions: With Formulas, Graphs, and Mathematical Tables, Dover.Google Scholar
[2]Arratia, R. and Tavaré, S. (1992) Limit theorems for combinatorial structures via discrete process approximations. Random Struct. Alg. 3 321–345.CrossRefGoogle Scholar
[3]Barbour, A. D. and Tavaré, S. (1994) A rate for the Erdös–Turán law. Combin. Probab. Comput. 3 167–176.CrossRefGoogle Scholar
[4]Deńes, J. (1970) Some combinatorial properties of transformations and their connections with the theory of graphs. J. Combin. Theory 9 108–116.CrossRefGoogle Scholar
[5]Erdös, P. and Turán, P. (1967) On some problems of a statistical group theory III. Acta Math. Acad. Sci. Hungar. 18 309–320.CrossRefGoogle Scholar
[6]Flajolet, P. and Sedgewick, R. (2009) Analytic Combinatorics, Cambridge University Press.CrossRefGoogle Scholar
[7]Goh, W. and Schmutz, E. (1991) The expected order of a random permutation. Bull. London Math. Soc. 23 34–42.CrossRefGoogle Scholar
[8]Hansen, J. C. (1989) A functional central limit theorem for random mappings. Ann. Probab. 17 317–332.CrossRefGoogle Scholar
[9]Harris, B. (1960) Probability distributions related to random mappings. Ann. Math. Statist. 31 1045–1062.CrossRefGoogle Scholar
[10]Harris, B. (1973) The asymptotic distribution of the order of elements in symmetric semigroups. J. Combin. Theory Ser. A 15 66–74.CrossRefGoogle Scholar
[11]Landau, E. (1953) Handbuch der Lehre von der Verteilung der Primzahlen, Vol. 2, Chelsea Publishing, pp. 222–229.Google Scholar
[12]Massias, J. P., Nicolas, J. L. and Robin, G. (1988) Évaluation asymptotique de l'ordre maximum d'un élément du groupe symétrique. Acta Arith. 50 221–242.CrossRefGoogle Scholar
[13]Odlyzko, A. M. (1992) Explicit Tauberian estimates for functions with positive coefficients. J. Comput. Appl. Math. 41 187–197.CrossRefGoogle Scholar
[14]Schmutz, E. (1988) Statistical group theory. Doctoral Dissertation, Mathematics Department, University of Pennsylvania, Philadelphia, USA.Google Scholar
[15]Sloane, N. J. A.The On-Line Encyclopedia of Integer Sequences, published electronically at: www.research.att.com/~njas/sequences/, sequence A000792, accessed March 2010.Google Scholar
[16]Stong, R. (1998) The average order of a permutation. Electron. J. Combin. 5 #41.CrossRefGoogle Scholar
[17]Szalay, M. (1980) On the maximal order in Sn and S*n. Acta Arith. 37 321–331.CrossRefGoogle Scholar
You have
Access
- 3
- Cited by