Generating functions: counting with algebra

First decide what counts as one way

First make the rules precise. We may use at most two one-unit coins and at most one two-unit coin, including none of either kind. Coins of the same value have no identifying labels, so we do not distinguish which particular coin was used. A separate rule says that a payment records the quantity of each value, not the order of handing them over. Thus “1 then 2” and “2 then 1” both leave the record “one 1 and one 2”. Below we can change what the record contains and inspect the difference.

Let $a$ name the number of one-unit coins and let $b$ name the number of two-unit coins. These letters name quantities: $a$ may be 0, 1 or 2, while $b$ may be 0 or 1. Each coin of the second kind contributes 2 units, so the amount is $a + 2b$. For example, $a = 1$ and $b = 1$ give $1 + 2 \times 1 = 3$ units.

For each a, we have the two choices $b = 0$ and $b = 1$. There are therefore $3 \times 2 = 6$ pairs of counts: (0,0), (0,1), (1,0), (1,1), (2,0), (2,1). We group them by a, and each group has exactly the two possible values of $b$. This includes every pair once. Their totals are 0, 2, 1, 3, 2 and 4, respectively.

The numbers of ways to make totals 0, 1, 2, 3 and 4 are therefore 1, 1, 2, 1 and 1. There is one way to make zero: take neither kind. That is a definite choice, different from having no legal choice at all. Next we want to keep this table of totals and counts in a form that also helps us calculate.

Can the record help us calculate?

Our ordinary table contains two different pieces of information: the amount paid, and how many payments give that amount. “Amount 2” and “2 ways” both contain a 2, but mean different things. Two columns keep them apart. We also want the record to help combine choices: a contribution of 2 joined to a contribution of 3 must record 5. Can we find a notation whose multiplication adds the recorded amounts?

Use the letter $x$ as a marker. Two copies multiplied together are written $x^{2}$, and three are written $x^{3}$. The raised number is the exponent; it tells us how many copies of $x$ are multiplied. Now $x^{2}x^{3}=(x\times x)(x\times x\times x)=x^{5}$: the groups of 2 and 3 contain 5 copies altogether. This is the rule we need, so we choose the exponent to record the amount. Here $x$ does not name a coin and we do not substitute the amount for it. The amount is already in the exponent.

For amount zero, there are no copies of $x$ to join. We write its record as $x^0=1$. Why 1? Joining a payment to “pay nothing” must leave its amount unchanged, and multiplying by 1 leaves the other term unchanged too. This convention lets zero follow the same combination rule.

Each choice contributes one term. If two different choices both give total 2, they contribute $x^{2} + x^{2} = 2x^{2}$. The 2 in front is the coefficient: it counts ways. The 2 above $x$ is the exponent: it records the total. If there is no way to make 5, its term is $0x^{5}$, which we usually leave unwritten. Our table therefore becomes:

For example, the term $2x^{2}$ reads “total 2, two ways”. The constant term 1 reads “total zero, one way”. To answer a question about one total, we find that exponent and read its coefficient; we do not evaluate the whole expression at that total.

Why do we sometimes add and sometimes multiply?

Begin with addition. Return to our two opening pictures: take two 1s, or take one 2. These choices do not overlap, because the first has no two-unit coin and the second has one. Each contributes $x^{2}$, giving $x^{2} + x^{2} = 2x^{2}$: two ways to make total 2. Addition counts alternatives when the groups of choices do not overlap. If the same choice appears in both lists, adding their counts would count it twice.

Now return to the coins. We are not choosing one kind instead of the other: we make a choice for each kind. Taking 0, 1 or 2 one-unit coins gives $A(x) = 1 + x + x^{2}$. Taking 0 or 1 two-unit coin gives $B(x) = 1 + x^{2}$. We need one term from A together with one term from $B$. Each expression being multiplied is called a factor, so $A$ and $B$ are our two factors.

When we combine two choices, their totals must add. Multiplication does exactly this: $x^{2}x^{3} = (x \times x)(x \times x \times x) = x^{5}$. The two groups contain $2 + 3 = 5$ copies of $x$. In general, joining $i$ copies and $j$ copies gives $i + j$ copies, so $x^{i}x^{j} = x^{i+j}$. If either exponent is zero, its factor is 1 and leaves the other total unchanged, just as choosing nothing should.

