Lecture 6: More on Generating Functions

Quick Overview

Peter Shor reviews fundamental operations on generating functions, including addition for disjoint unions and multiplication for direct products, before demonstrating how to derive closed-form expressions for sequences like binary strings and Fibonacci numbers using recurrence relations and partial fraction decomposition.

Key Points: The generating function for the disjoint union of two classes of things, $C = A \cup B$, is $C(x) = A(x) + B(x)$, while the generating function for the direct product, $C = A \times B$, is $C(x) = A(x)B(x)$. The generating function $S(x)$ for the set of finite sequences of things in set $A$, where $A(x)$ is the generating function for $A$, is $S(x) = 1 + A(x) + A(x)^2 + A(x)^3 + \dots = 1 / (1 - A(x))$. The number of messages that can be sent using dots (length 1, represented by $x$) and dashes (length 2, represented by $x^2$) follows the Fibonacci sequence, leading to the generating function $f(x) = 1 / (1 - x - x^2)$ using the sequence definition $f0=1, f1=1$. Shor derives the closed form for the Fibonacci numbers using partial fractions on $f(x) = 1 / (1 - x - x^2)$, identifying roots $\phi+$ and $\phi-$ of $y^2 - y - 1 = 0$, resulting in $fn = a\phi+^{n+1} + b\phi-^{n+1}$. The information transmission rate for the dot/dash channel is determined by the growth rate of the Fibonacci numbers, approximately $\log2(\phi+)$. Shor demonstrates deriving the generating function for tiling a $2 \times n$ strip using specific tiles as $g(x) = 1 / (1 - x^2 - 2x^3)$ by recognizing the tiling structure corresponds to the sequence formula $1 / (1 - 2x^3 / (1 - x^2))$. Sums along the diagonals of Pascal's triangle yield Fibonacci numbers; substituting $x=z^2$ and $y=z$ into the 2D generating function $1 / (1 - x - y)$ produces the generating function for these diagonal sums: $1 / (1 - z - z^2)$.

Context: This lecture, titled "Lecture 6: More on Generating Functions," continues the discussion on using generating functions to solve combinatorial problems, building upon previous material. Peter Shor reviews basic generating function operations for set combinations (union/disjoint union, direct product) and then applies these concepts to derive closed-form solutions for more complex sequences, specifically focusing on binary strings and the Fibonacci numbers derived from a telegraph coding problem involving dots (length 1) and dashes (length 2).