2. Generating Functions
What is # of compositions of \( n \) with summands from \( \lbrace 1, 2 \rbrace \)?
- Case 1: \( x_k = 1 \), then \( x_1 + \dots + x_{k-1} = n-1 \),
- Case 2: \( x_k = 2 \), then \( x_1 + \dots + x_{k-1} = n-2 \).
Thus \( a_n = a_{n-1} + a_{n-2} \).
Catalan Number
\( C_n \): # of full binary trees with \( n+1 \) leaves
Using recursion: \( C_0 = 1 \), for all \( n \geqslant 1 \),
\[ C_n = \sum\limits_{k=0}^{n-1}C_k C_{n-1-k} \]
Double Decks
How to choose \( m \) cards from \( 2 \) decks of \( n \) cards?
Each card can be chosen for no times, once and twice:
\[ (x_1^0 + x_1^1 + x_1^2) (x_2^0 + x_2^1 + x_2^2) \cdots (x_n^0 + x_n^1 + x_n^2) \]
\[ \Rightarrow (1+x+x^2)^n = \sum_k \sum_{l \leqslant k} {n \choose k}{k \choose l} x^{k+l} = \sum_m \left( \sum_l {n \choose m-l} {m-l \choose l} \right) x^m \]
Multisets
Multisets on \( S = \lbrace x_1, \dots, x_n \rbrace \).
Each element can be chosen for no time, once, twice, ...
\[ (1 + x_1^1 + x_1^2 + \dots) (1 + x_2^1 + x_2^2 + \dots) \cdots (1 + x_n^1 + x_n^2 + \dots) \]
\[ (1 + x^1 + x^2 + \dots)^n = \sum_{m \in \mathbb{N}^n} x^{m_1 + \dots + m_n} = \sum_{k \geqslant 0} \left( {n \choose k} \right) x^k \]
By some magic:
\[ (1 + x^1 + x^2 + \dots)^n = (1-x)^{-n} = \sum_{k \geqslant 0} {n+k-1 \choose k} x^k \]
Therefore \( \left( {n \choose k} \right) = {n+k-1 \choose k} \).
Ordinary Generating Function
\( G(x) = \sum\limits_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + \dots \)
Define \( [x^n]G(x) = a_n \).
Fibonacci Number
Solution of \( F_n \): \( \phi = \dfrac{1 + \sqrt{5}}{2}, \hat{\phi} = \dfrac{1 - \sqrt{5}}{2} \)
\[ F_n = \dfrac{1}{\sqrt{5}} \left( \phi^n - \hat{\phi}^n \right). \]
By recursion:
\( G(x) = F_0 + F_1 x + \sum\limits_{n \geqslant 2} F_n x^n = x + \sum\limits_{n \geqslant 2} F_{n-1} x^n + \sum\limits_{n \geqslant 2} F_{n-2} x^n \)
Identity: \( G(x) = x + (x + x^2) G(x) \).
Solution: \( G(x) = \dfrac{x}{1-x-x^2} \).
Formal Power Series
\( G(x) = \sum\limits_{n=0}^{\infty} a_n x^n \)
\( \mathbb{C}[x] \): ring of formal power series with complex coefficient
Inverse: \( F(x)G(x) = 1 \Longrightarrow F(x) = G^{-1}(x) = \dfrac{1}{G(x)} \)
Generatingfunctionology
- Recurrence: \( a_n = a_{n-1} + a_{n-2} \)
- Manipulation: \( G(x) = x + (x + x^2) G(x) \)
- Solving: \( G(x) = \dfrac{x}{1-x-x^2} = \dots \)
Generating Function Manipulations
\( G(x) = \sum\limits_{n \geqslant 0} g_n x^n, F(x) = \sum\limits_{n \geqslant 0} f_n x^n \)
- shift: \( x^kG(x) = \sum\limits_{n \geqslant k} g_{n-k} x^n \)
- addition: \( F(x)+G(x) = \sum\limits_{n \geqslant 0} (f_n + g_n) x^n \)
- convolution: \( F(x)G(x) = \sum\limits_{n \geqslant 0} \sum\limits_{k=0}^n f_k g_{n-k} x^n \)
- differentiation: \( G'(x) = \sum\limits_{n \geqslant 0} (n+1) g_{n+1} x^n \)
Expanding Generating Functions
- Taylor's expansion: \[ G(x) = \sum_{n \geqslant 0} \dfrac{G^{(n)}(0)}{n!} x^n \]
- Geometric sequence: \[ \dfrac{a}{1-bx} = a \sum_{n \geqslant 0} (bx)^n \]
- Binomial theorem (Newton's formula): \[ (1+x)^\alpha = \sum_{n \geqslant 0} {\alpha \choose n} x^n \]
Generalized binomial coefficient: \[ {\alpha \choose n} = \dfrac{\alpha (\alpha-1) \cdots (\alpha - n + 1)}{n!} \]
Catalan Number (cont'd)
\( C_0 = 1 \), for all \( n \geqslant 1 \),
\[ C_n = \sum\limits_{k=0}^{n-1}C_k C_{n-1-k} \]
Manipulation:
\( G(x) = \sum_{n \geqslant 0} C_nx^n = C_0 + \sum_{n \geqslant 1} \sum_{k=0}^{n-1} C_{k} C_{n-1-k} x^n \)
\( \Longrightarrow G(x) = 1 + xG^2(x) \)
Solving:
\( \Longrightarrow G(x) = \dfrac{1 \pm (1-4x)^{1 / 2}}{2x} \)
Since \( \lim\limits_{x \rightarrow 0} G(x) = C_0 = 1 \), we have
\[ G(x) = \dfrac{1 - (1-4x)^{1 / 2}}{2x} \]
Expanding (by Newton's formula):
\[ \begin{align} (1-4x)^{1 / 2} &= \sum\limits_{n \geqslant 0} {1 / 2 \choose n} (-4x)^n \\ &= 1 + \sum\limits_{n \geqslant 1} {1 / 2 \choose n} (-4x)^n \\ &= 1 + \sum\limits_{n \geqslant 0} {1 / 2 \choose n + 1} (-4x)^{n+1} \\ &= 1 - 4x \sum\limits_{n \geqslant 0} {1 / 2 \choose n} (-4x)^n \end{align} \]
Therefore, \( G(x) = \dfrac{1 - (1-4x)^{1 / 2}}{2x} = 2 \sum\limits_{n \geqslant 0} {1 / 2 \choose n + 1} (-4x)^n = \sum\limits_{n \geqslant 0} 2 {1 / 2 \choose n + 1} (-4)^n x^n \)
We get \( C_n = 2 {1 / 2 \choose n + 1} (-4)^n \).
Further more, \( C_n = \dfrac{1}{n+1} {2n \choose n} \).
Quicksort
Complexity:
- worst case: \( \Theta(n^2) \)
- average case: ?
Let \( T_n \) be the average # of comparisons used by quick sort.
Suppose \( \pi \) is a uniform random permutation of \( S_n \), then we run quick sort on \( \pi \).
Suppost the pivot is the \( k \)-th smallest number in \( \pi \), then we have the # of elements in both sections:
- \( \vert L \vert = k - 1 \)
- \( \vert R \vert = n - k \)
Since \( \pi \) is uniformly random, the probability of pivot being the \( k \)-th smallest element for any \( k \) is \( \dfrac{1}{n} \).
By recursion, we have \[ T_n = \dfrac{1}{n} \sum\limits_{k=1}^n (n-1 + T_{k-1} + T_{n-k}) \]
-> \( T_n = \Theta(n \lg n) \) (see the slides).