Why does multiplying the brackets list every choice? By the distributive law, each term of A multiplies the whole of $B$. This means multiplying it by each of $B$’s two terms and adding the results. Each choice from A is therefore paired once with every choice from $B$. Writing every intermediate term lets us check the pairs:

The table below keeps all six pairings visible. Choose a target, then press “Count next pair”. Each matching cell contributes 1, and its contribution stays in the running count. The other cells remain visible too. Blue coins are marked 1 and gold coins are marked 2; their written values identify them as well as their colours.

For target 2, one pair uses the constant term of $A$ and the $x^{2}$ term of $B$. This means zero one-unit coins and one two-unit coin. Another uses the $x^{2}$ term of $A$ and the constant term of $B$: two one-unit coins and zero two-unit coins. Each pair contributes $x^{2}$, so the coefficient becomes $1+1=2$. The two contributions retain the two payments we began with.

Read the general rule from the small table

Later we write $a_{n}$ for the number of ways to make total $n$. The subscript tells us which total we mean: $a_{0}$ is the count for zero and $a_{1}$ the count for one. They are not a multiplied by 0 or by 1. The expression that places these numbers beside successive powers of $x$ is called the ordinary generating function of the sequence. This is the kind of generating function we use on this page.

$A(x)$ names the whole record. Why does the name still contain “function”? A finite record is a polynomial, and an infinite record can also define a numerical function under suitable conditions. Here we use its coefficient-recording meaning. We will specify exactly how infinite records are handled, without needing to draw a curve or assume numerical convergence.

In each individual factor so far, an allowed amount had only one choice. For example, using only one-unit coins, the only way to make 2 was to take two coins. Now let the first record $A$ have $a_i$ choices of amount $i$, and the second record $B$ have $b_j$ choices of amount $j$. The subscripts identify amounts; the coefficients count choices. Each of the $a_i$ first choices can be paired with all $b_j$ second choices. There are $a_i$ groups of $b_j$ pairs, giving $a_ib_j$ pairs altogether, each of amount $i+j$.

To make total $n$, we need $i + j = n$. Since neither total is negative, $i$ can only run from 0 to $n$; once $i$ is fixed, $j$ must be $n - i$. We therefore check (0,n), $(1,n-1)$, and so on through (n,0), then add their numbers of pairs. This is the coefficient of $x^{n}$ in the product.

The symbol $[x^{n}]$ means “take the coefficient of $x^{n}$ in the expression that follows”; it does not mean multiply by $x^{n}$. The symbol $\Sigma$ abbreviates the addition we just described: let $i$ take each value 0, 1, …, $n$, form $a_{i}b_{n-i}$, then add all these terms. This rule for multiplying coefficients and grouping by total exponent is also called convolution. The name adds no new operation.

The justification works in both directions. Every legal pair has definite totals $i$ and $j$, so it appears in one of the listed terms and cannot be missed. Conversely, a listed term uses only a choice of total $i$ together with one of total $n - i$, so it cannot include a pair of the wrong total. Different values of $i$ cannot describe the same pair, because that pair’s A-choice has one definite total. There is no duplication between terms.

There is one more check: does a final object correspond to exactly one pair of choices? For the coins, the final collection tells us uniquely how many of each kind were taken, so it does: the correspondence is one-to-one. If the factors record the same decision twice, or some pairs are forbidden, we cannot multiply them unchanged. The algebra follows the rules we encode; it does not repair an incorrectly chosen counting model.

What if the supply has no upper limit?

Now remove the limit on one-unit coins. We may take 0, 1, 2, 3, … coins, with one choice for each quantity, so the record becomes $S(x) = 1 + x + x^{2} + x^{3} + \cdots$. The dots mean continue by this stated rule: the coefficient of every nonnegative integer power is 1. We are defining the whole record, not guessing it from a few samples.

A record arranged by nonnegative integer powers, with infinitely many terms allowed, is called a formal power series. “Formal” reminds us to read coefficients first, rather than substitute a number for $x$ and ask for an infinite numerical sum. Two such series are equal when their coefficients agree at every exponent. Addition adds corresponding coefficients, and multiplication uses the pairing rule from the previous section.

