Combinatorial generating function: Definition & Examples

A combinatorial generating function stores a sequence of counts as the coefficients of a power series. Algebra on the series then counts objects built from simpler objects. For a quant, this can turn a constrained scenario or execution-sequence count into a coefficient calculation—before any probabilities or prices are assigned.

The ordinary generating function (OGF) of counts $a_0,a_1,\ldots$ is

A(z)=\sum_{n\geq0}a_nz^n, \qquad [z^n]A(z)=a_n.

Here

n

measures size and

[z^n]

means “take the coefficient of

z^n

.” The symbol

z

is a bookkeeping variable. Initially, the series is formal: equality means equality of every coefficient; no numerical value of

z

or convergence assumption is needed. Convergence matters if we later evaluate an infinite series numerically. Hulpke’s university notes develop this coefficient-based arithmetic.

A sequence of one- and two-unit blocks

Consider a toy execution planner that permits blocks of one or two units. Count every ordered block-size sequence with total quantity $n$ ; there are no timing, price or liquidity constraints. Thus $(1,1,2)$ and $(2,1,1)$ are different sequences. This is a count of admissible plans, with no claim that plans are equally likely.

Let

a_n

be the count. The empty sequence gives

a_0=1

, and

a_1=1

. Every nonempty sequence ends in either a 1-unit block or a 2-unit block. Remove that final block and the remaining total is

n-1

n-2

. These cases are disjoint and exhaustive, giving the recurrence relation

a_n=a_{n-1}+a_{n-2},\qquad n\geq2.

At total quantity four, the five sequences are

(1,1,1,1),\quad(1,1,2),\quad(1,2,1),\quad(2,1,1),\quad(2,2).

Five ordered sequences of total size four: 1111, 121 and 211 end in one; 112 and 22 end in two. Their counts are three plus two equals five. Counts for total sizes zero through four are one, one, two, three and five.

Original counting illustration: the final block separates the five sequences into groups of three and two. The coefficient records the count at each total quantity.

One block has generating function $B(z)=z+z^2$ . A sequence is either empty or a shorter sequence followed by one block, so

A(z)=1+A(z)(z+z^2).

Solving as a formal power-series identity,

A(z)=\frac{1}{1-z-z^2} =1+z+2z^2+3z^3+5z^4+\cdots.

The constant term 1 in the denominator makes the formal inverse well defined. Another way to read the answer is

A(z)=\sum_{k\geq0}(z+z^2)^k.

The

k

th term counts sequences with exactly

k

blocks. At any fixed total quantity

n

, only

k\leq n

can contribute. This is why the infinite sum is legitimate formally. The sequence construction requires positive-size blocks: permitting arbitrarily many zero-size blocks would create infinitely many sequences of the same total size. See Aspnes’s counting constructions for the sum, product and repetition rules.

Why multiplying counts works

Suppose $U(z)$ counts choices for a first component and $V(z)$ counts choices for a second. Then

[z^n]U(z)V(z)=\sum_{j=0}^{n}u_jv_{n-j}.

This convolution sums over every split of total size $n$ . Within a split, choose either component freely, so the counts multiply. The decomposition must identify each resulting object uniquely; otherwise the product counts construction histories rather than the intended objects.

For the blocks above, $(z+z^2)^2=z^2+2z^3+z^4$ : the coefficient 2 represents the distinct pairs $(1,2)$ and $(2,1)$ . Multiplication here expresses combinatorial choices; it does not assert probabilistic independence.

Ordinary, exponential and probability generating functions

The coefficient convention changes what multiplication means.

Encoding	Series	Recover the quantity
Ordinary generating function	$A(z)=\sum a_nz^n$	$a_n=[z^n]A(z)$
Exponential generating function	$E(z)=\sum a_nz^n/n!$	$a_n=n![z^n]E(z)$
Probability generating function	$G_X(z)=\sum \mathbb{P}(X=n)z^n$	$\mathbb{P}(X=n)=[z^n]G_X(z)$

An exponential generating function (EGF) is particularly useful for labelled objects. In a labelled product, distributing

n

distinct labels between two components of sizes

j

and

n-j

introduces the binomial coefficient

\binom{n}{j}

. EGF multiplication incorporates it:

n![z^n]E_U(z)E_V(z) =\sum_{j=0}^{n}\binom{n}{j}u_jv_{n-j}.

For example, a set has one structure on any given label set, hence EGF

e^z

. Assigning each label to either of two named sets gives

e^ze^z=e^{2z}

and count

2^n

. At

n=3

, the coefficient is

8/3!=4/3

, but the count is 8. Forgetting the factorial changes the answer. These product conventions are explained in Aspnes’s variants section.

A probability generating function instead has nonnegative coefficients summing to one, so $G_X(1)=1$ . The counting series $A$ above is not a PGF. To introduce probability, specify a sampling model. If we choose uniformly from the five total-four sequences and let $K$ be the number of blocks, then

G_K(t)=\frac{t^2+3t^3+t^4}{5}.

There is one two-block sequence, three three-block sequences and one four-block sequence. Here

t

tracks number of blocks, whereas

z

A(z)

tracks total units. Counting alone supplies neither that uniform sampling rule nor a discount factor for pricing. Norris’s probability notes, §13.1 give the PGF definition.

For the underlying choice between ordered selections, subsets and labelled partitions, Counting and Combinatorics develops the counting principles with worked examples. Its preview is public; full lesson access requires membership.

Change the permitted blocks

A planner now permits blocks of size 1 or 3. How many ordered sequences total six units? Why would counting only unordered block collections give a different answer?

Answer. The OGF is

1/(1-z-z^3)

. There is one sequence of six 1s; four sequences with one 3 and three 1s, because the 3 can occupy any of four positions; and one sequence

(3,3)

. Therefore

[z^6](1-z-z^3)^{-1}=1+4+1=6

. Ignoring order leaves only three collections. That counts a different class of objects and discards the planner’s sequence information.

Sources

Alexander Hulpke, Colorado State University: Combinatorics, Chapter 2, §1 — formal power series, equality and coefficient arithmetic.
James Aspnes, Yale University: Generating Functions, §§4, 5, 10–11 — combinatorial constructions, recurrences and EGF product conventions.
J. R. Norris, Cambridge: Probability, §13.1 — probability generating functions and normalization.

A sequence of one- and two-unit blocks

Why multiplying counts works

Ordinary, exponential and probability generating functions

Change the permitted blocks

Sources

Related terms

Binomial coefficient

Factorial

Recurrence relation