Course contentsShow
← Mathematics
Lesson 2641 of 3,12152. CombinatoricsFree lesson

Operations on Generating Functions: Multiplication

Understand convolution: how multiplying generating functions corresponds to combining sequences.

Operations on Generating Functions: Multiplication

What You'll Learn

You'll discover how multiplying two generating functions corresponds to convolving their sequences—a powerful way to count combinations of objects from two different sources.

The Core Idea

When you multiply two generating functions, you're essentially asking: "In how many ways can I combine elements from sequence A with elements from sequence B?"

Let's say you have:

  • Generating function A: A(x)=a0+a1x+a2x2+...A(x) = a_0 + a_1x + a_2x^2 + ...
  • Generating function B: B(x)=b0+b1x+b2x2+...B(x) = b_0 + b_1x + b_2x^2 + ...

When you multiply them: A(x)⋅B(x)=C(x)A(x) \cdot B(x) = C(x), the coefficient cnc_n of xnx^n in the product is:

cn=a0bn+a1bn−1+a2bn−2+...+anb0=∑k=0nakbn−kc_n = a_0b_n + a_1b_{n-1} + a_2b_{n-2} + ... + a_nb_0 = \sum_{k=0}^{n} a_k b_{n-k}

This formula is called convolution.

Why This Matters

Think of it like making exact change. Suppose aka_k counts ways to select kk items from basket A, and bjb_j counts ways to select jj items from basket B. If you want exactly nn items total, you need to consider all splits: 0 from A and nn from B, or 1 from A and n−1n-1 from B, etc. Convolution adds up all these possibilities.

Example

If A(x)=1+2x+x2A(x) = 1 + 2x + x^2 (sequence: 1, 2, 1) and B(x)=1+xB(x) = 1 + x (sequence: 1, 1), then:

C(x)=(1+2x+x2)(1+x)=1+3x+3x2+x3C(x) = (1 + 2x + x^2)(1 + x) = 1 + 3x + 3x^2 + x^3

The coefficient of x2x^2 is c2=(1)(1)+(2)(1)+(1)(0)=3c_2 = (1)(1) + (2)(1) + (1)(0) = 3.

Key Takeaway: Multiplying generating functions combines sequences through convolution: the nn-th coefficient in the product counts all ways to pair elements from the two sequences that sum to index nn.