6.3 Generating Functions: Encoding Counting Sequences into Algebraic Motifs

As the number of supply options grows, the combinatorial explosion quickly overwhelms the tallying staff. Tower counters encode entire sequences of counts into a single power series.

When counting constraints involve "multiple selections allowed per category," "total count exactly equal to n," or "combinations of multiple components," manually enumerating all possibilities becomes unwieldy. Generating functions embed a sequence into the coefficients of a power series, transforming combinatorial choices into polynomial multiplication.

Ordinary Generating Functions

A sequence:

a₀, a₁, a₂, ...

has an ordinary generating function (OGF):

A(x) = Σ_{n≥0} a_n x^n

x is a formal variable representing scale, and [x^n]A(x) denotes the coefficient of x^n:

a_n = [x^n]A(x)

A generating function does not compute individual terms of a sequence by plugging values into a function; instead, it packages the entire sequence of coefficients, enabling algebraic manipulation of counts.

How Choosing Counts Become Polynomials

A component can be selected 0, 1, or 2 times:

1 + x + x²

Another component can be selected 0 or 3 times:

1 + x³

When selecting from both categories simultaneously, multiply the expressions:

(1 + x + x²)(1 + x³)
= 1 + x + x² + x³ + x⁴ + x⁵

The coefficient of x⁴ is 1, indicating one combination that totals 4: one instance of the first component and three of the second.

If multiple sources can contribute to the same total in different ways, the coefficients of like powers in the expanded product sum automatically, completing the count without manual intervention.

Infinite Geometric Series

A certain kind of object may have zero or more instances:

1+x+x²+...=1/(1-x)

As a formal power series, this identity arises from:

(1-x)(1+x+x²+...)=1

If there are k class objects, any number per class:

1/(1-x)^k

Its x^n coefficient is:

C(n+k-1,k-1)

This matches the combinatorial formula obtained by the partition method.

Coin Change Generating Functions

Given coin denominations 1,2,5, where each type can be used any number of times, and combinations are considered unordered:

G(x) = 1 / [(1 - x)(1 - x²)(1 - x⁵)]

[x^n]G(x) represents the number of ways to make amount n using these coins.

If each coin type can be used at most once:

(1 + x)(1 + x²)(1 + x⁵)

If the 2-yuan coin is limited to at most three coins:

1 + x² + x⁴ + x⁶

Each factor in the generating function directly encodes a local constraint on coin usage.

Note: The order of coins is not considered here. If 1+2 and 2+1 are treated as distinct sequences, a different model is required.

Solving the Fibonacci Recurrence with Generating Functions

Define:

F₀=0, F₁=1
Fₙ=Fₙ₋₁+Fₙ₋₂

Let:

F(x)=Σ_{n≥0}Fₙxⁿ

Multiply the recurrence relation by xⁿ and sum over all n ≥ 2:

F(x)-x = xF(x)+x²F(x)

Thus:

F(x)=x/(1-x-x²)

Factor the denominator and perform partial fraction decomposition to recover Binet's formula. Generating functions transform recursive relationships into algebraic equations, this is one of their core applications in combinatorics.

n≥2xⁿ

Convolution Corresponds to Combinatorial Partitioning by Scale

If:

A(x) = Σ a_n x^n
B(x) = Σ b_n x^n

then:

[x^n] A(x)B(x) = Σ_{k=0..n} a_k b_{n-k}

The right-hand side represents discrete convolution: it partitions the total scale n into k and n-k, selecting one component from A and one from B.

This kind of decomposition appears in problems such as parsing bracketed structures, counting parenthetical expressions, string concatenation, and dynamic programming. Convolution in algorithms can be accelerated using techniques like FFT, though numerical precision and modulus selection are topics for later discussion.

When Exponential Generating Functions Appear

When objects are labeled, ordinary generating functions (OGFs) often fail to directly handle label assignments. Exponential generating functions (EGFs) are written as:

A(x) = Σ a_n x^n / n!

They are well-suited for problems involving permutations, labeled structures, and set partitions. The multiplication rules for OGFs and EGFs encode different combinatorial operations, and the two should not be conflated simply because of their similar names.

This lesson establishes a clear distinction:

• OGFs are typically used for unlabeled combinations counted by size;
• EGFs are typically used for labeled objects;
• The specific choice depends on the structure of the combinatorial class, not on mechanically selecting an EGF whenever factorials appear.

State Counting in Software

Generating functions are well-suited for counting constrained configurations. For example, with 10 plugins:

• Each foundational plugin is optional: a factor of (1+x);
• A certain class of plugins can be selected at most twice: a factor of 1+x+x²;
• Each plugin may have different weights, allowing the exponent to track cost rather than just count.

However, software states often involve dependencies and exclusions, making it inadvisable to blindly multiply individual option factors. If plugin B depends on plugin A, we can:

• Partition the options into "not selecting A, therefore not selecting B" and "selecting A, then deciding whether to select B";
• Construct a finite state machine and use a transition matrix to model state evolution;
• Apply SAT/SMT or BDD techniques to count satisfying assignments.

The resulting count may still overcount configurations that are behaviorally equivalent. To properly quotient by symmetry, more advanced tools such as group actions and Burnside’s Lemma are required.

From Scale to Testing Strategy

Knowing that the state space is vast only proves that exhaustive testing is infeasible. The next steps must include:

• Identifying reachable states under constraints;
• Selecting boundary and representative cases based on risk;
• Using pairwise coverage to test t-way interactions;
• Employing property-based testing to generate and shrink counterexamples;
• Applying solvers or model checking to critical finite models.

Pairwise coverage ensures that every pair of parameter values appears together at least once, but it does not guarantee the detection of all three-way or higher-order interaction defects, nor does it prove system correctness.

Completion Checklist

1. Write the ordinary generating functions (OGFs) for each of the four component types, with at most three components per type;
2. Calculate the total number of ways to select five components;
3. Derive the generating function for coins of denominations 1, 3, and 4 with unlimited supply;
4. Derive the generating function for the recurrence relation a_n=2a_{n-1}+1;
5. Explain why simple multiplication in a plugin configuration with dependencies overcounts invalid states.

References

• MIT Mathematics for Computer Science
• generatingfunctionology