# 组合数学 (Fall 2011)/Generating functions

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## Generating Functions

In Stanley's magnificent book Enumerative Combinatorics, he comments the generating function as "the most useful but most difficult to understand method (for counting)".

The solution to a counting problem is usually represented as some $\displaystyle a_n$ depending a parameter $\displaystyle n$ . Sometimes this $\displaystyle a_n$ is called a counting function as it is a function of the parameter $\displaystyle n$ . $\displaystyle a_n$ can also be treated as a infinite series:

$\displaystyle a_0,a_1,a_2,\ldots$

The ordinary generating function (OGF) defined by $\displaystyle a_n$ is

$\displaystyle G(x)=\sum_{n\ge 0} a_nx^n.$

So $\displaystyle G(x)=a_0+a_1x+a_2x^2+\cdots$ . An expression in this form is called a formal power series, and $\displaystyle a_0,a_1,a_2,\ldots$ is the sequence of coefficients.

Furthermore, the generating function can be expanded as

G(x)=$\displaystyle (\underbrace{1+\cdots+1}_{a_0})+(\underbrace{x+\cdots+x}_{a_1})+(\underbrace{x^2+\cdots+x^2}_{a_2})+\cdots+(\underbrace{x^n+\cdots+x^n}_{a_n})+\cdots$

so it indeed "generates" all the possible instances of the objects we want to count.

Usually, we do not evaluate the generating function $\displaystyle GF(x)$ on any particular value. $\displaystyle x$ remains as a formal variable without assuming any value. The numbers that we want to count are the coefficients carried by the terms in the formal power series. So far the generating function is just another way to represent the sequence

$\displaystyle (a_0,a_1,a_2,\ldots\ldots)$ .

The true power of generating functions comes from the various algebraic operations that we can perform on these generating functions. We use an example to demonstrate this.

### Combinations

Suppose we wish to enumerate all subsets of an $\displaystyle n$ -set. To construct a subset, we specifies for every element of the $\displaystyle n$ -set whether the element is chosen or not. Let us denote the choice to omit an element by $\displaystyle x_0$ , and the choice to include it by $\displaystyle x_1$ . Using "$\displaystyle +$ " to represent "OR", and using the multiplication to denote "AND", the choices of subsets of the $\displaystyle n$ -set are expressed as

$\displaystyle \underbrace{(x_0+x_1)(x_0+x_1)\cdots (x_0+x_1)}_{n\mbox{ elements}}=(x_0+x_1)^n$ .

For example, when $\displaystyle n=3$ , we have

\displaystyle \begin{align} (x_0+x_1)^3 &=x_0x_0x_0+x_0x_0x_1+x_0x_1x_0+x_0x_1x_1\\ &\quad +x_1x_0x_0+x_1x_0x_1+x_1x_1x_0+x_1x_1x_1 \end{align} .

So it "generate" all subsets of the 3-set. Writing $\displaystyle 1$ for $\displaystyle x_0$ and $\displaystyle x$ for $\displaystyle x_1$ , we have $\displaystyle (1+x)^3=1+3x+3x^2+x^3$ . The coefficient of $\displaystyle x^k$ is the number of $\displaystyle k$ -subsets of a 3-element set.

In general, $\displaystyle (1+x)^n$ has the coefficients which are the number of subsets of fixed sizes of an $\displaystyle n$ -element set.

Suppose that we have twelve balls: 3 red, 4 blue, and 5 green. Balls with the same color are indistinguishable.

We want to determine the number of ways to select $\displaystyle k$ balls from these twelve balls, for some $\displaystyle 0\le k\le 12$ .

The generating function of this sequence is

\displaystyle \begin{align} &\quad {\color{Red}(1+x+x^2+x^3)}{\color{Blue}(1+x+x^2+x^3+x^4)}{\color{OliveGreen}(1+x+x^2+x^3+x^4+x^5)}\\ &=1+3x+6x^2+10x^3+14x^4+17x^5+18x^6+17x^7+14x^8+10x^9+6x^{10}+3x^{11}+x^{12}. \end{align}

The coefficient of $\displaystyle x^k$ gives the number of ways to select $\displaystyle k$ balls.

### Fibonacci numbers

Consider the following counting problems.

