CodeTikki
LoginGet StartedFREE

// 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·Mathematics · Combinatorics
Reviewed by CodeTikki Academic Team

Prerequisites: Ordinary GFs · 1/(1-x) · 1/(1-x)^k · Exponential GFs · Fibonacci GF · Catalan GF · Partitions · Coefficient extraction

// 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 · Extracting coefficients from rational GFs
1function extractCoefficient(P, Q, n):
2 // P(x)/Q(x) -> linear recurrence
3 k = degree(Q)
4 // Find recurrence: a[n] = c1*a[n-1] + ... + ck*a[n-k]
5 if n < k:
6 return P[n] // base case from numerator
7 // Matrix exponentiation: O(k³ log n)
8 M = companion matrix of Q
9 result = M^(n-k+1) * initial_vector
10 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
YesNoStartIdentify objects& constraintsBuild factor GFsG₁, G₂, …, GₖMultiply factorsG = G₁·G₂·…·GₖSimplify toclosed formExtract [xⁿ]Matches bruteforce?Output answerEnd

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 exponentiation
L5
Find the number of ways to make change for n cents
L8
Count the number of partitions of n
L7
Compute Catalan numbers mod p
L6
Solve linear recurrence with Kitamasa
L8

// 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