# How this expression leads to the given sequence

Here given is a sequence from OEIS.

The sequence is triangle of coefficients from fractional iteration of $e^x - 1$. Few terms are:
1, 1, 3, 1, 13, 18, 1, 50, 205, 180, 1, 201, 1865, 4245, 2700, 1, 875, 16674
as a triangle this can be written as

 1
1,  3
1, 13,  18
1, 50, 205, 180
1,201,1865,4245,2700


The expression of finding the sequence is also given as:
$A(n;x)$ for n-th row satisfies
$$A(n;x) = \sum_{k=0}^{n-1} \mathrm{Stirling}_2(n, k) * A(k;x)*x,\ A(1;x) = 1.$$

The tabular view shows the entries row wise. $\mathrm{Stirling}_2(n,k)$ is most probably stirling numbers of the second type

I am not able to get how above expression is resulting in the given sequence.
In summation, $k$ begins from 0, but nothing is mentioned about $A(0;x)$. I assumed it to be 0, but still can't get the above values.

Please explain how the first few terms are resulting from the expression.

• The Mathematica function at OEIS works as desired. Jun 13, 2013 at 8:36
• @Fred Kline are you sure of that? Can you explain the the computation manually for the first few terms? I am getting wrong results. Jun 13, 2013 at 9:02
• I have changed the mathematical expressions to correct LaTeX. Hope this helps.
– user22882
Jun 26, 2013 at 8:36

Stirling numbers of the second kind $S_2(n,k)$ vanish for $k=0$, so the $k=0$ term in the sum does not contribute. You ask for a manual computation of the first few terms. Here we go:

Stirling numbers: $S_2(n,1)=S_2(n,n)=1$, $S_2(3,2)=3$, $S_2(4,2)=7$, $S_2(4,3)=6$

$$a(2,x)=xa(1,x)=x$$

$$a(3,x)=xa(1,x)+3xa(2,x)=x+3x^2$$

$$a(4,x)=xa(1,x)+7xa(2,x)+6xa(3,x)=x+7x^2+6x^2+18x^3=x+13x^2+18x^3$$

This gives the first few coefficients: $1,1,3,1,13,18$.

• if x means the column-index, then all elements in the matrix $A$ in the first column are zero by $a(2,0)=0 \cdot a(1,0) = 0$. Is that really meant? It would contradict the table-view in OEIS where the first column is 1. Are the indexes for S2 and A are thought differently (for S2 beginning at 0 and for A beginning at 1 ?) Dec 9, 2013 at 14:54
• @GottfriedHelms --- my understanding is that $x$ is a variable, not an index; the function $a(n,x)$ is a polynomial of degree $n-1$ in the variable $x$; you are seeking a triangle of coefficients, such that the $n$-th row of the triangle has at the $m$-th position the coefficient of the term $x^m$ in $a(n,x)$. As I worked it out above, you see that this indeed gives the series mentioned by the OP. In particular, the fourth row has elements $1,13,18$, which are the coefficients of $a(4,x)=x+13x^2+18x^3$. Dec 9, 2013 at 16:34
• Carlo, see my accidental beautiful observation in my new answer... Dec 10, 2013 at 23:55

[update] Here -for possibly a nicer reference- I give a screenshot, where the identity by the OEIS-formulae (and kindly expanded by @Carlo Beenakker) is interpreted as matrix-multiplication. It indicates also, that the given formula of relations between the Stirling and A-numbers is near to an eigenvector/eigenmatrix-relation (in fact is a Jordan-decomposition) which I described in my first version of this post (which I kept below).

Here is the matrix-multiplication scheme: Another approach gave the numbers in a completely surprising context; I've no explanation so far. ([update]:It is clear now. Carlo's expansion gave the key hint!).

For the function $\exp(x)-1$ the matrix $S_2$ of Stirling numbers 2'nd kind is involved. I've just recently begun to exercise with the Jordan-decomposition, and for some exercise I took this matrix

$$\large S_2 \qquad = \qquad \small{ \begin{bmatrix} 1 & . & . & . & . \\ 1 & 1 & . & . & . \\ 1 & 3 & 1 & . & . \\ 1 & 7 & 6 & 1 & . \\ 1 & 15 & 25 & 10 & 1 \end{bmatrix}}$$ and let WolframAlpha Jordan-decompose it such that $$S_2 = A \cdot J \cdot A^{-1}$$

This gave the three matrices:

