Polynomials as Counting Tools

Pillar: Set --- "A polynomial encodes a SET of choices: the coefficient of \(x^k\) counts the number of ways to make total \(k\). Multiplying two polynomials = combining two independent sets of choices."

The Setup

You have coins of value \(1\), \(2\), and \(5\). How many ways can you make change for \(7\)?

You could enumerate by hand. One \(5\) plus one \(2\). One \(5\) plus two \(1\)s. And so on. For small values that works. But when you have \(50\) coin types and a target of \(10^5\), brute force is hopeless.

There's a tool that solves this in a single operation: polynomial multiplication. The trick is encoding each coin type as a polynomial, then multiplying them together. The answer to "how many ways to make \(k\)?" is sitting right there as the coefficient of \(x^k\) in the product.

This isn't a coincidence. Polynomials and counting are the same thing, viewed from different angles.

The Key Idea: Polynomials Encode Choices

Think of a polynomial as a menu of options. Each term \(c_k x^k\) says: "there are \(c_k\) ways to contribute exactly \(k\) to the total."

For a coin of value \(2\), you can use it \(0\), \(1\), \(2\), ... times. Using it \(j\) times contributes \(2j\) to the total. The polynomial encoding is:

\[1 + x^2 + x^4 + x^6 + \cdots\]