• Count the number of ways that the nonnegative integer $\displaystyle n$ can be written as a sum of ones and twos (in order).
The problem asks for the number of compositions of $\displaystyle n$ with summands from $\displaystyle \{1,2\}$ . Formally, we are counting the number of tuples $\displaystyle (x_1,x_2,\ldots,x_k)$ for some $\displaystyle k\le n$ such that $\displaystyle x_i\in\{1,2\}$ and $\displaystyle x_1+x_2+\cdots+x_k=n$ .
Let $\displaystyle F_n$ be the solution. We observe that a composition either starts with a 1, in which case the rest is a composition of $\displaystyle n-1$ ; or starts with a 2, in which case the rest is a composition of $\displaystyle n-2$ . So we have the recursion for $\displaystyle F_n$ that
$\displaystyle F_n=F_{n-1}+F_{n-2}$ .
• Count the ways to completely cover a $\displaystyle 2\times n$ rectangle with $\displaystyle 2\times 1$ dominos without any overlaps.
Dominos are identical $\displaystyle 2\times 1$ rectangles, so that only their orientations --- vertical or horizontal matter.
Let $\displaystyle F_n$ be the solution. It also holds that $\displaystyle F_n=F_{n-1}+F_{n-2}$ . The proof is left as an exercise.

In both problems, the solution is given by $\displaystyle F_n$ which satisfies the following recursion.

$\displaystyle F_n=\begin{cases} F_{n-1}+F_{n-2} & \mbox{if }n\ge 2,\\ 1 & \mbox{if }n=1\\ 0 & \mbox{if }n=0. \end{cases}$

$\displaystyle F_n$ is called the Fibonacci number.

 Theorem $\displaystyle F_n=\frac{1}{\sqrt{5}}\left(\phi^n-\hat{\phi}^n\right)$ , where $\displaystyle \phi=\frac{1+\sqrt{5}}{2}$ and $\displaystyle \hat{\phi}=\frac{1-\sqrt{5}}{2}$ .

The quantity $\displaystyle \phi=\frac{1+\sqrt{5}}{2}$ is the so-called golden ratio, a constant with some significance in mathematics and aesthetics.

We now prove this theorem by using generating functions. The ordinary generating function for the Fibonacci number $\displaystyle F_{n}$ is

$\displaystyle G(x)=\sum_{n\ge 0}F_n x^n$ .

We have that $\displaystyle F_{n}=F_{n-1}+F_{n-2}$ for $\displaystyle n\ge 2$ , thus

\displaystyle \begin{align} G(x) &= \sum_{n\ge 0}F_n x^n &= F_0+F_1x+\sum_{n\ge 2}F_n x^n &= x+\sum_{n\ge 2}(F_{n-1}+F_{n-2})x^n. \end{align}

For generating functions, there are general ways to generate $\displaystyle F_{n-1}$ and $\displaystyle F_{n-2}$ , or the coefficients with any smaller indices.

\displaystyle \begin{align} xG(x) &=\sum_{n\ge 0}F_n x^{n+1}=\sum_{n\ge 1}F_{n-1} x^n=\sum_{n\ge 2}F_{n-1} x^n\\ x^2G(x) &=\sum_{n\ge 0}F_n x^{n+2}=\sum_{n\ge 2}F_{n-2} x^n. \end{align}

So we have

$\displaystyle G(x)=x+(x+x^2)G(x)\,$ ,

hence

$\displaystyle G(x)=\frac{x}{1-x-x^2}$ .

The value of $\displaystyle F_n$ is the coefficient of $\displaystyle x^n$ in the Taylor series for this formular, which is $\displaystyle \frac{G^{(n)}(0)}{n!}=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n$ . Although this expansion works in principle, the detailed calculus is rather painful.

It is easier to expand the generating function by breaking it into two geometric series.

 Proposition Let $\displaystyle \phi=\frac{1+\sqrt{5}}{2}$ and $\displaystyle \hat{\phi}=\frac{1-\sqrt{5}}{2}$ . It holds that $\displaystyle \frac{x}{1-x-x^2}=\frac{1}{\sqrt{5}}\cdot\frac{1}{1-\phi x}-\frac{1}{\sqrt{5}}\cdot\frac{1}{1-\hat{\phi} x}$ .

