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.

For $A(x)=\sum a_nx^n$, the operator $xA'(x)$ has coefficients $na_n$ and preserves size; differentiation alone also shifts powers downward. Multiplication by $x$ shifts size by one, and division by $1-x$ takes prefix sums of coefficients. Give each operation a model before assigning it a combinatorial interpretation.

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 may give a compact expression; exponentiation and large-integer arithmetic still have a cost.

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.
• Ordinary versus exponential normalization. Any sequence admits an OGF. Ordinary multiplication convolves counts by size; exponential normalization is useful when the product construction also chooses how labels are distributed. Ordered objects can certainly be counted with OGFs.
• 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 to the workshop model

Use this concept to justify or challenge one result in the workshop project. Specify the counted objects or graph semantics before interpreting any numerical output.

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

Use the bounded reading guide to locate the topic in MCS or Rosen. These links open indexes. Check the actual heading in your edition, read one targeted explanation, then reconstruct the argument with the book closed.

Formal operations keep size conventions visible

If A(x)=Σaₙxⁿ, then xA′(x)=Σn·aₙxⁿ preserves size while marking one of n distinguishable positions. A′ alone shifts powers downward. Such a marking interpretation requires the modeled objects to have n markable features; the algebraic identity holds whether or not that interpretation is useful.

Any sequence can be recorded in an ordinary generating function, including counts of ordered objects. Multiplication convolves sizes without a binomial label-interleaving factor. Exponential normalization is useful when that label choice is part of the construction. The formal geometric series for arbitrary sequences of parts requires a part series with zero constant coefficient, so each target coefficient receives finitely many contributions. Transfer: P10–P11.

After your attempt use practice feedback and model contracts to check the argument.