Not sure if this is a "good" question for this forum or if it'll get panned, but here goes anyway…
Consider this problem. I've been trying to find a formula to expand the "regular iteration" of "exp". Regular iteration is a special kind of complex function that is a solution of the equation
$$f(z+1) = \exp(f(z))$$
(or more generally for functions other than $\exp$. It is called "regular" because as a solution it is characterized by the fact the the functional iterates $F^t(z) = f(t + f^{-1}(z))$, with $F$ being the function that is $\exp$ in this case, are "regular", or analytic, at a chosen fixed point of $F$, for all non-integer $t$. There are regular iterations for every fixed point.)
This regular iteration in particular is an entire function. To get it, we take a fixed point $L$ of $\exp$ and expand a solution in powers of $L^z$. The result is to obtain a Fourier series
$$f(z) = \sum_{n=0}^{\infty} a_n L^{nz}$$
where
$$a_0 = L$$
$$a_1 = 1$$
$$a_n = \frac{B_n(1! a_1, 2! a_2, …, (n-1)! a_{n-1}, 0)}{n!(L^{n-1} – 1)}$$
with $B_n$ being the nth "complete" Bell polynomial. This recursive formula yields the following expansions:
$$a_2 = \frac{1}{2L – 2}$$
$$a_3 = \frac{L + 2}{6L^3 – 6L^2 – 6L + 6}$$
$$a_4 = \frac{L^3 + 5L^2 + 6L + 6}{24L^6 – 24L^5 – 24L^4 + 24L^2 + 24L – 24}$$
$$a_5 = \frac{L^6 + 9L^5 + 24L^4 + 40L^3 + 46L^2 + 36L + 24}{120L^{10} – 120L^9 – 120L^8 + 240L^5 – 120L^2 – 120L + 120}$$
…
It appears that, by pattern recognition and factoring the denominators,
$$a_n = \frac{\sum_{j=0}^{\frac{(n-1)(n-2)}{2}} mag_{n,j} L^j}{\prod_{j=2}^{n} j(L^{j-1} – 1)}$$
where $\mathrm{mag}_{n,j}$ is a sequence of "magic" numbers (integers) that looks like this (with the leftmost column being $j = 0$):
[update]: remark: for readability I transposed the original table. But I did not adapt the use of "columns" and "rows" in the surrounding text, so that must be translated in mind (Gottfried Helms)
n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 ...
--------------------------------------------------------------
1 1 2 6 24 120 720 5040 40320 362880 ...
1 6 36 240 1800 15120 141120 1451520
5 46 390 3480 33600 352800 4021920
1 40 480 5250 58800 695520 8769600
24 514 7028 91014 1204056 16664760
9 416 8056 124250 1855728 28264320
1 301 8252 155994 2640832 44216040
160 7426 177220 3473156 64324680
64 5979 186810 4277156 88189476
14 4208 181076 4942428 114342744
1 2542 163149 5395818 141184014
1295 134665 5561296 166279080
504 102745 5433412 187614312
139 71070 5021790 202901634
20 44605 4391304 210825718
1 24550 3625896 210403826
11712 2820686 201934358
4543 2056845 186191430
1344 1398299 164980407
265 879339 140216446
27 504762 114231817
1 260613 88934355
117748 66047166
45178 46576620
13845 31071602
3156 19460271
461 11365652
35 6112650
1 2987358
1298181
488878
153094
37692
6705
749
44
1
But what is the simplest (or at least "reasonably" simple) non-recursive formula for these numbers, or perhaps the numerators in general? Like a sum formula, or something like that. Is there some kind of "combinatorical"-like formula here (sums/products, perhaps nested, of factorials and powers and stuff like that, binomial coefficients, special numbers, etc.)? I notice that the first column is factorials… (how can one prove that?)
And regardless of the formula for the "mag", can one prove from the recurrence formula that the $a_n$ have the form given, and if so, how? Especially, how can one prove the numerator has degree $\frac{(n-1)(n-2)}{2}$? Perhaps that might provide insight into how to find the formula for the "mag".
The ultimate goal here is to try and obtain a series expansion for the "tetration" function $^z e$, more specifically, Kneser's tetrational function, described in Kneser's papers on solutions of $f(f(x)) = \exp(x)$ and related equations (paper is in German, I only saw the translations.). Though this may not be the best way to go, since after constructing this regular iteration function, we then need a special mapping derived from a Riemann mapping to "distort" it so it becomes real-valued at the real axis, and I don't know if there's any good way to construct Riemann mappings even as "non-closed" infinite expansions. But I'm still curious to see if at least a formula for this function is possible.
EDIT: Oh, and for all its worth, apparently
$$\sum_{j=0}^{\frac{(n-1)(n-2)}{2}} \mathrm{mag}_{n,j} = \frac{n!(n-1)!}{2^{n-1}}$$
if that helps any (don't see how it would, and this is not proven, I just got it by looking up the sums on the integer sequences dictionary site.). Perhaps maybe some hints as to why it has that value could help in finding the formula, though…
Justification for thinking a formula exists
Why do I think this even exists, when there's no guarantee that this kind of really non-trivial recurrence relation should even have a non-recursive solution in the first place? Well, for one, the fact that so much of it could be put in simple form as given, and also I did manage to come up with an explicit formula from a very roundabout way but this formula is excessively complicated and based on very general techniques.
It is difficult to describe that formula here, but the outline of the process to construct it is this, for all its worth:
- A general recurrence of the form
$$A_1 = r_{1, 1}$$
$$A_n = \sum_{m=1}^{n-1} r_{n,m} A_m$$
has a non-recursive solution formula. This I found myself, but it is hideous and involves binary bit operations. This kind of recurrence is very general, and it also includes the recurrence for the Bernoulli numbers and other kinds of recurrences.
- The "regular Schroder function" of $F(z) = e^{uz} – 1$, i.e. the function satisfying $\mathrm{RSF}(F(z)) = K \mathrm{RSF}(z)$ (sometimes called the Schroder functional equation, hence the name) which is "regular" in that it can be turned into the regular iteration of $F$ (as we do next), can be given as a Taylor series
$$\mathrm{RSF}(z) = \sum_{n=1}^{\infty} A_n z^n$$
where $A_n$ is given by the recurrence-solving formula with $r_{1,1} = 1$ and $r_{n, m} = \frac{u^{n-1}}{1 – u^{n-1}} \frac{m!}{n!} S(n, m)$ (here, $S(n, m)$ is a Stirling number of the 2nd kind). This is hideous, involving lots of "binary bit manipulation" stuff such as counting 1 bits and positions of 1 bits, which have not-so-nice formulas (the latter involves a set indicator function, at least in the formulation I found myself…). Not sure at all how this could be simplified. The formulas just don't seem to lend themselves to simplification, at least not any that I know of.
-
Invert the regular Schroder function using the Lagrange inversion theorem. This can be expanded in an explicit "non-recursive" form, but it needs so-called "potential polynomials" and other complexity. Plug the huge $A_n$ formula into this. Horrific!
-
Now $U(z) = \mathrm{RSF}^{-1}(u^z)$ is a "regular iteration" of $e^{uz} – 1$, giveable as a Fourier series, or Taylor series in $u^z$.
-
Apply the topological conjugation to conjugate it to iteration of $e^{vz}$ by taking $v = ue^{-u}$ thus $u = -W(-v)$ (Lambert's W-function). Take $H(z) = e^{-u} z – 1$ then find $H^{-1} o U o H$. This gives a regular iteration of $e^{vz}$, thus set $v = 1$ ($u = -W(-1) = \mathrm{fixed\ point\ of\ exponential}$). Though, there may be a constant displacement of some kind offsetting this regular from the one given by the $a_n$-formula.
EDIT: Oops!!!! That should be $H^{-1}(U(U^{-1}(H(U(0))) + z))$, but wait, that's just a constant-shift of $H^{-1} o U$, so just take $H^{-1} o U$ as the regular iteration of $e^{vz}$, probably displaced (in $z$) from the one we're trying to solve for by a constant, but should be structurally identical (and you can try and compute $U^{-1}(H(U(0)))$. Perhaps that is the shift required, but I don't know.).
(EDIT: Apparently the step-numbering above isn't working right for some reason.)
So by this, I think an explicit formula exists (though that constant-shift at the end may be a little problem, but not much, since it is immaterial to the structure of the function). I'm just interested in something simpler than this, preferably something to "fill out" the "mag" formula I gave…
EDIT: Now I'm pratically sure explicit non-recursive solution is possible. Using some numerical tests, I figured the constant shift should be (for $v = 1$, i.e. $u = L$) simply -1, that is, take $H^{-1}(U(z – 1))$ and the coefficients of the Fourier expansion will be equal to $a_n$ in explicit non-recursive form (but atrocious, hence my question, to find something more elegant. This at least evidences that an explicit non-recursive solution is possible, addressing any skeptics' concerns that it isn't and so an elegant one wouldn't exist either. And it is a good bet that if an atrocious formula exists derived from very general principles (note Step 1 above), there may be a more elegant one derived from more specific principles.). So, almost a proof. It could probably be turned into one with a little more work, though that would be much too long to post here.
Best Answer
Let $\beta_n$ denote the flag $h$-vector (as defined in EC1, Section 3.13) of the partition lattice $\Pi_n$ (EC1, Example 3.10.4). Then $$ \mathrm{mag}_{n,{n-1\choose 2}-j} = \sum_S \beta_n(S), $$ where $S$ ranges over all subsets of $\lbrace 1,2,\dots,n-2\rbrace$ whose elements sum to $j$. An explicit formula for $\beta_n(S)$ is given by $$ \beta_n(S) = \sum_{T\subseteq S} (-1)^{|S-T|} \alpha_n(T), $$ where if the elements of $T$ are $t_1<\cdots < t_k$, then $$ \alpha_n(T) = S(n,n-t_1)S(n-t_1,n-t_2) S(n-t_2,n-t_3)\cdots S(n-t_{k-1},n-t_k). $$ Here $S(m,j)$ denotes a Stirling number of the second kind.
Addendum. A combinatorial description of the mag numbers is somewhat complicated. Consider all ways to start with the $n$ sets $\lbrace 1 \rbrace,\dots, \lbrace n \rbrace$. At each step we take two of our sets and replace them by their union. After $n-1$ steps we will have the single set $\lbrace 1,2,\dots,n \rbrace$. An example for $n=6$ is (writing a set like $\lbrace 2,3,5\rbrace$ as 235) 1-2-3-4-5-6, 1-2-36-4-5, 14-36-2-5, 14-356-2, 14356-2, 123456. At the $i$th step suppose we take the union of two sets $S$ and $T$. Let $a_i$ be the least integer $j$ such that $j$ belongs to one of the sets $S$ or $T$, and some number smaller than $j$ belongs to the other set. For the example above we get $(a_1,\dots,a_5)=(6,4,5,3,2)$. If $\nu$ denotes this merging process, then let $f(\nu) = \sum i$, summed over all $i$ for which $a_i>a_{i+1}$. For the above example, $f(\nu) = 1+3+4=8$. (The number $f(\nu)$ is called the major index of the sequence $(a_1,\dots,a_{n-1})$.) Then $\mathrm{mag}_{n,{n-1\choose 2}-j}$ is the number of merging processes $\nu$ for which $f(\nu)=j$. This might look completely contrived to the uninitiated, but it is very natural within the theory of flag $h$-vectors.