It is easy to verify the above equation, but to deduce it, we need some (high school) calculation.

 $\displaystyle 1-x-x^2$ has two roots $\displaystyle \frac{-1\pm\sqrt{5}}{2}$ . Denote that $\displaystyle \phi=\frac{2}{-1+\sqrt{5}}=\frac{1+\sqrt{5}}{2}$ and $\displaystyle \hat{\phi}=\frac{2}{-1-\sqrt{5}}=\frac{1-\sqrt{5}}{2}$ . Then $\displaystyle (1-x-x^2)=(1-\phi x)(1-\hat{\phi}x)$ , so we can write \displaystyle \begin{align} \frac{x}{1-x-x^2} &=\frac{x}{(1-\phi x)(1-\hat{\phi} x)}\\ &=\frac{\alpha}{(1-\phi x)}+\frac{\beta}{(1-\hat{\phi} x)}, \end{align} where $\displaystyle \alpha$ and $\displaystyle \beta$ satisfying that $\displaystyle \begin{cases} \alpha+\beta=0\\ \alpha\phi+\beta\hat{\phi}= -1. \end{cases}$ Solving this we have that $\displaystyle \alpha=\frac{1}{\sqrt{5}}$ and $\displaystyle \beta=-\frac{1}{\sqrt{5}}$ . Thus, $\displaystyle G(x)=\frac{x}{1-x-x^2}=\frac{1}{\sqrt{5}}\cdot\frac{1}{1-\phi x}-\frac{1}{\sqrt{5}}\cdot\frac{1}{1-\hat{\phi} x}$ .
$\displaystyle \square$

Note that the expression $\displaystyle \frac{1}{1-z}$ has a well known geometric expansion:

$\displaystyle \frac{1}{1-z}=\sum_{n\ge 0}z^n$ .

Therefore, $\displaystyle G(x)$ can be expanded as

\displaystyle \begin{align} G(x) &=\frac{1}{\sqrt{5}}\cdot\frac{1}{1-\phi x}-\frac{1}{\sqrt{5}}\cdot\frac{1}{1-\hat{\phi} x}\\ &=\frac{1}{\sqrt{5}}\sum_{n\ge 0}(\phi x)^n-\frac{1}{\sqrt{5}}\sum_{n\ge 0}(\hat{\phi} x)^n\\ &=\sum_{n\ge 0}\frac{1}{\sqrt{5}}\left(\phi^n-\hat{\phi}^n\right)x^n. \end{align}

So the $\displaystyle n$ th Fibonacci number is given by

$\displaystyle F_n=\frac{1}{\sqrt{5}}\left(\phi^n-\hat{\phi}^n\right)=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n$ .

## Solving recurrences

The following steps describe a general methodology of solving recurrences by generating functions.

1. Give a recursion that computes $\displaystyle a_n$ . In the case of Fibonacci sequence
$\displaystyle a_n=a_{n-1}+a_{n-2}$ .
2. Multiply both sides of the equation by $\displaystyle x^n$ and sum over all $\displaystyle n$ . This gives the generating function
$\displaystyle G(x)=\sum_{n\ge 0}a_nx^n=\sum_{n\ge 0}(a_{n-1}+a_{n-2})x^n$ .
And manipulate the right hand side of the equation so that it becomes some other expression involving $\displaystyle G(x)$ .
$\displaystyle G(x)=x+(x+x^2)G(x)\,$ .
3. Solve the resulting equation to derive an explicit formula for $\displaystyle G(x)$ .
$\displaystyle G(x)=\frac{x}{1-x-x^2}$ .
4. Expand $\displaystyle G(x)$ into a power series and read off the coefficient of $\displaystyle x^n$ , which is a closed form for $\displaystyle a_n$ .

The first step is usually established by combinatorial observations, or explicitly given by the problem. The third step is trivial.

The second and the forth steps need some non-trivial analytic techniques.

### Algebraic operations on generating functions

The second step in the above methodology is somehow tricky. It involves first applying the recurrence to the coefficients of $\displaystyle G(x)$ , which is easy; and then manipulating the resulting formal power series to express it in terms of $\displaystyle G(x)$ , which is more difficult (because it works backwards).

