Generating Functions

Applied Combinatorics (CC BY-SA) · appliedcombinatorics.org

Hang a whole sequence on the powers of x: a₀ + a₁x + a₂x² + … . Now combinatorial operations become algebra. Multiplying two generating functions convolves their sequences, which is exactly "choose some from here and some from there."

Why multiplication is the whole trick

The coefficient of xⁿ in A(x)B(x) sums a_jb_n−j over all splits j. That is precisely the count of ways to take j objects of one type and n−j of another. Raising (1+x) to the n-th power therefore reproduces Pascal's row, because each factor offers "take this element or not."

Scheme

; Coefficient lists, low degree first. Convolution = polynomial product.
(define (conv a b)
  (let ((la (length a)) (lb (length b)))
    (let loop ((i 0) (acc '()))
      (if (> i (- (+ la lb) 2))
          (reverse acc)
          (loop (+ i 1)
                (cons (let sum ((j 0) (s 0))
                        (if (> j i) s
                            (sum (+ j 1)
                                 (+ s (* (if (< j la) (list-ref a j) 0)
                                         (let ((m (- i j)))
                                           (if (and (>= m 0) (< m lb)) (list-ref b m) 0)))))))
                      acc))))))

; (1 + x)^n via repeated convolution
(define (binom-poly n)
  (let loop ((k 0) (p '(1)))
    (if (= k n) p (loop (+ k 1) (conv p '(1 1))))))

(display "(1+x)^4 = ") (display (binom-poly 4)) (newline)  ; (1 4 6 4 1)
(display "(1+x)^6 = ") (display (binom-poly 6)) (newline)

Neighbors

🧮 Ch.6 Recurrence Relations — generating functions solve recurrences in closed form
📡 Information Theory — generating functions count codewords by weight

← Inclusion–Exclusion · 4 of 10 by june.kim Recurrence Relations · 6 of 10 →