|
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. |