The generating function A(x) encodes the sequence (1, 2, 3, 4, …) and B(x) encodes (1, 0, 1, 0, …). What does the coefficient of x³ in A(x)·B(x) represent?
AThe sum of the sequences at position 3: a₃ + b₃ = 4 + 0 = 4
CThe pointwise product of the sequences at position 3: a₃ · b₃ = 4 · 0 = 0
DThe maximum of the sequences at position 3: max(a₃, b₃) = 4
Multiplying generating functions corresponds to *convolution* of their coefficient sequences, not pointwise addition or multiplication. The coefficient of xⁿ in A(x)·B(x) is Σₖ aₖ·bₙ₋ₖ — all ways of splitting n into k and n−k. For n = 3: a₀·b₃ + a₁·b₂ + a₂·b₁ + a₃·b₀ = 1·0 + 2·1 + 3·0 + 4·1 = 6. This convolution structure is what makes generating functions powerful for counting: it naturally captures combining independent choices — choosing k items of one type and n−k of another.
Question 2 Multiple Choice
What is the coefficient of x⁴ in the generating function 1/(1−x)²?
A4
B6
C5
D16
The expansion of 1/(1−x)² is 1 + 2x + 3x² + 4x³ + 5x⁴ + ⋯, where the coefficient of xⁿ is n + 1. For n = 4, the coefficient is 5. Combinatorially: 1/(1−x)² = [1/(1−x)]·[1/(1−x)], and by convolution the coefficient of x⁴ counts ordered pairs (k, 4−k) of non-negative integers summing to 4: (0,4), (1,3), (2,2), (3,1), (4,0) — exactly 5. The general formula 1/(1−x)^n has coefficient C(n+k−1, k) at xᵏ, the stars-and-bars count for distributing k identical items into n bins.
Question 3 True / False
In combinatorics, generating functions are treated as formal algebraic objects — the variable x is a placeholder and convergence of the power series is irrelevant.
TTrue
FFalse
Answer: True
The key philosophical shift in combinatorial generating functions is that you never substitute a real number for x and ask whether the series converges. Instead, you manipulate series algebraically — multiplying, factoring, taking partial fractions — and read off coefficients. This means you can freely use 1/(1−2) symbolically in a derivation without concern, because you are working with the formal series, not evaluating a function. Convergence becomes relevant only if you want to use analytic tools like contour integrals or saddle-point approximations, but for purely combinatorial coefficient extraction it is irrelevant.
Question 4 True / False
The coefficient of x³ in the generating function 1/(1−x)² is 3.
TTrue
FFalse
Answer: False
The coefficient of xⁿ in 1/(1−x)² is n + 1, not n. For n = 3 the coefficient is 4, not 3. The full expansion is 1/(1−x)² = 1 + 2x + 3x² + 4x³ + 5x⁴ + ⋯. You can derive this by differentiating the geometric series: d/dx[1/(1−x)] = 1/(1−x)² and d/dx[Σ xⁿ] = Σ n·xⁿ⁻¹, so 1/(1−x)² = Σ (n+1)xⁿ. The off-by-one error (thinking the coefficient is n rather than n+1) is common when first working with this generating function.
Question 5 Short Answer
Explain why generating functions treat power series as formal algebraic objects rather than functions of a real variable, and why this matters for combinatorial applications.
Think about your answer, then reveal below.
Model answer: In combinatorics, we only care about the coefficients of the power series — each coefficient is the answer to a counting question. The variable x is just a positional label; we never evaluate the series at a specific number. Treating it as a formal object means we can apply algebraic identities — multiply, factor, use partial fractions — without worrying about convergence. This frees us to manipulate expressions like 1/(1−2) purely symbolically, as long as we only read off coefficients at the end and never actually substitute 2.
The practical benefit is enormous: every algebraic identity between rational functions becomes a combinatorial identity between the sequences they encode, and algebraic proofs are often far shorter than direct combinatorial ones. For example, the Vandermonde identity C(m+n, r) = Σ C(m,k)·C(n, r−k) follows immediately from the coefficient of xʳ in (1+x)^m · (1+x)^n = (1+x)^(m+n) — a one-line algebraic argument. The formal perspective turns combinatorics into algebra and lets you use the full machinery of rational functions, partial fractions, and power series to solve counting problems.