Does this multiplication demand an infinite addition for a single coefficient? No. For a fixed $x^{n}$, nonnegative $i$ and $j$ with $i + j = n$ give only the $n + 1$ pairs from (0,n) to (n,0). Higher powers cannot lower their exponent to help make $n$. That is why a finite calculation can determine one requested coefficient exactly.

We would like a shorter expression for $S(x)$. Multiplying by $x$ adds 1 to every exponent, so $xS(x) = x + x^{2} + x^{3} + \cdots$. Subtract the two records. Their constant coefficients give $1 - 0 = 1$, while every positive-power coefficient gives $1 - 1 = 0$. Thus:

We have not cancelled a mysterious “last term”. We performed a finite subtraction at each specified coefficient. Negative coefficients are allowed in this intermediate algebra: for example, the coefficient of $x$ in $1 - x$ is $-1$. This intermediate factor is not counting “minus one choice”. The final counting record still has nonnegative integer coefficients.

An expression that multiplies $1 - x$ to give 1 is its multiplicative inverse, written $1/(1 - x)$. Here that fraction means an inverse in formal power series. We have just shown that $S$ is such an expression.

If each coin has positive integer value $d$, taking 0, 1, 2, … coins contributes $1, x^{d}, x^{2d}$, …. Multiplying by $x^{d}$ moves each allowed exponent to the next allowed exponent. Subtraction leaves only the constant 1; at exponents that are not multiples of $d$, the coefficients remain $0 - 0$. Therefore:

Here $d$ must be positive. If we allowed unlimited zero-value coins and regarded different quantities as different choices, there would already be infinitely many ways to make total zero. A finite integer coefficient could no longer record the count. The condition matters. We have also not substituted $x = 1$: the formal identity does not claim that $1 + 1 + 1 + \cdots$ is a finite number.

Example 1: making a total with 1, 2 and 5-unit coins

Now use coins of values 1, 2 and 5, with any nonnegative integer quantity of each allowed. Coins of the same value are indistinguishable, and rearranging them does not create a new way. We want total 5. The previous section gives one record for each coin value, and multiplication combines the three quantity choices:

May we multiply, regroup and reorder these infinite records as we do ordinary brackets? Yes. For any one target exponent $n$, only exponents from 0 to $n$ can take part, so each coefficient comes from finitely many ordinary integer products. This is what permits the denominator cancellations below; the full reason is in the optional note.

The final fraction combines the three inverses: multiplying $C(x)$ by the three denominator factors makes each factor cancel its corresponding series, leaving 1. This shortens the record, but it has not yet supplied a numerical answer for our target. We still need the coefficient of $x^{5}$.

If we take $a$, $b$ and $c$ coins, the selected terms are $x^{a}, x^{2b}$ and $x^{5c}$, whose product is $x^{a+2b+5c}$. We therefore list the nonnegative integer counts satisfying $a + 2b + 5c = 5$. First fix $c$. It can only be 0 or 1, because $c \ge 2$ would contribute at least 10 from the five-unit coins alone, already above 5.

The construction below fixes the number of 5s first, increases the number of 2s one at a time, and uses 1s to fill the remainder. Blue is marked 1, gold 2 and pink 5. “Add next choice” retains both its coins and its equation. Changing the target clears the old list so that counts for different questions are not mixed.

Why is this enumeration complete? For target $n$, every legal choice has one definite $c$. Once $c$ is fixed it also has one definite $b$, and $a$ must equal $n - 5c - 2b$. We allow only $5c \le n$ and $2b \le n - 5c$, then calculate this nonnegative a. Thus every generated triple is legal, and every legal triple is generated exactly once. The proof comes from these two directions, not from noticing a pattern in a few pictures.

As a nearby check, change the target to 6. With $c = 0$, the values $b = 0, 1, 2, 3$ give $a = 6, 4, 2$, 0: four choices. With $c = 1$, only 1 remains, so $b = 0$ and $a = 1$: one more choice. The total is $4 + 1 = 5$. This differs from the four choices for target 5, and the list shows the actual objects behind the change.

This also connects to Diophantine equations: we are counting the nonnegative integer solutions of $a + 2b + 5c = n$. A generating function places the answers for different $n$ in one record. It preserves the integer and nonnegativity restrictions through the exponents allowed in each factor.

