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).