We can apply several natural algebraic operations on the formal power series.

 Generating function manipulation Let $\displaystyle G(x)=\sum_{n\ge 0}g_nx^n$ and $\displaystyle F(x)=\sum_{n\ge 0}f_nx^n$ . \displaystyle \begin{align} &\text{right shift:} &x^k G(x) &= \sum_{n\ge k}g_{n-k}x^n, &\qquad (\mbox{integer }k\ge 0)\\ &\text{left shift:} &\frac{G(x)-\sum_{i=0}^{k-1}g_ix^i}{x^k} &=\sum_{n\ge 0}g_{n+k}x^n, &\qquad (\mbox{integer }k\ge 0)\\ &\text{addition:} & F(x)+G(x) &= \sum_{n\ge 0} (f_n+ g_n)x^n\\ &\text{scaling:} &G(cx) &= \sum_{n\ge 0} c^ng_n x^n\\ &\text{convolution:} &F(x)G(x) &= \sum_{n\ge 0}\sum_{k=0}^nf_kg_{n-k}x^n\\ &\text{differentiation:} &G'(x) &=\sum_{n\ge 0}(n+1)g_{n+1}x^n \end{align}

When manipulating generating functions, these rules are applied backwards; that is, from the right-hand-side to the left-hand-side.

### Expanding generating functions

The last step of solving recurrences by generating function is expanding the closed form generating function $\displaystyle G(x)$ to evaluate its $\displaystyle n$ -th coefficient. In principle, we can always use the Taylor series

$\displaystyle G(x)=\sum_{n\ge 0}\frac{G^{(n)}(0)}{n!}x^n$ ,

where $\displaystyle G^{(n)}(0)$ is the value of the $\displaystyle n$ -th derivative of $\displaystyle G(x)$ evaluated at $\displaystyle x=0$ .

Some interesting special cases are very useful.

#### Geometric sequence

In the example of Fibonacci numbers, we use the well known geometric series:

$\displaystyle \frac{1}{1-x}=\sum_{n\ge 0}x^n$ .

It is useful when we can express the generating function in the form of $\displaystyle G(x)=\frac{a_1}{1-b_1x}+\frac{a_2}{1-b_2x}+\cdots+\frac{a_k}{1-b_kx}$ . The coefficient of $\displaystyle x^n$ in such $\displaystyle G(x)$ is $\displaystyle a_1b_1^n+a_2b_2^n+\cdots+a_kb_k^n$ .

#### Binomial theorem

The $\displaystyle n$ -th derivative of $\displaystyle (1+x)^\alpha$ for some real $\displaystyle \alpha$ is

$\displaystyle \alpha(\alpha-1)(\alpha-2)\cdots(\alpha-n+1)(1+x)^{\alpha-n}$ .

By Taylor series, we get a generalized version of the binomial theorem known as Newton's formula:

 Newton's formular (generalized binomial theorem) If $\displaystyle |x|<1$ , then $\displaystyle (1+x)^\alpha=\sum_{n\ge 0}{\alpha\choose n}x^{n}$ , where $\displaystyle {\alpha\choose n}$ is the generalized binomial coefficient defined by $\displaystyle {\alpha\choose n}=\frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-n+1)}{n!}$ .

### Example: multisets

In the last lecture we gave a combinatorial proof of the number of $\displaystyle k$ -multisets on an $\displaystyle n$ -set. Now we give a generating function approach to the problem.

Let $\displaystyle S=\{x_1,x_2,\ldots,x_n\}$ be an $\displaystyle n$ -element set. We have

$\displaystyle (1+x_1+x_1^2+\cdots)(1+x_2+x_2^2+\cdots)\cdots(1+x_n+x_n^2+\cdots)=\sum_{m:S\rightarrow\mathbb{N}} \prod_{x_i\in S}x_i^{m(x_i)}$ ,

where each $\displaystyle m:S\rightarrow\mathbb{N}$ species a possible multiset on $\displaystyle S$ with multiplicity function $\displaystyle m$ .

Let all $\displaystyle x_i=x$ . Then

\displaystyle \begin{align} (1+x+x^2+\cdots)^n &= \sum_{m:S\rightarrow\mathbb{N}}x^{m(x_1)+\cdots+m(x_n)}\\ &= \sum_{\text{multiset }M\text{ on }S}x^{|M|}\\ &= \sum_{k\ge 0}\left({n\choose k}\right)x^k. \end{align}

