An example instance of the algebraic classes: power series represented as sequences of derivatives at zero (Maclaurin series, or exponential generating functions). This representation supports the same operations as the coefficients representation, but often with different constraints. For example, the derivatives may be integers while the coefficients are fractional.

• Dusko Pavlovic and M. Escardó, "Calculus in coinductive form", Thirteenth Annual IEEE Symposium on Logic in Computer Science, 1998. http://www.isg.rhul.ac.uk/dusko/papers/1998-lapl-LICS.pdf
• M. Douglas McIlroy, "The music of streams", Information Processing Letters 77 (2001) 189-195.

This representation corresponds to viewing a power series \( \sum_{n=0}^\infty a_n {x^n \over n!} \) as the exponential generating function of a sequence \( \{a_n\} \). The corresponding sequence may be extracted using derivatives.

Examples

• Euler zigzag numbers, the number of alternating permutations of \(n\) elements (OEIS A000111) have the exponential generating function \( \sec x + \tan x \):

>>> derivatives $ secS + tanS
[1,1,1,2,5,16,61,272,1385,7936,50521,353792,2702765,22368256,...

• Double factorials of odd numbers (OEIS A001147) have the exponential generating function \( 1 \over \sqrt{1 - 2x}\):

>>> derivatives $ powerRatio 1 2
[1,1,3,15,105,945,10395,135135,2027025,34459425,654729075,...

• Bernoulli numbers (OEIS A027641 / OEIS A027642) have the exponential generating function \(x \over e^x - 1\):

>>> derivatives $ identity `div` integral expS
[1 % 1,(-1) % 2,1 % 6,0 % 1,(-1) % 30,0 % 1,1 % 42,0 % 1,(-1) % 30,0 % 1,...

• The alternative convention, differing only in the sign of \(B_1\), has the exponential generating function \(x + {x \over e^x - 1} = {x e^x \over e^x - 1}\):

>>> derivatives $ identity*expS `div` integral expS
[1 % 1,1 % 2,1 % 6,0 % 1,(-1) % 30,0 % 1,1 % 42,0 % 1,(-1) % 30,0 % 1,...

We can use div here, because it divides evenly when the numerator has at least as many leading non-zero terms as the denominator.

Multiplying the exponential generating function of a sequence \( \{a_n\} \) by \(e^x\) yields the exponential generating function of the sequence

\[ b_n = \sum_{k=0}^{n} \binom{n}{k} a_k \]

The same transformation on sequences from ordinary generating functions is performed by binomialTransform.

The inverse transformation, namely

\[ a_n = \sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} b_k \]

is obtained by multiplying by \(e^{ -x}\). The same transformation on sequences from ordinary generating functions is performed by inverseBinomialTransform.

Examples

• Maximal number of pieces obtained by cutting a circle with \(n\) lines (OEIS A000124).

>>> derivatives $ expS*fromDerivatives [1,1,1]
[1,2,4,7,11,16,22,29,37,46,56,67,79,92,106,121,137,154,172,191,211,232,...

• Maximal number of pieces obtained by cutting a sphere with \(n\) planes (OEIS A000125).

>>> derivatives $ expS*fromDerivatives [1,1,1,1]
[1,2,4,8,15,26,42,64,93,130,176,232,299,378,470,576,697,834,988,1160,...

• Maximal number of regions obtained by the straight lines joining \(n\) points around a circle (OEIS A000127).

>>> derivatives $ expS*fromDerivatives [1,1,1,1,1]
[1,2,4,8,16,31,57,99,163,256,386,562,794,1093,1471,1941,2517,3214,...

If \(a(x)\) is the exponential generating function of a sequence \(\{a_n\}\) with \(a_0 = 0\), then \(e^{a(x)}\) is the exponential generating function of the sequence

\[ b_n = \sum_{k=1}^{n} B_n(a_1, \ldots, a_n) \]

where \(B_n\) are complete Bell polynomials (see Data.YAP.FiniteMap).

Examples

• Bell numbers, the number of ways to partition \(n\) elements (OEIS A000110) have the exponential generating function \(e^{e^x - 1}\). Using integral expS instead of the equivalent expS - 1 avoids requiring subtraction:

>>> derivatives $ expS `compose` integral expS
[1,1,2,5,15,52,203,877,4140,21147,115975,678570,...

• The number of ways to partition \(n\) elements into sets of at least two elements (OEIS A000296) has the exponential generating function \(e^{e^x - x - 1}\).

>>> derivatives $ expS `compose` integral (integral expS)
[1,0,1,1,4,11,41,162,715,3425,17722,98253,580317,3633280,...

• The number of ways of partitioning \(n\) elements into lists (OEIS A000262) has the exponential generating function \(e^{x \over x - 1}\):

>>> derivatives $ expS `compose` (identity * recipOneMinus)
[1,1,3,13,73,501,4051,37633,394353,4596553,58941091,824073141,...

• Hermite numbers (OEIS A067994) have the exponential generating function \(e^{ -x^2}\):

>>> derivatives $ expS `compose` (- identity^2)
[1,0,-2,0,12,0,-120,0,1680,0,-30240,0,665280,0,-17297280,0,...

If \(a(x)\) is the exponential generating function of a sequence \( \{a_n\} \), then \(a(e^x-1)\) is the exponential generating function of the sequence

\[ b_n = \sum_{k=0}^n S(n, k) a_k \]

where the coefficients \(S(n,k)\) are Stirling numbers of the second kind (OEIS A048993).

The inverse transform \(b(\log (x+1))\) has exponential generating function

\[ a_n = \sum_{k=0}^n s(n, k) b_k \]

where the coefficients \(s(n,k)\) are Stirling numbers of the first kind (OEIS A048994).

Examples

• The expression for the Bell numbers given above is also a Stirling transform of \(e^x\):

>>> derivatives $ expS `compose` integral expS
[1,1,2,5,15,52,203,877,4140,21147,115975,678570,...

• The Stirling transform of \(x e^x\) generates the 2-Bell numbers (OEIS A005493):

>>> derivatives $ mulX expS `compose` integral expS
[0,1,3,10,37,151,674,3263,17007,94828,562595,3535027,23430840,...

• The Stirling transform of \(\cosh x\) generates the number of partitions of \(n\) elements into an even number of classes (OEIS A024430):

>>> derivatives $ coshS `compose` integral expS
[1,0,1,3,8,25,97,434,2095,10707,58194,338195,2097933,13796952,...

• The Stirling transform of \(\sinh x\) generates the number of partitions of \(n\) elements into an odd number of classes (OEIS A024429):

>>> derivatives $ sinhS `compose` integral expS
[0,1,1,2,7,27,106,443,2045,10440,57781,340375,2115664,13847485,...

• Fubini numbers, the number of weak orders on \(n\) elements (OEIS A000670) have the exponential generating function \( {1 \over 2 - e^x} = {1 \over 1 - (e^x - 1)} \), i.e. the Stirling transform of \( 1 \over 1-x \):

>>> derivatives $ recipOneMinus `compose` integral expS
[1,1,3,13,75,541,4683,47293,545835,7087261,102247563,1622632573,...

A polynomial sequence is a sequence of polynomials \(\{p_n(x)\}\) where each polynomial \(p_n\) has degree at most \(n\), so that the coefficients form a triangle. Such sequences can be defined by exponential generating functions of the form

\[ \sum_{n=0}^\infty p_n(x) {t^n \over n!} \]

An Appell sequence is a polynomial sequence with an exponential generating function of the form \(a(t)e^{xt}\), which can be constructed as constants a * monomials.

• Substituting \(x = 0\) shows that the original sequence is included as the constant terms of the polynomial sequence.
• Substituting \(x = 1\) shows that the sequence of sums of coefficients of the polynomials is generated by \(a(t)e^t\), the binomial transform of \(a(t)\).

If \(a(t)\) is an exponential generating function for a sequence \(\{a_n\}\), then \(a(t) e^{xt}\) is the exponential generating function for the polynomial sequence \(\{p_n(x)\}\) where

\[ p_n(x) = \sum_{k=0}^n {n \choose k} a_{n-k} x^k \]

Examples

The exponential generating function \(e^{(1+x)t} = e^t e^{xt}\) yields a sequence of polynomials with binomial coefficients (Pascal's triangle, OEIS A007318):

>>> derivatives $ constants expS * monomials
[fromCoefficients [1],
 fromCoefficients [1,1],
 fromCoefficients [1,2,1],
 fromCoefficients [1,3,3,1],
 fromCoefficients [1,4,6,4,1],
 fromCoefficients [1,5,10,10,5,1],...

The exponential generating function \(2 e^{xt} \over e^t + 1\) yields Euler polynomials (OEIS A060096 / OEIS A060097):

>>> derivatives $ constants (2 `div` (expS + 1)) * monomials
[fromCoefficients [1 % 1],
 fromCoefficients [(-1) % 2,1 % 1],
 fromCoefficients [0 % 1,(-1) % 1,1 % 1],
 fromCoefficients [1 % 4,0 % 1,(-3) % 2,1 % 1],
 fromCoefficients [0 % 1,1 % 1,0 % 1,(-2) % 1,1 % 1],
 fromCoefficients [(-1) % 2,0 % 1,5 % 2,0 % 1,(-5) % 2,1 % 1],...

The exponential generating function \(t e^{xt} \over e^t - 1\) yields Bernoulli polynomials (OEIS A196838 / OEIS A196839):

>>> derivatives $ constants (identity `div` (expS - 1)) * monomials
[fromCoefficients [1 % 1],
 fromCoefficients [(-1) % 2,1 % 1],
 fromCoefficients [1 % 6,(-1) % 1,1 % 1],
 fromCoefficients [0 % 1,1 % 2,(-3) % 2,1 % 1],
 fromCoefficients [(-1) % 30,0 % 1,1 % 1,(-2) % 1,1 % 1],...

A generalization of Appell sequences and sequences of binomial type is Sheffer sequences (or exponential Riordan arrays), which have exponential generating functions of the form

\[ \sum_{n=0}^\infty p_n(x) {t^n \over n!} = a(t) e^{x b(t)} \]

where \(b_0\) is zero and \(a_0\) and \(b_1\) are non-zero, which can be constructed as constants a * binomialType b.

Setting \(x = 1\) yields \( a(t) e^{b(t)} \), the exponential generating function of the sequence of sums of the coefficients of the rows.

Examples

The Hermite polynomials (OEIS A060821) have the exponential generating function

\[ \sum_{n=0}^\infty H_n(x) {t^n \over n!} = e^{2xt - t^2} = e^{ -t^2} e^{2xt} \]

>>> derivatives $ constants (expS .* (-1) .^ 2) * binomialType (2*identity)
[fromCoefficients [1],
 fromCoefficients [0,2],
 fromCoefficients [-2,0,4],
 fromCoefficients [0,-12,0,8],
 fromCoefficients [12,0,-48,0,16],
 fromCoefficients [0,120,0,-160,0,32],...

A variant of the Lah polynomials above yields the unsigned Laguerre polynomials, with exponential generating function

\[ e^{xt \over 1-t} \over 1-t \]

whose coefficents are the number of partial bijections of height \(k\) on an \(n\)-element set, or equivalently the number of ways to place \(k\) rooks on an \(n \times n\) chessboard with none attacking another (OEIS A144084):

>>> derivatives $ constants recipOneMinus * binomialType (identity * recipOneMinus)
[fromCoefficients [1],
 fromCoefficients [1,1],
 fromCoefficients [2,4,1],
 fromCoefficients [6,18,9,1],
 fromCoefficients [24,96,72,16,1],
 fromCoefficients [120,600,600,200,25,1],...

The sequence of Eulerian polynomials has the exponential generating function

\[ \sum_{n=0}^\infty \left( \sum_{k=0}^n A(n,k) x^k \right) \frac{t^n}{n!} = {x - 1 \over x - e^{(x-1)t}} = {1 \over 1 - {e^{(x-1)t} - 1 \over x - 1}} \]

where the coefficients \(A(n,k)\) are the Eulerian numbers (OEIS A008292), the number of permutations of the numbers 1 to \(n\) in which exactly \(k\) elements are greater than the previous element:

>>> import qualified Data.YAP.Polynomial as Poly
>>> derivatives $ recipOneMinus `compose` integral (expS .* Poly.fromCoefficients [-1, 1])
[fromCoefficients [1],
 fromCoefficients [1],
 fromCoefficients [1,1],
 fromCoefficients [1,4,1],
 fromCoefficients [1,11,11,1],
 fromCoefficients [1,26,66,26,1],...

All polynomials after the first have a leading coefficient of 0, which is not shown.

Faulhaber's formula expresses the sum \(\sum_{k=1}^n k^p\) as a polynomial of degree \(p+1\) in \(n\). For example,

\[ \begin{align} \sum_{k=1}^n k^0 & = n \\ \sum_{k=1}^n k^1 & = {n(n+1) \over 2} = {n^2 \over 2} + {n \over 2} \\ \sum_{k=1}^n k^2 & = {n(n+1)(2n+1) \over 6} = {n^3 \over 3} + {n^2 \over 2} + {n \over 6} \end{align} \]

The exponential generating function for this polynomial sequence (OEIS A220962 / OEIS A220963) is

\[ \int_0^t e^u {e^{xu} - 1 \over e^u - 1} du \]

>>> derivatives $ integral $ constants (mulX expS `div` (expS - 1)) * divX (monomials - 1)
[fromCoefficients [],
 fromCoefficients [0 % 1,1 % 1],
 fromCoefficients [0 % 1,1 % 2,1 % 2],
 fromCoefficients [0 % 1,1 % 6,1 % 2,1 % 3],
 fromCoefficients [0 % 1,0 % 1,1 % 4,1 % 2,1 % 4],
 fromCoefficients [0 % 1,(-1) % 30,0 % 1,1 % 3,1 % 2,1 % 5],
 fromCoefficients [0 % 1,0 % 1,(-1) % 12,0 % 1,5 % 12,1 % 2,1 % 6],...

(This expression uses mulX and divX to introduce cancelling factors so that the div divides exactly.)

The moment generating function of a random variable \(X\) is

\[ E[e^{tX}] = \sum_{n=0}^\infty m_n {t^n \over n!} \]

where \(m_n\) is the \(n\)th moment of the distribution of \(X\).

• one is the MGF for the constant random variable with value 0.
• expS is the MGF for the constant random variable with value 1.
• If pX is the MGF for the random variable \(X\), then the MGF for \(c X\) is pX .* c.
• The product of MGFs for independent random variables \(X\) and \(Y\) is the MGF for \(X+Y\).
• If a natural number valued random variable \(X\) has probability generating function \(f\) (see Data.YAP.PowerSeries), then its MGF is \(f(e^t)\). We can't express this using compose (because the constant term of \(e^t\) is non-zero), but can often find an equivalent expression.