GENERATING FUNCTIONS — 1-Page Cheat Sheet
1. Basic Series
- 1/(1 - x) = Σ x^n → [x^n] = 1
- 1/(1 - ax) = Σ a^n x^n → [x^n] = a^n
- 1/(1 - x)^k → [x^n] = C(n+k-1, k-1)
- 1/(1 - x^2) = 1 + x^2 + x^4 + …
- (1 + x)^a = Σ C(a, n)x^n
2. Restrictions
- x ≥ m → x^m/(1 - x)
- x ≤ M → (1 - x^(M+1))/(1 - x)
- x even → 1/(1 - x^2)
- x odd → x/(1 - x^2)
- unrestricted → 1/(1 - x)
3. Partial Fractions Templates
- 1/[(1-ax)(1-bx)] = A/(1-ax) + B/(1-bx)
- 1/[(1-x)^3(1+x)] = A/(1+x) + B/(1-x) + C/(1-x)^2 + D/(1-x)^3
Key expansions:
- 1/(1-x) → 1
- 1/(1-x)^2 → n+1
- 1/(1-x)^3 → C(n+2,2)
- 1/(1-ax) → a^n
- 1/(1+x) → (-1)^n
4. Coefficient Extraction Formulas
- [x^n](1 - x)^(-k) = C(n+k-1, k-1)
- [x^n] 1/(1 - ax)^k = a^n C(n+k-1, k-1)
- [x^n](x^m f) = [x^(n-m)] f
- [x^n](1 + x)^a = C(a, n)
- Convolution: [x^n](A·B) = Σ a_k b_(n-k)
5. Distribution Problems
- unrestricted k vars: C(n+k-1, k-1)
- xi ≥ mi: x^(sum mi)*(1-x)^(-k)
- xi ≤ Mi: Π (1-x^(Mi+1))/(1-x)
6. Quick Coefficient Table
- [x^n](1-x)^(-2)=n+1
- [x^n](1-x)^(-3)=C(n+2,2)
- [x^n](1-x)^(-4)=C(n+3,3)
- [x^n]1/(1-ax)=a^n
- [x^n]1/(1+x)=(-1)^n
7. Workflow
1) Build GF
2) Multiply
3) Simplify
4) Expand
5) Extract [x^n]
6) Combine