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

$(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$

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