$$\begin{array} {} A &=&\small { \begin{bmatrix} 1 & . & . & . & . \\ 0 & 1 & . & . & . \\ 0 & 1 & 3 & . & . \\ 0 & 1 & 13 & 18 & . \\ 0 & 1 & 50 & 205 & 180 \end{bmatrix} } \\ J&=& \small {\begin{bmatrix} 1 & . & . & . & . \\ 1 & 1 & . & . & . \\ 0 & 1 & 1 & . & . \\ 0 & 0 & 1 & 1 & . \\ 0 & 0 & 0 & 1 & 1 \end{bmatrix} } \\ A^{-1}&=&\small {\begin{bmatrix} 1 & . & . & . & . \\ 0 & 1 & . & . & . \\ 0 & -1/3 & 1/3 & . & . \\ 0 & 5/27 & -13/54 & 1/18 & . \\ 0 & -301/2430 & 353/1944 & -41/648 & 1/180 \end{bmatrix}}\end{array}$$ (Note: I've transposed the input to Woframalpha and then also the output to keep in line with my usual conventions with that type of matrix-discussion)
The surprise is: that we find the coefficients in the matrix $A$

The relation can also be written as $$S_2 \cdot A = A \cdot J$$ and if $J$ is decomposed in the sum of two (diagonal and subdiagonal) components $J=J_0+J_1$ where $J_0=I$ and $J_1$ the transpose of my $J$ in the update of this post above, then we can reformulate $$S_2 \cdot A = A \cdot (I+J_1) \\ (S_2 - I) \cdot A = A \cdot J_1 \\ S_2^* \cdot A = A \cdot J_1 \\$$ from which -in my opinion- we could formulate a slightly more convenient relation than that given in the OEIS.

Additional remark because there is a relation to the Schröder-function for fractional iteration: for the use for the function $f(x) = \exp(x)-1$ the matrix $S_2$ is factorially similarity-scaled and -when let unscaled- becomes the Bell/(transposed) Carleman-matrix for that function. In that view the scaling $F^{-1} \cdot S_2 \cdot F$ is a matrixoperator; and the matrices $A$ and $A^{-1}$ are in a very similar role as the operators for the Schröder-function of $f(x)$ which is indeed at the heart of the Schröder/Abel-type of fractional iteration...

This is the input for W/A's input field:
JordanForm({{1,1,1,1,1},{0,1,3,7,15},{0,0,1,6,25},{0,0,0,1,10},{0,0,0,0,1}})

After the observation (and display in my earlier answer) that the coefficients occur in the Jordan-decomposition of the Stirlingmatrix 2nd kind, there is a much easier decomposition.

First to make the pattern smoother you should prepend coefficients to the example in your question:

1, 0,  0, ...
0, 1,  0, ...
0, 1,  3, ...
0, 1, 13,  18
0, 1, 50, 205, 180
0, 1,201,1865,4245,2700
..., ..., ...


Let us define the function $$u(x)=\exp(x)-1$$ and denote the $$h$$'th iterates as $$u_h(x)$$ such that $$u_0(x) = x$$ and $$u_1(x)=u(x)$$
then the egf (exponential generating function) for the coefficients

• in column 0 is $$1 u_0(x)$$,
• in column 1 is $$1 u_1(x)- 1 u_0(x)$$
• in column 2 is $$1 u_2(x)- 2 u_1(x) + 1 u_0(x)$$
• in column 3 is $$1 u_3(x)- 3 u_2(x) + 3 u_1(x)- 1 u_0(x)$$
• ...

and so on with composition with according binomial coefficients.

(In Pari/GP having the egf $$C(x)$$ for some coefficients $$[c_0,c_1,c_2,...]$$
such that $$\small C(x)= c_0+c_1 x + c_2/2! x^2+ c_3 /3! x^3 + ...$$ then serlaplace(C(x)) gives c_0+c_1 x + c_2 x^2+ c_3 x^3 + ... , the ordinary generating function, which is what you see in your second column)

That illustrates the very nice machinery of the Jordan-decomposition and the fractional iterations of $$u(x)$$ : the matrix $$A$$ in $$S2 = A \cdot J \cdot A^{-1}$$ provides the inner sum in the Newton-method to compute the fractional iterate (as for instance explained in [Comtet]), and the postmultiplication by the (fractional) powers of $$J$$ the outer (fractional) binomial coefficients by which the inner sums are weighted and added to get the powerseries for the fractional iterated $$u_h(x)$$.