The last equation is due to the the definition of $\displaystyle \left({n\choose k}\right)$ . Our task is to evaluate $\displaystyle \left({n\choose k}\right)$ .

Due to the geometric sequence and the Newton's formula

$\displaystyle (1+x+x^2+\cdots)^n=(1-x)^{-n}=\sum_{k\ge 0}{-n\choose k}(-x)^k.$

So

$\displaystyle \left({n\choose k}\right)=(-1)^k{-n\choose k}={n+k-1\choose k}.$

The last equation is due to the definition of the generalized binomial coefficient. We use an analytic (generating function) proof to get the same result of $\displaystyle \left({n\choose k}\right)$ as the combinatorial proof.

## Catalan Number

We now introduce a class of counting problems, all with the same solution, called Catalan number.

The $\displaystyle n$ th Catalan number is denoted as $\displaystyle C_n$ . In Volume 2 of Stanley's Enumerative Combinatorics, a set of exercises describe 66 different interpretations of the Catalan numbers. We give a few examples, cited from Wikipedia.

• Cn is the number of Dyck words of length 2n. A Dyck word is a string consisting of n X's and n Y's such that no initial segment of the string has more Y's than X's (see also Dyck language). For example, the following are the Dyck words of length 6:
XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.
• Re-interpreting the symbol X as an open parenthesis and Y as a close parenthesis, Cn counts the number of expressions containing n pairs of parentheses which are correctly matched:
((()))     ()(())     ()()()     (())()     (()())
• Cn is the number of different ways n + 1 factors can be completely parenthesized (or the number of ways of associating n applications of a binary operator). For n = 3, for example, we have the following five different parenthesizations of four factors:
$\displaystyle ((ab)c)d \quad (a(bc))d \quad(ab)(cd) \quad a((bc)d) \quad a(b(cd))$
• Successive applications of a binary operator can be represented in terms of a full binary tree. (A rooted binary tree is full if every vertex has either two children or no children.) It follows that Cn is the number of full binary trees with n + 1 leaves:
• Cn is the number of monotonic paths along the edges of a grid with n × n square cells, which do not pass above the diagonal. A monotonic path is one which starts in the lower left corner, finishes in the upper right corner, and consists entirely of edges pointing rightwards or upwards. Counting such paths is equivalent to counting Dyck words: X stands for "move right" and Y stands for "move up". The following diagrams show the case n = 4:
• Cn is the number of different ways a convex polygon with n + 2 sides can be cut into triangles by connecting vertices with straight lines. The following hexagons illustrate the case n = 4:
• Cn is the number of stack-sortable permutations of {1, ..., n}. A permutation w is called stack-sortable if S(w) = (1, ..., n), where S(w) is defined recursively as follows: write wunv where n is the largest element in w and u and v are shorter sequences, and set S(w) = S(u)S(v)n, with S being the identity for one-element sequences.
• Cn is the number of ways to tile a stairstep shape of height n with n rectangles. The following figure illustrates the case n = 4:

### Solving the Catalan numbers

 Recurrence relation for Catalan numbers $\displaystyle C_0=1$ , and for $\displaystyle n\ge1$ , $\displaystyle C_n= \sum_{k=0}^{n-1}C_kC_{n-1-k}$ .

Let $\displaystyle G(x)=\sum_{n\ge 0}C_nx^n$ be the generating function. Then

\displaystyle \begin{align} G(x)^2 &=\sum_{n\ge 0}\sum_{k=0}^{n}C_kC_{n-k}x^n\\ xG(x)^2 &=\sum_{n\ge 0}\sum_{k=0}^{n}C_kC_{n-k}x^{n+1}=\sum_{n\ge 1}\sum_{k=0}^{n-1}C_kC_{n-1-k}x^n. \end{align}

Due to the recurrence,

$\displaystyle G(x)=\sum_{n\ge 0}C_nx^n=C_0+\sum_{n\ge 1}\sum_{k=0}^{n-1}C_kC_{n-1-k}x^n=1+xG(x)^2$ .

Solving $\displaystyle xG(x)^2-G(x)+1=0$ , we obtain

$\displaystyle G(x)=\frac{1\pm(1-4x)^{1/2}}{2x}$ .

Only one of these functions can be the generating function for $\displaystyle C_n$ , and it must satisfy

