Logo
Tetration.org
What Lies Beyond Exponentiation?
Home
Fractals
Tetration
Dynamics
Combinatorics
Ackermann
Function
Resources
Links
About
periods of tetration around real axis

Combinatorics of Iterated Functions

An interesting demonstration of the power discrete mathematics is the importance of combinatorics in the study of the dynamics of continuous iteration. The Bell polynomials, which are related to set partitions, are the foundation of Continuous iteration of dynamical maps and the Stirling numbers of the first and second kind are also referenced. In Analysis of Carleman Representation of Analytical Recursionsthe Catalan numbers and the ballot numbers are used in deriving the continuous iteration of the logistics equation. Complementary to the study of the dynamics of fixed points is combinatorial dynamics which studies the dynamics of periodic fixed points. It is an outgrowth of Sharkovskii's Theorem and makes use of permutations and graphs. It is interesting to note that not only are the subjects themselves complementary but the combinatoric structures used are complementary as well; trees for continuous iteration and graphs for combinatorial dynamics.

Combinatorial Dynamics

The biggest advance in my research into continuous iteration in the last ten years came from learning about the On-Line Encyclopedia of Integer Sequences (OEIS) while reading one of the biographies of Paul Erdös. Perhaps you have heard of the term spaghetti code? Well my work in dynamics was spaghetti mathematics, it appeared to be correct but it was very ugly. So I entered the integer sequence from summing the coefficients from the first step of my work into the OEIS and found out that I was working with the Bell polynomials, the derivatives of composite functions and isomorphic to the combinatoric structure set partitions, also known as the Bell numbers. I entered the number of terms from the first step of my work into the OEIS and came up with the integer partitions, also known as the partition function. This caused me to think about what combinatoric structure might be isomorphic to the derivatives of iterated functions. It seemed reasonable that the derivatives of the iterated composition of functions would be isomorphic to recursive partitioning. I made a couple of guesses as to the sum of the coefficients and the number of terms; the OEIS indicated I was looking at combinatoric structures from Ernst Schroeder's 1870 paper Vier combinatorische Probleme. I was utterly amazed to find out that one year later Schroeder wrote Über iterirte Functionen, the first paper on dynamical systems, and that he was interested in tetration. Revisiting the OEIS entry for set partitions, I found a cross reference to the combinatoric structure Schroeder's Fourth Problem, also known as hierarchies and total partitions. I typically refer to Schroeder's Fourth Problem as hierarchies and their unlabeled version as unlabeled hierarchies. This is out of respect for Philippe Flajolet who coined the name and is arguably the preeminent expert on the subject as well as being the author of a vast number of beautiful and accessible papers on combinatorics. Also with the hierarchies combinatoric structure's central role in iterated functions and thus the general dynamical system.

Schroeder diagrams and summations for D4 f n(p)

A visualization of recursive partitioning is presented in Partition Diagrams using recursive Bell number diagrams to create "Schroeder diagrams" which enumerate the hierarchies of n items. Having a good idea of where I needed to end up, I was finally able to formulate my work in terms of labeled and unlabeled hierarchies and whose analytic representation of the derivatives of iterated functions I refer to as Schroeder summations. The nth derivative of iterated functions at a fixed point consist of unlabeled hierarchies of n or uhier(n) terms; the table above shows that uhier(4)=5. Likewise, the sum of the integer coefficients of the nth derivative of iterated functions gives the hierarchies of n, in this case hier(4)=26. These relationships or morphisms are best expressed in terms of category theory in the following communitive diagram. I highly recommend John Baez's web site in order to learn more about category theory


 

The Schroeder summations page is an export from a Mathematica 4.1 notebook based on an Iterate package I wrote. The first eight Schroeder summations are computed, but only the first five are displayed due to their size. The first eight Schroeder summations are shown to correct from f 1(p) though f 8(p) where p is a fixed point. The Schroeder summations are shown to be associated with both the unlabeled and labeled hierarchies. The hierarchies of 4 items are enumerated by generalizing the algorithm for enumerating the set partitions using the pointing operator.

Dynamical Combinatorics

Finally, the generating function for the hierarchies of height n is computed, I believe for the first time, and shown to generate the hierarchies of heights 1/4, 1/3, 1/2, 2, 3, 4, -1/2, -1, -2, i, 2i. Consider the case where f(z)=ez-1, a fixed point is at zero and the coefficient of z is one so we have a parabolic rational neutral fixed point. Summing the 5 terms of the Schroeder summation in this case gives a simple polynomial; 1/2(6n3-5n2+n). The generating function f 2(z) is eez-1-1, the generating function of the set partitions with the 0th term set to zero instead of one. A quick calculation shows that Bell(4) = 1/2(6n3-5n2+n)|n=2 = 15. The function f -1(z) is Log(z+1), D4 Log[z+1]|z=0 =1/2(6n3-5n2+n)|n=-1 = -6 which displays a well known but beautiful combinatoric truth, that the Stirling numbers of the second kind become the Stirling numbers of the first kind when n is negative. Let f -1/2(z)=a(z), then a(a(z))=ez-1. The numerators for a(z) are given at A052122 in the OEIS with the fourth term as zero which agrees with 1/2(6n3-5n2+n)|n=1/2 = 0. The derivatives of f n(z) where f(z)=0, f '(z)=1, and Dk f(z) is rational are polynomial in n with rational coefficients and thus much more likely to lead to integer sequences which can be verified on the OEIS. See Generating Flows for other combinatorial structures.


Contact: [email protected]
Copyright  ©  2001-2012 Daniel Geisler