ExponentialGeneratingFunction

The exponential generating function $\sum_n \mathrm{expr}(n)\,x^n/n!$ of a sequence, in closed form, when one exists.

✓ checked against that system · ! checked, with disagreements (hover a chip)Wolfram LanguageExponentialGeneratingFunction!↗

ExponentialGeneratingFunction(expr, n, x)the exponential generating function of expr(n) in x

Typed signatures

Type	Package	Applies
(any, symbol, symbol) -> any	combinatorics	always

Domain: Combinatorics

Details

• For a C-finite sequence of recurrence order at most 2 (Fibonacci-like sequences), the characteristic roots come straight out of the compute engine's own Sqrt/arithmetic, so an irrational discriminant stays exact rather than being hand-simplified -- e.g. Fibonacci's $\sqrt5$.
• A small registry covers named factorial-growth sequences that are not C-finite at all -- $n!$, the derangement numbers, and the Bell numbers -- each with a textbook closed form.
• Higher-order C-finite sequences and other non-C-finite sequences stay symbolic: only order ≤ 2 is attempted here.

Examples

Basic #

$1/(1-x)$

live ↗

In$\mathrm{ExponentialGeneratingFunction}(n!, n, x)$Out$\frac{1}{1-x}$

$e^{-x}/(1-x)$

live ↗

In$\mathrm{ExponentialGeneratingFunction}(\mathrm{Subfactorial}(n), n, x)$Out$\frac{e^{-x}}{1-x}$

$e^{e^x-1}$ -- the exponential formula for set partitions

live ↗

In$\mathrm{ExponentialGeneratingFunction}(\mathrm{BellNumber}(n), n, x)$Out$e^{e^{x}-1}$

Binet's formula, exponentiated -- built from the order-2 recurrence's own roots $(1\pm\sqrt5)/2$

live ↗

In$\mathrm{ExponentialGeneratingFunction}(\mathrm{Fibonacci}(n), n, x)$Out$\frac{1}{5}\sqrt{5}e^{\frac{1}{2}x×(1+5^{1/2})}-\frac{1}{5}\sqrt{5}e^{\frac{1}{2}x×(1-5^{1/2})}$

The constant sequence $1$ has exponential generating function $e^x$

live ↗

In$\mathrm{ExponentialGeneratingFunction}(1, n, x)$Out$e^{x}$

Scope #

live ↗

In$\bigl\lbrack\mathrm{ExponentialGeneratingFunction}(\mathrm{UnitStep}(n), n, z), \mathrm{ExponentialGeneratingFunction}(\mathrm{UnitStep}(n-3), n, z)\bigr\rbrack$Out$\bigl\lbrack e^{z}, -\frac{z^2}{2}-z+e^{z}-1\bigr\rbrack$

live ↗

In$\bigl\lbrack\mathrm{ExponentialGeneratingFunction}(n\mathrm{UnitStep}(n), n, z), \mathrm{ExponentialGeneratingFunction}((n-3)\mathrm{UnitStep}(n-3), n, z)\bigr\rbrack$Out$\bigl\lbrack ze^{z}, \frac{z^2}{2}+2z+(z-3)e^{z}+3\bigr\rbrack$

live ↗

In$\bigl\lbrack\mathrm{ExponentialGeneratingFunction}(n, n, z), \mathrm{ExponentialGeneratingFunction}(n^2, n, z)\bigr\rbrack$Out$\bigl\lbrack ze^{z}, (z^2+z)e^{z}\bigr\rbrack$

A compound argument substitutes through: $\sum z^{-n}/n! = e^{1/z}$

live ↗

In$\mathrm{ExponentialGeneratingFunction}(1, n, \frac{1}{z})$Out$\sqrt[z]{e}$

Fibonacci numbers give a difference of two exponentials with exponents $z\varphi$ and $z\bar\varphi$, via Binet's formula

live ↗

In$\mathrm{ExponentialGeneratingFunction}(\mathrm{Fibonacci}(n), n, z)$Out$\frac{1}{5}\sqrt{5}e^{\frac{1}{2}z×(1+5^{1/2})}-\frac{1}{5}\sqrt{5}e^{\frac{1}{2}z×(1-5^{1/2})}$

Properties #

live ↗

In$\bigl\lbrack\mathrm{ExponentialGeneratingFunction}(n, n, z), \mathrm{GeneratingFunction}(\frac{n}{n!}, n, z)\bigr\rbrack$Out$\bigl\lbrack ze^{z}, \mathrm{GeneratingFunction}(\frac{n}{n!}, n, z)\bigr\rbrack$

live ↗

In$\mathrm{ExponentialGeneratingFunction}(n^2, n, z)$Out$(z^2+z)e^{z}$

About

Examples	12
Checked against	Wolfram Language 11 agree1 differ
Crosswalk	Wolfram Language

See also: GeneratingFunction, FindSequenceFunction, DiscreteRatio