Skip to main content

Ordinary Generating Functions as Encoded Counting

What This Concept Is​

An ordinary generating function (OGF) packages a sequence $a_0, a_1, a_2, \ldots$ into a formal power series:

$$A(x) = \sum_{n \ge 0} a_n x^n.$$

In counting, the coefficient of $x^n$ -- written $[x^n],A(x)$ -- records the number of objects of size $n$. The variable $x$ is a formal marker for size, not a quantity to be substituted with a number.

The key identity that makes OGFs powerful:

$$\text{If } A(x) \text{ counts objects of type } A \text{ by size, and } B(x) \text{ counts type } B, \text{ then}$$

$$A(x) \cdot B(x) \text{ counts ordered pairs } (a, b) \text{ by } \text{size}(a) + \text{size}(b).$$

In plain words: multiplication of generating functions encodes the convolution of independent size-additive choices. Summation encodes case splits. Exponents encode sizes. The arithmetic of power series corresponds exactly to the combinatorics of constructing larger objects from smaller parts.

Two small but vital closed forms to know by heart:

$$\frac{1}{1 - x} = 1 + x + x^2 + x^3 + \cdots \quad (\text{choose any number of unit parts})$$

$$\frac{1}{1 - x^k} = 1 + x^k + x^{2k} + \cdots \quad (\text{choose any number of parts of size } k)$$

$$\frac{1}{(1 - x)^k} = \sum_{n \ge 0} \binom{n + k - 1}{k - 1} x^n \quad (\text{stars-and-bars in series form})$$

The last identity is stars and bars rewritten -- a strong sign you are on the right track.

Operations on series have combinatorial meaning. Differentiation $\frac{d}{dx} A(x)$ multiplies $a_n$ by $n$, corresponding to "mark one of the $n$ parts"; multiplication by $x$ shifts the index, corresponding to "add a new distinguished element of size $1$"; the operator $\frac{1}{1-x}$ takes partial sums. Fluency with these four operations (product, sum, derivative, shift) covers 90% of undergraduate OGF manipulation.

Why It Matters Here​

Generating functions turn difficult counting questions into algebra on series. They are especially effective when:

  • independent part-sizes combine additively (coin-change, partition-into-parts, compositions)
  • repetition is allowed
  • a recurrence needs a closed form, and coefficient extraction beats direct casework
  • you need to prove identities between counting sequences by manipulating the power-series representation

They also shift your thinking from "count directly" to "encode, manipulate, extract." This shift is the foundation for Semester 2's more advanced algorithm analysis (amortized analysis, probabilistic recurrence solving) and Semester 3's dynamic-programming tabulation techniques.

A working engineer usually reaches for generating functions when:

  • a loop of combinatorial casework would fork into cases that differ only in which "coin" (unit of size) was added, and you want to replace that fork with an algebraic product.
  • a recurrence is easy to write but hard to solve, and you suspect a closed form or at least a generating-function-based asymptotic.
  • you need to extract one specific coefficient $[x^N]$ where $N$ is large but the structure is simple (partial fractions give $O(1)$ per root).

Concrete Examples​

Example 1: partitions into $1$s and $2$s. The number of ways to write $n$ as an unordered sum using parts of size $1$ and $2$ (e.g., $4 = 1+1+1+1 = 1+1+2 = 2+2$, giving $3$ for $n=4$).

  • Factor for parts of size $1$: $1 + x + x^2 + \cdots = \frac{1}{1-x}$ (choose any number of $1$s).
  • Factor for parts of size $2$: $1 + x^2 + x^4 + \cdots = \frac{1}{1-x^2}$ (choose any number of $2$s).

Product:

$$A(x) = \frac{1}{(1-x)(1-x^2)}.$$

The coefficient $[x^n] A(x)$ is the number of ways to write $n = a + 2b$ with $a, b \ge 0$, which is $\lfloor n/2 \rfloor + 1$. For $n = 4$: $\lfloor 2 \rfloor + 1 = 3$. ✓

Example 2: coin-change ($1$¢, $5$¢, $10$¢, $25$¢). The number of ways to make $n$ cents from pennies, nickels, dimes, and quarters.

$$C(x) = \frac{1}{1-x} \cdot \frac{1}{1-x^5} \cdot \frac{1}{1-x^{10}} \cdot \frac{1}{1-x^{25}}.$$

The coefficient $[x^{100}] C(x)$ is the number of ways to make change for a dollar ($= 242$, a classic result). Direct enumeration of the $242$ combinations is tedious; expanding the generating function (for instance by convolution) is mechanical.

Example 3: restricted compositions. Count compositions of $n$ into parts of size $1$ or $2$ (ordered sums). Each position in the composition independently chooses a $1$-part or $2$-part, which are encoded by a single factor $(x + x^2)$, and an arbitrary number of positions by

$$K(x) = \frac{1}{1 - (x + x^2)}.$$

The coefficient $[x^n] K(x)$ is the Fibonacci number $F_{n+1}$. This matches the structural recurrence from the previous concept, and here it drops out of the algebraic manipulation with no case analysis.