Example 2: at most, or at least, a given number

An unlimited supply cannot stand in for a bounded one. If a coin has positive integer value $d$ and we may take at most $m$ of them, where $m$ is a nonnegative integer, the allowed quantities are only 0 through $m$. Its record must stop at $x^{md}$:

As before, multiplying by $x^{d}$ gives $x^{d} + x^{2d} + \cdots + x^{(m+1)d}$. In $B - x^{d}B$, the coefficients from power $d$ through $md$ become $1 - 1$. The constant 1 remains. The highest term $x^{(m+1)d}$ appears only in the expression being subtracted, so it leaves $-x^{(m+1)d}$. Thus:

The last step multiplies both sides by the formal inverse $1/(1 - x^{d})$ already constructed. It is not division by a numerical expression that might vanish at some substituted $x$. When $m = 0$ there are no middle terms to cancel: $B = 1$, and the formula likewise gives $(1 - x^{d})/(1 - x^{d}) = 1$.

For example, with only two two-unit coins available, we may take 0, 1 or 2, giving $1 + x^{2} + x^{4}$. Substituting $d = 2$ and $m = 2$ gives $(1 - x^{6})/(1 - x^{2})$, where 6 comes from $(2 + 1) \times 2$. If one-unit coins are unlimited and the target is 5, taking 0, 1 or 2 twos leaves 5, 3 or 1 ones. There are three ways.

If we must take at least $r$ coins of value $d$, first set aside the required $r$ coins, contributing $rd$. Then take 0, 1, 2, … extra coins, contributing $0, d, 2d$, …. The record is $x^{rd}(1 + x^{d} + x^{2d} + \cdots )$. Every permitted choice can uniquely have those $r$ required coins removed, leaving a nonnegative quantity. This gives a complete decomposition without duplication.

For example, require at least one two-unit coin, allow unlimited one-unit coins, and make total 5. Remove the required 2 first, leaving $5 - 2 = 3$. Make that remainder with three 1s, or with one 2 and one 1: two choices. Restoring the required 2 gives (number of 1s, number of 2s) $= (3, 1)$ and $(1, 2)$. The record is $x^{2}/((1 - x)(1 - x^{2}))$; the initial $x^{2}$ increases every original total by 2.

Example 3: why two dice keep their identities

Change the objects being counted. We have a first die and a second die, each with possible face values 1 through 6. We are counting outcomes, without assuming fairness or calculating probabilities. A 1 on the first die with a 6 on the second is different from a 6 on the first with a 1 on the second, because the dice are distinguishable.

Each face value occurs once on a die, so its record is $D(x) = x + x^{2} + x^{3} + x^{4} + x^{5} + x^{6}$. There is no constant term because zero is not an outcome for a die. The two factors have the same expression, but the first records the first die and the second the second die. Their positions are retained when we pair choices.

If the first die is $i$, the second must be $7 - i$. Let $i = 1, 2, 3, 4, 5, 6$; the second values are then 6, 5, 4, 3, 2, 1, all allowed. The pairs are (1,6), (2,5), (3,4), (4,3), (5,2), (6,1). Each contributes $1 \times 1 = 1$, so there are six outcomes.

The rows below retain the first die’s value and the columns the second die’s value. Each cell shows their sum; ✓ marks a match to the target. Change the target, inspect the matching cells, then read the count written as an addition below. For example, target 2 has only (1,1), while target 12 has only (6,6).

The fact that multiplication permits exchanging the two factors does not erase the identities of the objects. Exchanging the names of the dice sends (1,6) to (6,1), showing that the two naming conventions have the same total count; it does not merge the outcomes. For coins we chose the quantity of each kind from the start. For dice we chose each die’s value separately from the start. Different counting questions require different records.

Example 4: derive a generating function from a tiling recurrence

Our earlier factors came from kinds of object whose quantities could be chosen separately. Now consider a different problem: cover a single row of length $n$ with tiles of length 1 and 2, without overlap or gaps. All tiles lie horizontally. Length-1 tiles are identical to one another, as are length-2 tiles, but left-to-right order is part of a tiling. On a row of length 3, a 1 followed by a 2 occupies different positions from a 2 followed by a 1.