$\displaystyle \lim_{x\rightarrow 0}G(x)=C_0=1$ .

It is easy to check that the correct function is

$\displaystyle G(x)=\frac{1-(1-4x)^{1/2}}{2x}$ .

Expanding $\displaystyle (1-4x)^{1/2}$ by Newton's formula,

\displaystyle \begin{align} (1-4x)^{1/2} &= \sum_{n\ge 0}{1/2\choose n}(-4x)^n\\ &= 1+\sum_{n\ge 1}{1/2\choose n}(-4x)^n\\ &= 1-4x\sum_{n\ge 0}{1/2\choose n+1}(-4x)^n \end{align}

Then, we have

\displaystyle \begin{align} G(x) &= \frac{1-(1-4x)^{1/2}}{2x}\\ &= 2\sum_{n\ge 0}{1/2\choose n+1}(-4x)^n \end{align}

Thus,

\displaystyle \begin{align} C_n &=2{1/2\choose n+1}(-4)^n\\ &=2\cdot\left(\frac{1}{2}\cdot\frac{-1}{2}\cdot\frac{-3}{2}\cdots\frac{-(2n-1)}{2}\right)\cdot\frac{1}{(n+1)!}\cdot(-4)^n\\ &=\frac{2^n}{(n+1)!}\prod_{k=1}^n(2k-1)\\ &=\frac{2^n}{(n+1)!}\prod_{k=1}^n\frac{(2k-1)2k}{2k}\\ &=\frac{1}{n!(n+1)!}\prod_{k=1}^n (2k-1)2k\\ &=\frac{(2n)!}{n!(n+1)!}\\ &=\frac{1}{n+1}{2n\choose n}. \end{align}

So we prove the following closed form for Catalan number.

 Theorem $\displaystyle C_n=\frac{1}{n+1}{2n\choose n}$ .

## Analysis of Quicksort