Example 4: extracting a specific coefficient. Find $[x^{20}]$ in $\frac{1}{(1-x)(1-x^2)(1-x^5)}$. This is the number of ways to partition $20$ into parts of size $1$, $2$, or $5$. By the standard partial-fraction decomposition of $\frac{1}{(1-x)(1-x^2)(1-x^5)}$ one obtains a closed form that is a polynomial in $n$ plus periodic corrections. Plugging $n = 20$ gives $29$ partitions (verifiable by direct enumeration on a small computer). The point is that the method is mechanical: decompose, identify coefficient in each piece, sum.

Common Confusion / Misconceptions​

  • Treating $x$ as a number. In this context $x$ is a formal marker. Questions of convergence are secondary; coefficient bookkeeping is primary. Do not ask "what if $x = 2$?"
  • Writing factors without combinatorial meaning. Every factor in a product must correspond to a specific combinatorial choice family (e.g., "how many $2$s to use"). If you cannot explain what a factor counts, your derivation has drifted into formalism.
  • Confusing ordinary and exponential generating functions. OGF is for unlabeled/unordered structures where convolution is additive in size; exponential generating functions (EGF, $\sum a_n x^n/n!$) handle labeled structures where multiplication encodes interleaving of labels. This cluster is OGF-only; EGFs are a topic for later.
  • Missing the empty object. Almost every factor starts with a "$1$" term (the choice of zero parts). Forgetting it omits the empty contribution and shifts the index.
  • "Closed form = easier" fallacy. A rational closed form $P(x)/Q(x)$ is not automatically easier to extract coefficients from than the original product. Always ask: is the denominator factorable into simple roots (geometric series), or will I need partial fractions? If partial fractions are ugly, sometimes the original product form is the computational answer.

How To Use It​

To build a generating function for a counting problem:

  1. decide what the exponent represents (usually total size $n$).
  2. identify the independent choice families. Each independent family becomes a factor in the product.
  3. for each factor, write a power series whose allowed exponents are the allowed contributions to total size.
  4. multiply the factors.
  5. simplify using closed forms for $1/(1-x^k)$ or partial fractions where appropriate.
  6. extract the coefficient of $x^n$ by known series expansions, recurrence unrolling, or computer algebra.
  7. sanity check: the constant term should count the empty object (typically $1$); $[x^1] A(x)$ should count minimal objects.

Always explain the combinatorial meaning of each factor before simplifying algebraically. If you cannot, the algebra is formal but undisciplined.

Transfer / Where This Shows Up Later​

  • Semester 2 algorithms: generating functions solve many recurrence runtimes. The Akra-Bazzi theorem generalizes the Master Theorem via generating-function machinery. Approximate counting (Flajolet-Martin) uses GF analysis of probabilistic processes.
  • Semester 3 data structures: Catalan, Motzkin, Schröder numbers -- all with explicit OGFs -- count BSTs, triangulations, and lattice paths arising in data-structure design.
  • Semester 4 databases: query-cost estimation models the combinatorial size of intermediate result sets; OGFs give tight bounds on worst-case output cardinality.
  • Semester 5 OS: distribution of workload across cores, modeled as a sum of independent job sizes, is an OGF convolution.
  • Semester 6 distributed systems: failure-probability generating functions compute the probability of $k$ of $n$ replicas failing -- often through a product $\prod_i (p_i + q_i x)$ whose coefficient $[x^k]$ is exactly the $k$-failure probability.

Check Yourself​

  1. What does the coefficient of $x^n$ represent in a counting OGF?
  2. Why does multiplication of generating functions encode independent additive choices?
  3. What is the factor for "choose any nonnegative number of parts of size $5$"?
  4. Derive $\frac{1}{(1-x)^2} = \sum_{n \ge 0} (n+1) x^n$ by pairing the two $\frac{1}{1-x}$ factors combinatorially.
  5. Why is the coin-change problem for ${1, 5, 10, 25}$ naturally a product of four factors, not a sum?
  6. For the generating function of Example 1, predict $[x^7] A(x)$ before computing: it should equal $\lfloor 7/2 \rfloor + 1 = 4$. What four partitions realize it?
  7. If $A(x) = \sum_{n \ge 0} a_n x^n$, what sequence does $xA'(x)$ encode? Give a one-sentence combinatorial interpretation.

Mini Drill or Application​

Write, but do not yet simplify, generating functions for the following. State the combinatorial meaning of each factor.

  1. Partitions of $n$ into parts of size $1$, $3$, and $4$.
  2. Ways to make $n$ cents from pennies and nickels only.
  3. Binary strings where each 1 contributes weight $2$ and each 0 contributes weight $1$ (counted by total weight).
  4. Compositions of $n$ into an odd number of parts, each part size $\ge 2$.
  5. Ways to tile a $1 \times n$ board with tiles of sizes $1, 2, 3$ where tiles of each size carry an individual color (so a size-$2$ red tile differs from a size-$2$ blue tile). (Hint: the factor for position-by-position placement becomes $(x + 2x^2 + 3x^3)$ if each size $k$ has $k$ colors.)

Read This Only If Stuck​