Write $a_{n}$ for the number of tilings of length $n$. For length zero there are no cells to cover: placing no tiles completes the task, so $a_{0} = 1$. For length one, only one length-1 tile fits, so $a_{1} = 1$. These starting values need to be explicit because every later count will grow from them.

For $n \ge 2$, classify a tiling by its last tile. If that tile has length 1, removing it leaves a complete tiling of length $n - 1$. Conversely, append a length-1 tile to any tiling of length $n - 1$ and get one unique tiling whose last tile is 1. These operations undo one another, so this class has exactly $a_{n-1}$ tilings.

If the last tile has length 2, removing it leaves a tiling of length $n - 2$, and appending a 2 uniquely restores the original. This class has $a_{n-2}$ tilings. A final tile cannot have both lengths, so the classes do not overlap. There are only these two tile lengths, so every tiling belongs to a class. We can therefore add them:

A rule that calculates later values from earlier ones is a recurrence relation. Here $a_{2} = a_{1} + a_{0} = 1 + 1 = 2$; $a_{3} = a_{2} + a_{1} = 2 + 1 = 3$; $a_{4} = a_{3} + a_{2} = 3 + 2 = 5$; and $a_{5} = a_{4} + a_{3} = 5 + 3 = 8$. This is a Fibonacci-type recurrence, but our reason for it is the complete classification by the last tile, not its name.

In the picture below, blue short tiles are marked 1 and gold long tiles are marked 2. Keep length 4 first and press “Next tiling” to inspect $1+1+1+1, 1+1+2, 1+2+1, 2+1+1$ and $2+2$. Each tile’s width corresponds to its length, and the addition below connects the picture to the total length.

Now shift the same record by one position

Put all the tiling counts into $F(x)$. To place $a_{n}, a_{n-1}$ and $a_{n-2}$ beside the same power, use $F$, $xF$ and $x^{2}F$. Multiplying by $x$ turns $a_{n-1}x^{n-1}$ into $a_{n-1}x^{n}$; multiplying by $x^{2}$ turns $a_{n-2}x^{n-2}$ into $a_{n-2}x^{n}$. We choose these multipliers to align the three terms of the recurrence.

Form $F - xF - x^{2}F$. Only $F$ supplies a constant term, so it is $a_{0} = 1$. The coefficient of $x$ is $a_{1} - a_{0} = 1 - 1 = 0$, because $x^{2}F$ has no $x$ term. For every $n \ge 2$, the coefficient of $x^{n}$ is $a_{n} - a_{n-1} - a_{n-2}$, which is zero by our proved recurrence. We handle the two starting coefficients separately: the recurrence applies only from $n = 2$.

The fraction again denotes a formal multiplicative inverse: $F$ is the record that gives 1 when multiplied by $1 - x - x^{2}$, and we constructed it from actual tiling counts.

A short fraction therefore stores both the recurrence and its starting values. It does not remove all calculation: to find the coefficient of $x^{5}$, we may still use the proved rule to get 1, 1, 2, 3, 5, 8, then read the 8 beside the fifth power. The recurrence retains counts rather than listing every tiling, while the generating function turns the recurrence into an algebraic record that can be multiplied with other records or shifted in exponent.

For example, attach one fixed end piece of length 2 to a tiled row, making a decorative board of total length 6. There is one end-piece choice, contributing $x^{2}$, so the record is $x^{2}F(x)$. To make $x^{6}$ it must pair with $x^{4}$ from $F$, whose coefficient is $a_{4} = 5$. Thus there are five boards. Removing the fixed end piece gives exactly the five tilings of length 4, checking the algebra against the objects once again.

Try it, then check each step

For each question, picture the actual choices and check them using coefficients. The worked answer is available below; no memorised counting formula is required. At each step, explain which objects you are counting and why each is counted exactly once.

We began with two ways to make 2, recorded each choice as a term, and proved that addition records disjoint alternatives while multiplication records combinations that can be uniquely separated. Exponents track totals; coefficients track counts. Unlimited supplies, bounded supplies, dice and tilings give different expressions, but the final check is the same: which actual choice does each contribution to this coefficient represent? Answering that is what makes the generating function more than a short expression.