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

  1. Recurrence: \( a_n = a_{n-1} + a_{n-2} \)
  2. Manipulation: \( G(x) = x + (x + x^2) G(x) \)
  3. 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).