The coefficient of \(x^{2j}\) is \(1\) (one way to contribute \(2j\) using this coin), and all odd-indexed coefficients are \(0\) (you can't make an odd total with only \(2\)-coins).

For a coin of value \(1\): \(1 + x + x^2 + x^3 + \cdots\)

For a coin of value \(5\): \(1 + x^5 + x^{10} + \cdots\)

Now the core insight. When you multiply two polynomials, the coefficient of \(x^k\) in the product counts the number of ways to split \(k\) into a contribution from the first polynomial and a contribution from the second. That's exactly what "combining two independent sets of choices" means.

If \(A(x) = \sum_i a_i x^i\) and \(B(x) = \sum_j b_j x^j\), then:

\[A(x) \cdot B(x) = \sum_k \left(\sum_{i+j=k} a_i \cdot b_j\right) x^k\]

The coefficient of \(x^k\) in the product is \(\sum_{i+j=k} a_i \cdot b_j\). This is the convolution of the two coefficient sequences. It sums over all pairs \((i, j)\) with \(i + j = k\), multiplying the number of ways to get \(i\) from the first set by the number of ways to get \(j\) from the second set.

Formal Definition: Ordinary Generating Functions

An ordinary generating function (OGF) for a sequence \(a_0, a_1, a_2, \ldots\) is the formal power series:

\[A(x) = \sum_{k=0}^{\infty} a_k x^k\]

You don't plug in values of \(x\). You never worry about convergence. The variable \(x\) is just a placeholder -- a "bookkeeping device" that tracks indices. What matters is the coefficient sequence.

Two operations on OGFs correspond directly to combinatorial operations:

OGF Operation	Combinatorial Meaning
\(A(x) + B(x)\)	Disjoint union: either choose from \(A\)'s options OR from \(B\)'s options
\(A(x) \cdot B(x)\)	Independent combination: choose from \(A\) AND independently from \(B\)

Multiplication = convolution. That's the entire engine of generating functions as counting tools.

Worked Example: Coins {1, 2, 5}, Target = 7

Encode each coin (with unlimited supply, up to target \(7\)):

Coin \(1\): \(C_1(x) = 1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7\)
Coin \(2\): \(C_2(x) = 1 + x^2 + x^4 + x^6\)
Coin \(5\): \(C_5(x) = 1 + x^5\)

(We truncate at \(x^7\) since higher terms don't affect the coefficient of \(x^7\).)

Step 1: Multiply \(C_1(x) \cdot C_2(x)\).

This gives us the number of ways to make each total using only coins \(1\) and \(2\). Trace a few coefficients:

Coefficient of \(x^0\): \(1 \cdot 1 = 1\) (use zero of each)
Coefficient of \(x^1\): \(1 \cdot 0 + 1 \cdot 0 = 0\)... wait, that's not right. Let's be careful.

\(C_1 = [1, 1, 1, 1, 1, 1, 1, 1]\) and \(C_2 = [1, 0, 1, 0, 1, 0, 1, 0]\).

For the convolution, coefficient of \(x^k\) in the product is \(\sum_{i=0}^{k} C_1[i] \cdot C_2[k-i]\).

\(k\)	Sum	Result
\(0\)	\(1 \cdot 1\)	\(1\)
\(1\)	\(1 \cdot 0 + 1 \cdot 1\)	\(1\)
\(2\)	\(1 \cdot 1 + 1 \cdot 0 + 1 \cdot 1\)	\(2\)
\(3\)	\(1 \cdot 0 + 1 \cdot 1 + 1 \cdot 0 + 1 \cdot 1\)	\(2\)
\(4\)	contributions from \(C_2[0], C_2[2], C_2[4]\)	\(3\)
\(5\)		\(3\)
\(6\)		\(4\)
\(7\)		\(4\)

So \(C_1 \cdot C_2\) gives us the sequence \([1, 1, 2, 2, 3, 3, 4, 4, \ldots]\) for coins \(\{1, 2\}\). You can verify: there are \(4\) ways to make \(7\) from \(1\)s and \(2\)s (\(7\), \(5{+}2\), \(3{+}2{+}2\), \(1{+}2{+}2{+}2\)).

Step 2: Multiply by \(C_5(x) = [1, 0, 0, 0, 0, 1]\) (truncated to degree \(7\)).

The coefficient of \(x^7\) in the final product:

\[\text{result}[7] = \text{prev}[7] \cdot C_5[0] + \text{prev}[2] \cdot C_5[5] = 4 \cdot 1 + 2 \cdot 1 = 6\]

There are \(\mathbf{6}\) ways to make change for \(7\) using coins \(\{1, 2, 5\}\).

Enumerate to verify: \((7)\), \((5{+}2)\), \((3{+}2{+}2)\), \((1{+}2{+}2{+}2)\), \((5{+}1{+}1)\), \((5{+}2)\)... actually let's list them cleanly:

Seven \(1\)s
Five \(1\)s + one \(2\)
Three \(1\)s + two \(2\)s
One \(1\) + three \(2\)s
Two \(1\)s + one \(5\)
One \(2\) + one \(5\)

Six ways. Confirmed.

The Algorithm: Naive Polynomial Multiplication

For polynomials of degree \(n\) and \(m\), the product has degree \(n + m\). Computing each coefficient takes \(O(n)\) work in the worst case, so the total is \(O(n \cdot m)\). When both have degree \(n\), that's \(O(n^2)\).

vector<long long> multiplyPolynomials(const vector<long long>& polyA, const vector<long long>& polyB) {
    int sizeA = polyA.size(), sizeB = polyB.size();
    vector<long long> product(sizeA + sizeB - 1, 0);
    for (int i = 0; i < sizeA; i++) {
        for (int j = 0; j < sizeB; j++) {
            product[i + j] += polyA[i] * polyB[j];
        }
    }
    return product;
}

For the coin change problem, build the generating function for each coin type and multiply them together one by one:

vector<long long> countCoinCombinations(const vector<int>& coinValues, int maxSum) {
    vector<long long> totalWays(maxSum + 1, 0);
    totalWays[0] = 1;
    for (int coin : coinValues) {
        vector<long long> coinPoly(maxSum + 1, 0);
        for (int k = 0; k * coin <= maxSum; k++) {
            coinPoly[k * coin] = 1;
        }
        vector<long long> newWays(maxSum + 1, 0);
        for (int i = 0; i <= maxSum; i++) {
            for (int j = 0; j <= maxSum - i; j++) {
                newWays[i + j] += totalWays[i] * coinPoly[j];
            }
        }
        totalWays = newWays;
    }
    return totalWays;
}

Complexity: \(O(C \cdot S^2)\) where \(C\) is the number of coin types and \(S\) is the target sum. This is the naive approach -- Ch11 L3 will bring it down to \(O(C \cdot S \log S)\) using FFT.

Convolution: The Operation Behind Everything

The operation \(c_k = \sum_{i+j=k} a_i \cdot b_j\) is called convolution. It appears everywhere:

Counting problems: number of ways to partition a sum into contributions from independent sources.
Probability: the distribution of \(X + Y\) (sum of independent random variables) is the convolution of their individual distributions.
Signal processing: filtering a signal = convolving with a kernel.

In competitive programming, whenever you see "count the number of ways to achieve total \(k\) by combining independent choices," think convolution. And convolution means polynomial multiplication.

The \(O(n^2)\) naive approach is fine when the degree is small (up to \(\sim 5000\)). For larger polynomials, you need FFT (\(O(n \log n)\)), which is the subject of Ch11 L3.

Exponential Generating Functions: A Brief Look

OGFs handle problems where order doesn't matter (combinations). When order matters (permutations), you use exponential generating functions (EGFs).

An EGF for a sequence \(a_0, a_1, a_2, \ldots\) is:

\[\hat{A}(x) = \sum_{k=0}^{\infty} a_k \frac{x^k}{k!}\]

The key difference: when you multiply two EGFs, the coefficient extraction rule accounts for the \(\binom{n}{k}\) ways to interleave two ordered sequences. The product of EGFs gives:

\[\text{coefficient of } \frac{x^n}{n!} \text{ in } \hat{A}(x) \cdot \hat{B}(x) = \sum_{k=0}^{n} \binom{n}{k} a_k b_{n-k}\]

That \(\binom{n}{k}\) factor is exactly what you need when counting labeled structures. For example, the number of ways to arrange \(n\) distinct objects into two groups where the first group follows pattern \(A\) and the second follows pattern \(B\).

The most famous EGF: \(e^x = \sum_{k=0}^{\infty} \frac{x^k}{k!}\). The sequence is \(a_k = 1\) for all \(k\), meaning "any number of elements is fine." This makes \(e^x\) the EGF for the "no restriction" option.

EGFs are less common in competitive programming than OGFs, but they appear in problems involving permutations, derangements, and labeled graphs. The computational backbone is the same: polynomial multiplication, accelerated by FFT.

Preview: The Partition Function

The partition function \(p(n)\) counts the number of ways to write \(n\) as a sum of positive integers, ignoring order. For example, \(p(5) = 7\):

\[5, \; 4{+}1, \; 3{+}2, \; 3{+}1{+}1, \; 2{+}2{+}1, \; 2{+}1{+}1{+}1, \; 1{+}1{+}1{+}1{+}1\]

The generating function for \(p(n)\) is:

\[\prod_{k=1}^{\infty} \frac{1}{1 - x^k} = \prod_{k=1}^{\infty} (1 + x^k + x^{2k} + x^{3k} + \cdots)\]

Each factor is the OGF for "how many times do we use the part \(k\)?" -- zero times (\(1\)), once (\(x^k\)), twice (\(x^{2k}\)), and so on. Multiplying all these factors together is exactly the polynomial multiplication framework from this lesson, applied to infinitely many coin types.

Computing \(p(n)\) for large \(n\) efficiently requires the FFT techniques from later in this chapter, combined with Euler's pentagonal theorem for even faster approaches.

Common Mistakes

Confusing OGF and EGF. If order doesn't matter (combinations, partitions, coin change), use OGF. If order matters (permutations, labeled structures), use EGF. Using the wrong one gives meaningless coefficients.
Truncating too early. When you only care about coefficients up to \(x^S\), truncate all polynomials to degree \(S\) before multiplying. Otherwise you waste time computing coefficients you'll never use, and the product polynomial grows unnecessarily large.
Overflow in the coefficient array. Coefficients can grow fast. If the problem asks for answers modulo some prime, apply the modulus during multiplication, not after. For the coin change example with a large target sum, intermediate coefficients can exceed \(10^{18}\) even when individual coin polynomials have coefficients of \(0\) or \(1\).

Quick Recap

A polynomial \(\sum a_k x^k\) encodes a counting problem: \(a_k\) = number of ways to achieve "total \(k\)."
Multiplying two polynomials = convolving their coefficient sequences = combining two independent sets of choices.
OGFs handle unordered combinations. EGFs handle ordered/labeled structures.
Naive polynomial multiplication is \(O(n^2)\). FFT brings it to \(O(n \log n)\) (Ch11 L3).
Whenever a problem says "count ways to reach total \(k\) from independent contributions," you're looking at polynomial multiplication.

Problems

Problem	Link	Difficulty	Focus
CSES -- Dice Combinations	cses.fi/problemset/task/1633	Easy	OGF for dice as polynomial, extract coefficient (DP equivalent)
CSES -- Coin Combinations I	cses.fi/problemset/task/1635	Easy	Direct coin change with order, OGF multiplication
CSES -- Coin Combinations II	cses.fi/problemset/task/1636	Medium	Unordered coin change, exactly the OGF product from this lesson
CF 1556D -- Take a Guess	codeforces.com/problemset/problem/1556/D	Medium	Convolution-style counting with bitwise operations

Next lesson: Polynomials as Points -- the DFT, roots of unity, and why evaluating at the right points makes everything invertible.