Generating Function

A generating function is a formal power series

(1)

whose coefficients give the sequence .

The Wolfram Language command GeneratingFunction[expr, n, x] gives the generating function in the variable for the sequence whose th term is expr. Given a sequence of terms, FindGeneratingFunction[{a1, a2, ...}, x] attempts to find a simple generating function in whose th coefficient is .

Given a generating function, the analytic expression for the th term in the corresponding series can be computed using SeriesCoefficient[expr, {x, x0, n}]. The generating function is sometimes said to "enumerate" (Hardy 1999, p. 85).

Generating functions giving the first few powers of the nonnegative integers are given in the following table.

		series
1

There are many beautiful generating functions for special functions in number theory. A few particularly nice examples are

			(2)
			(3)
			(4)

for the partition function P, where is a q-Pochhammer symbol, and

			(5)
			(6)
			(7)

for the Fibonacci numbers .

Generating functions are very useful in combinatorial enumeration problems. For example, the subset sum problem, which asks the number of ways to select out of given integers such that their sum equals , can be solved using generating functions.

Generalized generating functions can enumerate objects whose sizes are nonnegative real numbers. Let count the objects of size , and assume that only finitely many objects have size at most for every finite . The corresponding series is

(8)

where is the set of sizes that occur. Its associated Dirichlet series is

(9)

For real in the region of convergence, . A Tauberian theorem applied to can give asymptotic estimates for the cumulative count , even when the individual coefficients fluctuate (Bevan and Condé 2026, pp. 3-4, 27, 32-33).

The generating function of of a sequence of numbers is given by the Z-transform of in the variable (Germundsson 2000).