GeneratingFunction

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

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

GeneratingFunction(expr, n, x)the ordinary generating function of expr(n) in x

Typed signatures

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

Domain: Combinatorics

Details

• C-finite sequences (satisfying a constant-coefficient linear recurrence -- Fibonacci-like sequences, fixed-$k$ binomials, polynomials in $n$, geometric terms, and any combination of those) get a rational generating function, found from the recurrence by Berlekamp--Massey -- there is no family-specific code.
• A handful of named, non-C-finite sequences are recognised directly by value, not by name: the Catalan numbers have the algebraic generating function $(1-\sqrt{1-4x})/(2x)$.
• Count(Family(n)) is not special-cased either: it is sampled numerically like any other sequence, so a family whose cardinality happens to be Catalan (or any C-finite sequence) gets the matching closed form automatically.
• Falls back to staying symbolic when no closed form is found (e.g. $n!$ has none), the same as Wolfram.

Examples

Basic #

$x/(1-x-x^2)$

live ↗

In$\mathrm{GeneratingFunction}(\mathrm{Fibonacci}(n), n, x)$Out$\frac{x}{-x^2-x+1}$

$(1-\sqrt{1-4x})/(2x)$ -- algebraic, not rational: Catalan numbers are not C-finite

live ↗

In$\mathrm{GeneratingFunction}(\mathrm{CatalanNumber}(n), n, x)$Out$\frac{1-\sqrt{1-4x}}{2x}$

the same Catalan generating function, reached through a collection's cardinality rather than CatalanNumber directly

live ↗

In$\mathrm{GeneratingFunction}(\mathrm{Count}(\mathrm{DyckPaths}(n)), n, x)$Out$\frac{1-\sqrt{1-4x}}{2x}$

$x^3/(1-x)^4$

live ↗

In$\mathrm{GeneratingFunction}(\binom{n}{3}, n, x)$Out$\frac{x^3}{x^4-4x^3+6x^2-4x+1}$

$1/(1-2x)$

live ↗

In$\mathrm{GeneratingFunction}(2^{n}, n, x)$Out$\frac{1}{1-2x}$

The constant sequence $1$ sums to the geometric series $1/(1-x)$

live ↗

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

Scope #

$n!$ has no elementary ordinary generating function -- stays unevaluated, as Wolfram does too

live ↗

In$\mathrm{GeneratingFunction}(n!, n, x)$Out$\mathrm{GeneratingFunction}(n!, n, x)$

live ↗

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

live ↗

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

live ↗

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

The sequence $n$ gives $z/(1-z)^2$

live ↗

In$\mathrm{GeneratingFunction}(n, n, z)$Out$\frac{z}{z^2-2z+1}$

Properties #

The squares give $z(1+z)/(1-z)^3$, one more pole order than $n$

live ↗

In$\mathrm{GeneratingFunction}(n^2, n, z)$Out$\frac{z^2+z}{-z^3+3z^2-3z+1}$

live ↗

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

Possible issues #

live ↗

In$\bigl\lbrack\sum_{n=0}^{∞}2^{n}, \mathrm{GeneratingFunction}(2^{n}, n, 1)\bigr\rbrack$Out$\bigl\lbrack∞, -1\bigr\rbrack$

About

Examples	14
Checked against	Wolfram Language 11 agree2 differ
Crosswalk	Wolfram Language

See also: ExponentialGeneratingFunction, FindSequenceFunction, DiscreteRatio