// COMBINATORICS · ADVANCED

Generating Functions

Encode sequences as power series, manipulate them algebraically, and extract coefficients to solve counting problems.

Explore Series Play Coefficient Hunter
Advanced·35 min·Combinatorics
Reviewed by CodeTikki Academic Team

Prerequisites: Permutations & Combinations · Binomial coefficients

// SERIES EXPANSION

Visualize generating functions

Select a generating function to see its power series expansion. Each coefficient [xⁿ] encodes the nth term of the sequence.

G(x) = 1 + x + x² + x³ + x⁴ + ...

1
x⁰
1
x¹
1
x²
1
x³
1
x^4
1
x^5
1
x^6
1
x^7

Coefficient of xn gives the nth term of the sequence.

// KEY IDENTITIES

Common generating functions

1/(1-x)

1 + x + x² + x³ + ...

Sequence: 1, 1, 1, 1, ...

1/(1-x)²

1 + 2x + 3x² + 4x³ + ...

Sequence: 1, 2, 3, 4, ...

1/(1-x)ᵏ

Σ C(n+k-1, k-1) xⁿ

Sequence: Multiset coefficients

1/(1-x-x²)

x + x² + 2x³ + 3x⁴ + 5x⁵ + ...

Sequence: Fibonacci: 0, 1, 1, 2, 3, 5, ...

(1-√(1-4x))/(2x)

1 + x + 2x² + 5x³ + 14x⁴ + ...

Sequence: Catalan: 1, 1, 2, 5, 14, ...

eˣ

1 + x + x²/2! + x³/3! + ...

Sequence: 1, 1, 1/2, 1/6, ... (EGF)

// ALGORITHM

Extracting coefficients from rational GFs

A rational GF P(x)/Q(x) yields a linear recurrence. Use matrix exponentiation for large n.

// PSEUDOCODE · Extract Coefficient from Rational GF
P(x)/Q(x) → linear recurrence → matrix exponentiation
n = 1000
1function extractCoefficient(P, Q, n):
2 // P(x)/Q(x) -> linear recurrence
3 k = degree(Q)
4 if n < k:
5 return P[n] // base case
6 // Matrix exponentiation: O(k^3 log n)
7 M = companion matrix of Q
8 result = M^(n-k+1) * initial_vector
9 return result[0]

Press PLAY to step through the algorithm line by line.

0 / 6

// INTERACTIVE GAME

Coefficient Hunter

Given a generating function, find the coefficient of xⁿ. Test your mastery of common GFs!

Coefficient Hunter

Extract the coefficient of xⁿ from the generating function

You'll be shown a generating function and a power n. Find the coefficient of xⁿ!

// FLOWCHART

Solving counting problems with GFs

// FLOWCHART · Solving Counting Problems with GFs
From objects to coefficients
YesNoStartIdentify objects& constraintsBuild factor GFsG1(x), G2(x), ...Multiply factorsG(x) = G1·G2·...·GkCan simplifyalgebraically?Apply identitiesfor closed formExtract [x^n]Verify smallcasesDone

Press PLAY to trace the algorithm through the flowchart.

0 / 9

// TUTORIAL QUIZZES

Test your mastery

From basic series expansion to matrix exponentiation for large coefficients.

// PRACTICE & ASSESS

Test your understanding

Now that you've learned the concept, put it into practice. Solve coding problems and take quizzes to reinforce what you've learned.

💻

Coding Problems

Compute nth Fibonacci using matrix exponentiationL5Find the number of ways to make change for n centsL6Count the number of partitions of nL7Compute Catalan numbers mod pL6Solve linear recurrence with KitamasaL8

// REFERENCES

Sources & further reading

  1. [1]
    GeneratingfunctionologyHerbert S. Wilf — the definitive reference on generating functions
  2. [2]
    Concrete MathematicsRonald L. Graham, Donald E. Knuth, Oren Patashnik — GFs in discrete math
  3. [3]
    Introduction to Algorithms (CLRS)T. H. Cormen et al. — recurrence solving via GFs
  4. [4]
    The Art of Computer Programming, Vol. 1Donald E. Knuth — generating functions and series

// READY?

Count distributions with stars and bars

Next up: Stars and Bars — a combinatorics technique for counting ways to distribute identical objects into distinct bins.

Stars and Bars Browse Tutorials