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:
- Generating function B:
When you multiply them: , the coefficient of in the product is:
This formula is called convolution.
Why This Matters
Think of it like making exact change. Suppose counts ways to select items from basket A, and counts ways to select items from basket B. If you want exactly items total, you need to consider all splits: 0 from A and from B, or 1 from A and from B, etc. Convolution adds up all these possibilities.
Example
If (sequence: 1, 2, 1) and (sequence: 1, 1), then:
The coefficient of is .
Key Takeaway: Multiplying generating functions combines sequences through convolution: the -th coefficient in the product counts all ways to pair elements from the two sequences that sum to index .