Given as input a set $\displaystyle S$ of $\displaystyle n$ numbers, we want to sort the numbers in $\displaystyle S$ in increasing order. One of the most famous algorithm for this problem is the Quicksort algorithm.

 Quicksort algorithm Input: a set $\displaystyle S$ of $\displaystyle n$ numbers. if $\displaystyle |S|>1$ do: pick an $\displaystyle x\in S$ as the pivot; partition $\displaystyle S$ into $\displaystyle S_1=\{y\in S\mid y and $\displaystyle S_2=\{y\in S\mid y>x\}$ ; recursively sort $\displaystyle S_1$ and $\displaystyle S_2$ ;

Usually the input set $\displaystyle S$ is given as an array of the $\displaystyle n$ elements in an arbitrary order. The pivot is picked from a fixed position in the arrary (e.g. the first number in the array).

The time complexity of this sorting algorithm is measured by the number of comparisons.

### The quicksort recursion

It is easy to observe that the running time of the algorithm depends only on the relative order of the elements in the input array.

Let $\displaystyle T_n$ be the average number of comparison used by the Quicksort to sort an array of $\displaystyle n$ numbers, where the average is taken over all $\displaystyle n!$ total orders of the elements in the array.

 The Quicksort recursion $\displaystyle T_n= \frac{1}{n}\sum_{k=1}^n\left(n-1+T_{k-1}+T_{n-k}\right)$ and $\displaystyle T_0=T_1=0\,$ .

The recursion is got from averaging over the $\displaystyle n$ sub-cases that the pivot is chosen as the $\displaystyle k$ -th smallest element for $\displaystyle k=1,2,\ldots,n$ . Partitioning the input set $\displaystyle S$ to $\displaystyle S_1$ and $\displaystyle S_2$ takes exactly $\displaystyle n-1$ comparisons regardless the choice of the pivot. Given that the pivot is chosen as the $\displaystyle k$ -th smallest element, the sizes of $\displaystyle S_1$ and $\displaystyle S_2$ are $\displaystyle k-1$ and $\displaystyle n-k$ respectively, thus the costs of sorting $\displaystyle S_1$ and $\displaystyle S_2$ are given recursively by $\displaystyle T_{k-1}$ and $\displaystyle T_{n-k}$ .

### Manipulating the OGF

We write the ordinary generating function (OGF) for the quicksort:

\displaystyle \begin{align} G(x) &=\sum_{n\ge 0}T_nx^n. \end{align}

The quicksort recursion also gives us another equation for formal power series:

\displaystyle \begin{align} \sum_{n\ge 0}nT_nx^n &=\sum_{n\ge 0}\left(\sum_{k=1}^n\left(n-1+T_{k-1}+T_{n-k}\right)\right)x^n\\ &=\sum_{n\ge 0}n(n-1)x^n+2\sum_{n\ge 0}\left(\sum_{k=0}^{n-1}T_{k}\right)x^n. \end{align}

We express the three terms $\displaystyle \sum_{n\ge 0}n(n-1)x^n$ , $\displaystyle 2\sum_{n\ge 0}\left(\sum_{k=0}^{n-1}T_{k}\right)x^n$ and $\displaystyle \sum_{n\ge 0}nT_nx^n$ in closed form involving $\displaystyle G(x)$ as follows:

1. Evaluate the power series: $\displaystyle \sum_{n\ge 0}n(n-1)x^n=x^2\sum_{n\ge 0}n(n-1)x^{n-2}=\frac{2x^2}{(1-x)^3}$ .
2. Apply the convolution rule of OGF: $\displaystyle 2\sum_{n\ge 0}\left(\sum_{k=0}^{n-1}T_{k}\right)x^n=2x\sum_{n\ge 0}\left(\sum_{k=0}^{n}T_{k}\right)x^{n}=2xF(x)G(x)$ ,
where $\displaystyle F(x)=\sum_{n\ge 0}x^n=\frac{1}{1-x}$ ,
therefore, $\displaystyle 2\sum_{n\ge 0}\left(\sum_{k=0}^{n-1}T_{k}\right)x^n=2xF(x)G(x)=\frac{2x}{1-x}G(x)$ .
3. Apply the differentiation rule of OGF: $\displaystyle \sum_{n\ge 0}nT_nx^n=x\sum_{n\ge 0}(n+1)T_{n+1}x^{n}=xG'(x)$ .

Therefore we have the following identity for the OGF for quicksort:

 Equation for the generating function $\displaystyle xG'(x)=\frac{2x^2}{(1-x)^3}+\frac{2x}{1-x}G(x)$ .

### Solving the equation

The above equation for the generating function $\displaystyle G(x)$ is a first-order linear differential equation, for which there is a standard method for solution.

$\displaystyle G(x)=\frac{2}{(1-x)^2}\ln\frac{1}{1-x}$ .

### Expanding

Due to Taylor's expansion,

$\displaystyle \frac{2}{(1-x)^2}=2\sum_{n\ge 0}(n+1) x^{n}$ .
$\displaystyle \ln\frac{1}{1-x}=\sum_{n\ge 1}\frac{x^n}{n}$ .

The generating function $\displaystyle G(x)$ is a convolution product of these two series.

\displaystyle \begin{align} G(x) &=\frac{2}{(1-x)^2}\ln\frac{1}{1-x}\\ &=2\sum_{n\ge 0}(n+1) x^{n}\sum_{n\ge 1}\frac{x^n}{n}\\ &=2\sum_{n\ge 1}\left(\sum_{k=1}^{n}(n-k+1)\frac{1}{k}\right)x^n \end{align}

Thus the coefficient of $\displaystyle x^n$ in $\displaystyle G(x)$ , denoted as $\displaystyle [x^n]G(x)$ , is:

\displaystyle \begin{align} \,[x^n]G(x) &=2\sum_{k=1}^{n}(n-k+1)\frac{1}{k}\\ &=2(n+1)\sum_{k=1}^n\frac{1}{k}-2\sum_{k=1}^nk\cdot\frac{1}{k}\\ &=2(n+1)H(n)-2n, \end{align}

where $\displaystyle H(n)$ is the $\displaystyle n$ th harmonic number defined as $\displaystyle H(n)=\sum_{k=1}^n\frac{1}{k}$ .

Therefore, the average number of comparisons used by the quicksort to sort lists of length $\displaystyle n$ is

$\displaystyle T_n=2(n+1)H(n)-2n= 2n\ln n+O(n)\,$ .

## Reference

• Graham, Knuth, and Patashnik, Concrete Mathematics: A Foundation for Computer Science, Chapter 7.
• van Lin and Wilson, A course in combinatorics, Chapter 14.