TCS Wiki - User contributions [en]

Combinatorics (Fall 2010)/Extremal graphs

2010-10-14T07:14:17Z

172.21.1.240: /* Erdős–Stone theorem */

== Extremal Graph Theory ==

=== Mantel's theorem ===
We consider a typical extremal problem for graphs: the largest possible number of edges of '''triangle-free''' graphs, i.e. graphs contains no <math>K_3</math>.

{{Theorem|Theorem (Mantel 1907)|
:Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4}</math>.
}}

{{Prooftitle|First proof. (pigeonhole principle)|
We prove an equivalent theorem: Any <math>G(V,E)</math> with <math>|V|=n</math> and <math>|E|>\frac{n^2}{4}</math> must have a triangle.

Use induction on <math>n</math>. The theorem holds trivially for <math>n\le 3</math>.

Induction hypothesis: assume the theorem hold for <math>|V|\le n-1</math>.

For <math>G</math> with <math>n</math> vertices, without loss of generality, assume that <math>|E|=\frac{n^2}{4}+1</math>, we will show that <math>G</math> must contain a triangle. Take a <math>uv\in E</math>, and let <math>H</math> be the subgraph of <math>G</math> induced by <math>V\setminus \{u,v\}</math>. Clearly, <math>H</math> has <math>n-2</math> vertices.
:'''Case.1:''' If <math>H</math> has <math>>\frac{(n-2)^2}{4}</math> edges, then by the induction hypothesis, <math>H</math> has a triangle.
:'''Case.2:''' If <math>H</math> has <math>\le\frac{(n-2)^2}{4}</math> edges, then at least <math>\left(\frac{n^2}{4}+1\right)-\frac{(n-2)^2}{4}-1=n-1</math> edges are between <math>H</math> and <math>\{u,v\}</math>. By pigeonhole principle, there must be a vertex in <math>H</math> that is adjacent to both <math>u</math> and <math>v</math>. Thus, <math>G</math> has a triangle.
}}

{{Prooftitle|Second proof. (Cauchy-Schwarz inequality)|(Mantel's original proof)
For any edge <math>uv\in E</math>, no vertex can be a neighbor of both <math>u</math> and <math>v</math>, or otherwise there will be a triangle. Thus, for any edge <math>uv\in E</math>, <math>d_u+d_v\le n</math>. It follows that
:<math>\sum_{uv\in E}(d_u+d_v)\le n|E|</math>.
Note that <math>d(v)</math> appears exactly <math>d_v</math> times in the sum, so that
:<math>\sum_{uv\in E}(d_u+d_v)=\sum_{v\in V}d_v^2</math>.
Applying Chauchy-Schwarz inequality,
:<math>
n|E|\ge\sum_{v\in V}d_v^2\ge\frac{\left(\sum_{v\in V}d_v\right)^2}{n}=\frac{4|E|^2}{n},
</math>
where the last equation is due to Euler's equality <math>\sum_{v\in V}d_v=2|E|</math>. The theorem follows.
}}

{{Prooftitle|Third proof. (inequality of the arithmetic and geometric mean)|
Assume that <math>G(V,E)</math> has <math>|V|=n</math> vertices and is triangle-free.

Let <math>A</math> be the largest independent set in <math>G</math> and let <math>\alpha=|A|</math>.
Since <math>G</math> is triangle-free, for very vertex <math>v</math>, all its neighbors must form an independent set, thus <math>d(v)\le \alpha</math> for all <math>v\in V</math>.

Take <math>B=V\setminus A</math> and let <math>\beta=|B|</math>.
Since <math>A</math> is an independent set, all edges in <math>E</math> must have at least one endpoint in <math>B</math>. Counting the edges in <math>E</math> according to their endpoints in <math>B</math>, we obtain <math>|E|\le\sum_{v\in B}d_v</math>. By the inequality of the arithmetic and geometric mean,
:<math>|E|\le\sum_{v\in B}d_v\le\alpha\beta\le\left(\frac{\alpha+\beta}{2}\right)^2=\frac{n^2}{4}</math>.
}}

=== Turán's theorem ===
{{Theorem|Theorem (Turán 1941)|
:Let <math>G(V,E)</math> be a graph with <math>|V|=n</math>. If <math>G</math> has no <math>r</math>-clique, <math>k\ge 2</math>, then
::<math>|E|\le\frac{r-2}{2(r-1)}n^2</math>.
}}

{{Prooftitle|First proof. (induction)|(Turán's original proof)
}}

{{Prooftitle|Second proof. (weight shifting)|(due to Motzkin and Straus)
}}

{{Prooftitle|Third proof. (the probabilistic method)|(due to Alon and Spencer)
}}

{{Prooftitle|Fourth proof.|
Let <math>G(V,E)</math> be a <math>r</math>-clique-free graph on <math>n</math> vertices with a maximum number of edges.
:'''Claim:''' <math>G</math> does not contain three vertices <math>u,v,w</math> such that <math>uv\in E</math> but <math>uw\not\in E, vw\not\in E</math>.
Suppose otherwise. There are two cases.
* '''Case.1:''' <math>d(w)<d(u)</math> or <math>d(w)<d(v)</math>. Without loss of generality, suppose that <math>d(w)<d(u)</math>. We duplicate <math>u</math> by creating a new vertex <math>u'</math> which has exactly the same neighbors as <math>u</math> (but <math>uu'</math> is not an edge). Such duplication will not increase the clique size. We then remove <math>w</math>. The resulting graph <math>G'</math> is still <math>r</math>-clique-free, and has <math>n</math> vertices. The number of edges in <math>G'</math> is
::<math>|E(G')|=|E(G)|+d(u)-d(w)>|E(G)|\,</math>,
:which contradicts the assumption that <math>|E(G)|</math> is maximal.
* '''Case.2:''' <math>d(w)\ge d(u)</math> and <math>d(w)\ge d(v)</math>. Duplicate <math>w</math> twice and delete <math>u</math> and <math>v</math>. The new graph <math>G'</math> has no <math>r</math>-clique, and the number of edges is
::<math>|E(G')|=|E(G)|+2d(w)-(d(u)+d(v)+1)>|E(G)|\,</math>.
:Contradiction again.

The claim implies that <math>uv\not\in E</math> defines an equivalence relation on vertices (to be more precise, it guarantees the transitivity of the relation, while the reflexivity and symmetry hold directly). Graph <math>G</math> must be a complete multipartite graph <math>K_{n_1,n_2,\ldots,n_{r-1}}</math> with <math>n_1+n_2+\cdots +n_{r-1}=n</math>. Optimize the edge number, we have the Turán graph.
}}

=== Erdős–Stone theorem ===
Let <math>K_s^r=K_{\underbrace{s,s,\cdots,s}_{r}}</math> be the complete <math>r</math>-partite graph with <math>s</math> vertices in each class, i.e., the Turán graph <math>T(rs,r)</math>.

{{Theorem|Fundamental theorem of extremal graph theory (Erdős–Stone 1946)|
:For any integers <math>r\ge 2</math> and <math>s\ge 1</math>, and any <math>\epsilon>0</math>, if <math>n</math> is sufficiently large then every graph on <math>n</math> vertices and with at least <math>\left(\frac{r-2}{2(r-1)}+\epsilon\right)n^2</math> edges contains <math>K_{r,s}</math> as a subgraph, i.e.,
:::<math>\mathrm{ex}(n,K_s^r)= \left(\frac{r-2}{2(r-1)}+o(1)\right)n^2</math>.
}}

{{Theorem|Corollary|
:For every nonempty graph <math>H</math>,
::<math>\lim_{n\rightarrow\infty}\frac{\mathrm{ex}(n,H)}{{n\choose 2}}=\frac{\chi(H)-2}{\chi(H)-1}</math>.
}}

== Cycle Structures ==
=== Girth ===

=== Hamiltonian cycle ===

Combinatorics (Fall 2010)/Extremal graphs

2010-10-14T07:04:04Z

172.21.1.240: /* Erdős–Stone theorem */

== Extremal Graph Theory ==

=== Mantel's theorem ===
We consider a typical extremal problem for graphs: the largest possible number of edges of '''triangle-free''' graphs, i.e. graphs contains no <math>K_3</math>.

{{Theorem|Theorem (Mantel 1907)|
:Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4}</math>.
}}

{{Prooftitle|First proof. (pigeonhole principle)|
We prove an equivalent theorem: Any <math>G(V,E)</math> with <math>|V|=n</math> and <math>|E|>\frac{n^2}{4}</math> must have a triangle.

Use induction on <math>n</math>. The theorem holds trivially for <math>n\le 3</math>.

Induction hypothesis: assume the theorem hold for <math>|V|\le n-1</math>.

For <math>G</math> with <math>n</math> vertices, without loss of generality, assume that <math>|E|=\frac{n^2}{4}+1</math>, we will show that <math>G</math> must contain a triangle. Take a <math>uv\in E</math>, and let <math>H</math> be the subgraph of <math>G</math> induced by <math>V\setminus \{u,v\}</math>. Clearly, <math>H</math> has <math>n-2</math> vertices.
:'''Case.1:''' If <math>H</math> has <math>>\frac{(n-2)^2}{4}</math> edges, then by the induction hypothesis, <math>H</math> has a triangle.
:'''Case.2:''' If <math>H</math> has <math>\le\frac{(n-2)^2}{4}</math> edges, then at least <math>\left(\frac{n^2}{4}+1\right)-\frac{(n-2)^2}{4}-1=n-1</math> edges are between <math>H</math> and <math>\{u,v\}</math>. By pigeonhole principle, there must be a vertex in <math>H</math> that is adjacent to both <math>u</math> and <math>v</math>. Thus, <math>G</math> has a triangle.
}}

{{Prooftitle|Second proof. (Cauchy-Schwarz inequality)|(Mantel's original proof)
For any edge <math>uv\in E</math>, no vertex can be a neighbor of both <math>u</math> and <math>v</math>, or otherwise there will be a triangle. Thus, for any edge <math>uv\in E</math>, <math>d_u+d_v\le n</math>. It follows that
:<math>\sum_{uv\in E}(d_u+d_v)\le n|E|</math>.
Note that <math>d(v)</math> appears exactly <math>d_v</math> times in the sum, so that
:<math>\sum_{uv\in E}(d_u+d_v)=\sum_{v\in V}d_v^2</math>.
Applying Chauchy-Schwarz inequality,
:<math>
n|E|\ge\sum_{v\in V}d_v^2\ge\frac{\left(\sum_{v\in V}d_v\right)^2}{n}=\frac{4|E|^2}{n},
</math>
where the last equation is due to Euler's equality <math>\sum_{v\in V}d_v=2|E|</math>. The theorem follows.
}}

{{Prooftitle|Third proof. (inequality of the arithmetic and geometric mean)|
Assume that <math>G(V,E)</math> has <math>|V|=n</math> vertices and is triangle-free.

Let <math>A</math> be the largest independent set in <math>G</math> and let <math>\alpha=|A|</math>.
Since <math>G</math> is triangle-free, for very vertex <math>v</math>, all its neighbors must form an independent set, thus <math>d(v)\le \alpha</math> for all <math>v\in V</math>.

Take <math>B=V\setminus A</math> and let <math>\beta=|B|</math>.
Since <math>A</math> is an independent set, all edges in <math>E</math> must have at least one endpoint in <math>B</math>. Counting the edges in <math>E</math> according to their endpoints in <math>B</math>, we obtain <math>|E|\le\sum_{v\in B}d_v</math>. By the inequality of the arithmetic and geometric mean,
:<math>|E|\le\sum_{v\in B}d_v\le\alpha\beta\le\left(\frac{\alpha+\beta}{2}\right)^2=\frac{n^2}{4}</math>.
}}

=== Turán's theorem ===
{{Theorem|Theorem (Turán 1941)|
:Let <math>G(V,E)</math> be a graph with <math>|V|=n</math>. If <math>G</math> has no <math>r</math>-clique, <math>k\ge 2</math>, then
::<math>|E|\le\frac{r-2}{2(r-1)}n^2</math>.
}}

{{Prooftitle|First proof. (induction)|(Turán's original proof)
}}

{{Prooftitle|Second proof. (weight shifting)|(due to Motzkin and Straus)
}}

{{Prooftitle|Third proof. (the probabilistic method)|(due to Alon and Spencer)
}}

{{Prooftitle|Fourth proof.|
Let <math>G(V,E)</math> be a <math>r</math>-clique-free graph on <math>n</math> vertices with a maximum number of edges.
:'''Claim:''' <math>G</math> does not contain three vertices <math>u,v,w</math> such that <math>uv\in E</math> but <math>uw\not\in E, vw\not\in E</math>.
Suppose otherwise. There are two cases.
* '''Case.1:''' <math>d(w)<d(u)</math> or <math>d(w)<d(v)</math>. Without loss of generality, suppose that <math>d(w)<d(u)</math>. We duplicate <math>u</math> by creating a new vertex <math>u'</math> which has exactly the same neighbors as <math>u</math> (but <math>uu'</math> is not an edge). Such duplication will not increase the clique size. We then remove <math>w</math>. The resulting graph <math>G'</math> is still <math>r</math>-clique-free, and has <math>n</math> vertices. The number of edges in <math>G'</math> is
::<math>|E(G')|=|E(G)|+d(u)-d(w)>|E(G)|\,</math>,
:which contradicts the assumption that <math>|E(G)|</math> is maximal.
* '''Case.2:''' <math>d(w)\ge d(u)</math> and <math>d(w)\ge d(v)</math>. Duplicate <math>w</math> twice and delete <math>u</math> and <math>v</math>. The new graph <math>G'</math> has no <math>r</math>-clique, and the number of edges is
::<math>|E(G')|=|E(G)|+2d(w)-(d(u)+d(v)+1)>|E(G)|\,</math>.
:Contradiction again.

The claim implies that <math>uv\not\in E</math> defines an equivalence relation on vertices (to be more precise, it guarantees the transitivity of the relation, while the reflexivity and symmetry hold directly). Graph <math>G</math> must be a complete multipartite graph <math>K_{n_1,n_2,\ldots,n_{r-1}}</math> with <math>n_1+n_2+\cdots +n_{r-1}=n</math>. Optimize the edge number, we have the Turán graph.
}}

=== Erdős–Stone theorem ===

{{Theorem|Fundamental theorem of extremal graph theory (Erdős–Stone 1946)|
:For any integers <math>r\ge 2</math> and <math>s\ge 1</math>, and any <math>\epsilon>0</math>, if <math>n</math> is sufficiently large then every graph on <math>n</math> vertices and with at least <math>\left(\frac{r-2}{2(r-1)}+\epsilon\right)n^2</math> edges contains <math>K_{r,s}</math> as a subgraph, i.e.,
:::<math>\mathrm{ex}(n,K_{r,s})= \left(\frac{r-2}{2(r-1)}+o(1)\right)n^2</math>.
}}

{{Theorem|Corollary|
:For every nonempty graph <math>H</math>,
::<math>\lim_{n\rightarrow\infty}\frac{\mathrm{ex}(n,H)}{{n\choose 2}}=\frac{\chi(H)-2}{\chi(H)-1}</math>.
}}

== Cycle Structures ==
=== Girth ===

=== Hamiltonian cycle ===

Combinatorics (Fall 2010)/Extremal graphs

2010-10-14T07:00:05Z

172.21.1.240: /* Erdős–Stone theorem */

== Extremal Graph Theory ==

=== Mantel's theorem ===
We consider a typical extremal problem for graphs: the largest possible number of edges of '''triangle-free''' graphs, i.e. graphs contains no <math>K_3</math>.

{{Theorem|Theorem (Mantel 1907)|
:Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4}</math>.
}}

{{Prooftitle|First proof. (pigeonhole principle)|
We prove an equivalent theorem: Any <math>G(V,E)</math> with <math>|V|=n</math> and <math>|E|>\frac{n^2}{4}</math> must have a triangle.

Use induction on <math>n</math>. The theorem holds trivially for <math>n\le 3</math>.

Induction hypothesis: assume the theorem hold for <math>|V|\le n-1</math>.

For <math>G</math> with <math>n</math> vertices, without loss of generality, assume that <math>|E|=\frac{n^2}{4}+1</math>, we will show that <math>G</math> must contain a triangle. Take a <math>uv\in E</math>, and let <math>H</math> be the subgraph of <math>G</math> induced by <math>V\setminus \{u,v\}</math>. Clearly, <math>H</math> has <math>n-2</math> vertices.
:'''Case.1:''' If <math>H</math> has <math>>\frac{(n-2)^2}{4}</math> edges, then by the induction hypothesis, <math>H</math> has a triangle.
:'''Case.2:''' If <math>H</math> has <math>\le\frac{(n-2)^2}{4}</math> edges, then at least <math>\left(\frac{n^2}{4}+1\right)-\frac{(n-2)^2}{4}-1=n-1</math> edges are between <math>H</math> and <math>\{u,v\}</math>. By pigeonhole principle, there must be a vertex in <math>H</math> that is adjacent to both <math>u</math> and <math>v</math>. Thus, <math>G</math> has a triangle.
}}

{{Prooftitle|Second proof. (Cauchy-Schwarz inequality)|(Mantel's original proof)
For any edge <math>uv\in E</math>, no vertex can be a neighbor of both <math>u</math> and <math>v</math>, or otherwise there will be a triangle. Thus, for any edge <math>uv\in E</math>, <math>d_u+d_v\le n</math>. It follows that
:<math>\sum_{uv\in E}(d_u+d_v)\le n|E|</math>.
Note that <math>d(v)</math> appears exactly <math>d_v</math> times in the sum, so that
:<math>\sum_{uv\in E}(d_u+d_v)=\sum_{v\in V}d_v^2</math>.
Applying Chauchy-Schwarz inequality,
:<math>
n|E|\ge\sum_{v\in V}d_v^2\ge\frac{\left(\sum_{v\in V}d_v\right)^2}{n}=\frac{4|E|^2}{n},
</math>
where the last equation is due to Euler's equality <math>\sum_{v\in V}d_v=2|E|</math>. The theorem follows.
}}

{{Prooftitle|Third proof. (inequality of the arithmetic and geometric mean)|
Assume that <math>G(V,E)</math> has <math>|V|=n</math> vertices and is triangle-free.

Let <math>A</math> be the largest independent set in <math>G</math> and let <math>\alpha=|A|</math>.
Since <math>G</math> is triangle-free, for very vertex <math>v</math>, all its neighbors must form an independent set, thus <math>d(v)\le \alpha</math> for all <math>v\in V</math>.

Take <math>B=V\setminus A</math> and let <math>\beta=|B|</math>.
Since <math>A</math> is an independent set, all edges in <math>E</math> must have at least one endpoint in <math>B</math>. Counting the edges in <math>E</math> according to their endpoints in <math>B</math>, we obtain <math>|E|\le\sum_{v\in B}d_v</math>. By the inequality of the arithmetic and geometric mean,
:<math>|E|\le\sum_{v\in B}d_v\le\alpha\beta\le\left(\frac{\alpha+\beta}{2}\right)^2=\frac{n^2}{4}</math>.
}}

=== Turán's theorem ===
{{Theorem|Theorem (Turán 1941)|
:Let <math>G(V,E)</math> be a graph with <math>|V|=n</math>. If <math>G</math> has no <math>r</math>-clique, <math>k\ge 2</math>, then
::<math>|E|\le\frac{r-2}{2(r-1)}n^2</math>.
}}

{{Prooftitle|First proof. (induction)|(Turán's original proof)
}}

{{Prooftitle|Second proof. (weight shifting)|(due to Motzkin and Straus)
}}

{{Prooftitle|Third proof. (the probabilistic method)|(due to Alon and Spencer)
}}

{{Prooftitle|Fourth proof.|
Let <math>G(V,E)</math> be a <math>r</math>-clique-free graph on <math>n</math> vertices with a maximum number of edges.
:'''Claim:''' <math>G</math> does not contain three vertices <math>u,v,w</math> such that <math>uv\in E</math> but <math>uw\not\in E, vw\not\in E</math>.
Suppose otherwise. There are two cases.
* '''Case.1:''' <math>d(w)<d(u)</math> or <math>d(w)<d(v)</math>. Without loss of generality, suppose that <math>d(w)<d(u)</math>. We duplicate <math>u</math> by creating a new vertex <math>u'</math> which has exactly the same neighbors as <math>u</math> (but <math>uu'</math> is not an edge). Such duplication will not increase the clique size. We then remove <math>w</math>. The resulting graph <math>G'</math> is still <math>r</math>-clique-free, and has <math>n</math> vertices. The number of edges in <math>G'</math> is
::<math>|E(G')|=|E(G)|+d(u)-d(w)>|E(G)|\,</math>,
:which contradicts the assumption that <math>|E(G)|</math> is maximal.
* '''Case.2:''' <math>d(w)\ge d(u)</math> and <math>d(w)\ge d(v)</math>. Duplicate <math>w</math> twice and delete <math>u</math> and <math>v</math>. The new graph <math>G'</math> has no <math>r</math>-clique, and the number of edges is
::<math>|E(G')|=|E(G)|+2d(w)-(d(u)+d(v)+1)>|E(G)|\,</math>.
:Contradiction again.

The claim implies that <math>uv\not\in E</math> defines an equivalence relation on vertices (to be more precise, it guarantees the transitivity of the relation, while the reflexivity and symmetry hold directly). Graph <math>G</math> must be a complete multipartite graph <math>K_{n_1,n_2,\ldots,n_{r-1}}</math> with <math>n_1+n_2+\cdots +n_{r-1}=n</math>. Optimize the edge number, we have the Turán graph.
}}

=== Erdős–Stone theorem ===

{{Theorem|Fundamental theorem of extremal graph theory (Erdős–Stone 1946)|
:For any integers <math>r\ge 2</math> and <math>s\ge 1</math>, and any <math>\epsilon>0</math>, there exists an <math>N_0</math> such that every graph with <math>n\ge N_0</math> vertices and at least <math>\left(\frac{r-2}{2(r-1)}+\epsilon\right)n^2</math> edges contains <math>K_{r,s}</math> as a subgraph, i.e.,
:::<math>\mathrm{ex}(n,K_{r,s})= \left(\frac{r-2}{2(r-1)}+o(1)\right)n^2</math>.
}}

{{Theorem|Corollary|
:For every nonempty graph <math>H</math>,
::<math>\lim_{n\rightarrow\infty}\frac{\mathrm{ex}(n,H)}{{n\choose 2}}=\frac{\chi(H)-2}{\chi(H)-1}</math>.
}}

== Cycle Structures ==
=== Girth ===

=== Hamiltonian cycle ===

Combinatorics (Fall 2010)/Extremal graphs

2010-10-14T06:59:33Z

172.21.1.240: /* Erdős–Stone theorem */

== Extremal Graph Theory ==

=== Mantel's theorem ===
We consider a typical extremal problem for graphs: the largest possible number of edges of '''triangle-free''' graphs, i.e. graphs contains no <math>K_3</math>.

{{Theorem|Theorem (Mantel 1907)|
:Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4}</math>.
}}

{{Prooftitle|First proof. (pigeonhole principle)|
We prove an equivalent theorem: Any <math>G(V,E)</math> with <math>|V|=n</math> and <math>|E|>\frac{n^2}{4}</math> must have a triangle.

Use induction on <math>n</math>. The theorem holds trivially for <math>n\le 3</math>.

Induction hypothesis: assume the theorem hold for <math>|V|\le n-1</math>.

For <math>G</math> with <math>n</math> vertices, without loss of generality, assume that <math>|E|=\frac{n^2}{4}+1</math>, we will show that <math>G</math> must contain a triangle. Take a <math>uv\in E</math>, and let <math>H</math> be the subgraph of <math>G</math> induced by <math>V\setminus \{u,v\}</math>. Clearly, <math>H</math> has <math>n-2</math> vertices.
:'''Case.1:''' If <math>H</math> has <math>>\frac{(n-2)^2}{4}</math> edges, then by the induction hypothesis, <math>H</math> has a triangle.
:'''Case.2:''' If <math>H</math> has <math>\le\frac{(n-2)^2}{4}</math> edges, then at least <math>\left(\frac{n^2}{4}+1\right)-\frac{(n-2)^2}{4}-1=n-1</math> edges are between <math>H</math> and <math>\{u,v\}</math>. By pigeonhole principle, there must be a vertex in <math>H</math> that is adjacent to both <math>u</math> and <math>v</math>. Thus, <math>G</math> has a triangle.
}}

{{Prooftitle|Second proof. (Cauchy-Schwarz inequality)|(Mantel's original proof)
For any edge <math>uv\in E</math>, no vertex can be a neighbor of both <math>u</math> and <math>v</math>, or otherwise there will be a triangle. Thus, for any edge <math>uv\in E</math>, <math>d_u+d_v\le n</math>. It follows that
:<math>\sum_{uv\in E}(d_u+d_v)\le n|E|</math>.
Note that <math>d(v)</math> appears exactly <math>d_v</math> times in the sum, so that
:<math>\sum_{uv\in E}(d_u+d_v)=\sum_{v\in V}d_v^2</math>.
Applying Chauchy-Schwarz inequality,
:<math>
n|E|\ge\sum_{v\in V}d_v^2\ge\frac{\left(\sum_{v\in V}d_v\right)^2}{n}=\frac{4|E|^2}{n},
</math>
where the last equation is due to Euler's equality <math>\sum_{v\in V}d_v=2|E|</math>. The theorem follows.
}}

{{Prooftitle|Third proof. (inequality of the arithmetic and geometric mean)|
Assume that <math>G(V,E)</math> has <math>|V|=n</math> vertices and is triangle-free.

Let <math>A</math> be the largest independent set in <math>G</math> and let <math>\alpha=|A|</math>.
Since <math>G</math> is triangle-free, for very vertex <math>v</math>, all its neighbors must form an independent set, thus <math>d(v)\le \alpha</math> for all <math>v\in V</math>.

Take <math>B=V\setminus A</math> and let <math>\beta=|B|</math>.
Since <math>A</math> is an independent set, all edges in <math>E</math> must have at least one endpoint in <math>B</math>. Counting the edges in <math>E</math> according to their endpoints in <math>B</math>, we obtain <math>|E|\le\sum_{v\in B}d_v</math>. By the inequality of the arithmetic and geometric mean,
:<math>|E|\le\sum_{v\in B}d_v\le\alpha\beta\le\left(\frac{\alpha+\beta}{2}\right)^2=\frac{n^2}{4}</math>.
}}

=== Turán's theorem ===
{{Theorem|Theorem (Turán 1941)|
:Let <math>G(V,E)</math> be a graph with <math>|V|=n</math>. If <math>G</math> has no <math>r</math>-clique, <math>k\ge 2</math>, then
::<math>|E|\le\frac{r-2}{2(r-1)}n^2</math>.
}}

{{Prooftitle|First proof. (induction)|(Turán's original proof)
}}

{{Prooftitle|Second proof. (weight shifting)|(due to Motzkin and Straus)
}}

{{Prooftitle|Third proof. (the probabilistic method)|(due to Alon and Spencer)
}}

{{Prooftitle|Fourth proof.|
Let <math>G(V,E)</math> be a <math>r</math>-clique-free graph on <math>n</math> vertices with a maximum number of edges.
:'''Claim:''' <math>G</math> does not contain three vertices <math>u,v,w</math> such that <math>uv\in E</math> but <math>uw\not\in E, vw\not\in E</math>.
Suppose otherwise. There are two cases.
* '''Case.1:''' <math>d(w)<d(u)</math> or <math>d(w)<d(v)</math>. Without loss of generality, suppose that <math>d(w)<d(u)</math>. We duplicate <math>u</math> by creating a new vertex <math>u'</math> which has exactly the same neighbors as <math>u</math> (but <math>uu'</math> is not an edge). Such duplication will not increase the clique size. We then remove <math>w</math>. The resulting graph <math>G'</math> is still <math>r</math>-clique-free, and has <math>n</math> vertices. The number of edges in <math>G'</math> is
::<math>|E(G')|=|E(G)|+d(u)-d(w)>|E(G)|\,</math>,
:which contradicts the assumption that <math>|E(G)|</math> is maximal.
* '''Case.2:''' <math>d(w)\ge d(u)</math> and <math>d(w)\ge d(v)</math>. Duplicate <math>w</math> twice and delete <math>u</math> and <math>v</math>. The new graph <math>G'</math> has no <math>r</math>-clique, and the number of edges is
::<math>|E(G')|=|E(G)|+2d(w)-(d(u)+d(v)+1)>|E(G)|\,</math>.
:Contradiction again.

The claim implies that <math>uv\not\in E</math> defines an equivalence relation on vertices (to be more precise, it guarantees the transitivity of the relation, while the reflexivity and symmetry hold directly). Graph <math>G</math> must be a complete multipartite graph <math>K_{n_1,n_2,\ldots,n_{r-1}}</math> with <math>n_1+n_2+\cdots +n_{r-1}=n</math>. Optimize the edge number, we have the Turán graph.
}}

=== Erdős–Stone theorem ===

{{Theorem|Fundamental theorem of extremal graph theory (Erdős–Stone 1946)|
:For any integers <math>r\ge 2</math> and <math>s\ge 1</math>, and any <math>\epsilon>0</math>, there exists an <math>N_0</math> such that every graph with <math>n\ge N_0</math> vertices and at least <math>\left(\frac{r-2}{2(r-1)}+\epsilon\right)n^2</math> edges contains <math>K_{r,s}</math> as a subgraph, i.e.,
:::<math>\mathrm{ex}(n,K_{s,r})= \left(\frac{r-2}{2(r-1)}+o(1)\right)n^2</math>.
}}

{{Theorem|Corollary|
:For every nonempty graph <math>H</math>,
::<math>\lim_{n\rightarrow\infty}\frac{\mathrm{ex}(n,H)}{{n\choose 2}}=\frac{\chi(H)-2}{\chi(H)-1}</math>.
}}

== Cycle Structures ==
=== Girth ===

=== Hamiltonian cycle ===

Combinatorics (Fall 2010)/Extremal graphs

2010-10-14T06:58:37Z

172.21.1.240: /* Erdős–Stone theorem */

== Extremal Graph Theory ==

=== Mantel's theorem ===
We consider a typical extremal problem for graphs: the largest possible number of edges of '''triangle-free''' graphs, i.e. graphs contains no <math>K_3</math>.

{{Theorem|Theorem (Mantel 1907)|
:Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4}</math>.
}}

{{Prooftitle|First proof. (pigeonhole principle)|
We prove an equivalent theorem: Any <math>G(V,E)</math> with <math>|V|=n</math> and <math>|E|>\frac{n^2}{4}</math> must have a triangle.

Use induction on <math>n</math>. The theorem holds trivially for <math>n\le 3</math>.

Induction hypothesis: assume the theorem hold for <math>|V|\le n-1</math>.

For <math>G</math> with <math>n</math> vertices, without loss of generality, assume that <math>|E|=\frac{n^2}{4}+1</math>, we will show that <math>G</math> must contain a triangle. Take a <math>uv\in E</math>, and let <math>H</math> be the subgraph of <math>G</math> induced by <math>V\setminus \{u,v\}</math>. Clearly, <math>H</math> has <math>n-2</math> vertices.
:'''Case.1:''' If <math>H</math> has <math>>\frac{(n-2)^2}{4}</math> edges, then by the induction hypothesis, <math>H</math> has a triangle.
:'''Case.2:''' If <math>H</math> has <math>\le\frac{(n-2)^2}{4}</math> edges, then at least <math>\left(\frac{n^2}{4}+1\right)-\frac{(n-2)^2}{4}-1=n-1</math> edges are between <math>H</math> and <math>\{u,v\}</math>. By pigeonhole principle, there must be a vertex in <math>H</math> that is adjacent to both <math>u</math> and <math>v</math>. Thus, <math>G</math> has a triangle.
}}

{{Prooftitle|Second proof. (Cauchy-Schwarz inequality)|(Mantel's original proof)
For any edge <math>uv\in E</math>, no vertex can be a neighbor of both <math>u</math> and <math>v</math>, or otherwise there will be a triangle. Thus, for any edge <math>uv\in E</math>, <math>d_u+d_v\le n</math>. It follows that
:<math>\sum_{uv\in E}(d_u+d_v)\le n|E|</math>.
Note that <math>d(v)</math> appears exactly <math>d_v</math> times in the sum, so that
:<math>\sum_{uv\in E}(d_u+d_v)=\sum_{v\in V}d_v^2</math>.
Applying Chauchy-Schwarz inequality,
:<math>
n|E|\ge\sum_{v\in V}d_v^2\ge\frac{\left(\sum_{v\in V}d_v\right)^2}{n}=\frac{4|E|^2}{n},
</math>
where the last equation is due to Euler's equality <math>\sum_{v\in V}d_v=2|E|</math>. The theorem follows.
}}

{{Prooftitle|Third proof. (inequality of the arithmetic and geometric mean)|
Assume that <math>G(V,E)</math> has <math>|V|=n</math> vertices and is triangle-free.

Let <math>A</math> be the largest independent set in <math>G</math> and let <math>\alpha=|A|</math>.
Since <math>G</math> is triangle-free, for very vertex <math>v</math>, all its neighbors must form an independent set, thus <math>d(v)\le \alpha</math> for all <math>v\in V</math>.

Take <math>B=V\setminus A</math> and let <math>\beta=|B|</math>.
Since <math>A</math> is an independent set, all edges in <math>E</math> must have at least one endpoint in <math>B</math>. Counting the edges in <math>E</math> according to their endpoints in <math>B</math>, we obtain <math>|E|\le\sum_{v\in B}d_v</math>. By the inequality of the arithmetic and geometric mean,
:<math>|E|\le\sum_{v\in B}d_v\le\alpha\beta\le\left(\frac{\alpha+\beta}{2}\right)^2=\frac{n^2}{4}</math>.
}}

=== Turán's theorem ===
{{Theorem|Theorem (Turán 1941)|
:Let <math>G(V,E)</math> be a graph with <math>|V|=n</math>. If <math>G</math> has no <math>r</math>-clique, <math>k\ge 2</math>, then
::<math>|E|\le\frac{r-2}{2(r-1)}n^2</math>.
}}

{{Prooftitle|First proof. (induction)|(Turán's original proof)
}}

{{Prooftitle|Second proof. (weight shifting)|(due to Motzkin and Straus)
}}

{{Prooftitle|Third proof. (the probabilistic method)|(due to Alon and Spencer)
}}

{{Prooftitle|Fourth proof.|
Let <math>G(V,E)</math> be a <math>r</math>-clique-free graph on <math>n</math> vertices with a maximum number of edges.
:'''Claim:''' <math>G</math> does not contain three vertices <math>u,v,w</math> such that <math>uv\in E</math> but <math>uw\not\in E, vw\not\in E</math>.
Suppose otherwise. There are two cases.
* '''Case.1:''' <math>d(w)<d(u)</math> or <math>d(w)<d(v)</math>. Without loss of generality, suppose that <math>d(w)<d(u)</math>. We duplicate <math>u</math> by creating a new vertex <math>u'</math> which has exactly the same neighbors as <math>u</math> (but <math>uu'</math> is not an edge). Such duplication will not increase the clique size. We then remove <math>w</math>. The resulting graph <math>G'</math> is still <math>r</math>-clique-free, and has <math>n</math> vertices. The number of edges in <math>G'</math> is
::<math>|E(G')|=|E(G)|+d(u)-d(w)>|E(G)|\,</math>,
:which contradicts the assumption that <math>|E(G)|</math> is maximal.
* '''Case.2:''' <math>d(w)\ge d(u)</math> and <math>d(w)\ge d(v)</math>. Duplicate <math>w</math> twice and delete <math>u</math> and <math>v</math>. The new graph <math>G'</math> has no <math>r</math>-clique, and the number of edges is
::<math>|E(G')|=|E(G)|+2d(w)-(d(u)+d(v)+1)>|E(G)|\,</math>.
:Contradiction again.

The claim implies that <math>uv\not\in E</math> defines an equivalence relation on vertices (to be more precise, it guarantees the transitivity of the relation, while the reflexivity and symmetry hold directly). Graph <math>G</math> must be a complete multipartite graph <math>K_{n_1,n_2,\ldots,n_{r-1}}</math> with <math>n_1+n_2+\cdots +n_{r-1}=n</math>. Optimize the edge number, we have the Turán graph.
}}

=== Erdős–Stone theorem ===

{{Theorem|Fundamental theorem of extremal graph theory (Erdős–Stone 1946)|
:For any integers <math>r\ge 2</math> and <math>s\ge 1</math>, and any <math>\epsilon>0</math>, there exists an <math>N_0</math> such that every graph with <math>n\ge N_0</math> vertices and at least <math>\left(\frac{r-2}{2(r-1)}+\epsilon\right)n^2</math> edges contains <math>K_{r,s}</math> as a subgraph, i.e.,
:::<math>\mathrm{ex}(n,K_{s,r})\le \left(\frac{r-2}{2(r-1)}+o(1)\right)n^2</math>.
}}

{{Theorem|Corollary|
:For every nonempty graph <math>H</math>,
::<math>\lim_{n\rightarrow\infty}\frac{\mathrm{ex}(n,H)}{{n\choose 2}}=\frac{\chi(H)-2}{\chi(H)-1}</math>.
}}

== Cycle Structures ==
=== Girth ===

=== Hamiltonian cycle ===

Combinatorics (Fall 2010)/Extremal graphs

2010-10-14T06:50:52Z

172.21.1.240: /* Erdős–Stone theorem */

== Extremal Graph Theory ==

=== Mantel's theorem ===
We consider a typical extremal problem for graphs: the largest possible number of edges of '''triangle-free''' graphs, i.e. graphs contains no <math>K_3</math>.

{{Theorem|Theorem (Mantel 1907)|
:Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4}</math>.
}}

{{Prooftitle|First proof. (pigeonhole principle)|
We prove an equivalent theorem: Any <math>G(V,E)</math> with <math>|V|=n</math> and <math>|E|>\frac{n^2}{4}</math> must have a triangle.

Use induction on <math>n</math>. The theorem holds trivially for <math>n\le 3</math>.

Induction hypothesis: assume the theorem hold for <math>|V|\le n-1</math>.

For <math>G</math> with <math>n</math> vertices, without loss of generality, assume that <math>|E|=\frac{n^2}{4}+1</math>, we will show that <math>G</math> must contain a triangle. Take a <math>uv\in E</math>, and let <math>H</math> be the subgraph of <math>G</math> induced by <math>V\setminus \{u,v\}</math>. Clearly, <math>H</math> has <math>n-2</math> vertices.
:'''Case.1:''' If <math>H</math> has <math>>\frac{(n-2)^2}{4}</math> edges, then by the induction hypothesis, <math>H</math> has a triangle.
:'''Case.2:''' If <math>H</math> has <math>\le\frac{(n-2)^2}{4}</math> edges, then at least <math>\left(\frac{n^2}{4}+1\right)-\frac{(n-2)^2}{4}-1=n-1</math> edges are between <math>H</math> and <math>\{u,v\}</math>. By pigeonhole principle, there must be a vertex in <math>H</math> that is adjacent to both <math>u</math> and <math>v</math>. Thus, <math>G</math> has a triangle.
}}

{{Prooftitle|Second proof. (Cauchy-Schwarz inequality)|(Mantel's original proof)
For any edge <math>uv\in E</math>, no vertex can be a neighbor of both <math>u</math> and <math>v</math>, or otherwise there will be a triangle. Thus, for any edge <math>uv\in E</math>, <math>d_u+d_v\le n</math>. It follows that
:<math>\sum_{uv\in E}(d_u+d_v)\le n|E|</math>.
Note that <math>d(v)</math> appears exactly <math>d_v</math> times in the sum, so that
:<math>\sum_{uv\in E}(d_u+d_v)=\sum_{v\in V}d_v^2</math>.
Applying Chauchy-Schwarz inequality,
:<math>
n|E|\ge\sum_{v\in V}d_v^2\ge\frac{\left(\sum_{v\in V}d_v\right)^2}{n}=\frac{4|E|^2}{n},
</math>
where the last equation is due to Euler's equality <math>\sum_{v\in V}d_v=2|E|</math>. The theorem follows.
}}

{{Prooftitle|Third proof. (inequality of the arithmetic and geometric mean)|
Assume that <math>G(V,E)</math> has <math>|V|=n</math> vertices and is triangle-free.

Let <math>A</math> be the largest independent set in <math>G</math> and let <math>\alpha=|A|</math>.
Since <math>G</math> is triangle-free, for very vertex <math>v</math>, all its neighbors must form an independent set, thus <math>d(v)\le \alpha</math> for all <math>v\in V</math>.

Take <math>B=V\setminus A</math> and let <math>\beta=|B|</math>.
Since <math>A</math> is an independent set, all edges in <math>E</math> must have at least one endpoint in <math>B</math>. Counting the edges in <math>E</math> according to their endpoints in <math>B</math>, we obtain <math>|E|\le\sum_{v\in B}d_v</math>. By the inequality of the arithmetic and geometric mean,
:<math>|E|\le\sum_{v\in B}d_v\le\alpha\beta\le\left(\frac{\alpha+\beta}{2}\right)^2=\frac{n^2}{4}</math>.
}}

=== Turán's theorem ===
{{Theorem|Theorem (Turán 1941)|
:Let <math>G(V,E)</math> be a graph with <math>|V|=n</math>. If <math>G</math> has no <math>r</math>-clique, <math>k\ge 2</math>, then
::<math>|E|\le\frac{r-2}{2(r-1)}n^2</math>.
}}

{{Prooftitle|First proof. (induction)|(Turán's original proof)
}}

{{Prooftitle|Second proof. (weight shifting)|(due to Motzkin and Straus)
}}

{{Prooftitle|Third proof. (the probabilistic method)|(due to Alon and Spencer)
}}

{{Prooftitle|Fourth proof.|
Let <math>G(V,E)</math> be a <math>r</math>-clique-free graph on <math>n</math> vertices with a maximum number of edges.
:'''Claim:''' <math>G</math> does not contain three vertices <math>u,v,w</math> such that <math>uv\in E</math> but <math>uw\not\in E, vw\not\in E</math>.
Suppose otherwise. There are two cases.
* '''Case.1:''' <math>d(w)<d(u)</math> or <math>d(w)<d(v)</math>. Without loss of generality, suppose that <math>d(w)<d(u)</math>. We duplicate <math>u</math> by creating a new vertex <math>u'</math> which has exactly the same neighbors as <math>u</math> (but <math>uu'</math> is not an edge). Such duplication will not increase the clique size. We then remove <math>w</math>. The resulting graph <math>G'</math> is still <math>r</math>-clique-free, and has <math>n</math> vertices. The number of edges in <math>G'</math> is
::<math>|E(G')|=|E(G)|+d(u)-d(w)>|E(G)|\,</math>,
:which contradicts the assumption that <math>|E(G)|</math> is maximal.
* '''Case.2:''' <math>d(w)\ge d(u)</math> and <math>d(w)\ge d(v)</math>. Duplicate <math>w</math> twice and delete <math>u</math> and <math>v</math>. The new graph <math>G'</math> has no <math>r</math>-clique, and the number of edges is
::<math>|E(G')|=|E(G)|+2d(w)-(d(u)+d(v)+1)>|E(G)|\,</math>.
:Contradiction again.

The claim implies that <math>uv\not\in E</math> defines an equivalence relation on vertices (to be more precise, it guarantees the transitivity of the relation, while the reflexivity and symmetry hold directly). Graph <math>G</math> must be a complete multipartite graph <math>K_{n_1,n_2,\ldots,n_{r-1}}</math> with <math>n_1+n_2+\cdots +n_{r-1}=n</math>. Optimize the edge number, we have the Turán graph.
}}

=== Erdős–Stone theorem ===

{{Theorem|Fundamental theorem of extremal graph theory (Erdős–Stone 1946)|
:For any <math>r\ge 2</math> and <math>s\ge 1</math>, and every sufficiently large <math>n</math>, every graph with <math>n</math> vertices and at least <math>\left(\frac{r-2}{2(r-1)}+\epsilon\right)n^2</math> edges contains <math>K_{r,s}</math> as a subgraph.
}}

{{Theorem|Corollary|

}}

== Cycle Structures ==
=== Girth ===

=== Hamiltonian cycle ===

Combinatorics (Fall 2010)/Partitions, sieve methods

2010-09-12T06:33:00Z

172.21.1.108: /* Reference */

== Partitions ==
We count the ways of partitioning <math>n</math> ''identical'' objects into <math>k</math> ''unordered'' groups. This is equivalent to counting the ways partitioning a number <math>n</math> into <math>k</math> unordered parts.

A '''<math>k</math>-partition''' of a number <math>n</math> is a multiset <math>\{x_1,x_2,\ldots,x_k\}</math> with <math>x_i\ge 1</math> for every element <math>x_i</math> and <math>x_1+x_2+\cdots+x_k=n</math>.

We define <math>p_k(n)</math> as the number of <math>k</math>-partitions of <math>n</math>.

For example, number 7 has the following partitions:
<div class="center"><math>
\begin{align}
&\{7\}
& p_1(7)=1\\
&\{1,6\},\{2,5\},\{3,4\}
& p_2(7)=3\\
&\{1,1,5\}, \{1,2,4\}, \{1,3,3\}, \{2,2,3\}
& p_3(7)=4\\
&\{1,1,1,4\},\{1,1,2,3\}, \{1,2,2,2\}
& p_4(7)=3\\
&\{1,1,1,1,3\},\{1,1,1,2,2\}
& p_5(7)=2\\
&\{1,1,1,1,1,2\}
& p_6(7)=1\\
&\{1,1,1,1,1,1,1\}
& p_7(7)=1
\end{align}
</math></div>

Equivalently, we can also define that A <math>k</math>-partition of a number <math>n</math> is a <math>k</math>-tuple <math>(x_1,x_2,\ldots,x_k)</math> with:
* <math>x_1\ge x_2\ge\cdots\ge x_k\ge 1</math>;
* <math>x_1+x_2+\cdots+x_k=n</math>.

<math>p_k(n)</math> the number of integral solutions to the above system.

Let <math>p(n)=\sum_{k=1}^n p_k(n)</math> be the total number of partitions of <math>n</math>. The function <math>p(n)</math> is called the '''partition number'''.

=== Counting <math>p_k(n)</math>===
We now try to determine <math>p_k(n)</math>. Unlike most problems we learned in the last lecture, <math>p_k(n)</math> does not have a nice closed form formula. We now give a recurrence for <math>p_k(n)</math>.

{{Theorem|Proposition|
:<math>p_k(n)=p_{k-1}(n-1)+p_k(n-k)\,</math>.
}}
{{Proof|
Suppose that <math>(x_1,\ldots,x_k)</math> is a <math>k</math>-partition of <math>n</math>. Note that it must hold that
:<math>x_1\ge x_2\ge \cdots \ge x_k\ge 1</math>.
There are two cases: <math>x_k=1</math> or <math>x_k>1</math>.
;Case 1.
:If <math>x_k=1</math>, then <math>(x_1,\cdots,x_{k-1})</math> is a distinct <math>(k-1)</math>-partition of <math>n-1</math>. And every <math>(k-1)</math>-partition of <math>n-1</math> can be obtained in this way. Thus the number of <math>k</math>-partitions of <math>n</math> in this case is <math>p_{k-1}(n-1)</math>.
;Case 2.
:If <math>x_k>1</math>, then <math>(x_1-1,\cdots,x_{k}-1)</math> is a distinct <math>k</math>-partition of <math>n-k</math>. And every <math>k</math>-partition of <math>n-k</math> can be obtained in this way. Thus the number of <math>k</math>-partitions of <math>n</math> in this case is <math>p_{k}(n-k)</math>.
In conclusion, the number of <math>k</math>-partitions of <math>n</math> is <math>p_{k-1}(n-1)+p_k(n-k)</math>, i.e.
:<math>p_k(n)=p_{k-1}(n-1)+p_k(n-k)\,</math>.
}}

Use the above recurrence, we can compute the <math>p_k(n)</math> for some decent <math>n</math> and <math>k</math> by computer simulation.

If we are not restricted ourselves to the precise estimation of <math>p_k(n)</math>, the next theorem gives an asymptotic estimation of <math>p_k(n)</math>. Note that it only holds for '''constant''' <math>k</math>, i.e. <math>k</math> does not depend on <math>n</math>.

{{Theorem|Theorem|
For any fixed <math>k</math>,
:<math>p_k(n)\sim\frac{n^{k-1}}{k!(k-1)!}</math>,
as <math>n\rightarrow \infty</math>.
}}
{{Proof|
Suppose that <math>(x_1,\ldots,x_k)</math> is a <math>k</math>-partition of <math>n</math>. Then <math>x_1+x_2+\cdots+x_k=n</math> and <math>x_1\ge x_2\ge \cdots \ge x_k\ge 1</math>.

The <math>k!</math> permutations of <math>(x_1,\ldots,x_k)</math> yield at most <math>k!</math> many <math>k</math>-compositions (the ''ordered'' sum of <math>k</math> positive integers). There are <math>{n-1\choose k-1}</math> many <math>k</math>-compositions of <math>n</math>, every one of which can be yielded in this way by permuting a partition. Thus,
:<math>k!p_k(n)\ge{n-1\choose k-1}</math>.

Let <math>y_i=x_i+k-i</math>. That is, <math>y_k=x_k, y_{k-1}=x_k+1, y_{k-2}=x_k+2,\ldots, y_{1}=x_k+k-1</math>. Then, it holds that
* <math>y_1>y_2>\cdots>y_k\ge 1</math>; and
* <math>y_1+y_2+\cdots+y_k=n+\frac{k(k-1)}{2}</math>.
Each permutation of <math>(y_1,y_2,\ldots,y_k)</math> yields a '''distinct''' <math>k</math>-composition of <math>n+\frac{k(k-1)}{2}</math>, because all <math>y_i</math> are distinct.
Thus,
:<math>k!p_k(n)\le {n+\frac{k(k-1)}{2}-1\choose k-1}</math>.

Combining the two inequalities, we have
:<math>\frac{{n-1\choose k-1}}{k!}\le p_k(n)\le \frac{{n+\frac{k(k-1)}{2}-1\choose k-1}}{k!}</math>.
The theorem follows.
}}

=== Ferrers diagram ===
A partition of a number <math>n</math> can be represented as a diagram of dots (or squares), called a '''Ferrers diagram''' (the square version of Ferrers diagram is also called a '''Young diagram''', named after a structured called Young tableaux).

Let <math>(x_1,x_2,\ldots,x_k)</math> with that <math>x_1\ge x_2\ge \cdots x_k\ge 1</math> be a partition of <math>n</math>. Its Ferrers diagram consists of <math>k</math> rows, where the <math>i</math>-th row contains <math>x_i</math> dots (or squares).

<div class="center">
{|border="0"
|
{|border="0"
|[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]
|-
|[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]
|-
|[[File:Chess xot45.svg|22px]]||[[File:Chess xot45.svg|22px]]
|-
|[[File:Chess xot45.svg|22px]]
|}
|
[[File:Chess t45.svg|120px]]
|align=center|
{|border="2" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]
|}
|-
|align=center|Ferrers diagram (''dot version'') of (5,4,2,1)||
|align=center|Ferrers diagram (''square version'') of (5,4,2,1)
|}
</div>

;Conjugate partition
The partition we get by reading the Ferrers diagram by column instead of rows is called the '''conjugate''' of the original partition.
<div class="center">
{|border="0"
|align=center|
{|border="2" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]
|}
|
[[File:Chess t45.svg|120px]]
|align=center|
{|border="2" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]||[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]
|-
|[[File:Chess t45.svg|22px]]
|}
|-
|align=center|<math>(6,4,4,2,1)</math>||
|align=center|conjugate: <math>(5,4,3,3,1,1)</math>
|}
</div>

Clearly,
* different partitions cannot have the same conjugate, and
* every partition of <math>n</math> is the conjugate of some partition of <math>n</math>,
so the conjugation mapping is a permutation on the set of partitions of <math>n</math>. This fact is very useful in proving theorems for partitions numbers.

Some theorems of partitions can be easily proved by representing partitions in Ferrers diagrams.

{{Theorem|Proposition|
# The number of partitions of <math>n</math> which have largest summand <math>k</math>, is <math>p_k(n)</math>.
# The number of <math>n</math> into <math>k</math> parts equals the number of partitions of <math>n-k</math> into at most <math>k</math> parts. Formally,
::<math>p_k(n)=\sum_{j=1}^k p_j(n-k)</math>.
}}
{{Proof|
# For every <math>k</math>-partition, the conjugate partition has largest part <math>k</math>. And vice versa.
# For a <math>k</math>-partition of <math>n</math>, remove the leftmost cell of every row of the Ferrers diagram. Totally <math>k</math> cells are removed and the remaining diagram is a partition of <math>n-k</math> into at most <math>k</math> parts. And for a partition of <math>n-k</math> into at most <math>k</math> parts, add a cell to each of the <math>k</math> rows (including the empty ones). This will give us a <math>k</math>-partition of <math>n</math>. It is easy to see the above mappings are 1-1 correspondences. Thus, the number of <math>n</math> into <math>k</math> parts equals the number of partitions of <math>n-k</math> into at most <math>k</math> parts.
}}

== Principle of Inclusion-Exclusion ==
Let <math>A</math> and <math>B</math> be two finite sets. The cardinality of their union is
:<math>|A\cup B|=|A|+|B|-{\color{Blue}|A\cap B|}</math>.
For three sets <math>A</math>, <math>B</math>, and <math>C</math>, the cardinality of the union of these three sets is computed as
:<math>|A\cup B\cup C|=|A|+|B|+|C|-{\color{Blue}|A\cap B|}-{\color{Blue}|A\cap C|}-{\color{Blue}|B\cap C|}+{\color{Red}|A\cap B\cap C|}</math>.
This is illustrated by the following figure.
::[[Image:Inclusion-exclusion.png|200px|border|center]]

Generally, the '''Principle of Inclusion-Exclusion''' states the rule for computing the union of <math>n</math> finite sets <math>A_1,A_2,\ldots,A_n</math>, such that
{{Equation|
<math>
\begin{align}
\left|\bigcup_{i=1}^nA_i\right|
&=
\sum_{I\subseteq\{1,\ldots,n\}}(-1)^{|I|-1}\left|\bigcap_{i\in I}A_i\right|.
\end{align}
</math>
}}
-----

In combinatorial enumeration, the Principle of Inclusion-Exclusion is usually applied in its complement form.

Let <math>A_1,A_2,\ldots,A_n\subseteq U</math> be subsets of some finite set <math>U</math>. Here <math>U</math> is some universe of combinatorial objects, whose cardinality is easy to calculate (e.g. all strings, tuples, permutations), and each <math>A_i</math> contains the objects with some specific property (e.g. a "pattern") which we want to avoid. The problem is to count the number of objects without any of the <math>n</math> properties. We write <math>\bar{A_i}=U-A</math>. The number of objects without any of the properties <math>A_1,A_2,\ldots,A_n</math> is
{{Equation|
<math>
\begin{align}
\left|\bar{A_1}\cap\bar{A_2}\cap\cdots\cap\bar{A_n}\right|=\left|U-\bigcup_{i=1}^nA_i\right|
&=
|U|-\sum_{I\subseteq\{1,\ldots,n\}}(-1)^{|I|}\left|\bigcap_{i\in I}A_i\right|.
\end{align}
</math>
}}
For an <math>I\subseteq\{1,2,\ldots,n\}</math>, we denote
:<math>A_I=\bigcap_{i\in I}A_i</math>
with the convention that <math>A_\emptyset=U</math>. The above equation is stated as:
{{Theorem|Principle of Inclusion-Exclusion|
:Let <math>A_1,A_2,\ldots,A_n</math> be a family of subsets of <math>U</math>. Then the number of elements of <math>U</math> which lie in none of the subsets <math>A_i</math> is
::<math>\sum_{I\subseteq\{1,\ldots, n\}}(-1)^{|I|}|A_I|</math>.
}}

Let <math>S_k=\sum_{|I|=k}|A_I|\,</math>. Conventionally, <math>S_0=|A_\emptyset|=|U|</math>. The principle of inclusion-exclusion can be expressed as
{{Equation|<math>
S_0-S_1+S_2+\cdots+(-1)^nS_n.
</math>
}}

=== Surjections ===
In the twelvefold way, we discuss the counting problems incurred by the mappings <math>f:N\rightarrow M</math>. The basic case is that elements from both <math>N</math> and <math>M</math> are distinguishable. In this case, it is easy to count the number of arbitrary mappings (which is <math>m^n</math>) and the number of injective (one-to-one) mappings (which is <math>(m)_n</math>), but the number of surjective is difficult. Here we apply the principle of inclusion-exclusion to count the number of surjective (onto) mappings.
{{Theorem|Theorem|
:The number of surjective mappings from an <math>n</math>-set to an <math>m</math>-set is given by
::<math>\sum_{k=1}^m(-1)^{m-k}{m\choose k}k^n</math>.
}}
{{Proof|
Let <math>U=\{f:[n]\rightarrow[m]\}</math> be the set of mappings from <math>[n]</math> to <math>[m]</math>. Then <math>|U|=m^n</math>.

For <math>i\in[m]</math>, let <math>A_i</math> be the set of mappings <math>f:[n]\rightarrow[m]</math> that none of <math>j\in[n]</math> is mapped to <math>i</math>, i.e. <math>A_i=\{f:[n]\rightarrow[m]\setminus\{i\}\}</math>, thus <math>|A_i|=(m-1)^n</math>.

More generally, for <math>I\subseteq [m]</math>, <math>A_I=\bigcap_{i\in I}A_i</math> contains the mappings <math>f:[n]\rightarrow[m]\setminus I</math>. And <math>|A_I|=(m-|I|)^n\,</math>.

A mapping <math>f:[n]\rightarrow[m]</math> is surjective if <math>f</math> lies in none of <math>A_i</math>. By the principle of inclusion-exclusion, the number of surjective <math>f:[n]\rightarrow[m]</math> is
:<math>\sum_{I\subseteq[m]}(-1)^{|I|}\left|A_I\right|=\sum_{I\subseteq[m]}(-1)^{|I|}(m-|I|)^n=\sum_{j=0}^m(-1)^j{m\choose j}(m-j)^n</math>.
Let <math>k=m-j</math>. The theorem is proved.
}}

Recall that, in the twelvefold way, we establish a relation between surjections and partitions.

* Surjection to ordered partition:
:For a surjective <math>f:[n]\rightarrow[m]</math>, <math>(f^{-1}(0),f^{-1}(1),\ldots,f^{-1}(m-1))</math> is an '''ordered partition''' of <math>[n]</math>.
* Ordered partition to surjection:
:For an ordered <math>m</math>-partition <math>(B_0,B_1,\ldots, B_{m-1})</math> of <math>[n]</math>, we can define a function <math>f:[n]\rightarrow[m]</math> by letting <math>f(i)=j</math> if and only if <math>i\in B_j</math>. <math>f</math> is surjective since as a partition, none of <math>B_i</math> is empty.

Therefore, we have a one-to-one correspondence between surjective mappings from an <math>n</math>-set to an <math>m</math>-set and the ordered <math>m</math>-partitions of an <math>n</math>-set.

The Stirling number of the second kind <math>S(n,m)</math> is the number of <math>m</math>-partitions of an <math>n</math>-set. There are <math>m!</math> ways to order an <math>m</math>-partition, thus the number of surjective mappings <math>f:[n]\rightarrow[m]</math> is <math>m! S(n,m)</math>. Combining with what we have proved for surjections, we give the following result for the Stirling number of the second kind.

{{Theorem|Proposition|
:<math>S(n,m)=\frac{1}{m!}\sum_{k=1}^m(-1)^{m-k}{m\choose k}k^n</math>.
}}

=== Derangements ===
We now count the number of bijections from a set to itself with no fixed points. This is the '''derangement problem'''.

For a permutation <math>\pi</math> of <math>\{1,2,\ldots,n\}</math>, a '''fixed point''' is such an <math>i\in\{1,2,\ldots,n\}</math> that <math>\pi(i)=i</math>.
A [http://en.wikipedia.org/wiki/Derangement '''derangement'''] of <math>\{1,2,\ldots,n\}</math> is a permutation of <math>\{1,2,\ldots,n\}</math> that has no fixed points.

{{Theorem|Theorem|
:The number of derangements of <math>\{1,2,\ldots,n\}</math> given by
::<math>n!\sum_{k=0}^n\frac{(-1)^k}{k!}\approx \frac{n!}{\mathrm{e}}</math>.
}}
{{Proof|
Let <math>U</math> be the set of all permutations of <math>\{1,2,\ldots,n\}</math>. So <math>|U|=n!</math>.

Let <math>A_i</math> be the set of permutations with fixed point <math>i</math>; so <math>|A_i|=(n-1)!</math>. More generally, for any <math>I\subseteq \{1,2,\ldots,n\}</math>, <math>A_I=\bigcap_{i\in I}A_i</math>, and <math>|A_I|=(n-|I|)!</math>, since permutations in <math>A_I</math> fix every point in <math>I</math> and permute the remaining points arbitrarily. A permutation is a derangement if and only if it lies in none of the sets <math>A_i</math>. So the number of derangements is
:<math>\sum_{I\subseteq\{1,2,\ldots,n\}}(-1)^{|I|}(n-|I|)!=\sum_{k=0}^n(-1)^k{n\choose k}(n-k)!=n!\sum_{k=0}^n\frac{(-1)^k}{k!}.</math>
By Taylor's series,
:<math>\frac{1}{\mathrm{e}}=\sum_{k=0}^\infty\frac{(-1)^k}{k!}=\sum_{k=0}^n\frac{(-1)^k}{k!}\pm o\left(\frac{1}{n!}\right)</math>.
It is not hard to see that <math>n!\sum_{k=0}^n\frac{(-1)^k}{k!}</math> is the closest integer to <math>\frac{n!}{\mathrm{e}}</math>.
}}

Therefore, there are about <math>\frac{1}{\mathrm{e}}</math> fraction of all permutations with no fixed points.

=== Permutations with restricted positions ===
We introduce a general theory of counting permutations with restricted positions. In the derangement problem, we count the number of permutations that <math>\pi(i)\neq i</math>. We now generalize to the problem of counting permutations which avoid a set of arbitrarily specified positions.

It is traditionally described using terminology from the game of chess. Let <math>B\subseteq \{1,\ldots,n\}\times \{1,\ldots,n\}</math>, called a '''board'''. As illustrated below, we can think of <math>B</math> as a chess board, with the positions in <math>B</math> marked by "<math>\times</math>".
{{Chess diagram small
|
|
|=
8 |__|xx|xx|__|xx|__|__|xx|=
7 |xx|__|__|xx|__|__|xx|__|=
6 |xx|__|xx|xx|__|xx|xx|__|=
5 |__|xx|__|__|xx|__|xx|__|=
4 |xx|__|__|__|xx|xx|xx|__|=
3 |__|xx|__|xx|__|__|__|xx|=
2 |__|__|xx|__|xx|__|__|xx|=
1 |xx|__|__|xx|__|xx|__|__|=
a b c d e f g h
|
}}
For a permutation <math>\pi</math> of <math>\{1,\ldots,n\}</math>, define the '''graph''' <math>G_\pi(V,E)</math> as
:<math>
\begin{align}
G_\pi &= \{(i,\pi(i))\mid i\in \{1,2,\ldots,n\}\}.
\end{align}
</math>
This can also be viewed as a set of marked positions on a chess board. Each row and each column has only one marked position, because <math>\pi</math> is a permutation. Thus, we can identify each <math>G_\pi</math> as a placement of <math>n</math> rooks (“城堡”，规则同中国象棋里的“车”) without attacking each other.

For example, the following is the <math>G_\pi</math> of such <math>\pi</math> that <math>\pi(i)=i</math>.
{{Chess diagram small
|
|
|=
8 |rl|__|__|__|__|__|__|__|=
7 |__|rl|__|__|__|__|__|__|=
6 |__|__|rl|__|__|__|__|__|=
5 |__|__|__|rl|__|__|__|__|=
4 |__|__|__|__|rl|__|__|__|=
3 |__|__|__|__|__|rl|__|__|=
2 |__|__|__|__|__|__|rl|__|=
1 |__|__|__|__|__|__|__|rl|=
a b c d e f g h
|
}}
Now define
:<math>\begin{align}
N_0 &= \left|\left\{\pi\mid B\cap G_\pi=\emptyset\right\}\right|\\
r_k &= \mbox{number of }k\mbox{-subsets of }B\mbox{ such that no two elements have a common coordinate}\\
&=\left|\left\{S\in{B\choose k} \,\bigg|\, \forall (i_1,j_1),(i_2,j_2)\in S, i_1\neq i_2, j_1\neq j_2 \right\}\right|
\end{align}
</math>
Interpreted in chess game,
* <math>B</math>: a set of marked positions in an <math>[n]\times [n]</math> chess board.
* <math>N_0</math>: the number of ways of placing <math>n</math> non-attacking rooks on the chess board such that none of these rooks lie in <math>B</math>.
* <math>r_k</math>: number of ways of placing <math>k</math> non-attacking rooks on <math>B</math>.

Our goal is to count <math>N_0</math> in terms of <math>r_k</math>. This gives the number of permutations avoid all positions in a <math>B</math>.

{{Theorem|Theorem|
:<math>N_0=\sum_{k=0}^n(-1)^kr_k(n-k)!</math>.
}}
{{Proof|
For each <math>i\in[n]</math>, let <math>A_i=\{\pi\mid (i,\pi(i))\in B\}</math> be the set of permutations <math>\pi</math> whose <math>i</math>-th position is in <math>B</math>.

<math>N_0</math> is the number of permutations avoid all positions in <math>B</math>. Thus, our goal is to count the number of permutations <math>\pi</math> in none of <math>A_i</math> for <math>i\in [n]</math>.

For each <math>I\subseteq [n]</math>, let <math>A_I=\bigcap_{i\in I}A_i</math>, which is the set of permutations <math>\pi</math> such that <math>(i,\pi(i))\in B</math> for all <math>i\in I</math>. Due to the principle of inclusion-exclusion,
:<math>N_0=\sum_{I\subseteq [n]} (-1)^{|I|}|A_I|=\sum_{k=0}^n(-1)^k\sum_{I\in{[n]\choose k}}|A_I|</math>.

The next observation is that
:<math>\sum_{I\in{[n]\choose k}}|A_I|=r_k(n-k)!</math>,
because we can count both sides by first placing <math>k</math> non-attacking rooks on <math>B</math> and placing <math>n-k</math> additional non-attacking rooks on <math>[n]\times [n]</math> in <math>(n-k)!</math> ways.

Therefore,
:<math>N_0=\sum_{k=0}^n(-1)^kr_k(n-k)!</math>.
}}

====Derangement problem====
We use the above general method to solve the derange problem again.

Take <math>B=\{(1,1),(2,2),\ldots,(n,n)\}</math> as the chess board. A derangement <math>\pi</math> is a placement of <math>n</math> non-attacking rooks such that none of them is in <math>B</math>.
{{Chess diagram small
|
|
|=
8 |xx|__|__|__|__|__|__|__|=
7 |__|xx|__|__|__|__|__|__|=
6 |__|__|xx|__|__|__|__|__|=
5 |__|__|__|xx|__|__|__|__|=
4 |__|__|__|__|xx|__|__|__|=
3 |__|__|__|__|__|xx|__|__|=
2 |__|__|__|__|__|__|xx|__|=
1 |__|__|__|__|__|__|__|xx|=
a b c d e f g h
|
}}
Clearly, the number of ways of placing <math>k</math> non-attacking rooks on <math>B</math> is <math>r_k={n\choose k}</math>. We want to count <math>N_0</math>, which gives the number of ways of placing <math>n</math> non-attacking rooks such that none of these rooks lie in <math>B</math>.

By the above theorem
:<math>
N_0=\sum_{k=0}^n(-1)^kr_k(n-k)!=\sum_{k=0}^n(-1)^k{n\choose k}(n-k)!=\sum_{k=0}^n(-1)^k\frac{n!}{k!}=n!\sum_{k=0}^n(-1)^k\frac{1}{k!}\approx\frac{n!}{e}.
</math>

====Problème des ménages====
Suppose that in a banquet, we want to seat <math>n</math> couples at a circular table, satisfying the following constraints:
* Men and women are in alternate places.
* No one sits next to his/her spouse.

In how many ways can this be done?

(For convenience, we assume that every seat at the table marked differently so that rotating the seats clockwise or anti-clockwise will end up with a '''different''' solution.)

First, let the <math>n</math> ladies find their seats. They may either sit at the odd numbered seats or even numbered seats, in either case, there are <math>n!</math> different orders. Thus, there are <math>2(n!)</math> ways to seat the <math>n</math> ladies.

After sitting the wives, we label the remaining <math>n</math> places clockwise as <math>0,1,\ldots, n-1</math>. And a seating of the <math>n</math> husbands is given by a permutation <math>\pi</math> of <math>[n]</math> defined as follows. Let <math>\pi(i)</math> be the seat of the husband of he lady sitting at the <math>i</math>-th place.

It is easy to see that <math>\pi</math> satisfies that <math>\pi(i)\neq i</math> and <math>\pi(i)\not\equiv i+1\pmod n</math>, and every permutation <math>\pi</math> with these properties gives a feasible seating of the <math>n</math> husbands. Thus, we only need to count the number of permutations <math>\pi</math> such that <math>\pi(i)\not\equiv i, i+1\pmod n</math>.

Take <math>B=\{(0,0),(1,1),\ldots,(n-1,n-1), (0,1),(1,2),\ldots,(n-2,n-1),(n-1,0)\}</math> as the chess board. A permutation <math>\pi</math> which defines a way of seating the husbands, is a placement of <math>n</math> non-attacking rooks such that none of them is in <math>B</math>.
{{Chess diagram small
|
|
|=
8 |xx|xx|__|__|__|__|__|__|=
7 |__|xx|xx|__|__|__|__|__|=
6 |__|__|xx|xx|__|__|__|__|=
5 |__|__|__|xx|xx|__|__|__|=
4 |__|__|__|__|xx|xx|__|__|=
3 |__|__|__|__|__|xx|xx|__|=
2 |__|__|__|__|__|__|xx|xx|=
1 |xx|__|__|__|__|__|__|xx|=
a b c d e f g h
|
}}
We need to compute <math>r_k</math>, the number of ways of placing <math>k</math> non-attacking rooks on <math>B</math>. For our choice of <math>B</math>, <math>r_k</math> is the number of ways of choosing <math>k</math> points, no two consecutive, from a collection of <math>2n</math> points arranged in a circle.

We first see how to do this in a ''line''.
{{Theorem|Lemma|
:The number of ways of choosing <math>k</math> ''non-consecutive'' objects from a collection of <math>m</math> objects arranged in a ''line'', is <math>{m-k+1\choose k}</math>.
}}
{{Proof|
We draw a line of <math>m-k</math> black points, and then insert <math>k</math> red points into the <math>m-k+1</math> spaces between the black points (including the beginning and end).
::<math>
\begin{align}
&\sqcup \, \bullet \, \sqcup \, \bullet \, \sqcup \, \bullet \, \sqcup \, \bullet \, \sqcup \, \bullet \, \sqcup \, \bullet \, \sqcup \, \bullet \, \sqcup \\
&\qquad\qquad\qquad\quad\Downarrow\\
&\sqcup \, \bullet \,\, {\color{Red}\bullet} \, \bullet \,\, {\color{Red}\bullet} \, \bullet \, \sqcup \, \bullet \,\, {\color{Red}\bullet}\, \, \bullet \, \sqcup \, \bullet \, \sqcup \, \bullet \,\, {\color{Red}\bullet}
\end{align}
</math>
This gives us a line of <math>m</math> points, and the red points specifies the chosen objects, which are non-consecutive. The mapping is 1-1 correspondence.
There are <math>{m-k+1\choose k}</math> ways of placing <math>k</math> red points into <math>m-k+1</math> spaces.
}}

The problem of choosing non-consecutive objects in a circle can be reduced to the case that the objects are in a line.

{{Theorem|Lemma|
:The number of ways of choosing <math>k</math> ''non-consecutive'' objects from a collection of <math>m</math> objects arranged in a ''circle'', is <math>\frac{m}{m-k}{m-k\choose k}</math>.
}}
{{Proof|
Let <math>f(m,k)</math> be the desired number; and let <math>g(m,k)</math> be the number of ways of choosing <math>k</math> non-consecutive points from <math>m</math> points arranged in a circle, next coloring the <math>k</math> points red, and then coloring one of the uncolored point blue.

Clearly, <math>g(m,k)=(m-k)f(m,k)</math>.

But we can also compute <math>g(m,k)</math> as follows:
* Choose one of the <math>m</math> points and color it blue. This gives us <math>m</math> ways.
* Cut the circle to make a line of <math>m-1</math> points by removing the blue point.
* Choose <math>k</math> non-consecutive points from the line of <math>m-1</math> points and color them red. This gives <math>{m-k\choose k}</math> ways due to the previous lemma.

Thus, <math>g(m,k)=m{m-k\choose k}</math>. Therefore we have the desired number <math>f(m,k)=\frac{m}{m-k}{m-k\choose k}</math>.
}}

By the above lemma, we have that <math>r_k=\frac{2n}{2n-k}{2n-k\choose k}</math>. Then apply the theorem of counting permutations with restricted positions,
:<math>
N_0=\sum_{k=0}^n(-1)^kr_k(n-k)!=\sum_{k=0}^n(-1)^k\frac{2n}{2n-k}{2n-k\choose k}(n-k)!.
</math>

This gives the number of ways of seating the <math>n</math> husbands ''after the ladies are seated''. Recall that there are <math>2n!</math> ways of seating the <math>n</math> ladies. Thus, the total number of ways of seating <math>n</math> couples as required by problème des ménages is
:<math>
2n!\sum_{k=0}^n(-1)^k\frac{2n}{2n-k}{2n-k\choose k}(n-k)!.
</math>

=== The Euler totient function ===
Two integers <math>m, n</math> are said to be '''relatively prime''' if their greatest common diviser <math>\mathrm{gcd}(m,n)=1</math>. For a positive integer <math>n</math>, let <math>\phi(n)</math> be the number of positive integers from <math>\{1,2,\ldots,n\}</math> that are relative prime to <math>n</math>. This function, called the Euler <math>\phi</math> function or '''the Euler totient function''', is fundamental in number theory.

We know derive a formula for this function by using the principle of inclusion-exclusion.
{{Theorem|Theorem (The Euler totient function)|
Suppose <math>n</math> is divisible by precisely <math>r</math> different primes, denoted <math>p_1,\ldots,p_r</math>. Then
:<math>\phi(n)=n\prod_{i=1}^r\left(1-\frac{1}{p_i}\right)</math>.
}}
{{Proof|
Let <math>U=\{1,2,\ldots,n\}</math> be the universe. The number of positive integers from <math>U</math> which is divisible by some <math>p_{i_1},p_{i_2},\ldots,p_{i_s}\in\{p_1,\ldots,p_r\}</math>, is <math>\frac{n}{p_{i_1}p_{i_2}\cdots p_{i_s}}</math>.

<math>\phi(n)</math> is the number of integers from <math>U</math> which is not divisible by any <math>p_1,\ldots,p_r</math>.
By principle of inclusion-exclusion,
:<math>
\begin{align}
\phi(n)
&=n+\sum_{k=1}^r(-1)^k\sum_{1\le i_1<i_2<\cdots <i_k\le n}\frac{n}{p_{i_1}p_{i_2}\cdots p_{i_k}}\\
&=n-\sum_{1\le i\le n}\frac{n}{p_i}+\sum_{1\le i<j\le n}\frac{n}{p_i p_j}-\sum_{1\le i<j<k\le n}\frac{n}{p_{i} p_{j} p_{k}}+\cdots + (-1)^r\frac{n}{p_{1}p_{2}\cdots p_{r}}\\
&=n\left(1-\sum_{1\le i\le n}\frac{1}{p_i}+\sum_{1\le i<j\le n}\frac{1}{p_i p_j}-\sum_{1\le i<j<k\le n}\frac{1}{p_{i} p_{j} p_{k}}+\cdots + (-1)^r\frac{1}{p_{1}p_{2}\cdots p_{r}}\right)\\
&=n\prod_{i=1}^n\left(1-\frac{1}{p_i}\right).
\end{align}
</math>
}}

== Reference ==
* ''Stanley,'' Enumerative Combinatorics, Volume 1, Chapter 2.
* ''van Lin and Wilson'', A course in combinatorics, Chapter 10, 15.

Combinatorics (Fall 2010)/Generating functions

2010-09-12T06:32:36Z

172.21.1.108: /* Reference */

== 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 <math>a_n</math> depending a parameter <math>n</math>. Sometimes this <math>a_n</math> is called a ''counting function'' as it is a function of the parameter <math>n</math>. <math>a_n</math> can also be treated as a infinite series:
:<math>a_0,a_1,a_2,\ldots</math>

The '''ordinary generating function (OGF)''' defined by <math>a_n</math> is
:<math>
G(x)=\sum_{n\ge 0} a_nx^n.
</math>

So <math>G(x)=a_0+a_1x+a_2x^2+\cdots</math>. An expression in this form is called a [http://en.wikipedia.org/wiki/Formal_power_series '''formal power series'''], and <math>a_0,a_1,a_2,\ldots</math> is the sequence of '''coefficients'''.

Furthermore, the generating function can be expanded as
:G(x)=<math>(\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</math>
so it indeed "generates" all the possible instances of the objects we want to count.

Usually, we do not evaluate the generating function <math>GF(x)</math> on any particular value. <math>x</math> 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
:<math>(a_0,a_1,a_2,\ldots\ldots)</math>.

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 <math>n</math>-set. To construct a subset, we specifies for every element of the <math>n</math>-set whether the element is chosen or not. Let us denote the choice to omit an element by <math>x_0</math>, and the choice to include it by <math>x_1</math>. Using "<math>+</math>" to represent "OR", and using the multiplication to denote "AND", the choices of subsets of the <math>n</math>-set are expressed as
:<math>\underbrace{(x_0+x_1)(x_0+x_1)\cdots (x_0+x_1)}_{n\mbox{ elements}}=(x_0+x_1)^n</math>.

For example, when <math>n=3</math>, we have
:<math>\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}</math>.

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

In general, <math>(1+x)^n</math> has the coefficients which are the number of subsets of fixed sizes of an <math>n</math>-element set.

-----

Suppose that we have twelve balls: <font color="red">3 red</font>, <font color="blue">4 blue</font>, and <font color="green">5 green</font>. Balls with the same color are indistinguishable.

We want to determine the number of ways to select <math>k</math> balls from these twelve balls, for some <math>0\le k\le 12</math>.

The generating function of this sequence is
:<math>\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}</math>
The coefficient of <math>x^k</math> gives the number of ways to select <math>k</math> balls.

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

In both problems, the solution is given by <math>F_n</math> which satisfies the following recursion.
:<math>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}</math>

<math>F_n</math> is called the [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number].

{{Theorem|Theorem|
::<math>F_n=\frac{1}{\sqrt{5}}\left(\phi^n-\hat{\phi}^n\right)</math>,
:where <math>\phi=\frac{1+\sqrt{5}}{2}</math> and <math>\hat{\phi}=\frac{1-\sqrt{5}}{2}</math>.
}}
The quantity <math>\phi=\frac{1+\sqrt{5}}{2}</math> is the so-called [http://en.wikipedia.org/wiki/Golden_ratio 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 <math>F_{n}</math> is
:<math>G(x)=\sum_{n\ge 0}F_n x^n</math>.
We have that <math>F_{n}=F_{n-1}+F_{n-2}</math> for <math>n\ge 2</math>, thus
:<math>\begin{align}
G(x)
&=
\sum_{n\ge 0}F_n x^n
&=
x+\sum_{n\ge 2}(F_{n-1}+F_{n-2})x^n.
\end{align}
</math>
For generating functions, there are general ways to generate <math>F_{n-1}</math> and <math>F_{n-2}</math>, or the coefficients with any smaller indices.
:<math>
\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}
</math>
So we have
:<math>G(x)=x+(x+x^2)G(x)\,</math>,
hence
:<math>G(x)=\frac{x}{1-x-x^2}</math>.
The value of <math>F_n</math> is the coefficient of <math>x^n</math> in the Taylor series for this formular, which is <math>\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</math>. 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.
{{Theorem|Proposition|
:Let <math>\phi=\frac{1+\sqrt{5}}{2}</math> and <math>\hat{\phi}=\frac{1-\sqrt{5}}{2}</math>. It holds that
::<math>\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}</math>.
}}

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

{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|
:{|
|
<math>1-x-x^2</math> has two roots <math>\frac{-1\pm\sqrt{5}}{2}</math>.

Denote that <math>\phi=\frac{2}{-1+\sqrt{5}}=\frac{1+\sqrt{5}}{2}</math> and <math>\hat{\phi}=\frac{2}{-1-\sqrt{5}}=\frac{1-\sqrt{5}}{2}</math>.

Then <math>(1-x-x^2)=(1-\phi x)(1-\hat{\phi}x)</math>, so we can write
:<math>
\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}
</math>
where <math>\alpha</math> and <math>\beta</math> satisfying that
:<math>\begin{cases}
\alpha+\beta=0\\
\alpha\phi+\beta\hat{\phi}= -1.
\end{cases}</math>
Solving this we have that <math>\alpha=\frac{1}{\sqrt{5}}</math> and <math>\beta=-\frac{1}{\sqrt{5}}</math>. Thus,
:<math>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}</math>.
|}
:<math>\square</math>
|}

Note that the expression <math>\frac{1}{1-z}</math> has a well known geometric expansion:
:<math>\frac{1}{1-z}=\sum_{n\ge 0}z^n</math>.

Therefore, <math>G(x)</math> can be expanded as
:<math>
\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}</math>
So the <math>n</math>th Fibonacci number is given by
:<math>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</math>.

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

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 <math>G(x)</math>, which is easy; and then manipulating the resulting formal power series to express it in terms of <math>G(x)</math>, which is more difficult (because it works backwards).

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

{{Theorem|Generating function manipulation|
:Let <math>G(x)=\sum_{n\ge 0}g_nx^n</math> and <math>F(x)=\sum_{n\ge 0}f_nx^n</math>.
----

::<math>
\begin{align}
x^k G(x)
&= \sum_{n\ge k}g_{n-k}x^n, &\qquad (\mbox{integer }k\ge 0)\\
\frac{G(x)-\sum_{i=0}^{k-1}g_iz^i}{x^k}
&=\sum_{n\ge 0}g_{n+k}x^n, &\qquad (\mbox{integer }k\ge 0)\\
\alpha F(x)+\beta G(x)
&= \sum_{n\ge 0} (\alpha f_n+\beta g_n)x^n\\
F(x)G(x)
&= \sum_{n\ge 0}\sum_{k=0}^nf_kg_{n-k}x^n\\
G(cx)
&= \sum_{n\ge 0} c^ng_n x^n\\
G'(x)
&=
\sum_{n\ge 0}(n+1)g_{n+1}x^n
\end{align}
</math>
}}

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 <math>G(x)</math> to evaluate its <math>n</math>-th coefficient. In principle, we can always use the [http://en.wikipedia.org/wiki/Taylor_series Taylor series]
:<math>G(x)=\sum_{n\ge 0}\frac{G^{(n)}(0)}{n!}x^n</math>,
where <math>G^{(n)}(0)</math> is the value of the <math>n</math>-th derivative of <math>G(x)</math> evaluated at <math>x=0</math>.

Some interesting special cases are very useful.

====Geometric sequence====
In the example of Fibonacci numbers, we use the well known geometric series:
:<math>\frac{1}{1-x}=\sum_{n\ge 0}x^n</math>.
It is useful when we can express the generating function in the form of <math>G(x)=\frac{a_1}{1-b_1x}+\frac{a_2}{1-b_2x}+\cdots+\frac{a_k}{1-b_kx}</math>. The coefficient of <math>x^n</math> in such <math>G(x)</math> is <math>a_1b_1^n+a_2b_2^n+\cdots+a_kb_k^n</math>.

====Binomial theorem====
The <math>n</math>-th derivative of <math>(1+x)^\alpha</math> for some real <math>\alpha</math> is
:<math>\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-n+1)(1+x)^{\alpha-n}</math>.
By Taylor series, we get a generalized version of the binomial theorem known as [http://en.wikipedia.org/wiki/Binomial_coefficient#Newton.27s_binomial_series '''Newton's formula''']:
{{Theorem|Newton's formular (generalized binomial theorem)|
If <math>|x|<1</math>, then
:<math>(1+x)^\alpha=\sum_{n\ge 0}{\alpha\choose n}x^{n}</math>,
where <math>{\alpha\choose n}</math> is the '''generalized binomial coefficient''' defined by
:<math>{\alpha\choose n}=\frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-n+1)}{n!}</math>.
}}

=== Example: multisets ===
In the last lecture we gave a combinatorial proof of the number of <math>k</math>-multisets on an <math>n</math>-set. Now we give a generating function approach to the problem.

Let <math>S=\{x_1,x_2,\ldots,x_n\}</math> be an <math>n</math>-element set. We have
:<math>(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)}</math>,
where each <math>m:S\rightarrow\mathbb{N}</math> species a possible multiset on <math>S</math> with multiplicity function <math>m</math>.

Let all <math>x_i=x</math>. Then
:<math>
\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}
</math>
The last equation is due to the the definition of <math>\left({n\choose k}\right)</math>. Our task is to evaluate <math>\left({n\choose k}\right)</math>.

Due to the geometric sequence and the Newton's formula
:<math>
(1+x+x^2+\cdots)^n=(1-x)^{-n}=\sum_{k\ge 0}{-n\choose k}(-x)^k.
</math>
So
:<math>
\left({n\choose k}\right)=(-1)^k{-n\choose k}={n+k-1\choose k}.
</math>
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 <math>\left({n\choose k}\right)</math> as the combinatorial proof.

=== Example: Quicksort ===

== Catalan Number ==
We now introduce a class of counting problems, all with the same solution, called [http://en.wikipedia.org/wiki/Catalan_number '''Catalan number'''].

The <math>n</math>th Catalan number is denoted as <math>C_n</math>.
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.
* ''C''<sub>''n''</sub> is the number of '''Dyck words''' of length 2''n''. 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 [http://en.wikipedia.org/wiki/Dyck_language Dyck language]). For example, the following are the Dyck words of length 6:
<div class="center"><big> XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.</big></div>

* Re-interpreting the symbol X as an open parenthesis and Y as a close parenthesis, ''C''<sub>''n''</sub> counts the number of expressions containing ''n'' pairs of parentheses which are correctly matched:
<div class="center"><big> ((()))     ()(())     ()()()     (())()     (()()) </big></div>

* ''C''<sub>''n''</sub> 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:
<div class="center"><math>((ab)c)d \quad (a(bc))d \quad(ab)(cd) \quad a((bc)d) \quad a(b(cd))</math></div>

* 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 ''C''<sub>''n''</sub> is the number of full binary trees with ''n'' + 1 leaves:
[[Image:Catalan number binary tree example.png|center]]

* ''C''<sub>''n''</sub> 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:
[[Image:Catalan number 4x4 grid example.svg.png|450px|center]]

* ''C''<sub>''n''</sub> is the number of different ways a [http://en.wikipedia.org/wiki/Convex_polygon '''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:
[[Image:Catalan-Hexagons-example.png|400px|center]]

* ''C''<sub>''n''</sub> is the number of [http://en.wikipedia.org/wiki/Stack_(data_structure) '''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 ''w'' = ''unv'' 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.

* ''C''<sub>''n''</sub> is the number of ways to tile a stairstep shape of height ''n'' with ''n'' rectangles. The following figure illustrates the case ''n'' = 4:
[[Image:Catalan stairsteps 4.png|400px|center]]

{{Theorem|Recurrence relation for Catalan numbers|
:<math>C_0=0</math>, <math>C_1=1</math>, and for <math>n>1</math>,
::<math>
C_n=\sum_{i=1}^{n-1}C_iC_{n-i}.
</math>
}}

Let <math>G(x)=\sum_{n\ge 0}C_nx^n</math> be the generating function. Apply the product rule,
:<math>G(x)^2=\sum_{n\ge 0}\sum_{k=0}^{n}C_kC_{n-k}x^n=\sum_{n\ge 2}\sum_{k=1}^{n-1}C_kC_{n-k}x^n</math>.
Due to the recurrence,
:<math>G(x)=\sum_{n\ge 0}C_nx^n=x+\sum_{n\ge 2}\sum_{k=1}^{n-1}C_kC_{n-k}x^n=x+G(x)^2</math>.
Solving this, we obtain
:<math>G(x)=\frac{1\pm(1-4x)^{1/2}}{2}</math>.
Because <math>C_0=0</math>, it must hold that <math>G(x)=\frac{1-(1-4x)^{1/2}}{2}</math>, or otherwise the constant term is not zero. Expanding <math>(1-4x)^{1/2}</math> by Newton's formula, we have
:<math>
\begin{align}
G(x)
&=
\frac{1-(1-4x)^{1/2}}{2}\\
&=
1-\frac{1}{2}\sum_{n\ge 0}{1/2\choose n}(-4x)^n
\end{align}
</math>
Thus,
:<math>
\begin{align}
C_n
&=-\frac{1}{2}{1/2\choose n}(-4)^n\\
&=-\frac{1}{2}\cdot\frac{1}{2}\cdot\frac{-1}{2}\cdot\frac{-3}{2}\cdots\frac{-(2n-3)}{2}\cdot(-4)^n/n!\\
&=\frac{(2n-2)!}{(n-1)!n!}\\
&=\frac{1}{n}{2n-2\choose n-1}.
\end{align}
</math>
So we prove the following closed form for Catalan number.
{{Theorem|Theorem|
:<math>C_n=\frac{1}{n}{2n-2\choose n-1}</math>.
}}

== Reference ==
* ''Graham, Knuth, and Patashnik'', Concrete Mathematics: A Foundation for Computer Science, Chapter 7.
* ''Cameron'', Combinatorics: Topics, Techniques, Algorithms, Chapter 4.
* ''van Lin and Wilson'', A course in combinatorics, Chapter 14.

Combinatorics (Fall 2010)/Generating functions

2010-09-12T06:32:05Z

172.21.1.108:

== 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 <math>a_n</math> depending a parameter <math>n</math>. Sometimes this <math>a_n</math> is called a ''counting function'' as it is a function of the parameter <math>n</math>. <math>a_n</math> can also be treated as a infinite series:
:<math>a_0,a_1,a_2,\ldots</math>

The '''ordinary generating function (OGF)''' defined by <math>a_n</math> is
:<math>
G(x)=\sum_{n\ge 0} a_nx^n.
</math>

So <math>G(x)=a_0+a_1x+a_2x^2+\cdots</math>. An expression in this form is called a [http://en.wikipedia.org/wiki/Formal_power_series '''formal power series'''], and <math>a_0,a_1,a_2,\ldots</math> is the sequence of '''coefficients'''.

Furthermore, the generating function can be expanded as
:G(x)=<math>(\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</math>
so it indeed "generates" all the possible instances of the objects we want to count.

Usually, we do not evaluate the generating function <math>GF(x)</math> on any particular value. <math>x</math> 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
:<math>(a_0,a_1,a_2,\ldots\ldots)</math>.

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 <math>n</math>-set. To construct a subset, we specifies for every element of the <math>n</math>-set whether the element is chosen or not. Let us denote the choice to omit an element by <math>x_0</math>, and the choice to include it by <math>x_1</math>. Using "<math>+</math>" to represent "OR", and using the multiplication to denote "AND", the choices of subsets of the <math>n</math>-set are expressed as
:<math>\underbrace{(x_0+x_1)(x_0+x_1)\cdots (x_0+x_1)}_{n\mbox{ elements}}=(x_0+x_1)^n</math>.

For example, when <math>n=3</math>, we have
:<math>\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}</math>.

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

In general, <math>(1+x)^n</math> has the coefficients which are the number of subsets of fixed sizes of an <math>n</math>-element set.

-----

Suppose that we have twelve balls: <font color="red">3 red</font>, <font color="blue">4 blue</font>, and <font color="green">5 green</font>. Balls with the same color are indistinguishable.

We want to determine the number of ways to select <math>k</math> balls from these twelve balls, for some <math>0\le k\le 12</math>.

The generating function of this sequence is
:<math>\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}</math>
The coefficient of <math>x^k</math> gives the number of ways to select <math>k</math> balls.

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

In both problems, the solution is given by <math>F_n</math> which satisfies the following recursion.
:<math>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}</math>

<math>F_n</math> is called the [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number].

{{Theorem|Theorem|
::<math>F_n=\frac{1}{\sqrt{5}}\left(\phi^n-\hat{\phi}^n\right)</math>,
:where <math>\phi=\frac{1+\sqrt{5}}{2}</math> and <math>\hat{\phi}=\frac{1-\sqrt{5}}{2}</math>.
}}
The quantity <math>\phi=\frac{1+\sqrt{5}}{2}</math> is the so-called [http://en.wikipedia.org/wiki/Golden_ratio 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 <math>F_{n}</math> is
:<math>G(x)=\sum_{n\ge 0}F_n x^n</math>.
We have that <math>F_{n}=F_{n-1}+F_{n-2}</math> for <math>n\ge 2</math>, thus
:<math>\begin{align}
G(x)
&=
\sum_{n\ge 0}F_n x^n
&=
x+\sum_{n\ge 2}(F_{n-1}+F_{n-2})x^n.
\end{align}
</math>
For generating functions, there are general ways to generate <math>F_{n-1}</math> and <math>F_{n-2}</math>, or the coefficients with any smaller indices.
:<math>
\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}
</math>
So we have
:<math>G(x)=x+(x+x^2)G(x)\,</math>,
hence
:<math>G(x)=\frac{x}{1-x-x^2}</math>.
The value of <math>F_n</math> is the coefficient of <math>x^n</math> in the Taylor series for this formular, which is <math>\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</math>. 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.
{{Theorem|Proposition|
:Let <math>\phi=\frac{1+\sqrt{5}}{2}</math> and <math>\hat{\phi}=\frac{1-\sqrt{5}}{2}</math>. It holds that
::<math>\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}</math>.
}}

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

{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|
:{|
|
<math>1-x-x^2</math> has two roots <math>\frac{-1\pm\sqrt{5}}{2}</math>.

Denote that <math>\phi=\frac{2}{-1+\sqrt{5}}=\frac{1+\sqrt{5}}{2}</math> and <math>\hat{\phi}=\frac{2}{-1-\sqrt{5}}=\frac{1-\sqrt{5}}{2}</math>.

Then <math>(1-x-x^2)=(1-\phi x)(1-\hat{\phi}x)</math>, so we can write
:<math>
\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}
</math>
where <math>\alpha</math> and <math>\beta</math> satisfying that
:<math>\begin{cases}
\alpha+\beta=0\\
\alpha\phi+\beta\hat{\phi}= -1.
\end{cases}</math>
Solving this we have that <math>\alpha=\frac{1}{\sqrt{5}}</math> and <math>\beta=-\frac{1}{\sqrt{5}}</math>. Thus,
:<math>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}</math>.
|}
:<math>\square</math>
|}

Note that the expression <math>\frac{1}{1-z}</math> has a well known geometric expansion:
:<math>\frac{1}{1-z}=\sum_{n\ge 0}z^n</math>.

Therefore, <math>G(x)</math> can be expanded as
:<math>
\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}</math>
So the <math>n</math>th Fibonacci number is given by
:<math>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</math>.

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

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 <math>G(x)</math>, which is easy; and then manipulating the resulting formal power series to express it in terms of <math>G(x)</math>, which is more difficult (because it works backwards).

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

{{Theorem|Generating function manipulation|
:Let <math>G(x)=\sum_{n\ge 0}g_nx^n</math> and <math>F(x)=\sum_{n\ge 0}f_nx^n</math>.
----

::<math>
\begin{align}
x^k G(x)
&= \sum_{n\ge k}g_{n-k}x^n, &\qquad (\mbox{integer }k\ge 0)\\
\frac{G(x)-\sum_{i=0}^{k-1}g_iz^i}{x^k}
&=\sum_{n\ge 0}g_{n+k}x^n, &\qquad (\mbox{integer }k\ge 0)\\
\alpha F(x)+\beta G(x)
&= \sum_{n\ge 0} (\alpha f_n+\beta g_n)x^n\\
F(x)G(x)
&= \sum_{n\ge 0}\sum_{k=0}^nf_kg_{n-k}x^n\\
G(cx)
&= \sum_{n\ge 0} c^ng_n x^n\\
G'(x)
&=
\sum_{n\ge 0}(n+1)g_{n+1}x^n
\end{align}
</math>
}}

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 <math>G(x)</math> to evaluate its <math>n</math>-th coefficient. In principle, we can always use the [http://en.wikipedia.org/wiki/Taylor_series Taylor series]
:<math>G(x)=\sum_{n\ge 0}\frac{G^{(n)}(0)}{n!}x^n</math>,
where <math>G^{(n)}(0)</math> is the value of the <math>n</math>-th derivative of <math>G(x)</math> evaluated at <math>x=0</math>.

Some interesting special cases are very useful.

====Geometric sequence====
In the example of Fibonacci numbers, we use the well known geometric series:
:<math>\frac{1}{1-x}=\sum_{n\ge 0}x^n</math>.
It is useful when we can express the generating function in the form of <math>G(x)=\frac{a_1}{1-b_1x}+\frac{a_2}{1-b_2x}+\cdots+\frac{a_k}{1-b_kx}</math>. The coefficient of <math>x^n</math> in such <math>G(x)</math> is <math>a_1b_1^n+a_2b_2^n+\cdots+a_kb_k^n</math>.

====Binomial theorem====
The <math>n</math>-th derivative of <math>(1+x)^\alpha</math> for some real <math>\alpha</math> is
:<math>\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-n+1)(1+x)^{\alpha-n}</math>.
By Taylor series, we get a generalized version of the binomial theorem known as [http://en.wikipedia.org/wiki/Binomial_coefficient#Newton.27s_binomial_series '''Newton's formula''']:
{{Theorem|Newton's formular (generalized binomial theorem)|
If <math>|x|<1</math>, then
:<math>(1+x)^\alpha=\sum_{n\ge 0}{\alpha\choose n}x^{n}</math>,
where <math>{\alpha\choose n}</math> is the '''generalized binomial coefficient''' defined by
:<math>{\alpha\choose n}=\frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-n+1)}{n!}</math>.
}}

=== Example: multisets ===
In the last lecture we gave a combinatorial proof of the number of <math>k</math>-multisets on an <math>n</math>-set. Now we give a generating function approach to the problem.

Let <math>S=\{x_1,x_2,\ldots,x_n\}</math> be an <math>n</math>-element set. We have
:<math>(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)}</math>,
where each <math>m:S\rightarrow\mathbb{N}</math> species a possible multiset on <math>S</math> with multiplicity function <math>m</math>.

Let all <math>x_i=x</math>. Then
:<math>
\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}
</math>
The last equation is due to the the definition of <math>\left({n\choose k}\right)</math>. Our task is to evaluate <math>\left({n\choose k}\right)</math>.

Due to the geometric sequence and the Newton's formula
:<math>
(1+x+x^2+\cdots)^n=(1-x)^{-n}=\sum_{k\ge 0}{-n\choose k}(-x)^k.
</math>
So
:<math>
\left({n\choose k}\right)=(-1)^k{-n\choose k}={n+k-1\choose k}.
</math>
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 <math>\left({n\choose k}\right)</math> as the combinatorial proof.

=== Example: Quicksort ===

== Catalan Number ==
We now introduce a class of counting problems, all with the same solution, called [http://en.wikipedia.org/wiki/Catalan_number '''Catalan number'''].

The <math>n</math>th Catalan number is denoted as <math>C_n</math>.
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.
* ''C''<sub>''n''</sub> is the number of '''Dyck words''' of length 2''n''. 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 [http://en.wikipedia.org/wiki/Dyck_language Dyck language]). For example, the following are the Dyck words of length 6:
<div class="center"><big> XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.</big></div>

* Re-interpreting the symbol X as an open parenthesis and Y as a close parenthesis, ''C''<sub>''n''</sub> counts the number of expressions containing ''n'' pairs of parentheses which are correctly matched:
<div class="center"><big> ((()))     ()(())     ()()()     (())()     (()()) </big></div>

* ''C''<sub>''n''</sub> 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:
<div class="center"><math>((ab)c)d \quad (a(bc))d \quad(ab)(cd) \quad a((bc)d) \quad a(b(cd))</math></div>

* 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 ''C''<sub>''n''</sub> is the number of full binary trees with ''n'' + 1 leaves:
[[Image:Catalan number binary tree example.png|center]]

* ''C''<sub>''n''</sub> 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:
[[Image:Catalan number 4x4 grid example.svg.png|450px|center]]

* ''C''<sub>''n''</sub> is the number of different ways a [http://en.wikipedia.org/wiki/Convex_polygon '''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:
[[Image:Catalan-Hexagons-example.png|400px|center]]

* ''C''<sub>''n''</sub> is the number of [http://en.wikipedia.org/wiki/Stack_(data_structure) '''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 ''w'' = ''unv'' 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.

* ''C''<sub>''n''</sub> is the number of ways to tile a stairstep shape of height ''n'' with ''n'' rectangles. The following figure illustrates the case ''n'' = 4:
[[Image:Catalan stairsteps 4.png|400px|center]]

{{Theorem|Recurrence relation for Catalan numbers|
:<math>C_0=0</math>, <math>C_1=1</math>, and for <math>n>1</math>,
::<math>
C_n=\sum_{i=1}^{n-1}C_iC_{n-i}.
</math>
}}

Let <math>G(x)=\sum_{n\ge 0}C_nx^n</math> be the generating function. Apply the product rule,
:<math>G(x)^2=\sum_{n\ge 0}\sum_{k=0}^{n}C_kC_{n-k}x^n=\sum_{n\ge 2}\sum_{k=1}^{n-1}C_kC_{n-k}x^n</math>.
Due to the recurrence,
:<math>G(x)=\sum_{n\ge 0}C_nx^n=x+\sum_{n\ge 2}\sum_{k=1}^{n-1}C_kC_{n-k}x^n=x+G(x)^2</math>.
Solving this, we obtain
:<math>G(x)=\frac{1\pm(1-4x)^{1/2}}{2}</math>.
Because <math>C_0=0</math>, it must hold that <math>G(x)=\frac{1-(1-4x)^{1/2}}{2}</math>, or otherwise the constant term is not zero. Expanding <math>(1-4x)^{1/2}</math> by Newton's formula, we have
:<math>
\begin{align}
G(x)
&=
\frac{1-(1-4x)^{1/2}}{2}\\
&=
1-\frac{1}{2}\sum_{n\ge 0}{1/2\choose n}(-4x)^n
\end{align}
</math>
Thus,
:<math>
\begin{align}
C_n
&=-\frac{1}{2}{1/2\choose n}(-4)^n\\
&=-\frac{1}{2}\cdot\frac{1}{2}\cdot\frac{-1}{2}\cdot\frac{-3}{2}\cdots\frac{-(2n-3)}{2}\cdot(-4)^n/n!\\
&=\frac{(2n-2)!}{(n-1)!n!}\\
&=\frac{1}{n}{2n-2\choose n-1}.
\end{align}
</math>
So we prove the following closed form for Catalan number.
{{Theorem|Theorem|
:<math>C_n=\frac{1}{n}{2n-2\choose n-1}</math>.
}}

== Reference ==
* ''Graham, Knuth, and Patashnik'', Concrete Mathematics: A Foundation for Computer Science, Chapter 7.
* ''Cameron'', Combinatorics: Topics, Techniques, Algorithms, Chapter 4.
* "van Lin and Wilson", A course in combinatorics, Chapter 14.

Combinatorics (Fall 2010)/Generating functions

2010-09-12T06:24:37Z

172.21.1.108: /* Combinations */

Combinatorics (Fall 2010)/Generating functions

2010-09-12T06:19:53Z

172.21.1.108: /* Combinations */

== 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 <math>a_n</math> depending a parameter <math>n</math>. Sometimes this <math>a_n</math> is called a ''counting function'' as it is a function of the parameter <math>n</math>. <math>a_n</math> can also be treated as a infinite series:
:<math>a_0,a_1,a_2,\ldots</math>

The '''ordinary generating function (OGF)''' defined by <math>a_n</math> is
:<math>
G(x)=\sum_{n\ge 0} a_nx^n.
</math>

So <math>G(x)=a_0+a_1x+a_2x^2+\cdots</math>. An expression in this form is called a [http://en.wikipedia.org/wiki/Formal_power_series '''formal power series'''], and <math>a_0,a_1,a_2,\ldots</math> is the sequence of '''coefficients'''.

Furthermore, the generating function can be expanded as
:G(x)=<math>(\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</math>
so it indeed "generates" all the possible instances of the objects we want to count.

Usually, we do not evaluate the generating function <math>GF(x)</math> on any particular value. <math>x</math> 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
:<math>(a_0,a_1,a_2,\ldots\ldots)</math>.

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 <math>n</math>-set. To construct a subset, we specifies for every element of the <math>n</math>-set whether the element is chosen or not. Let us denote the choice to omit an element by <math>x_0</math>, and the choice to include it by <math>x_1</math>. Using "<math>+</math>" to represent "OR", and using the multiplication to denote "AND", the choices of subsets of the <math>n</math>-set are expressed as
:<math>\underbrace{(x_0+x_1)(x_0+x_1)\cdots (x_0+x_1)}_{n\mbox{ elements}}=(x_0+x_1)^n</math>.

For example, when <math>n=3</math>, we have
:<math>\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}</math>.

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

In general, <math>(1+x)^n</math> has the coefficients which are the number of subsets of fixed sizes of an <math>n</math>-element set.

-----

Suppose that we have twelve balls: <font color="red">3 red</font>, <font color="blue">4 blue</font>, and <font color="green">5 green</font>. Balls with the same color are indistinguishable.

We want to determine the number of ways to select <math>k</math> balls from these twelve balls, for some <math>0\le k\le 12</math>.

:<math>{\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)}</math>

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

In both problems, the solution is given by <math>F_n</math> which satisfies the following recursion.
:<math>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}</math>

<math>F_n</math> is called the [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number].

{{Theorem|Theorem|
::<math>F_n=\frac{1}{\sqrt{5}}\left(\phi^n-\hat{\phi}^n\right)</math>,
:where <math>\phi=\frac{1+\sqrt{5}}{2}</math> and <math>\hat{\phi}=\frac{1-\sqrt{5}}{2}</math>.
}}
The quantity <math>\phi=\frac{1+\sqrt{5}}{2}</math> is the so-called [http://en.wikipedia.org/wiki/Golden_ratio 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 <math>F_{n}</math> is
:<math>G(x)=\sum_{n\ge 0}F_n x^n</math>.
We have that <math>F_{n}=F_{n-1}+F_{n-2}</math> for <math>n\ge 2</math>, thus
:<math>\begin{align}
G(x)
&=
\sum_{n\ge 0}F_n x^n
&=
x+\sum_{n\ge 2}(F_{n-1}+F_{n-2})x^n.
\end{align}
</math>
For generating functions, there are general ways to generate <math>F_{n-1}</math> and <math>F_{n-2}</math>, or the coefficients with any smaller indices.
:<math>
\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}
</math>
So we have
:<math>G(x)=x+(x+x^2)G(x)\,</math>,
hence
:<math>G(x)=\frac{x}{1-x-x^2}</math>.
The value of <math>F_n</math> is the coefficient of <math>x^n</math> in the Taylor series for this formular, which is <math>\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</math>. 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.
{{Theorem|Proposition|
:Let <math>\phi=\frac{1+\sqrt{5}}{2}</math> and <math>\hat{\phi}=\frac{1-\sqrt{5}}{2}</math>. It holds that
::<math>\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}</math>.
}}

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

{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|
:{|
|
<math>1-x-x^2</math> has two roots <math>\frac{-1\pm\sqrt{5}}{2}</math>.

Denote that <math>\phi=\frac{2}{-1+\sqrt{5}}=\frac{1+\sqrt{5}}{2}</math> and <math>\hat{\phi}=\frac{2}{-1-\sqrt{5}}=\frac{1-\sqrt{5}}{2}</math>.

Then <math>(1-x-x^2)=(1-\phi x)(1-\hat{\phi}x)</math>, so we can write
:<math>
\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}
</math>
where <math>\alpha</math> and <math>\beta</math> satisfying that
:<math>\begin{cases}
\alpha+\beta=0\\
\alpha\phi+\beta\hat{\phi}= -1.
\end{cases}</math>
Solving this we have that <math>\alpha=\frac{1}{\sqrt{5}}</math> and <math>\beta=-\frac{1}{\sqrt{5}}</math>. Thus,
:<math>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}</math>.
|}
:<math>\square</math>
|}

Note that the expression <math>\frac{1}{1-z}</math> has a well known geometric expansion:
:<math>\frac{1}{1-z}=\sum_{n\ge 0}z^n</math>.

Therefore, <math>G(x)</math> can be expanded as
:<math>
\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}</math>
So the <math>n</math>th Fibonacci number is given by
:<math>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</math>.

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

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 <math>G(x)</math>, which is easy; and then manipulating the resulting formal power series to express it in terms of <math>G(x)</math>, which is more difficult (because it works backwards).

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

{{Theorem|Generating function manipulation|
:Let <math>G(x)=\sum_{n\ge 0}g_nx^n</math> and <math>F(x)=\sum_{n\ge 0}f_nx^n</math>.
----

::<math>
\begin{align}
x^k G(x)
&= \sum_{n\ge k}g_{n-k}x^n, &\qquad (\mbox{integer }k\ge 0)\\
\frac{G(x)-\sum_{i=0}^{k-1}g_iz^i}{x^k}
&=\sum_{n\ge 0}g_{n+k}x^n, &\qquad (\mbox{integer }k\ge 0)\\
\alpha F(x)+\beta G(x)
&= \sum_{n\ge 0} (\alpha f_n+\beta g_n)x^n\\
F(x)G(x)
&= \sum_{n\ge 0}\sum_{k=0}^nf_kg_{n-k}x^n\\
G(cx)
&= \sum_{n\ge 0} c^ng_n x^n\\
G'(x)
&=
\sum_{n\ge 0}(n+1)g_{n+1}x^n
\end{align}
</math>
}}

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 <math>G(x)</math> to evaluate its <math>n</math>-th coefficient. In principle, we can always use the [http://en.wikipedia.org/wiki/Taylor_series Taylor series]
:<math>G(x)=\sum_{n\ge 0}\frac{G^{(n)}(0)}{n!}x^n</math>,
where <math>G^{(n)}(0)</math> is the value of the <math>n</math>-th derivative of <math>G(x)</math> evaluated at <math>x=0</math>.

Some interesting special cases are very useful.

====Geometric sequence====
In the example of Fibonacci numbers, we use the well known geometric series:
:<math>\frac{1}{1-x}=\sum_{n\ge 0}x^n</math>.
It is useful when we can express the generating function in the form of <math>G(x)=\frac{a_1}{1-b_1x}+\frac{a_2}{1-b_2x}+\cdots+\frac{a_k}{1-b_kx}</math>. The coefficient of <math>x^n</math> in such <math>G(x)</math> is <math>a_1b_1^n+a_2b_2^n+\cdots+a_kb_k^n</math>.

====Binomial theorem====
The <math>n</math>-th derivative of <math>(1+x)^\alpha</math> for some real <math>\alpha</math> is
:<math>\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-n+1)(1+x)^{\alpha-n}</math>.
By Taylor series, we get a generalized version of the binomial theorem known as [http://en.wikipedia.org/wiki/Binomial_coefficient#Newton.27s_binomial_series '''Newton's formula''']:
{{Theorem|Newton's formular (generalized binomial theorem)|
If <math>|x|<1</math>, then
:<math>(1+x)^\alpha=\sum_{n\ge 0}{\alpha\choose n}x^{n}</math>,
where <math>{\alpha\choose n}</math> is the '''generalized binomial coefficient''' defined by
:<math>{\alpha\choose n}=\frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-n+1)}{n!}</math>.
}}

=== Example: multisets ===
In the last lecture we gave a combinatorial proof of the number of <math>k</math>-multisets on an <math>n</math>-set. Now we give a generating function approach to the problem.

Let <math>S=\{x_1,x_2,\ldots,x_n\}</math> be an <math>n</math>-element set. We have
:<math>(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)}</math>,
where each <math>m:S\rightarrow\mathbb{N}</math> species a possible multiset on <math>S</math> with multiplicity function <math>m</math>.

Let all <math>x_i=x</math>. Then
:<math>
\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}
</math>
The last equation is due to the the definition of <math>\left({n\choose k}\right)</math>. Our task is to evaluate <math>\left({n\choose k}\right)</math>.

Due to the geometric sequence and the Newton's formula
:<math>
(1+x+x^2+\cdots)^n=(1-x)^{-n}=\sum_{k\ge 0}{-n\choose k}(-x)^k.
</math>
So
:<math>
\left({n\choose k}\right)=(-1)^k{-n\choose k}={n+k-1\choose k}.
</math>
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 <math>\left({n\choose k}\right)</math> as the combinatorial proof.

=== Example: Quicksort ===

== Catalan Number ==
We now introduce a class of counting problems, all with the same solution, called [http://en.wikipedia.org/wiki/Catalan_number '''Catalan number'''].

The <math>n</math>th Catalan number is denoted as <math>C_n</math>.
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.
* ''C''<sub>''n''</sub> is the number of '''Dyck words''' of length 2''n''. 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 [http://en.wikipedia.org/wiki/Dyck_language Dyck language]). For example, the following are the Dyck words of length 6:
<div class="center"><big> XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.</big></div>

* Re-interpreting the symbol X as an open parenthesis and Y as a close parenthesis, ''C''<sub>''n''</sub> counts the number of expressions containing ''n'' pairs of parentheses which are correctly matched:
<div class="center"><big> ((()))     ()(())     ()()()     (())()     (()()) </big></div>

* ''C''<sub>''n''</sub> 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:
<div class="center"><math>((ab)c)d \quad (a(bc))d \quad(ab)(cd) \quad a((bc)d) \quad a(b(cd))</math></div>

* 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 ''C''<sub>''n''</sub> is the number of full binary trees with ''n'' + 1 leaves:
[[Image:Catalan number binary tree example.png|center]]

* ''C''<sub>''n''</sub> 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:
[[Image:Catalan number 4x4 grid example.svg.png|450px|center]]

* ''C''<sub>''n''</sub> is the number of different ways a [http://en.wikipedia.org/wiki/Convex_polygon '''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:
[[Image:Catalan-Hexagons-example.png|400px|center]]

* ''C''<sub>''n''</sub> is the number of [http://en.wikipedia.org/wiki/Stack_(data_structure) '''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 ''w'' = ''unv'' 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.

* ''C''<sub>''n''</sub> is the number of ways to tile a stairstep shape of height ''n'' with ''n'' rectangles. The following figure illustrates the case ''n'' = 4:
[[Image:Catalan stairsteps 4.png|400px|center]]

{{Theorem|Recurrence relation for Catalan numbers|
:<math>C_0=0</math>, <math>C_1=1</math>, and for <math>n>1</math>,
::<math>
C_n=\sum_{i=1}^{n-1}C_iC_{n-i}.
</math>
}}

Let <math>G(x)=\sum_{n\ge 0}C_nx^n</math> be the generating function. Apply the product rule,
:<math>G(x)^2=\sum_{n\ge 0}\sum_{k=0}^{n}C_kC_{n-k}x^n=\sum_{n\ge 2}\sum_{k=1}^{n-1}C_kC_{n-k}x^n</math>.
Due to the recurrence,
:<math>G(x)=\sum_{n\ge 0}C_nx^n=x+\sum_{n\ge 2}\sum_{k=1}^{n-1}C_kC_{n-k}x^n=x+G(x)^2</math>.
Solving this, we obtain
:<math>G(x)=\frac{1\pm(1-4x)^{1/2}}{2}</math>.
Because <math>C_0=0</math>, it must hold that <math>G(x)=\frac{1-(1-4x)^{1/2}}{2}</math>, or otherwise the constant term is not zero. Expanding <math>(1-4x)^{1/2}</math> by Newton's formula, we have
:<math>
\begin{align}
G(x)
&=
\frac{1-(1-4x)^{1/2}}{2}\\
&=
1-\frac{1}{2}\sum_{n\ge 0}{1/2\choose n}(-4x)^n
\end{align}
</math>
Thus,
:<math>
\begin{align}
C_n
&=-\frac{1}{2}{1/2\choose n}(-4)^n\\
&=-\frac{1}{2}\cdot\frac{1}{2}\cdot\frac{-1}{2}\cdot\frac{-3}{2}\cdots\frac{-(2n-3)}{2}\cdot(-4)^n/n!\\
&=\frac{(2n-2)!}{(n-1)!n!}\\
&=\frac{1}{n}{2n-2\choose n-1}.
\end{align}
</math>
So we prove the following closed form for Catalan number.
{{Theorem|Theorem|
:<math>C_n=\frac{1}{n}{2n-2\choose n-1}</math>.
}}

Combinatorics (Fall 2010)/Generating functions

2010-09-12T02:52:32Z

172.21.1.108: /* Example: multisets */

== 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 <math>a_n</math> depending a parameter <math>n</math>. Sometimes this <math>a_n</math> is called a ''counting function'' as it is a function of the parameter <math>n</math>. <math>a_n</math> can also be treated as a infinite series:
:<math>a_0,a_1,a_2,\ldots</math>

The '''ordinary generating function (OGF)''' defined by <math>a_n</math> is
:<math>
G(x)=\sum_{n\ge 0} a_nx^n.
</math>

So <math>G(x)=a_0+a_1x+a_2x^2+\cdots</math>. An expression in this form is called a [http://en.wikipedia.org/wiki/Formal_power_series '''formal power series'''], and <math>a_0,a_1,a_2,\ldots</math> is the sequence of '''coefficients'''.

Furthermore, the generating function can be expanded as
:G(x)=<math>(\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</math>
so it indeed "generates" all the possible instances of the objects we want to count.

Usually, we do not evaluate the generating function <math>GF(x)</math> on any particular value. <math>x</math> 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
:<math>(a_0,a_1,a_2,\ldots\ldots)</math>.

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 ===

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

In both problems, the solution is given by <math>F_n</math> which satisfies the following recursion.
:<math>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}</math>

<math>F_n</math> is called the [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number].

{{Theorem|Theorem|
::<math>F_n=\frac{1}{\sqrt{5}}\left(\phi^n-\hat{\phi}^n\right)</math>,
:where <math>\phi=\frac{1+\sqrt{5}}{2}</math> and <math>\hat{\phi}=\frac{1-\sqrt{5}}{2}</math>.
}}
The quantity <math>\phi=\frac{1+\sqrt{5}}{2}</math> is the so-called [http://en.wikipedia.org/wiki/Golden_ratio 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 <math>F_{n}</math> is
:<math>G(x)=\sum_{n\ge 0}F_n x^n</math>.
We have that <math>F_{n}=F_{n-1}+F_{n-2}</math> for <math>n\ge 2</math>, thus
:<math>\begin{align}
G(x)
&=
\sum_{n\ge 0}F_n x^n
&=
x+\sum_{n\ge 2}(F_{n-1}+F_{n-2})x^n.
\end{align}
</math>
For generating functions, there are general ways to generate <math>F_{n-1}</math> and <math>F_{n-2}</math>, or the coefficients with any smaller indices.
:<math>
\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}
</math>
So we have
:<math>G(x)=x+(x+x^2)G(x)\,</math>,
hence
:<math>G(x)=\frac{x}{1-x-x^2}</math>.
The value of <math>F_n</math> is the coefficient of <math>x^n</math> in the Taylor series for this formular, which is <math>\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</math>. 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.
{{Theorem|Proposition|
:Let <math>\phi=\frac{1+\sqrt{5}}{2}</math> and <math>\hat{\phi}=\frac{1-\sqrt{5}}{2}</math>. It holds that
::<math>\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}</math>.
}}

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

{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|
:{|
|
<math>1-x-x^2</math> has two roots <math>\frac{-1\pm\sqrt{5}}{2}</math>.

Denote that <math>\phi=\frac{2}{-1+\sqrt{5}}=\frac{1+\sqrt{5}}{2}</math> and <math>\hat{\phi}=\frac{2}{-1-\sqrt{5}}=\frac{1-\sqrt{5}}{2}</math>.

Then <math>(1-x-x^2)=(1-\phi x)(1-\hat{\phi}x)</math>, so we can write
:<math>
\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}
</math>
where <math>\alpha</math> and <math>\beta</math> satisfying that
:<math>\begin{cases}
\alpha+\beta=0\\
\alpha\phi+\beta\hat{\phi}= -1.
\end{cases}</math>
Solving this we have that <math>\alpha=\frac{1}{\sqrt{5}}</math> and <math>\beta=-\frac{1}{\sqrt{5}}</math>. Thus,
:<math>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}</math>.
|}
:<math>\square</math>
|}

Note that the expression <math>\frac{1}{1-z}</math> has a well known geometric expansion:
:<math>\frac{1}{1-z}=\sum_{n\ge 0}z^n</math>.

Therefore, <math>G(x)</math> can be expanded as
:<math>
\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}</math>
So the <math>n</math>th Fibonacci number is given by
:<math>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</math>.

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

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 <math>G(x)</math>, which is easy; and then manipulating the resulting formal power series to express it in terms of <math>G(x)</math>, which is more difficult (because it works backwards).

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

{{Theorem|Generating function manipulation|
:Let <math>G(x)=\sum_{n\ge 0}g_nx^n</math> and <math>F(x)=\sum_{n\ge 0}f_nx^n</math>.
----

::<math>
\begin{align}
x^k G(x)
&= \sum_{n\ge k}g_{n-k}x^n, &\qquad (\mbox{integer }k\ge 0)\\
\frac{G(x)-\sum_{i=0}^{k-1}g_iz^i}{x^k}
&=\sum_{n\ge 0}g_{n+k}x^n, &\qquad (\mbox{integer }k\ge 0)\\
\alpha F(x)+\beta G(x)
&= \sum_{n\ge 0} (\alpha f_n+\beta g_n)x^n\\
F(x)G(x)
&= \sum_{n\ge 0}\sum_{k=0}^nf_kg_{n-k}x^n\\
G(cx)
&= \sum_{n\ge 0} c^ng_n x^n\\
G'(x)
&=
\sum_{n\ge 0}(n+1)g_{n+1}x^n
\end{align}
</math>
}}

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 <math>G(x)</math> to evaluate its <math>n</math>-th coefficient. In principle, we can always use the [http://en.wikipedia.org/wiki/Taylor_series Taylor series]
:<math>G(x)=\sum_{n\ge 0}\frac{G^{(n)}(0)}{n!}x^n</math>,
where <math>G^{(n)}(0)</math> is the value of the <math>n</math>-th derivative of <math>G(x)</math> evaluated at <math>x=0</math>.

Some interesting special cases are very useful.

====Geometric sequence====
In the example of Fibonacci numbers, we use the well known geometric series:
:<math>\frac{1}{1-x}=\sum_{n\ge 0}x^n</math>.
It is useful when we can express the generating function in the form of <math>G(x)=\frac{a_1}{1-b_1x}+\frac{a_2}{1-b_2x}+\cdots+\frac{a_k}{1-b_kx}</math>. The coefficient of <math>x^n</math> in such <math>G(x)</math> is <math>a_1b_1^n+a_2b_2^n+\cdots+a_kb_k^n</math>.

====Binomial theorem====
The <math>n</math>-th derivative of <math>(1+x)^\alpha</math> for some real <math>\alpha</math> is
:<math>\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-n+1)(1+x)^{\alpha-n}</math>.
By Taylor series, we get a generalized version of the binomial theorem known as [http://en.wikipedia.org/wiki/Binomial_coefficient#Newton.27s_binomial_series '''Newton's formula''']:
{{Theorem|Newton's formular (generalized binomial theorem)|
If <math>|x|<1</math>, then
:<math>(1+x)^\alpha=\sum_{n\ge 0}{\alpha\choose n}x^{n}</math>,
where <math>{\alpha\choose n}</math> is the '''generalized binomial coefficient''' defined by
:<math>{\alpha\choose n}=\frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-n+1)}{n!}</math>.
}}

=== Example: multisets ===
In the last lecture we gave a combinatorial proof of the number of <math>k</math>-multisets on an <math>n</math>-set. Now we give a generating function approach to the problem.

Let <math>S=\{x_1,x_2,\ldots,x_n\}</math> be an <math>n</math>-element set. We have
:<math>(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)}</math>,
where each <math>m:S\rightarrow\mathbb{N}</math> species a possible multiset on <math>S</math> with multiplicity function <math>m</math>.

Let all <math>x_i=x</math>. Then
:<math>
\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}
</math>
The last equation is due to the the definition of <math>\left({n\choose k}\right)</math>. Our task is to evaluate <math>\left({n\choose k}\right)</math>.

Due to the geometric sequence and the Newton's formula
:<math>
(1+x+x^2+\cdots)^n=(1-x)^{-n}=\sum_{k\ge 0}{-n\choose k}(-x)^k.
</math>
So
:<math>
\left({n\choose k}\right)=(-1)^k{-n\choose k}={n+k-1\choose k}.
</math>
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 <math>\left({n\choose k}\right)</math> as the combinatorial proof.

=== Example: Quicksort ===

== Catalan Number ==
We now introduce a class of counting problems, all with the same solution, called [http://en.wikipedia.org/wiki/Catalan_number '''Catalan number'''].

The <math>n</math>th Catalan number is denoted as <math>C_n</math>.
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.
* ''C''<sub>''n''</sub> is the number of '''Dyck words''' of length 2''n''. 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 [http://en.wikipedia.org/wiki/Dyck_language Dyck language]). For example, the following are the Dyck words of length 6:
<div class="center"><big> XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.</big></div>

* Re-interpreting the symbol X as an open parenthesis and Y as a close parenthesis, ''C''<sub>''n''</sub> counts the number of expressions containing ''n'' pairs of parentheses which are correctly matched:
<div class="center"><big> ((()))     ()(())     ()()()     (())()     (()()) </big></div>

* ''C''<sub>''n''</sub> 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:
<div class="center"><math>((ab)c)d \quad (a(bc))d \quad(ab)(cd) \quad a((bc)d) \quad a(b(cd))</math></div>

* 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 ''C''<sub>''n''</sub> is the number of full binary trees with ''n'' + 1 leaves:
[[Image:Catalan number binary tree example.png|center]]

* ''C''<sub>''n''</sub> 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:
[[Image:Catalan number 4x4 grid example.svg.png|450px|center]]

* ''C''<sub>''n''</sub> is the number of different ways a [http://en.wikipedia.org/wiki/Convex_polygon '''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:
[[Image:Catalan-Hexagons-example.png|400px|center]]

* ''C''<sub>''n''</sub> is the number of [http://en.wikipedia.org/wiki/Stack_(data_structure) '''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 ''w'' = ''unv'' 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.

* ''C''<sub>''n''</sub> is the number of ways to tile a stairstep shape of height ''n'' with ''n'' rectangles. The following figure illustrates the case ''n'' = 4:
[[Image:Catalan stairsteps 4.png|400px|center]]

{{Theorem|Recurrence relation for Catalan numbers|
:<math>C_0=0</math>, <math>C_1=1</math>, and for <math>n>1</math>,
::<math>
C_n=\sum_{i=1}^{n-1}C_iC_{n-i}.
</math>
}}

Let <math>G(x)=\sum_{n\ge 0}C_nx^n</math> be the generating function. Apply the product rule,
:<math>G(x)^2=\sum_{n\ge 0}\sum_{k=0}^{n}C_kC_{n-k}x^n=\sum_{n\ge 2}\sum_{k=1}^{n-1}C_kC_{n-k}x^n</math>.
Due to the recurrence,
:<math>G(x)=\sum_{n\ge 0}C_nx^n=x+\sum_{n\ge 2}\sum_{k=1}^{n-1}C_kC_{n-k}x^n=x+G(x)^2</math>.
Solving this, we obtain
:<math>G(x)=\frac{1\pm(1-4x)^{1/2}}{2}</math>.
Because <math>C_0=0</math>, it must hold that <math>G(x)=\frac{1-(1-4x)^{1/2}}{2}</math>, or otherwise the constant term is not zero. Expanding <math>(1-4x)^{1/2}</math> by Newton's formula, we have
:<math>
\begin{align}
G(x)
&=
\frac{1-(1-4x)^{1/2}}{2}\\
&=
1-\frac{1}{2}\sum_{n\ge 0}{1/2\choose n}(-4x)^n
\end{align}
</math>
Thus,
:<math>
\begin{align}
C_n
&=-\frac{1}{2}{1/2\choose n}(-4)^n\\
&=-\frac{1}{2}\cdot\frac{1}{2}\cdot\frac{-1}{2}\cdot\frac{-3}{2}\cdots\frac{-(2n-3)}{2}\cdot(-4)^n/n!\\
&=\frac{(2n-2)!}{(n-1)!n!}\\
&=\frac{1}{n}{2n-2\choose n-1}.
\end{align}
</math>
So we prove the following closed form for Catalan number.
{{Theorem|Theorem|
:<math>C_n=\frac{1}{n}{2n-2\choose n-1}</math>.
}}

Combinatorics (Fall 2010)/Generating functions

2010-09-12T02:52:17Z

172.21.1.108: /* Example: multisets */

== 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 <math>a_n</math> depending a parameter <math>n</math>. Sometimes this <math>a_n</math> is called a ''counting function'' as it is a function of the parameter <math>n</math>. <math>a_n</math> can also be treated as a infinite series:
:<math>a_0,a_1,a_2,\ldots</math>

The '''ordinary generating function (OGF)''' defined by <math>a_n</math> is
:<math>
G(x)=\sum_{n\ge 0} a_nx^n.
</math>

So <math>G(x)=a_0+a_1x+a_2x^2+\cdots</math>. An expression in this form is called a [http://en.wikipedia.org/wiki/Formal_power_series '''formal power series'''], and <math>a_0,a_1,a_2,\ldots</math> is the sequence of '''coefficients'''.

Furthermore, the generating function can be expanded as
:G(x)=<math>(\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</math>
so it indeed "generates" all the possible instances of the objects we want to count.

Usually, we do not evaluate the generating function <math>GF(x)</math> on any particular value. <math>x</math> 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
:<math>(a_0,a_1,a_2,\ldots\ldots)</math>.

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 ===

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

In both problems, the solution is given by <math>F_n</math> which satisfies the following recursion.
:<math>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}</math>

<math>F_n</math> is called the [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number].

{{Theorem|Theorem|
::<math>F_n=\frac{1}{\sqrt{5}}\left(\phi^n-\hat{\phi}^n\right)</math>,
:where <math>\phi=\frac{1+\sqrt{5}}{2}</math> and <math>\hat{\phi}=\frac{1-\sqrt{5}}{2}</math>.
}}
The quantity <math>\phi=\frac{1+\sqrt{5}}{2}</math> is the so-called [http://en.wikipedia.org/wiki/Golden_ratio 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 <math>F_{n}</math> is
:<math>G(x)=\sum_{n\ge 0}F_n x^n</math>.
We have that <math>F_{n}=F_{n-1}+F_{n-2}</math> for <math>n\ge 2</math>, thus
:<math>\begin{align}
G(x)
&=
\sum_{n\ge 0}F_n x^n
&=
x+\sum_{n\ge 2}(F_{n-1}+F_{n-2})x^n.
\end{align}
</math>
For generating functions, there are general ways to generate <math>F_{n-1}</math> and <math>F_{n-2}</math>, or the coefficients with any smaller indices.
:<math>
\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}
</math>
So we have
:<math>G(x)=x+(x+x^2)G(x)\,</math>,
hence
:<math>G(x)=\frac{x}{1-x-x^2}</math>.
The value of <math>F_n</math> is the coefficient of <math>x^n</math> in the Taylor series for this formular, which is <math>\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</math>. 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.
{{Theorem|Proposition|
:Let <math>\phi=\frac{1+\sqrt{5}}{2}</math> and <math>\hat{\phi}=\frac{1-\sqrt{5}}{2}</math>. It holds that
::<math>\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}</math>.
}}

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

{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|
:{|
|
<math>1-x-x^2</math> has two roots <math>\frac{-1\pm\sqrt{5}}{2}</math>.

Denote that <math>\phi=\frac{2}{-1+\sqrt{5}}=\frac{1+\sqrt{5}}{2}</math> and <math>\hat{\phi}=\frac{2}{-1-\sqrt{5}}=\frac{1-\sqrt{5}}{2}</math>.

Then <math>(1-x-x^2)=(1-\phi x)(1-\hat{\phi}x)</math>, so we can write
:<math>
\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}
</math>
where <math>\alpha</math> and <math>\beta</math> satisfying that
:<math>\begin{cases}
\alpha+\beta=0\\
\alpha\phi+\beta\hat{\phi}= -1.
\end{cases}</math>
Solving this we have that <math>\alpha=\frac{1}{\sqrt{5}}</math> and <math>\beta=-\frac{1}{\sqrt{5}}</math>. Thus,
:<math>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}</math>.
|}
:<math>\square</math>
|}

Note that the expression <math>\frac{1}{1-z}</math> has a well known geometric expansion:
:<math>\frac{1}{1-z}=\sum_{n\ge 0}z^n</math>.

Therefore, <math>G(x)</math> can be expanded as
:<math>
\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}</math>
So the <math>n</math>th Fibonacci number is given by
:<math>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</math>.

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

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 <math>G(x)</math>, which is easy; and then manipulating the resulting formal power series to express it in terms of <math>G(x)</math>, which is more difficult (because it works backwards).

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

{{Theorem|Generating function manipulation|
:Let <math>G(x)=\sum_{n\ge 0}g_nx^n</math> and <math>F(x)=\sum_{n\ge 0}f_nx^n</math>.
----

::<math>
\begin{align}
x^k G(x)
&= \sum_{n\ge k}g_{n-k}x^n, &\qquad (\mbox{integer }k\ge 0)\\
\frac{G(x)-\sum_{i=0}^{k-1}g_iz^i}{x^k}
&=\sum_{n\ge 0}g_{n+k}x^n, &\qquad (\mbox{integer }k\ge 0)\\
\alpha F(x)+\beta G(x)
&= \sum_{n\ge 0} (\alpha f_n+\beta g_n)x^n\\
F(x)G(x)
&= \sum_{n\ge 0}\sum_{k=0}^nf_kg_{n-k}x^n\\
G(cx)
&= \sum_{n\ge 0} c^ng_n x^n\\
G'(x)
&=
\sum_{n\ge 0}(n+1)g_{n+1}x^n
\end{align}
</math>
}}

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 <math>G(x)</math> to evaluate its <math>n</math>-th coefficient. In principle, we can always use the [http://en.wikipedia.org/wiki/Taylor_series Taylor series]
:<math>G(x)=\sum_{n\ge 0}\frac{G^{(n)}(0)}{n!}x^n</math>,
where <math>G^{(n)}(0)</math> is the value of the <math>n</math>-th derivative of <math>G(x)</math> evaluated at <math>x=0</math>.

Some interesting special cases are very useful.

====Geometric sequence====
In the example of Fibonacci numbers, we use the well known geometric series:
:<math>\frac{1}{1-x}=\sum_{n\ge 0}x^n</math>.
It is useful when we can express the generating function in the form of <math>G(x)=\frac{a_1}{1-b_1x}+\frac{a_2}{1-b_2x}+\cdots+\frac{a_k}{1-b_kx}</math>. The coefficient of <math>x^n</math> in such <math>G(x)</math> is <math>a_1b_1^n+a_2b_2^n+\cdots+a_kb_k^n</math>.

====Binomial theorem====
The <math>n</math>-th derivative of <math>(1+x)^\alpha</math> for some real <math>\alpha</math> is
:<math>\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-n+1)(1+x)^{\alpha-n}</math>.
By Taylor series, we get a generalized version of the binomial theorem known as [http://en.wikipedia.org/wiki/Binomial_coefficient#Newton.27s_binomial_series '''Newton's formula''']:
{{Theorem|Newton's formular (generalized binomial theorem)|
If <math>|x|<1</math>, then
:<math>(1+x)^\alpha=\sum_{n\ge 0}{\alpha\choose n}x^{n}</math>,
where <math>{\alpha\choose n}</math> is the '''generalized binomial coefficient''' defined by
:<math>{\alpha\choose n}=\frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-n+1)}{n!}</math>.
}}

=== Example: multisets ===
In the last lecture we gave a combinatorial proof of the number of <math>k</math>-multisets on an <math>n</math>-set. Now we give a generating function approach to the problem.

Let <math>S=\{x_1,x_2,\ldots,x_n\}</math> be an <math>n</math>-element set. We have
:<math>(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)}</math>,
where each <math>m:S\rightarrow\mathbb{N}</math> species a possible multiset on <math>S</math> with multiplicity function <math>m</math>.

Let all <math>x_i=x</math>. Then
:<math>
\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}
</math>
The last equation is due to the the definition of <math>\left({n\choose k}\right)</math>. Our task is to evaluate <math>\left({n\choose k}\right)</math>.

Due to the geometric sequence and the Newton's formula
:<math>
(1+x+x^2+\cdots)^n=(1-x)^{-n}=\sum_{k\ge 0}{-n\choose k}(-x)^k.
</math>
So
:<math>
\left({n\choose k}\right)=(-1)^k{-n\choose k}={n+k-1\choose k}.
</math>
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 <math>\left({n\choose k}\right)</math> as the combinatorial proof.

=== Example: Quicksort ===

== Catalan Number ==
We now introduce a class of counting problems, all with the same solution, called [http://en.wikipedia.org/wiki/Catalan_number '''Catalan number'''].

The <math>n</math>th Catalan number is denoted as <math>C_n</math>.
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.
* ''C''<sub>''n''</sub> is the number of '''Dyck words''' of length 2''n''. 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 [http://en.wikipedia.org/wiki/Dyck_language Dyck language]). For example, the following are the Dyck words of length 6:
<div class="center"><big> XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.</big></div>

* Re-interpreting the symbol X as an open parenthesis and Y as a close parenthesis, ''C''<sub>''n''</sub> counts the number of expressions containing ''n'' pairs of parentheses which are correctly matched:
<div class="center"><big> ((()))     ()(())     ()()()     (())()     (()()) </big></div>

* ''C''<sub>''n''</sub> 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:
<div class="center"><math>((ab)c)d \quad (a(bc))d \quad(ab)(cd) \quad a((bc)d) \quad a(b(cd))</math></div>

* 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 ''C''<sub>''n''</sub> is the number of full binary trees with ''n'' + 1 leaves:
[[Image:Catalan number binary tree example.png|center]]

* ''C''<sub>''n''</sub> 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:
[[Image:Catalan number 4x4 grid example.svg.png|450px|center]]

* ''C''<sub>''n''</sub> is the number of different ways a [http://en.wikipedia.org/wiki/Convex_polygon '''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:
[[Image:Catalan-Hexagons-example.png|400px|center]]

* ''C''<sub>''n''</sub> is the number of [http://en.wikipedia.org/wiki/Stack_(data_structure) '''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 ''w'' = ''unv'' 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.

* ''C''<sub>''n''</sub> is the number of ways to tile a stairstep shape of height ''n'' with ''n'' rectangles. The following figure illustrates the case ''n'' = 4:
[[Image:Catalan stairsteps 4.png|400px|center]]

{{Theorem|Recurrence relation for Catalan numbers|
:<math>C_0=0</math>, <math>C_1=1</math>, and for <math>n>1</math>,
::<math>
C_n=\sum_{i=1}^{n-1}C_iC_{n-i}.
</math>
}}

Let <math>G(x)=\sum_{n\ge 0}C_nx^n</math> be the generating function. Apply the product rule,
:<math>G(x)^2=\sum_{n\ge 0}\sum_{k=0}^{n}C_kC_{n-k}x^n=\sum_{n\ge 2}\sum_{k=1}^{n-1}C_kC_{n-k}x^n</math>.
Due to the recurrence,
:<math>G(x)=\sum_{n\ge 0}C_nx^n=x+\sum_{n\ge 2}\sum_{k=1}^{n-1}C_kC_{n-k}x^n=x+G(x)^2</math>.
Solving this, we obtain
:<math>G(x)=\frac{1\pm(1-4x)^{1/2}}{2}</math>.
Because <math>C_0=0</math>, it must hold that <math>G(x)=\frac{1-(1-4x)^{1/2}}{2}</math>, or otherwise the constant term is not zero. Expanding <math>(1-4x)^{1/2}</math> by Newton's formula, we have
:<math>
\begin{align}
G(x)
&=
\frac{1-(1-4x)^{1/2}}{2}\\
&=
1-\frac{1}{2}\sum_{n\ge 0}{1/2\choose n}(-4x)^n
\end{align}
</math>
Thus,
:<math>
\begin{align}
C_n
&=-\frac{1}{2}{1/2\choose n}(-4)^n\\
&=-\frac{1}{2}\cdot\frac{1}{2}\cdot\frac{-1}{2}\cdot\frac{-3}{2}\cdots\frac{-(2n-3)}{2}\cdot(-4)^n/n!\\
&=\frac{(2n-2)!}{(n-1)!n!}\\
&=\frac{1}{n}{2n-2\choose n-1}.
\end{align}
</math>
So we prove the following closed form for Catalan number.
{{Theorem|Theorem|
:<math>C_n=\frac{1}{n}{2n-2\choose n-1}</math>.
}}

Combinatorics (Fall 2010)/Generating functions

2010-09-12T02:46:22Z

172.21.1.108: /* Pólya's problem of changing money */

== 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 <math>a_n</math> depending a parameter <math>n</math>. Sometimes this <math>a_n</math> is called a ''counting function'' as it is a function of the parameter <math>n</math>. <math>a_n</math> can also be treated as a infinite series:
:<math>a_0,a_1,a_2,\ldots</math>

The '''ordinary generating function (OGF)''' defined by <math>a_n</math> is
:<math>
G(x)=\sum_{n\ge 0} a_nx^n.
</math>

So <math>G(x)=a_0+a_1x+a_2x^2+\cdots</math>. An expression in this form is called a [http://en.wikipedia.org/wiki/Formal_power_series '''formal power series'''], and <math>a_0,a_1,a_2,\ldots</math> is the sequence of '''coefficients'''.

Furthermore, the generating function can be expanded as
:G(x)=<math>(\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</math>
so it indeed "generates" all the possible instances of the objects we want to count.

Usually, we do not evaluate the generating function <math>GF(x)</math> on any particular value. <math>x</math> 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
:<math>(a_0,a_1,a_2,\ldots\ldots)</math>.

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 ===

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

In both problems, the solution is given by <math>F_n</math> which satisfies the following recursion.
:<math>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}</math>

<math>F_n</math> is called the [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number].

{{Theorem|Theorem|
::<math>F_n=\frac{1}{\sqrt{5}}\left(\phi^n-\hat{\phi}^n\right)</math>,
:where <math>\phi=\frac{1+\sqrt{5}}{2}</math> and <math>\hat{\phi}=\frac{1-\sqrt{5}}{2}</math>.
}}
The quantity <math>\phi=\frac{1+\sqrt{5}}{2}</math> is the so-called [http://en.wikipedia.org/wiki/Golden_ratio 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 <math>F_{n}</math> is
:<math>G(x)=\sum_{n\ge 0}F_n x^n</math>.
We have that <math>F_{n}=F_{n-1}+F_{n-2}</math> for <math>n\ge 2</math>, thus
:<math>\begin{align}
G(x)
&=
\sum_{n\ge 0}F_n x^n
&=
x+\sum_{n\ge 2}(F_{n-1}+F_{n-2})x^n.
\end{align}
</math>
For generating functions, there are general ways to generate <math>F_{n-1}</math> and <math>F_{n-2}</math>, or the coefficients with any smaller indices.
:<math>
\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}
</math>
So we have
:<math>G(x)=x+(x+x^2)G(x)\,</math>,
hence
:<math>G(x)=\frac{x}{1-x-x^2}</math>.
The value of <math>F_n</math> is the coefficient of <math>x^n</math> in the Taylor series for this formular, which is <math>\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</math>. 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.
{{Theorem|Proposition|
:Let <math>\phi=\frac{1+\sqrt{5}}{2}</math> and <math>\hat{\phi}=\frac{1-\sqrt{5}}{2}</math>. It holds that
::<math>\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}</math>.
}}

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

{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|
:{|
|
<math>1-x-x^2</math> has two roots <math>\frac{-1\pm\sqrt{5}}{2}</math>.

Denote that <math>\phi=\frac{2}{-1+\sqrt{5}}=\frac{1+\sqrt{5}}{2}</math> and <math>\hat{\phi}=\frac{2}{-1-\sqrt{5}}=\frac{1-\sqrt{5}}{2}</math>.

Then <math>(1-x-x^2)=(1-\phi x)(1-\hat{\phi}x)</math>, so we can write
:<math>
\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}
</math>
where <math>\alpha</math> and <math>\beta</math> satisfying that
:<math>\begin{cases}
\alpha+\beta=0\\
\alpha\phi+\beta\hat{\phi}= -1.
\end{cases}</math>
Solving this we have that <math>\alpha=\frac{1}{\sqrt{5}}</math> and <math>\beta=-\frac{1}{\sqrt{5}}</math>. Thus,
:<math>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}</math>.
|}
:<math>\square</math>
|}

Note that the expression <math>\frac{1}{1-z}</math> has a well known geometric expansion:
:<math>\frac{1}{1-z}=\sum_{n\ge 0}z^n</math>.

Therefore, <math>G(x)</math> can be expanded as
:<math>
\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}</math>
So the <math>n</math>th Fibonacci number is given by
:<math>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</math>.

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

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 <math>G(x)</math>, which is easy; and then manipulating the resulting formal power series to express it in terms of <math>G(x)</math>, which is more difficult (because it works backwards).

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

{{Theorem|Generating function manipulation|
:Let <math>G(x)=\sum_{n\ge 0}g_nx^n</math> and <math>F(x)=\sum_{n\ge 0}f_nx^n</math>.
----

::<math>
\begin{align}
x^k G(x)
&= \sum_{n\ge k}g_{n-k}x^n, &\qquad (\mbox{integer }k\ge 0)\\
\frac{G(x)-\sum_{i=0}^{k-1}g_iz^i}{x^k}
&=\sum_{n\ge 0}g_{n+k}x^n, &\qquad (\mbox{integer }k\ge 0)\\
\alpha F(x)+\beta G(x)
&= \sum_{n\ge 0} (\alpha f_n+\beta g_n)x^n\\
F(x)G(x)
&= \sum_{n\ge 0}\sum_{k=0}^nf_kg_{n-k}x^n\\
G(cx)
&= \sum_{n\ge 0} c^ng_n x^n\\
G'(x)
&=
\sum_{n\ge 0}(n+1)g_{n+1}x^n
\end{align}
</math>
}}

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 <math>G(x)</math> to evaluate its <math>n</math>-th coefficient. In principle, we can always use the [http://en.wikipedia.org/wiki/Taylor_series Taylor series]
:<math>G(x)=\sum_{n\ge 0}\frac{G^{(n)}(0)}{n!}x^n</math>,
where <math>G^{(n)}(0)</math> is the value of the <math>n</math>-th derivative of <math>G(x)</math> evaluated at <math>x=0</math>.

Some interesting special cases are very useful.

====Geometric sequence====
In the example of Fibonacci numbers, we use the well known geometric series:
:<math>\frac{1}{1-x}=\sum_{n\ge 0}x^n</math>.
It is useful when we can express the generating function in the form of <math>G(x)=\frac{a_1}{1-b_1x}+\frac{a_2}{1-b_2x}+\cdots+\frac{a_k}{1-b_kx}</math>. The coefficient of <math>x^n</math> in such <math>G(x)</math> is <math>a_1b_1^n+a_2b_2^n+\cdots+a_kb_k^n</math>.

====Binomial theorem====
The <math>n</math>-th derivative of <math>(1+x)^\alpha</math> for some real <math>\alpha</math> is
:<math>\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-n+1)(1+x)^{\alpha-n}</math>.
By Taylor series, we get a generalized version of the binomial theorem known as [http://en.wikipedia.org/wiki/Binomial_coefficient#Newton.27s_binomial_series '''Newton's formula''']:
{{Theorem|Newton's formular (generalized binomial theorem)|
If <math>|x|<1</math>, then
:<math>(1+x)^\alpha=\sum_{n\ge 0}{\alpha\choose n}x^{n}</math>,
where <math>{\alpha\choose n}</math> is the '''generalized binomial coefficient''' defined by
:<math>{\alpha\choose n}=\frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-n+1)}{n!}</math>.
}}

=== Example: multisets ===
In the last lecture we gave a combinatorial proof of the number of <math>k</math>-multisets on an <math>n</math>-set. Now we give a generating function approach to the problem.

Let <math>S=\{x_1,x_2,\ldots,x_n\}</math> be an <math>n</math>-element set. We have
:<math>(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)}</math>,
where each <math>m:S\rightarrow\mathbb{N}</math> species a possible multiset on <math>S</math> with multiplicity function <math>m</math>.

Let all <math>x_i=x</math>. Then
:<math>
\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}
</math>
The last equation is due to the the definition of <math>\left({n\choose k}\right)</math>. Our task is to evaluate <math>\left({n\choose k}\right)</math>.

Due to the geometric sequence and the Newton's formula
:<math>
(1+x+x^2+\cdots)^n=(1-x)^{-n}=\sum_{k\ge 0}{-n\choose k}(-x)^k.
</math>
So
:<math>
\left({n\choose k}\right)=(-1)^k{-n\choose k}={n+k-1\choose k}.
</math>
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 <math>\left({n\choose k}\right)</math> as the combinatorial proof.

== Catalan Number ==
We now introduce a class of counting problems, all with the same solution, called [http://en.wikipedia.org/wiki/Catalan_number '''Catalan number'''].

The <math>n</math>th Catalan number is denoted as <math>C_n</math>.
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.
* ''C''<sub>''n''</sub> is the number of '''Dyck words''' of length 2''n''. 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 [http://en.wikipedia.org/wiki/Dyck_language Dyck language]). For example, the following are the Dyck words of length 6:
<div class="center"><big> XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.</big></div>

* Re-interpreting the symbol X as an open parenthesis and Y as a close parenthesis, ''C''<sub>''n''</sub> counts the number of expressions containing ''n'' pairs of parentheses which are correctly matched:
<div class="center"><big> ((()))     ()(())     ()()()     (())()     (()()) </big></div>

* ''C''<sub>''n''</sub> 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:
<div class="center"><math>((ab)c)d \quad (a(bc))d \quad(ab)(cd) \quad a((bc)d) \quad a(b(cd))</math></div>

* 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 ''C''<sub>''n''</sub> is the number of full binary trees with ''n'' + 1 leaves:
[[Image:Catalan number binary tree example.png|center]]

* ''C''<sub>''n''</sub> 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:
[[Image:Catalan number 4x4 grid example.svg.png|450px|center]]

* ''C''<sub>''n''</sub> is the number of different ways a [http://en.wikipedia.org/wiki/Convex_polygon '''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:
[[Image:Catalan-Hexagons-example.png|400px|center]]

* ''C''<sub>''n''</sub> is the number of [http://en.wikipedia.org/wiki/Stack_(data_structure) '''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 ''w'' = ''unv'' 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.

* ''C''<sub>''n''</sub> is the number of ways to tile a stairstep shape of height ''n'' with ''n'' rectangles. The following figure illustrates the case ''n'' = 4:
[[Image:Catalan stairsteps 4.png|400px|center]]

{{Theorem|Recurrence relation for Catalan numbers|
:<math>C_0=0</math>, <math>C_1=1</math>, and for <math>n>1</math>,
::<math>
C_n=\sum_{i=1}^{n-1}C_iC_{n-i}.
</math>
}}

Let <math>G(x)=\sum_{n\ge 0}C_nx^n</math> be the generating function. Apply the product rule,
:<math>G(x)^2=\sum_{n\ge 0}\sum_{k=0}^{n}C_kC_{n-k}x^n=\sum_{n\ge 2}\sum_{k=1}^{n-1}C_kC_{n-k}x^n</math>.
Due to the recurrence,
:<math>G(x)=\sum_{n\ge 0}C_nx^n=x+\sum_{n\ge 2}\sum_{k=1}^{n-1}C_kC_{n-k}x^n=x+G(x)^2</math>.
Solving this, we obtain
:<math>G(x)=\frac{1\pm(1-4x)^{1/2}}{2}</math>.
Because <math>C_0=0</math>, it must hold that <math>G(x)=\frac{1-(1-4x)^{1/2}}{2}</math>, or otherwise the constant term is not zero. Expanding <math>(1-4x)^{1/2}</math> by Newton's formula, we have
:<math>
\begin{align}
G(x)
&=
\frac{1-(1-4x)^{1/2}}{2}\\
&=
1-\frac{1}{2}\sum_{n\ge 0}{1/2\choose n}(-4x)^n
\end{align}
</math>
Thus,
:<math>
\begin{align}
C_n
&=-\frac{1}{2}{1/2\choose n}(-4)^n\\
&=-\frac{1}{2}\cdot\frac{1}{2}\cdot\frac{-1}{2}\cdot\frac{-3}{2}\cdots\frac{-(2n-3)}{2}\cdot(-4)^n/n!\\
&=\frac{(2n-2)!}{(n-1)!n!}\\
&=\frac{1}{n}{2n-2\choose n-1}.
\end{align}
</math>
So we prove the following closed form for Catalan number.
{{Theorem|Theorem|
:<math>C_n=\frac{1}{n}{2n-2\choose n-1}</math>.
}}

Randomized Algorithms (Spring 2010)/Tail inequalities

2010-02-23T06:43:30Z

172.21.1.247: /* The Chernoff bound */

== Select the Median ==

The [http://en.wikipedia.org/wiki/Selection_algorithm selection problem] is the problem of finding the <math>k</math>th smallest element in a set <math>S</math>. A typical case of selection problem is finding the '''median'''.

{|border="1"
|'''Definition'''
:The median of a set <math>S</math> is the <math>(\lceil n/2\rceil)</math>th element in the sorted order of <math>S</math>.
|}

The median can be found in <math>O(n\log n)</math> time by sorting. There is a linear-time deterministic algorithm, [http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22 "median of medians" algorithm], which is quite sophisticated. Here we introduce a much simpler randomized algorithm which also runs in linear time.

=== Randomized median algorithm ===
The idea of this algorithm is random sampling. For a set <math>S</math>, let <math>m\in S</math> denote the median. We observe that if we can find two elements <math>d,u\in S</math> satisfying the following properties:
# The median is between <math>d</math> and <math>u</math> in the sorted order, i.e. <math>d\le m\le u</math>;
# The total number of elements between <math>d</math> and <math>u</math> is small, specially for <math>C=\{x\in S\mid d\le x\le u\}</math>, <math>|C|=o(n/\log n)</math>.

Provided <math>d</math> and <math>u</math> with these two properties, within linear time, we can compute the ranks of <math>d</math> in <math>S</math>, construct <math>C</math>, and sort <math>C</math>. Therefore, the median <math>m</math> of <math>S</math> can be picked from <math>C</math> in linear time.

So how can we select such elements <math>d</math> and <math>u</math> from <math>S</math>? Certainly sorting <math>S</math> would give us the elements, but isn't that exactly what we want to avoid in the first place?

Observe that <math>d</math> and <math>u</math> are only asked to roughly satisfy some constraints. This hints us maybe we can construct a ''sketch'' of <math>S</math> which is small enough to sort cheaply and roughly represents <math>S</math>, and then pick <math>d</math> and <math>u</math> from this sketch. We construct the sketch by randomly sampling a relatively small number of elements from <math>S</math>. Then the strategy of algorithm is outlined by:
* Sample a set <math>R</math> of elements from <math>S</math>.
* Sort <math>R</math> and choose <math>d</math> and <math>u</math> somewhere around the median of <math>R</math>.
* If <math>d</math> and <math>u</math> have the desirable properties, we can compute the median in linear time, or otherwise the algorithm fails.

The parameters to be fixed are: the size of <math>R</math> (small enough to sort in linear time and large enough to contain sufficient information of <math>S</math>); and the order of <math>d</math> and <math>u</math> in <math>R</math> (not too close to have <math>m</math> between them, and not too far away to have <math>C</math> sortable in linear time).

We choose the size of <math>R</math> as <math>n^{3/4}</math>, and <math>d</math> and <math>u</math> are within <math>\sqrt{n}</math> range around the median of <math>R</math>.

{|border="1"
|'''Randomized Median Algorithm:'''
|-
|'''Input:''' a set <math>S</math> of <math>n</math> elements over totally ordered domain.
# Pick a multi-set <math>R</math> of <math>\left\lceil n^{3/4}\right\rceil</math> elements in <math>S</math>, chosen independently and uniformly at random with replacement, and sort <math>R</math>.
# Let <math>d</math> be the <math>\left\lfloor\frac{1}{2}n^{3/4}-\sqrt{n}\right\rfloor</math>-th smallest element in <math>R</math>, and let <math>u</math> be the <math>\left\lceil\frac{1}{2}n^{3/4}+\sqrt{n}\right\rceil</math>-th smallest element in <math>R</math>.
# Construct <math>C=\{x\in S\mid d\le x\le u\}</math> and compute the ranks <math>r_d=|\{x\in S\mid x<d\}|</math> and <math>r_u=|\{x\in S\mid x<u\}|</math>.
# If <math>r_d>\frac{n}{2}</math> or <math>r_u<\frac{n}{2}</math> or <math>|C|>4n^{3/4}</math> then return FAIL.
# Sort <math>C</math> and return the <math>\left(\left\lfloor\frac{n}{2}\right\rfloor-r_d+1\right)</math>th element in the sorted order of <math>C</math>.
|}

"Sample with replacement" (有放回采样) means that after sampling an element, we put the element back to the set. In this way, each sampled element is independently and identically distributed (''i.i.d'') (独立同分布). In the above algorithm, this is for our convenience of analysis.

=== Analysis ===
The algorithm always terminates in linear time because each line of the algorithm costs at most linear time. The last three line guarantees that the algorithm returns the correct median if it does not fail.

We then only need to bound the probability that the algorithm returns a FAIL. Let <math>m\in S</math> be the median of <math>S</math>. By Line 4, we know that the algorithm returns a FAIL if and only if at least one of the following events occurs:
* <math>\mathcal{E}_1: Y=|\{x\in R\mid x\le m\}|<\frac{1}{2}n^{3/4}-\sqrt{n}</math>;
* <math>\mathcal{E}_2: Z=|\{x\in R\mid x\ge m\}|<\frac{1}{2}n^{3/4}-\sqrt{n}</math>;
* <math>\mathcal{E}_3: |C|>4n^{3/4}</math>.

<math>\mathcal{E}_3</math> directly follows the third condition in Line 4. <math>\mathcal{E}_1</math> and <math>\mathcal{E}_2</math> are a bit tricky. The first condition in Line 4 is that <math>r_d>\frac{n}{2}</math>, which looks not exactly the same as <math>\mathcal{E}_1</math>, but both <math>\mathcal{E}_1</math> and that <math>r_d>\frac{n}{2}</math> are equivalent to the same event: the <math>\left\lfloor\frac{1}{2}n^{3/4}-\sqrt{n}\right\rfloor</math>-th smallest element in <math>R</math> is greater than <math>m</math>, thus they are actually equivalent. Similarly, <math>\mathcal{E}_2</math> is equivalent to the second condition of Line 4.

We now bound the probabilities of these events one by one.

{|border="1"
|'''Lemma 1'''
:<math>\Pr[\mathcal{E}_1]\le \frac{1}{4}n^{-1/4}</math>.
|}
'''Proof:''' Let <math>X_i</math> be the <math>i</math>th sampled element in Line 1 of the algorithm. Let <math>Y_i</math> be a indicator random variable such that
:<math>
Y_i=
\begin{cases}
1 & \mbox{if }X_i\le m,\\
0 & \mbox{otherwise.}
\end{cases}
</math>
It is obvious that <math>Y=\sum_{i=1}^{n^{3/4}}Y_i</math>, where <math>Y</math> is as defined in <math>\mathcal{E}_1</math>. For every <math>X_i</math>, there are <math>\left\lceil\frac{n}{2}\right\rceil</math> elements in <math>S</math> that are less than or equal to the median. The probability that <math>Y_i=1</math> is
:<math>
p=\Pr[Y_i=1]=\Pr[X_i\le m]=\frac{1}{n}\left\lceil\frac{n}{2}\right\rceil,
</math>
which is within the range of <math>\left[\frac{1}{2},\frac{1}{2}+\frac{1}{2n}\right]</math>. Thus
:<math>
\mathbf{E}[Y]=n^{3/4}p\ge \frac{1}{2}n^{3/4}.
</math>

The event <math>\mathcal{E}_1</math> is defined as that <math>Y<\frac{1}{2}n^{3/4}-\sqrt{n}</math>.

Note that <math>Y_i</math>'s are Bernoulli trials, and <math>Y</math> is the sum of <math>n^{3/4}</math> Bernoulli trials, which follows binomial distribution with parameters <math>n^{3/4}</math> and <math>p</math>. Thus, the variance is
:<math>\mathbf{Var}[Y]=n^{3/4}p(1-p)\le \frac{1}{4}n^{3/4}.
</math>

Applying Chebyshev's inequality,
:<math>
\begin{align}
\Pr[\mathcal{E}_1]
&=
\Pr\left[Y<\frac{1}{2}n^{3/4}-\sqrt{n}\right]\\
&\le
\Pr\left[|Y-\mathbf{E}[Y]|>\sqrt{n}\right]\\
&\le
\frac{\mathbf{Var}[Y]}{n}\\
&\le\frac{1}{4}n^{-1/4}.
\end{align}
</math>

<math>\square</math>

By a similar analysis, we can obtain the following bound for the event <math>\mathcal{E}_2</math>.

{|border="1"
|'''Lemma 2'''
:<math>\Pr[\mathcal{E}_2]\le \frac{1}{4}n^{-1/4}</math>.
|}

We now bound the probability of the event <math>\mathcal{E}_3</math>.

{|border="1"
|'''Lemma 3'''
:<math>\Pr[\mathcal{E}_3]\le \frac{1}{2}n^{-1/4}</math>.
|}
'''Proof:''' The event <math>\mathcal{E}_3</math> is defined as that <math>|C|>4 n^{3/4}</math>, which by the Pigeonhole Principle, implies that at leas one of the following must be true:
* <math>\mathcal{E}_3'</math>: at least <math>2n^{3/4}</math> elements of <math>C</math> is greater than <math>m</math>;
* <math>\mathcal{E}_3''</math>: at least <math>2n^{3/4}</math> elements of <math>C</math> is smaller than <math>m</math>.

We bound the probability that <math>\mathcal{E}_3'</math> occurs; the second will have the same bound by symmetry.

Recall that <math>C</math> is the region in <math>S</math> between <math>d</math> and <math>u</math>. If there are at least <math>2n^{3/4}</math> elements of <math>C</math> greater than the median <math>m</math> of <math>S</math>, then the rank of <math>u</math> in the sorted order of <math>S</math> must be at least <math>\frac{1}{2}n+2n^{3/4}</math> and thus <math>R</math> has at least <math>\frac{1}{2}n^{3/4}-\sqrt{n}</math> samples among the <math>\frac{1}{2}n-2n^{3/4}</math> largest elements in <math>S</math>.

Let <math>X_i\in\{0,1\}</math> indicate whether the <math>i</math>th sample is among the <math>\frac{1}{2}n-2n^{3/4}</math> largest elements in <math>S</math>. Let <math>X=\sum_{i=1}^{n^{3/4}}X_i</math> be the number of samples in <math>R</math> among the <math>\frac{1}{2}n-2n^{3/4}</math> largest elements in <math>S</math>.
It holds that
:<math>p=\Pr[X_i=1]=\frac{\frac{1}{2}n-2n^{3/4}}{n}=\frac{1}{2}-2n^{-1/4}</math>.

<math>X</math> is a binomial random variable with
:<math>
\mathbf{E}[X]=n^{3/4}p=\frac{1}{2}n^{3/4}-2\sqrt{n},
</math>
and
:<math>
\mathbf{Var}[X]=n^{3/4}p(1-p)=\frac{1}{4}n^{3/4}-4n^{1/4}<\frac{1}{4}n^{3/4}.
</math>
Applying Chebyshev's inequality,
:<math>
\begin{align}
\Pr[\mathcal{E}_3']
&=
\Pr\left[X\ge\frac{1}{2}n^{3/4}-\sqrt{n}\right]\\
&\le
\Pr\left[|X-\mathbf{E}[X]|\ge\sqrt{n}\right]\\
&\le
\frac{\mathbf{Var}[X]}{n}\\
&\le\frac{1}{4}n^{-1/4}.
\end{align}
</math>

Symmetrically, we have that <math>\Pr[\mathcal{E}_3'']\le\frac{1}{4}n^{-1/4}</math>.

Applying the union bound
:<math>\Pr[\mathcal{E}_3]\le \Pr[\mathcal{E}_3']+\Pr[\mathcal{E}_3'']\le\frac{1}{2}n^{-1/4}.
</math>
<math>\square</math>

Combining the three bounds. Applying the union bound to them, the probability that the algorithm returns a FAIL is at most
:<math>
\Pr[\mathcal{E}_1]+\Pr[\mathcal{E}_2]+\Pr[\mathcal{E}_3]\le n^{-1/4}.
</math>

Therefore the algorithm always terminates in linear time and returns the correct median with high probability.

== Chernoff Bound ==
Suppose that we have a fair coin. If we toss it once, then the outcome is completely unpredictable. But if we toss it, say for 1000 times, then the number of HEADs is very likely to be around 500. This striking phenomenon is called the '''concentration'''. The Chernoff bound captures the concentration of independent trials.

The Chernoff bound is also a tail bound for the sum of independent random variables which may give us ''exponentially'' sharp bounds.

Before proving the Chernoff bound, we should talk about the moment generating functions.

=== Moment generating functions ===
The more we know about the moments of a random variable <math>X</math>, the more information we would have about <math>X</math>. There is a so-called '''moment generating function''', which "packs" all the information about the moments of <math>X</math> into one function.

{|border="1"
|'''Definition:'''
:The moment generating function of a random variable <math>X</math> is defined as <math>\mathbf{E}\left[\mathrm{e}^{\lambda X}\right]</math> where <math>\lambda</math> is the parameter of the function.
|}

By Taylor's expansion and the linearity of expectations,
:<math>\begin{align}
\mathbf{E}\left[\mathrm{e}^{\lambda X}\right]
&=
\mathbf{E}\left[\sum_{k=0}^\infty\frac{\lambda^k}{k!}X^k\right]\\
&=\sum_{k=0}^\infty\frac{\lambda^k}{k!}\mathbf{E}\left[X^k\right]
\end{align}</math>

The moment generating function <math>\mathbf{E}\left[\mathrm{e}^{\lambda X}\right]</math> is a function of <math>\lambda</math>.

=== The Chernoff bound ===
The Chernoff bounds are tail inequalities with exponential decays for the sum of independent trials.
The bounds are obtained by applying Markov's inequality to the moment generating function of the sum of independent trials, with some appropriate choice of the parameter <math>\lambda</math>.
{|border="1"
|'''Chernoff bound (the upper tail):'''
:Let <math>X=\sum_{i=1}^n X_i</math>, where <math>X_1, X_2, \ldots, X_n</math> are independent Poisson trials. Let <math>\mu=\mathbf{E}[X]</math>.
:Then for any <math>\delta>0</math>,
::<math>\Pr[X\ge (1+\delta)\mu]\le\left(\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\right)^{\mu}.</math>
|}
'''Proof:''' For any <math>\lambda>0</math>, <math>X\ge (1+\delta)\mu</math> is equivalent to that <math>e^{\lambda X}\ge e^{\lambda (1+\delta)\mu}</math>, thus
:<math>\begin{align}
\Pr[X\ge (1+\delta)\mu]
&=
\Pr\left[e^{\lambda X}\ge e^{\lambda (1+\delta)\mu}\right]\\
&\le
\frac{\mathbf{E}\left[e^{\lambda X}\right]}{e^{\lambda (1+\delta)\mu}},
\end{align}</math>
where the last step follows by Markov's inequality.

Computing the moment generating function <math>\mathbf{E}[e^{\lambda X}]</math>:
:<math>\begin{align}
\mathbf{E}\left[e^{\lambda X}\right]
&=
\mathbf{E}\left[e^{\lambda \sum_{i=1}^n X_i}\right]\\
&=
\mathbf{E}\left[\prod_{i=1}^n e^{\lambda X_i}\right]\\
&=
\prod_{i=1}^n \mathbf{E}\left[e^{\lambda X_i}\right].
& (\mbox{for independent random variables})
\end{align}</math>

Let <math>p_i=\Pr[X_i=1]</math> for <math>i=1,2,\ldots,n</math>. Then,
:<math>\mu=\mathbf{E}[X]=\mathbf{E}\left[\sum_{i=1}^n X_i\right]=\sum_{i=1}^n\mathbf{E}[X_i]=\sum_{i=1}^n p_i</math>.

We bound the moment generating function for each individual <math>X_i</math> as follows.
:<math>\begin{align}
\mathbf{E}\left[e^{\lambda X_i}\right]
&=
p_i\cdot e^{\lambda\cdot 1}+(1-p_i)\cdot e^{\lambda\cdot 0}\\
&=
1+p_i(e^\lambda -1)\\
&\le
e^{p_i(e^\lambda-1)},
\end{align}</math>
where in the last step we apply the Taylor's expansion so that <math>e^y\ge 1+y</math> where <math>y=p_i(e^\lambda-1)\ge 0</math>. (By doing this, we can transform the product to the sum of <math>p_i</math>, which is <math>\mu</math>.)

Therefore,
:<math>\begin{align}
\mathbf{E}\left[e^{\lambda X}\right]
&=
\prod_{i=1}^n \mathbf{E}\left[e^{\lambda X_i}\right]\\
&\le
\prod_{i=1}^n e^{p_i(e^\lambda-1)}\\
&=
\exp\left(\sum_{i=1}^n p_i(e^{\lambda}-1)\right)\\
&=
e^{(e^\lambda-1)\mu}.
\end{align}</math>
Thus, we have shown that for any <math>\lambda>0</math>,
:<math>\begin{align}
\Pr[X\ge (1+\delta)\mu]
&\le
\frac{\mathbf{E}\left[e^{\lambda X}\right]}{e^{\lambda (1+\delta)\mu}}\\
&\le
\frac{e^{(e^\lambda-1)\mu}}{e^{\lambda (1+\delta)\mu}}\\
&=
\left(\frac{e^{(e^\lambda-1)}}{e^{\lambda (1+\delta)}}\right)^\mu
\end{align}</math>.
For any <math>\delta>0</math>, we can let <math>\lambda=\ln(1+\delta)>0</math> to get
:<math>\Pr[X\ge (1+\delta)\mu]\le\left(\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\right)^{\mu}.</math>

<math>\square</math>

The idea of the proof is actually quite clear: we apply Markov's inequality to <math>e^{\lambda X}</math> and for the rest, we just estimate the moment generating function <math>\mathbf{E}[e^{\lambda X}]</math>. To make the bound as tight as possible, we minimized the <math>\frac{e^{(e^\lambda-1)}}{e^{\lambda (1+\delta)}}</math> by setting <math>\lambda=\ln(1+\delta)</math>, which can be justified by taking derivatives of <math>\frac{e^{(e^\lambda-1)}}{e^{\lambda (1+\delta)}}</math>.

----

We then proceed to the lower tail, the probability that the random variable deviates below the mean value:

{|border="1"
|'''Chernoff bound (the lower tail):'''
:Let <math>X=\sum_{i=1}^n X_i</math>, where <math>X_1, X_2, \ldots, X_n</math> are independent Poisson trials. Let <math>\mu=\mathbf{E}[X]</math>.
:Then for any <math>0<\delta<1</math>,
::<math>\Pr[X\le (1-\delta)\mu]\le\left(\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}\right)^{\mu}.</math>
|}
'''Proof:''' For any <math>\lambda<0</math>, by the same analysis as in the upper tail version,
:<math>\begin{align}
\Pr[X\le (1-\delta)\mu]
&=
\Pr\left[e^{\lambda X}\ge e^{\lambda (1-\delta)\mu}\right]\\
&\le
\frac{\mathbf{E}\left[e^{\lambda X}\right]}{e^{\lambda (1-\delta)\mu}}\\
&\le
\left(\frac{e^{(e^\lambda-1)}}{e^{\lambda (1-\delta)}}\right)^\mu.
\end{align}</math>
For any <math>0<\delta<1</math>, we can let <math>\lambda=\ln(1-\delta)<0</math> to get
:<math>\Pr[X\ge (1-\delta)\mu]\le\left(\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}\right)^{\mu}.</math>

<math>\square</math>

----

Some useful special forms of the bounds can be derived directly from the above general forms of the bounds. We now know better why we say that the bounds are exponentially sharp.

{|border="1"
|'''Useful forms of the Chernoff bound'''
:Let <math>X=\sum_{i=1}^n X_i</math>, where <math>X_1, X_2, \ldots, X_n</math> are independent Poisson trials. Let <math>\mu=\mathbf{E}[X]</math>. Then
:1. for <math>0<\delta\le 1</math>,
::<math>\Pr[X\ge (1+\delta)\mu]<\exp\left(-\frac{\mu\delta^2}{3}\right);</math>
::<math>\Pr[X\le (1-\delta)\mu]<\exp\left(-\frac{\mu\delta^2}{2}\right);</math>
:2. for <math>t\ge 2e\mu</math>,
::<math>\Pr[X\ge t]\le 2^{-t}.</math>
|}
'''Proof:''' To obtain the bounds in (1), we need to show that for <math>0<\delta< 1</math>, <math>\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\le e^{-\delta^2/3}</math> and <math>\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}\le e^{-\delta^2/2}</math>. We can verify both inequalities by standard analysis techniques.

To obtain the bound in (2), let <math>t=(1+\delta)\mu</math>. Then <math>\delta=t/\mu-1\ge 2e-1</math>. Hence,
:<math>\begin{align}
\Pr[X\ge(1+\delta)\mu]
&\le
\left(\frac{e^\delta}{(1+\delta)^{(1+\delta)}}\right)^\mu\\
&\le
\left(\frac{e}{1+\delta}\right)^{(1+\delta)\mu}\\
&\le
\left(\frac{e}{2e}\right)^{2e\mu}\\
&\le
2^{-t}
\end{align}</math>

<math>\square</math>

== Applications of Chernoff Bounds ==
We now introduce some applications of Chernoff bounds in randomized algorithms.

=== Balls into bins ===
Throwing <math>m</math> balls uniformly and independently to <math>n</math> bins, what is the maximum load of all bins? In the last class, by using a counting argument, we proved that for the case that <math>m=n</math>, the maximum load is <math>O(\ln n\ln\ln n)</math> with high probability. Now we show that when there are more balls, the loads are more balanced.

For any <math>i\in[n]</math> and <math>j\in[m]</math>, let <math>X_{ij}</math> be the indicator variable for the event that ball <math>j</math> is thrown to bin <math>i</math>. Obviously
:<math>\mathbf{E}[X_{ij}]=\Pr[\mbox{ball }j\mbox{ is thrown to bin }i]=\frac{1}{n}</math>
Let <math>Y_i=\sum_{j\in[m]}X_{ij}</math> be the load of bin <math>i</math>.

Let us consider the case when <math>m=6n\ln n</math>. Then the expected load of bin <math>i</math> is
:<math>\mu=\mathbf{E}[Y_i]=\mathbf{E}\left[\sum_{j\in[m]}X_{ij}\right]=\sum_{j\in[m]}\mathbf{E}[X_{ij}]=m/n=6\ln n</math>.
Note that <math>Y_i</math> is a sum of <math>m</math> mutually independent indicator variable. Applying Chernoff bound, for any particular bin <math>i\in[n]</math>,
:<math>
\Pr[Y_i>12\ln n] =\Pr[Y_i>(1+1)\mu]\le e^{-\frac{\mu}{3}} = e^{-2\ln n}= \frac{1}{n^2}.
</math>
Applying the union bound, the probability that there exists a bin with load <math>>12\ln n</math> is
:<math>n\cdot \Pr[Y_1>12\ln n]\le \frac{1}{n}</math>.
Therefore, with probability at least <math>1-\frac{1}{n}</math>, the maximum load is within <math>12\ln n=O(m/n)</math>.

=== Set balancing ===
Supposed that we have an <math>n\times m</math> matrix <math>A</math> with 0-1 entries. We are looking for a <math>b\in\{-1,+1\}^m</math> that minimizes <math>\|Ab\|_\infty</math>.

Recall that <math>\|\cdot\|_\infty</math> is the infinity norm (also called <math>L_\infty</math> norm) of a vector, and for the vector <math>c=Ab</math>,
:<math>\|Ab\|_\infty=\max_{i=1,2,\ldots,n}|c_i|</math>.

We can also describe this problem as an optimization:
:<math>\begin{align}
\mbox{minimize }
&\quad
\|Ab\|_\infty\\
\mbox{subject to: }
&\quad
b\in\{-1,+1\}^m.
\end{align}</math>

{|border="1"
|The problem arises in designing statistical experiments. Suppose that we have <math>m</math> '''subjects''', each of which may have up to <math>n</math> '''features'''. This gives us an <math>n\times m</math> matrix <math>A</math>:
:<math>
\begin{array}{c}
\mbox{feature 1:}\\
\mbox{feature 2:}\\
\vdots\\
\mbox{feature n:}\\
\end{array}
\left[
\begin{array}{cccc}
a_{11} & a_{12} & \cdots & a_{1m}\\
a_{21} & a_{22} & \cdots & a_{2m}\\
\vdots & \vdots & \ddots & \vdots\\
a_{n1} & a_{n2} & \cdots & a_{nm}\\
\end{array}
\right],
</math>
where each column represents a subject and each row represent a feature. An entry <math>a_{ij}\in\{0,1\}</math> indicates whether subject <math>j</math> has feature <math>i</math>.

By multiplying a vector <math>b\in\{-1,+1\}^m</math>
:<math>
\left[
\begin{array}{cccc}
a_{11} & a_{12} & \cdots & a_{1m}\\
a_{21} & a_{22} & \cdots & a_{2m}\\
\vdots & \vdots & \ddots & \vdots\\
a_{n1} & a_{n2} & \cdots & a_{nm}\\
\end{array}
\right]
\left[
\begin{array}{c}
b_{1}\\
b_{2}\\
\vdots\\
b_{m}\\
\end{array}
\right]
=
\left[
\begin{array}{c}
c_{1}\\
c_{2}\\
\vdots\\
c_{n}\\
\end{array}
\right],
</math>
the subjects are partitioned into two disjoint groups: one for -1 and other other for +1. Each <math>c_i</math> gives the difference between the numbers of subjects with feature <math>i</math> in the two groups. By minimizing <math>\|Ab\|_\infty=\|c\|_\infty</math>, we ask for an optimal partition so that each feature is roughly as balanced as possible between the two groups.

In a scientific experiment, one of the group serves as a [http://en.wikipedia.org/wiki/Scientific_control control group] (对照组). Ideally, we want the two groups are statistically identical, which is usually impossible to achieve in practice. The requirement of minimizing <math>\|Ab\|_\infty</math> actually means the statistical difference between the two groups are minimized.
|}

We propose an extremely simple "randomized algorithm" for computing a <math>b\in\{-1,+1\}^m</math>: for each <math>i=1,2,\ldots, m</math>, let <math>b_i</math> be independently chosen from <math>\{-1,+1\}</math>, such that
:<math>b_i=
\begin{cases}
-1 & \mbox{with probability }\frac{1}{2}\\
+1 &\mbox{with probability }\frac{1}{2}
\end{cases}.
</math>

This procedure can hardly be called as an "algorithm", because its decision is made disregard of the input <math>A</math>. We then show that despite of this obliviousness, the algorithm chooses a good enough <math>b</math>, such that for any <math>A</math>, <math>\|Ab\|_\infty=O(\sqrt{m\ln n})</math> with high probability.
{|border="1"
|'''Theorem'''
:Let <math>A</math> be an <math>n\times m</math> matrix with 0-1 entries. For a random vector <math>b</math> with <math>m</math> entries chosen independently and with equal probability from <math>\{-1,+1\}</math>,
::<math>\Pr[\|Ab\|_\infty>2\sqrt{2m\ln n}]\le\frac{2}{n}</math>.
|}
'''Proof:'''
Consider particularly the <math>i</math>-th row of <math>A</math>. The entry of <math>Ab</math> contributed by row <math>i</math> is <math>c_i=\sum_{j=1}^m a_{ij}b_j</math>.

Let <math>k</math> be the non-zero entries in the row. If <math>k\le2\sqrt{2m\ln n}</math>, then clearly <math>|c_i|</math> is no greater than <math>2\sqrt{2m\ln n}</math>. On the other hand if <math>k>2\sqrt{2m\ln n}</math> then the <math>k</math> nonzero terms in the sum
:<math>c_i=\sum_{j=1}^m a_{ij}b_j</math>
are independent, each with probability 1/2 of being either +1 or -1.

Thus, for these <math>k</math> nonzero terms, each <math>b_i</math> is either positive or negative independently with equal probability. There are expectedly <math>\mu=\frac{k}{2}</math> positive <math>b_i</math>'s among these <math>k</math> terms, and <math>c_i<-2\sqrt{2m\ln n}</math> only occurs when there are less than <math>\frac{k}{2}-\sqrt{2m\ln n}=\left(1-\delta\right)\mu</math> positive <math>b_i</math>'s, where <math>\delta=\frac{2\sqrt{2m\ln n}}{k}</math>. Applying Chernoff bound, this event occurs with probability at most
:<math>\begin{align}
\exp\left(-\frac{\mu\delta^2}{2}\right)
&=
\exp\left(-\frac{k}{2}\cdot\frac{8m\ln n}{2k^2}\right)\\
&=
\exp\left(-\frac{2m\ln n}{k}\right)\\
&\le
\exp\left(-\frac{2m\ln n}{m}\right)\\
&\le n^{-2}.
\end{align}
</math>

The same argument can be applied to negative <math>b_i</math>'s, so that the probability that <math>c_i>2\sqrt{2m\ln n}</math> is at most <math>n^{-2}</math>. Therefore, by the union bound,
:<math>\Pr[|c_i|> 2\sqrt{2m\ln n}]\le\frac{2}{n^2}</math>.
Apply the union bound to all <math>n</math> rows.
:<math>\Pr[\|Ab\|_\infty>2\sqrt{2m\ln n}]\le n\cdot\Pr[|c_i|> 2\sqrt{2m\ln n}]\le\frac{2}{n}</math>.
<math>\square</math>

So how good is this randomized algorithm? In fact when <math>m=n</math> there exists a matrix <math>A</math> such that <math>\|Ab\|_\infty=\Omega(\sqrt{n})</math> for any choice of <math>b\in\{-1,+1\}^n</math>.

Randomized Algorithms (Spring 2010)/Tail inequalities

2010-02-23T06:40:38Z

172.21.1.247: /* The Chernoff bound */

== Select the Median ==

The [http://en.wikipedia.org/wiki/Selection_algorithm selection problem] is the problem of finding the <math>k</math>th smallest element in a set <math>S</math>. A typical case of selection problem is finding the '''median'''.

{|border="1"
|'''Definition'''
:The median of a set <math>S</math> is the <math>(\lceil n/2\rceil)</math>th element in the sorted order of <math>S</math>.
|}

The median can be found in <math>O(n\log n)</math> time by sorting. There is a linear-time deterministic algorithm, [http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22 "median of medians" algorithm], which is quite sophisticated. Here we introduce a much simpler randomized algorithm which also runs in linear time.

=== Randomized median algorithm ===
The idea of this algorithm is random sampling. For a set <math>S</math>, let <math>m\in S</math> denote the median. We observe that if we can find two elements <math>d,u\in S</math> satisfying the following properties:
# The median is between <math>d</math> and <math>u</math> in the sorted order, i.e. <math>d\le m\le u</math>;
# The total number of elements between <math>d</math> and <math>u</math> is small, specially for <math>C=\{x\in S\mid d\le x\le u\}</math>, <math>|C|=o(n/\log n)</math>.

Provided <math>d</math> and <math>u</math> with these two properties, within linear time, we can compute the ranks of <math>d</math> in <math>S</math>, construct <math>C</math>, and sort <math>C</math>. Therefore, the median <math>m</math> of <math>S</math> can be picked from <math>C</math> in linear time.

So how can we select such elements <math>d</math> and <math>u</math> from <math>S</math>? Certainly sorting <math>S</math> would give us the elements, but isn't that exactly what we want to avoid in the first place?

Observe that <math>d</math> and <math>u</math> are only asked to roughly satisfy some constraints. This hints us maybe we can construct a ''sketch'' of <math>S</math> which is small enough to sort cheaply and roughly represents <math>S</math>, and then pick <math>d</math> and <math>u</math> from this sketch. We construct the sketch by randomly sampling a relatively small number of elements from <math>S</math>. Then the strategy of algorithm is outlined by:
* Sample a set <math>R</math> of elements from <math>S</math>.
* Sort <math>R</math> and choose <math>d</math> and <math>u</math> somewhere around the median of <math>R</math>.
* If <math>d</math> and <math>u</math> have the desirable properties, we can compute the median in linear time, or otherwise the algorithm fails.

The parameters to be fixed are: the size of <math>R</math> (small enough to sort in linear time and large enough to contain sufficient information of <math>S</math>); and the order of <math>d</math> and <math>u</math> in <math>R</math> (not too close to have <math>m</math> between them, and not too far away to have <math>C</math> sortable in linear time).

We choose the size of <math>R</math> as <math>n^{3/4}</math>, and <math>d</math> and <math>u</math> are within <math>\sqrt{n}</math> range around the median of <math>R</math>.

{|border="1"
|'''Randomized Median Algorithm:'''
|-
|'''Input:''' a set <math>S</math> of <math>n</math> elements over totally ordered domain.
# Pick a multi-set <math>R</math> of <math>\left\lceil n^{3/4}\right\rceil</math> elements in <math>S</math>, chosen independently and uniformly at random with replacement, and sort <math>R</math>.
# Let <math>d</math> be the <math>\left\lfloor\frac{1}{2}n^{3/4}-\sqrt{n}\right\rfloor</math>-th smallest element in <math>R</math>, and let <math>u</math> be the <math>\left\lceil\frac{1}{2}n^{3/4}+\sqrt{n}\right\rceil</math>-th smallest element in <math>R</math>.
# Construct <math>C=\{x\in S\mid d\le x\le u\}</math> and compute the ranks <math>r_d=|\{x\in S\mid x<d\}|</math> and <math>r_u=|\{x\in S\mid x<u\}|</math>.
# If <math>r_d>\frac{n}{2}</math> or <math>r_u<\frac{n}{2}</math> or <math>|C|>4n^{3/4}</math> then return FAIL.
# Sort <math>C</math> and return the <math>\left(\left\lfloor\frac{n}{2}\right\rfloor-r_d+1\right)</math>th element in the sorted order of <math>C</math>.
|}

"Sample with replacement" (有放回采样) means that after sampling an element, we put the element back to the set. In this way, each sampled element is independently and identically distributed (''i.i.d'') (独立同分布). In the above algorithm, this is for our convenience of analysis.

=== Analysis ===
The algorithm always terminates in linear time because each line of the algorithm costs at most linear time. The last three line guarantees that the algorithm returns the correct median if it does not fail.

We then only need to bound the probability that the algorithm returns a FAIL. Let <math>m\in S</math> be the median of <math>S</math>. By Line 4, we know that the algorithm returns a FAIL if and only if at least one of the following events occurs:
* <math>\mathcal{E}_1: Y=|\{x\in R\mid x\le m\}|<\frac{1}{2}n^{3/4}-\sqrt{n}</math>;
* <math>\mathcal{E}_2: Z=|\{x\in R\mid x\ge m\}|<\frac{1}{2}n^{3/4}-\sqrt{n}</math>;
* <math>\mathcal{E}_3: |C|>4n^{3/4}</math>.

<math>\mathcal{E}_3</math> directly follows the third condition in Line 4. <math>\mathcal{E}_1</math> and <math>\mathcal{E}_2</math> are a bit tricky. The first condition in Line 4 is that <math>r_d>\frac{n}{2}</math>, which looks not exactly the same as <math>\mathcal{E}_1</math>, but both <math>\mathcal{E}_1</math> and that <math>r_d>\frac{n}{2}</math> are equivalent to the same event: the <math>\left\lfloor\frac{1}{2}n^{3/4}-\sqrt{n}\right\rfloor</math>-th smallest element in <math>R</math> is greater than <math>m</math>, thus they are actually equivalent. Similarly, <math>\mathcal{E}_2</math> is equivalent to the second condition of Line 4.

We now bound the probabilities of these events one by one.

{|border="1"
|'''Lemma 1'''
:<math>\Pr[\mathcal{E}_1]\le \frac{1}{4}n^{-1/4}</math>.
|}
'''Proof:''' Let <math>X_i</math> be the <math>i</math>th sampled element in Line 1 of the algorithm. Let <math>Y_i</math> be a indicator random variable such that
:<math>
Y_i=
\begin{cases}
1 & \mbox{if }X_i\le m,\\
0 & \mbox{otherwise.}
\end{cases}
</math>
It is obvious that <math>Y=\sum_{i=1}^{n^{3/4}}Y_i</math>, where <math>Y</math> is as defined in <math>\mathcal{E}_1</math>. For every <math>X_i</math>, there are <math>\left\lceil\frac{n}{2}\right\rceil</math> elements in <math>S</math> that are less than or equal to the median. The probability that <math>Y_i=1</math> is
:<math>
p=\Pr[Y_i=1]=\Pr[X_i\le m]=\frac{1}{n}\left\lceil\frac{n}{2}\right\rceil,
</math>
which is within the range of <math>\left[\frac{1}{2},\frac{1}{2}+\frac{1}{2n}\right]</math>. Thus
:<math>
\mathbf{E}[Y]=n^{3/4}p\ge \frac{1}{2}n^{3/4}.
</math>

The event <math>\mathcal{E}_1</math> is defined as that <math>Y<\frac{1}{2}n^{3/4}-\sqrt{n}</math>.

Note that <math>Y_i</math>'s are Bernoulli trials, and <math>Y</math> is the sum of <math>n^{3/4}</math> Bernoulli trials, which follows binomial distribution with parameters <math>n^{3/4}</math> and <math>p</math>. Thus, the variance is
:<math>\mathbf{Var}[Y]=n^{3/4}p(1-p)\le \frac{1}{4}n^{3/4}.
</math>

Applying Chebyshev's inequality,
:<math>
\begin{align}
\Pr[\mathcal{E}_1]
&=
\Pr\left[Y<\frac{1}{2}n^{3/4}-\sqrt{n}\right]\\
&\le
\Pr\left[|Y-\mathbf{E}[Y]|>\sqrt{n}\right]\\
&\le
\frac{\mathbf{Var}[Y]}{n}\\
&\le\frac{1}{4}n^{-1/4}.
\end{align}
</math>

<math>\square</math>

By a similar analysis, we can obtain the following bound for the event <math>\mathcal{E}_2</math>.

{|border="1"
|'''Lemma 2'''
:<math>\Pr[\mathcal{E}_2]\le \frac{1}{4}n^{-1/4}</math>.
|}

We now bound the probability of the event <math>\mathcal{E}_3</math>.

{|border="1"
|'''Lemma 3'''
:<math>\Pr[\mathcal{E}_3]\le \frac{1}{2}n^{-1/4}</math>.
|}
'''Proof:''' The event <math>\mathcal{E}_3</math> is defined as that <math>|C|>4 n^{3/4}</math>, which by the Pigeonhole Principle, implies that at leas one of the following must be true:
* <math>\mathcal{E}_3'</math>: at least <math>2n^{3/4}</math> elements of <math>C</math> is greater than <math>m</math>;
* <math>\mathcal{E}_3''</math>: at least <math>2n^{3/4}</math> elements of <math>C</math> is smaller than <math>m</math>.

We bound the probability that <math>\mathcal{E}_3'</math> occurs; the second will have the same bound by symmetry.

Recall that <math>C</math> is the region in <math>S</math> between <math>d</math> and <math>u</math>. If there are at least <math>2n^{3/4}</math> elements of <math>C</math> greater than the median <math>m</math> of <math>S</math>, then the rank of <math>u</math> in the sorted order of <math>S</math> must be at least <math>\frac{1}{2}n+2n^{3/4}</math> and thus <math>R</math> has at least <math>\frac{1}{2}n^{3/4}-\sqrt{n}</math> samples among the <math>\frac{1}{2}n-2n^{3/4}</math> largest elements in <math>S</math>.

Let <math>X_i\in\{0,1\}</math> indicate whether the <math>i</math>th sample is among the <math>\frac{1}{2}n-2n^{3/4}</math> largest elements in <math>S</math>. Let <math>X=\sum_{i=1}^{n^{3/4}}X_i</math> be the number of samples in <math>R</math> among the <math>\frac{1}{2}n-2n^{3/4}</math> largest elements in <math>S</math>.
It holds that
:<math>p=\Pr[X_i=1]=\frac{\frac{1}{2}n-2n^{3/4}}{n}=\frac{1}{2}-2n^{-1/4}</math>.

<math>X</math> is a binomial random variable with
:<math>
\mathbf{E}[X]=n^{3/4}p=\frac{1}{2}n^{3/4}-2\sqrt{n},
</math>
and
:<math>
\mathbf{Var}[X]=n^{3/4}p(1-p)=\frac{1}{4}n^{3/4}-4n^{1/4}<\frac{1}{4}n^{3/4}.
</math>
Applying Chebyshev's inequality,
:<math>
\begin{align}
\Pr[\mathcal{E}_3']
&=
\Pr\left[X\ge\frac{1}{2}n^{3/4}-\sqrt{n}\right]\\
&\le
\Pr\left[|X-\mathbf{E}[X]|\ge\sqrt{n}\right]\\
&\le
\frac{\mathbf{Var}[X]}{n}\\
&\le\frac{1}{4}n^{-1/4}.
\end{align}
</math>

Symmetrically, we have that <math>\Pr[\mathcal{E}_3'']\le\frac{1}{4}n^{-1/4}</math>.

Applying the union bound
:<math>\Pr[\mathcal{E}_3]\le \Pr[\mathcal{E}_3']+\Pr[\mathcal{E}_3'']\le\frac{1}{2}n^{-1/4}.
</math>
<math>\square</math>

Combining the three bounds. Applying the union bound to them, the probability that the algorithm returns a FAIL is at most
:<math>
\Pr[\mathcal{E}_1]+\Pr[\mathcal{E}_2]+\Pr[\mathcal{E}_3]\le n^{-1/4}.
</math>

Therefore the algorithm always terminates in linear time and returns the correct median with high probability.

== Chernoff Bound ==
Suppose that we have a fair coin. If we toss it once, then the outcome is completely unpredictable. But if we toss it, say for 1000 times, then the number of HEADs is very likely to be around 500. This striking phenomenon is called the '''concentration'''. The Chernoff bound captures the concentration of independent trials.

The Chernoff bound is also a tail bound for the sum of independent random variables which may give us ''exponentially'' sharp bounds.

Before proving the Chernoff bound, we should talk about the moment generating functions.

=== Moment generating functions ===
The more we know about the moments of a random variable <math>X</math>, the more information we would have about <math>X</math>. There is a so-called '''moment generating function''', which "packs" all the information about the moments of <math>X</math> into one function.

{|border="1"
|'''Definition:'''
:The moment generating function of a random variable <math>X</math> is defined as <math>\mathbf{E}\left[\mathrm{e}^{\lambda X}\right]</math> where <math>\lambda</math> is the parameter of the function.
|}

By Taylor's expansion and the linearity of expectations,
:<math>\begin{align}
\mathbf{E}\left[\mathrm{e}^{\lambda X}\right]
&=
\mathbf{E}\left[\sum_{k=0}^\infty\frac{\lambda^k}{k!}X^k\right]\\
&=\sum_{k=0}^\infty\frac{\lambda^k}{k!}\mathbf{E}\left[X^k\right]
\end{align}</math>

The moment generating function <math>\mathbf{E}\left[\mathrm{e}^{\lambda X}\right]</math> is a function of <math>\lambda</math>.

=== The Chernoff bound ===
The Chernoff bounds are tail inequalities with exponential decays for the sum of independent trials.
The bounds are obtained by applying Markov's inequality to the moment generating function of the sum of independent trials, with some appropriate choice of the parameter <math>\lambda</math>.
{|border="1"
|'''Chernoff bound (the upper tail):'''
:Let <math>X=\sum_{i=1}^n X_i</math>, where <math>X_1, X_2, \ldots, X_n</math> are independent Poisson trials. Let <math>\mu=\mathbf{E}[X]</math>.
:Then for any <math>\delta>0</math>,
::<math>\Pr[X\ge (1+\delta)\mu]\le\left(\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\right)^{\mu}.</math>
|}
'''Proof:''' For any <math>\lambda>0</math>, <math>X\ge (1+\delta)\mu</math> is equivalent to that <math>e^{\lambda X}\ge e^{\lambda (1+\delta)\mu}</math>, thus
:<math>\begin{align}
\Pr[X\ge (1+\delta)\mu]
&=
\Pr\left[e^{\lambda X}\ge e^{\lambda (1+\delta)\mu}\right]\\
&\le
\frac{\mathbf{E}\left[e^{\lambda X}\right]}{e^{\lambda (1+\delta)\mu}},
\end{align}</math>
where the last step follows by Markov's inequality.

Computing the moment generating function <math>\mathbf{E}[e^{\lambda X}]</math>:
:<math>\begin{align}
\mathbf{E}\left[e^{\lambda X}\right]
&=
\mathbf{E}\left[e^{\lambda \sum_{i=1}^n X_i}\right]\\
&=
\mathbf{E}\left[\prod_{i=1}^n e^{\lambda X_i}\right]\\
&=
\prod_{i=1}^n \mathbf{E}\left[e^{\lambda X_i}\right]. &(X_i\mbox{'s are independent})
\end{align}</math>

Let <math>p_i=\Pr[X_i=1]</math> for <math>i=1,2,\ldots,n</math>. Then,
:<math>\mu=\mathbf{E}[X]=\mathbf{E}\left[\sum_{i=1}^n X_i\right]=\sum_{i=1}^n\mathbf{E}[X_i]=\sum_{i=1}^n p_i</math>.

We bound the moment generating function for each individual <math>X_i</math> as follows.
:<math>\begin{align}
\mathbf{E}\left[e^{\lambda X_i}\right]
&=
p_i\cdot e^{\lambda\cdot 1}+(1-p_i)\cdot e^{\lambda\cdot 0}\\
&=
1+p_i(e^\lambda -1)\\
&\le
e^{p_i(e^\lambda-1)},
\end{align}</math>
where in the last step we apply the Taylor's expansion so that <math>e^y\ge 1+y</math> where <math>y=p_i(e^\lambda-1)\ge 0</math>. (By doing this, we can transform the product to the sum of <math>p_i</math>, which is <math>\mu</math>.)

Therefore,
:<math>\begin{align}
\mathbf{E}\left[e^{\lambda X}\right]
&=
\prod_{i=1}^n \mathbf{E}\left[e^{\lambda X_i}\right]\\
&\le
\prod_{i=1}^n e^{p_i(e^\lambda-1)}\\
&=
\exp\left(\sum_{i=1}^n p_i(e^{\lambda}-1)\right)\\
&=
e^{(e^\lambda-1)\mu}.
\end{align}</math>
Thus, we have shown that for any <math>\lambda>0</math>,
:<math>\begin{align}
\Pr[X\ge (1+\delta)\mu]
&\le
\frac{\mathbf{E}\left[e^{\lambda X}\right]}{e^{\lambda (1+\delta)\mu}}\\
&\le
\frac{e^{(e^\lambda-1)\mu}}{e^{\lambda (1+\delta)\mu}}\\
&=
\left(\frac{e^{(e^\lambda-1)}}{e^{\lambda (1+\delta)}}\right)^\mu
\end{align}</math>.
For any <math>\delta>0</math>, we can let <math>\lambda=\ln(1+\delta)>0</math> to get
:<math>\Pr[X\ge (1+\delta)\mu]\le\left(\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\right)^{\mu}.</math>

<math>\square</math>

The idea of the proof is actually quite clear: we apply Markov's inequality to <math>e^{\lambda X}</math> and for the rest, we just estimate the moment generating function <math>\mathbf{E}[e^{\lambda X}]</math>. To make the bound as tight as possible, we minimized the <math>\frac{e^{(e^\lambda-1)}}{e^{\lambda (1+\delta)}}</math> by setting <math>\lambda=\ln(1+\delta)</math>, which can be justified by taking derivatives of <math>\frac{e^{(e^\lambda-1)}}{e^{\lambda (1+\delta)}}</math>.

----

We then proceed to the lower tail, the probability that the random variable deviates below the mean value:

{|border="1"
|'''Chernoff bound (the lower tail):'''
:Let <math>X=\sum_{i=1}^n X_i</math>, where <math>X_1, X_2, \ldots, X_n</math> are independent Poisson trials. Let <math>\mu=\mathbf{E}[X]</math>.
:Then for any <math>0<\delta<1</math>,
::<math>\Pr[X\le (1-\delta)\mu]\le\left(\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}\right)^{\mu}.</math>
|}
'''Proof:''' For any <math>\lambda<0</math>, by the same analysis as in the upper tail version,
:<math>\begin{align}
\Pr[X\le (1-\delta)\mu]
&=
\Pr\left[e^{\lambda X}\ge e^{\lambda (1-\delta)\mu}\right]\\
&\le
\frac{\mathbf{E}\left[e^{\lambda X}\right]}{e^{\lambda (1-\delta)\mu}}\\
&\le
\left(\frac{e^{(e^\lambda-1)}}{e^{\lambda (1-\delta)}}\right)^\mu.
\end{align}</math>
For any <math>0<\delta<1</math>, we can let <math>\lambda=\ln(1-\delta)<0</math> to get
:<math>\Pr[X\ge (1-\delta)\mu]\le\left(\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}\right)^{\mu}.</math>

<math>\square</math>

----

Some useful special forms of the bounds can be derived directly from the above general forms of the bounds. We now know better why we say that the bounds are exponentially sharp.

{|border="1"
|'''Useful forms of the Chernoff bound'''
:Let <math>X=\sum_{i=1}^n X_i</math>, where <math>X_1, X_2, \ldots, X_n</math> are independent Poisson trials. Let <math>\mu=\mathbf{E}[X]</math>. Then
:1. for <math>0<\delta\le 1</math>,
::<math>\Pr[X\ge (1+\delta)\mu]<\exp\left(-\frac{\mu\delta^2}{3}\right);</math>
::<math>\Pr[X\le (1-\delta)\mu]<\exp\left(-\frac{\mu\delta^2}{2}\right);</math>
:2. for <math>t\ge 2e\mu</math>,
::<math>\Pr[X\ge t]\le 2^{-t}.</math>
|}
'''Proof:''' To obtain the bounds in (1), we need to show that for <math>0<\delta< 1</math>, <math>\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\le e^{-\delta^2/3}</math> and <math>\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}\le e^{-\delta^2/2}</math>. We can verify both inequalities by standard analysis techniques.

To obtain the bound in (2), let <math>t=(1+\delta)\mu</math>. Then <math>\delta=t/\mu-1\ge 2e-1</math>. Hence,
:<math>\begin{align}
\Pr[X\ge(1+\delta)\mu]
&\le
\left(\frac{e^\delta}{(1+\delta)^{(1+\delta)}}\right)^\mu\\
&\le
\left(\frac{e}{1+\delta}\right)^{(1+\delta)\mu}\\
&\le
\left(\frac{e}{2e}\right)^{2e\mu}\\
&\le
2^{-t}
\end{align}</math>

<math>\square</math>

== Applications of Chernoff Bounds ==
We now introduce some applications of Chernoff bounds in randomized algorithms.

=== Balls into bins ===
Throwing <math>m</math> balls uniformly and independently to <math>n</math> bins, what is the maximum load of all bins? In the last class, by using a counting argument, we proved that for the case that <math>m=n</math>, the maximum load is <math>O(\ln n\ln\ln n)</math> with high probability. Now we show that when there are more balls, the loads are more balanced.

For any <math>i\in[n]</math> and <math>j\in[m]</math>, let <math>X_{ij}</math> be the indicator variable for the event that ball <math>j</math> is thrown to bin <math>i</math>. Obviously
:<math>\mathbf{E}[X_{ij}]=\Pr[\mbox{ball }j\mbox{ is thrown to bin }i]=\frac{1}{n}</math>
Let <math>Y_i=\sum_{j\in[m]}X_{ij}</math> be the load of bin <math>i</math>.

Let us consider the case when <math>m=6n\ln n</math>. Then the expected load of bin <math>i</math> is
:<math>\mu=\mathbf{E}[Y_i]=\mathbf{E}\left[\sum_{j\in[m]}X_{ij}\right]=\sum_{j\in[m]}\mathbf{E}[X_{ij}]=m/n=6\ln n</math>.
Note that <math>Y_i</math> is a sum of <math>m</math> mutually independent indicator variable. Applying Chernoff bound, for any particular bin <math>i\in[n]</math>,
:<math>
\Pr[Y_i>12\ln n] =\Pr[Y_i>(1+1)\mu]\le e^{-\frac{\mu}{3}} = e^{-2\ln n}= \frac{1}{n^2}.
</math>
Applying the union bound, the probability that there exists a bin with load <math>>12\ln n</math> is
:<math>n\cdot \Pr[Y_1>12\ln n]\le \frac{1}{n}</math>.
Therefore, with probability at least <math>1-\frac{1}{n}</math>, the maximum load is within <math>12\ln n=O(m/n)</math>.

=== Set balancing ===
Supposed that we have an <math>n\times m</math> matrix <math>A</math> with 0-1 entries. We are looking for a <math>b\in\{-1,+1\}^m</math> that minimizes <math>\|Ab\|_\infty</math>.

Recall that <math>\|\cdot\|_\infty</math> is the infinity norm (also called <math>L_\infty</math> norm) of a vector, and for the vector <math>c=Ab</math>,
:<math>\|Ab\|_\infty=\max_{i=1,2,\ldots,n}|c_i|</math>.

We can also describe this problem as an optimization:
:<math>\begin{align}
\mbox{minimize }
&\quad
\|Ab\|_\infty\\
\mbox{subject to: }
&\quad
b\in\{-1,+1\}^m.
\end{align}</math>

{|border="1"
|The problem arises in designing statistical experiments. Suppose that we have <math>m</math> '''subjects''', each of which may have up to <math>n</math> '''features'''. This gives us an <math>n\times m</math> matrix <math>A</math>:
:<math>
\begin{array}{c}
\mbox{feature 1:}\\
\mbox{feature 2:}\\
\vdots\\
\mbox{feature n:}\\
\end{array}
\left[
\begin{array}{cccc}
a_{11} & a_{12} & \cdots & a_{1m}\\
a_{21} & a_{22} & \cdots & a_{2m}\\
\vdots & \vdots & \ddots & \vdots\\
a_{n1} & a_{n2} & \cdots & a_{nm}\\
\end{array}
\right],
</math>
where each column represents a subject and each row represent a feature. An entry <math>a_{ij}\in\{0,1\}</math> indicates whether subject <math>j</math> has feature <math>i</math>.

By multiplying a vector <math>b\in\{-1,+1\}^m</math>
:<math>
\left[
\begin{array}{cccc}
a_{11} & a_{12} & \cdots & a_{1m}\\
a_{21} & a_{22} & \cdots & a_{2m}\\
\vdots & \vdots & \ddots & \vdots\\
a_{n1} & a_{n2} & \cdots & a_{nm}\\
\end{array}
\right]
\left[
\begin{array}{c}
b_{1}\\
b_{2}\\
\vdots\\
b_{m}\\
\end{array}
\right]
=
\left[
\begin{array}{c}
c_{1}\\
c_{2}\\
\vdots\\
c_{n}\\
\end{array}
\right],
</math>
the subjects are partitioned into two disjoint groups: one for -1 and other other for +1. Each <math>c_i</math> gives the difference between the numbers of subjects with feature <math>i</math> in the two groups. By minimizing <math>\|Ab\|_\infty=\|c\|_\infty</math>, we ask for an optimal partition so that each feature is roughly as balanced as possible between the two groups.

In a scientific experiment, one of the group serves as a [http://en.wikipedia.org/wiki/Scientific_control control group] (对照组). Ideally, we want the two groups are statistically identical, which is usually impossible to achieve in practice. The requirement of minimizing <math>\|Ab\|_\infty</math> actually means the statistical difference between the two groups are minimized.
|}

We propose an extremely simple "randomized algorithm" for computing a <math>b\in\{-1,+1\}^m</math>: for each <math>i=1,2,\ldots, m</math>, let <math>b_i</math> be independently chosen from <math>\{-1,+1\}</math>, such that
:<math>b_i=
\begin{cases}
-1 & \mbox{with probability }\frac{1}{2}\\
+1 &\mbox{with probability }\frac{1}{2}
\end{cases}.
</math>

This procedure can hardly be called as an "algorithm", because its decision is made disregard of the input <math>A</math>. We then show that despite of this obliviousness, the algorithm chooses a good enough <math>b</math>, such that for any <math>A</math>, <math>\|Ab\|_\infty=O(\sqrt{m\ln n})</math> with high probability.
{|border="1"
|'''Theorem'''
:Let <math>A</math> be an <math>n\times m</math> matrix with 0-1 entries. For a random vector <math>b</math> with <math>m</math> entries chosen independently and with equal probability from <math>\{-1,+1\}</math>,
::<math>\Pr[\|Ab\|_\infty>2\sqrt{2m\ln n}]\le\frac{2}{n}</math>.
|}
'''Proof:'''
Consider particularly the <math>i</math>-th row of <math>A</math>. The entry of <math>Ab</math> contributed by row <math>i</math> is <math>c_i=\sum_{j=1}^m a_{ij}b_j</math>.

Let <math>k</math> be the non-zero entries in the row. If <math>k\le2\sqrt{2m\ln n}</math>, then clearly <math>|c_i|</math> is no greater than <math>2\sqrt{2m\ln n}</math>. On the other hand if <math>k>2\sqrt{2m\ln n}</math> then the <math>k</math> nonzero terms in the sum
:<math>c_i=\sum_{j=1}^m a_{ij}b_j</math>
are independent, each with probability 1/2 of being either +1 or -1.

Thus, for these <math>k</math> nonzero terms, each <math>b_i</math> is either positive or negative independently with equal probability. There are expectedly <math>\mu=\frac{k}{2}</math> positive <math>b_i</math>'s among these <math>k</math> terms, and <math>c_i<-2\sqrt{2m\ln n}</math> only occurs when there are less than <math>\frac{k}{2}-\sqrt{2m\ln n}=\left(1-\delta\right)\mu</math> positive <math>b_i</math>'s, where <math>\delta=\frac{2\sqrt{2m\ln n}}{k}</math>. Applying Chernoff bound, this event occurs with probability at most
:<math>\begin{align}
\exp\left(-\frac{\mu\delta^2}{2}\right)
&=
\exp\left(-\frac{k}{2}\cdot\frac{8m\ln n}{2k^2}\right)\\
&=
\exp\left(-\frac{2m\ln n}{k}\right)\\
&\le
\exp\left(-\frac{2m\ln n}{m}\right)\\
&\le n^{-2}.
\end{align}
</math>

The same argument can be applied to negative <math>b_i</math>'s, so that the probability that <math>c_i>2\sqrt{2m\ln n}</math> is at most <math>n^{-2}</math>. Therefore, by the union bound,
:<math>\Pr[|c_i|> 2\sqrt{2m\ln n}]\le\frac{2}{n^2}</math>.
Apply the union bound to all <math>n</math> rows.
:<math>\Pr[\|Ab\|_\infty>2\sqrt{2m\ln n}]\le n\cdot\Pr[|c_i|> 2\sqrt{2m\ln n}]\le\frac{2}{n}</math>.
<math>\square</math>

So how good is this randomized algorithm? In fact when <math>m=n</math> there exists a matrix <math>A</math> such that <math>\|Ab\|_\infty=\Omega(\sqrt{n})</math> for any choice of <math>b\in\{-1,+1\}^n</math>.

Randomized Algorithms (Spring 2010)/Tail inequalities

2010-02-23T06:37:53Z

172.21.1.247: /* The Chernoff bound */

== Select the Median ==

The [http://en.wikipedia.org/wiki/Selection_algorithm selection problem] is the problem of finding the <math>k</math>th smallest element in a set <math>S</math>. A typical case of selection problem is finding the '''median'''.

{|border="1"
|'''Definition'''
:The median of a set <math>S</math> is the <math>(\lceil n/2\rceil)</math>th element in the sorted order of <math>S</math>.
|}

The median can be found in <math>O(n\log n)</math> time by sorting. There is a linear-time deterministic algorithm, [http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22 "median of medians" algorithm], which is quite sophisticated. Here we introduce a much simpler randomized algorithm which also runs in linear time.

=== Randomized median algorithm ===
The idea of this algorithm is random sampling. For a set <math>S</math>, let <math>m\in S</math> denote the median. We observe that if we can find two elements <math>d,u\in S</math> satisfying the following properties:
# The median is between <math>d</math> and <math>u</math> in the sorted order, i.e. <math>d\le m\le u</math>;
# The total number of elements between <math>d</math> and <math>u</math> is small, specially for <math>C=\{x\in S\mid d\le x\le u\}</math>, <math>|C|=o(n/\log n)</math>.

Provided <math>d</math> and <math>u</math> with these two properties, within linear time, we can compute the ranks of <math>d</math> in <math>S</math>, construct <math>C</math>, and sort <math>C</math>. Therefore, the median <math>m</math> of <math>S</math> can be picked from <math>C</math> in linear time.

So how can we select such elements <math>d</math> and <math>u</math> from <math>S</math>? Certainly sorting <math>S</math> would give us the elements, but isn't that exactly what we want to avoid in the first place?

Observe that <math>d</math> and <math>u</math> are only asked to roughly satisfy some constraints. This hints us maybe we can construct a ''sketch'' of <math>S</math> which is small enough to sort cheaply and roughly represents <math>S</math>, and then pick <math>d</math> and <math>u</math> from this sketch. We construct the sketch by randomly sampling a relatively small number of elements from <math>S</math>. Then the strategy of algorithm is outlined by:
* Sample a set <math>R</math> of elements from <math>S</math>.
* Sort <math>R</math> and choose <math>d</math> and <math>u</math> somewhere around the median of <math>R</math>.
* If <math>d</math> and <math>u</math> have the desirable properties, we can compute the median in linear time, or otherwise the algorithm fails.

The parameters to be fixed are: the size of <math>R</math> (small enough to sort in linear time and large enough to contain sufficient information of <math>S</math>); and the order of <math>d</math> and <math>u</math> in <math>R</math> (not too close to have <math>m</math> between them, and not too far away to have <math>C</math> sortable in linear time).

We choose the size of <math>R</math> as <math>n^{3/4}</math>, and <math>d</math> and <math>u</math> are within <math>\sqrt{n}</math> range around the median of <math>R</math>.

{|border="1"
|'''Randomized Median Algorithm:'''
|-
|'''Input:''' a set <math>S</math> of <math>n</math> elements over totally ordered domain.
# Pick a multi-set <math>R</math> of <math>\left\lceil n^{3/4}\right\rceil</math> elements in <math>S</math>, chosen independently and uniformly at random with replacement, and sort <math>R</math>.
# Let <math>d</math> be the <math>\left\lfloor\frac{1}{2}n^{3/4}-\sqrt{n}\right\rfloor</math>-th smallest element in <math>R</math>, and let <math>u</math> be the <math>\left\lceil\frac{1}{2}n^{3/4}+\sqrt{n}\right\rceil</math>-th smallest element in <math>R</math>.
# Construct <math>C=\{x\in S\mid d\le x\le u\}</math> and compute the ranks <math>r_d=|\{x\in S\mid x<d\}|</math> and <math>r_u=|\{x\in S\mid x<u\}|</math>.
# If <math>r_d>\frac{n}{2}</math> or <math>r_u<\frac{n}{2}</math> or <math>|C|>4n^{3/4}</math> then return FAIL.
# Sort <math>C</math> and return the <math>\left(\left\lfloor\frac{n}{2}\right\rfloor-r_d+1\right)</math>th element in the sorted order of <math>C</math>.
|}

"Sample with replacement" (有放回采样) means that after sampling an element, we put the element back to the set. In this way, each sampled element is independently and identically distributed (''i.i.d'') (独立同分布). In the above algorithm, this is for our convenience of analysis.

=== Analysis ===
The algorithm always terminates in linear time because each line of the algorithm costs at most linear time. The last three line guarantees that the algorithm returns the correct median if it does not fail.

We then only need to bound the probability that the algorithm returns a FAIL. Let <math>m\in S</math> be the median of <math>S</math>. By Line 4, we know that the algorithm returns a FAIL if and only if at least one of the following events occurs:
* <math>\mathcal{E}_1: Y=|\{x\in R\mid x\le m\}|<\frac{1}{2}n^{3/4}-\sqrt{n}</math>;
* <math>\mathcal{E}_2: Z=|\{x\in R\mid x\ge m\}|<\frac{1}{2}n^{3/4}-\sqrt{n}</math>;
* <math>\mathcal{E}_3: |C|>4n^{3/4}</math>.

<math>\mathcal{E}_3</math> directly follows the third condition in Line 4. <math>\mathcal{E}_1</math> and <math>\mathcal{E}_2</math> are a bit tricky. The first condition in Line 4 is that <math>r_d>\frac{n}{2}</math>, which looks not exactly the same as <math>\mathcal{E}_1</math>, but both <math>\mathcal{E}_1</math> and that <math>r_d>\frac{n}{2}</math> are equivalent to the same event: the <math>\left\lfloor\frac{1}{2}n^{3/4}-\sqrt{n}\right\rfloor</math>-th smallest element in <math>R</math> is greater than <math>m</math>, thus they are actually equivalent. Similarly, <math>\mathcal{E}_2</math> is equivalent to the second condition of Line 4.

We now bound the probabilities of these events one by one.

{|border="1"
|'''Lemma 1'''
:<math>\Pr[\mathcal{E}_1]\le \frac{1}{4}n^{-1/4}</math>.
|}
'''Proof:''' Let <math>X_i</math> be the <math>i</math>th sampled element in Line 1 of the algorithm. Let <math>Y_i</math> be a indicator random variable such that
:<math>
Y_i=
\begin{cases}
1 & \mbox{if }X_i\le m,\\
0 & \mbox{otherwise.}
\end{cases}
</math>
It is obvious that <math>Y=\sum_{i=1}^{n^{3/4}}Y_i</math>, where <math>Y</math> is as defined in <math>\mathcal{E}_1</math>. For every <math>X_i</math>, there are <math>\left\lceil\frac{n}{2}\right\rceil</math> elements in <math>S</math> that are less than or equal to the median. The probability that <math>Y_i=1</math> is
:<math>
p=\Pr[Y_i=1]=\Pr[X_i\le m]=\frac{1}{n}\left\lceil\frac{n}{2}\right\rceil,
</math>
which is within the range of <math>\left[\frac{1}{2},\frac{1}{2}+\frac{1}{2n}\right]</math>. Thus
:<math>
\mathbf{E}[Y]=n^{3/4}p\ge \frac{1}{2}n^{3/4}.
</math>

The event <math>\mathcal{E}_1</math> is defined as that <math>Y<\frac{1}{2}n^{3/4}-\sqrt{n}</math>.

Note that <math>Y_i</math>'s are Bernoulli trials, and <math>Y</math> is the sum of <math>n^{3/4}</math> Bernoulli trials, which follows binomial distribution with parameters <math>n^{3/4}</math> and <math>p</math>. Thus, the variance is
:<math>\mathbf{Var}[Y]=n^{3/4}p(1-p)\le \frac{1}{4}n^{3/4}.
</math>

Applying Chebyshev's inequality,
:<math>
\begin{align}
\Pr[\mathcal{E}_1]
&=
\Pr\left[Y<\frac{1}{2}n^{3/4}-\sqrt{n}\right]\\
&\le
\Pr\left[|Y-\mathbf{E}[Y]|>\sqrt{n}\right]\\
&\le
\frac{\mathbf{Var}[Y]}{n}\\
&\le\frac{1}{4}n^{-1/4}.
\end{align}
</math>

<math>\square</math>

By a similar analysis, we can obtain the following bound for the event <math>\mathcal{E}_2</math>.

{|border="1"
|'''Lemma 2'''
:<math>\Pr[\mathcal{E}_2]\le \frac{1}{4}n^{-1/4}</math>.
|}

We now bound the probability of the event <math>\mathcal{E}_3</math>.

{|border="1"
|'''Lemma 3'''
:<math>\Pr[\mathcal{E}_3]\le \frac{1}{2}n^{-1/4}</math>.
|}
'''Proof:''' The event <math>\mathcal{E}_3</math> is defined as that <math>|C|>4 n^{3/4}</math>, which by the Pigeonhole Principle, implies that at leas one of the following must be true:
* <math>\mathcal{E}_3'</math>: at least <math>2n^{3/4}</math> elements of <math>C</math> is greater than <math>m</math>;
* <math>\mathcal{E}_3''</math>: at least <math>2n^{3/4}</math> elements of <math>C</math> is smaller than <math>m</math>.

We bound the probability that <math>\mathcal{E}_3'</math> occurs; the second will have the same bound by symmetry.

Recall that <math>C</math> is the region in <math>S</math> between <math>d</math> and <math>u</math>. If there are at least <math>2n^{3/4}</math> elements of <math>C</math> greater than the median <math>m</math> of <math>S</math>, then the rank of <math>u</math> in the sorted order of <math>S</math> must be at least <math>\frac{1}{2}n+2n^{3/4}</math> and thus <math>R</math> has at least <math>\frac{1}{2}n^{3/4}-\sqrt{n}</math> samples among the <math>\frac{1}{2}n-2n^{3/4}</math> largest elements in <math>S</math>.

Let <math>X_i\in\{0,1\}</math> indicate whether the <math>i</math>th sample is among the <math>\frac{1}{2}n-2n^{3/4}</math> largest elements in <math>S</math>. Let <math>X=\sum_{i=1}^{n^{3/4}}X_i</math> be the number of samples in <math>R</math> among the <math>\frac{1}{2}n-2n^{3/4}</math> largest elements in <math>S</math>.
It holds that
:<math>p=\Pr[X_i=1]=\frac{\frac{1}{2}n-2n^{3/4}}{n}=\frac{1}{2}-2n^{-1/4}</math>.

<math>X</math> is a binomial random variable with
:<math>
\mathbf{E}[X]=n^{3/4}p=\frac{1}{2}n^{3/4}-2\sqrt{n},
</math>
and
:<math>
\mathbf{Var}[X]=n^{3/4}p(1-p)=\frac{1}{4}n^{3/4}-4n^{1/4}<\frac{1}{4}n^{3/4}.
</math>
Applying Chebyshev's inequality,
:<math>
\begin{align}
\Pr[\mathcal{E}_3']
&=
\Pr\left[X\ge\frac{1}{2}n^{3/4}-\sqrt{n}\right]\\
&\le
\Pr\left[|X-\mathbf{E}[X]|\ge\sqrt{n}\right]\\
&\le
\frac{\mathbf{Var}[X]}{n}\\
&\le\frac{1}{4}n^{-1/4}.
\end{align}
</math>

Symmetrically, we have that <math>\Pr[\mathcal{E}_3'']\le\frac{1}{4}n^{-1/4}</math>.

Applying the union bound
:<math>\Pr[\mathcal{E}_3]\le \Pr[\mathcal{E}_3']+\Pr[\mathcal{E}_3'']\le\frac{1}{2}n^{-1/4}.
</math>
<math>\square</math>

Combining the three bounds. Applying the union bound to them, the probability that the algorithm returns a FAIL is at most
:<math>
\Pr[\mathcal{E}_1]+\Pr[\mathcal{E}_2]+\Pr[\mathcal{E}_3]\le n^{-1/4}.
</math>

Therefore the algorithm always terminates in linear time and returns the correct median with high probability.

== Chernoff Bound ==
Suppose that we have a fair coin. If we toss it once, then the outcome is completely unpredictable. But if we toss it, say for 1000 times, then the number of HEADs is very likely to be around 500. This striking phenomenon is called the '''concentration'''. The Chernoff bound captures the concentration of independent trials.

The Chernoff bound is also a tail bound for the sum of independent random variables which may give us ''exponentially'' sharp bounds.

Before proving the Chernoff bound, we should talk about the moment generating functions.

=== Moment generating functions ===
The more we know about the moments of a random variable <math>X</math>, the more information we would have about <math>X</math>. There is a so-called '''moment generating function''', which "packs" all the information about the moments of <math>X</math> into one function.

{|border="1"
|'''Definition:'''
:The moment generating function of a random variable <math>X</math> is defined as <math>\mathbf{E}\left[\mathrm{e}^{\lambda X}\right]</math> where <math>\lambda</math> is the parameter of the function.
|}

By Taylor's expansion and the linearity of expectations,
:<math>\begin{align}
\mathbf{E}\left[\mathrm{e}^{\lambda X}\right]
&=
\mathbf{E}\left[\sum_{k=0}^\infty\frac{\lambda^k}{k!}X^k\right]\\
&=\sum_{k=0}^\infty\frac{\lambda^k}{k!}\mathbf{E}\left[X^k\right]
\end{align}</math>

The moment generating function <math>\mathbf{E}\left[\mathrm{e}^{\lambda X}\right]</math> is a function of <math>\lambda</math>.

=== The Chernoff bound ===
The Chernoff bounds are tail inequalities with exponential decays for the sum of independent trials.
The bounds are obtained by applying Markov's inequality to the moment generating function of the sum of independent trials, with some appropriate choice of the parameter <math>\lambda</math>.
{|border="1"
|'''Chernoff bound (the upper tail):'''
:Let <math>X=\sum_{i=1}^n X_i</math>, where <math>X_1, X_2, \ldots, X_n</math> are independent Poisson trials. Let <math>\mu=\mathbf{E}[X]</math>.
:Then for any <math>\delta>0</math>,
::<math>\Pr[X\ge (1+\delta)\mu]\le\left(\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\right)^{\mu}.</math>
|}
'''Proof:''' For any <math>\lambda>0</math>, <math>X\ge (1+\delta)\mu</math> is equivalent to that <math>e^{\lambda X}\ge e^{\lambda (1+\delta)\mu}</math>, thus
:<math>\begin{align}
\Pr[X\ge (1+\delta)\mu]
&=
\Pr\left[e^{\lambda X}\ge e^{\lambda (1+\delta)\mu}\right]\\
&\le
\frac{\mathbf{E}\left[e^{\lambda X}\right]}{e^{\lambda (1+\delta)\mu}},
\end{align}</math>
where the last step follows by Markov's inequality.

Computing the moment generating function <math>\mathbf{E}[e^{\lambda X}]</math>:
:<math>\begin{align}
\mathbf{E}\left[e^{\lambda X}\right]
&=
\mathbf{E}\left[e^{\lambda \sum_{i=1}^n X_i}\right]\\
&=
\mathbf{E}\left[\prod_{i=1}^n e^{\lambda X_i}\right].
\end{align}</math>
For independent random variables, the expectation of the product equals the product of the expectations, therefore, for the last term above, we have
:<math>\begin{align}
\mathbf{E}\left[\prod_{i=1}^n e^{\lambda X_i}\right]
&=
\prod_{i=1}^n \mathbf{E}\left[e^{\lambda X_i}\right].
\end{align}</math>

Let <math>p_i=\Pr[X_i=1]</math> for <math>i=1,2,\ldots,n</math>. Then,
:<math>\mu=\mathbf{E}[X]=\mathbf{E}\left[\sum_{i=1}^n X_i\right]=\sum_{i=1}^n\mathbf{E}[X_i]=\sum_{i=1}^n p_i</math>.

We bound the moment generating function for each individual <math>X_i</math> as follows.
:<math>\begin{align}
\mathbf{E}\left[e^{\lambda X_i}\right]
&=
p_i\cdot e^{\lambda\cdot 1}+(1-p_i)\cdot e^{\lambda\cdot 0}\\
&=
1+p_i(e^\lambda -1)\\
&\le
e^{p_i(e^\lambda-1)},
\end{align}</math>
where in the last step we apply the Taylor's expansion so that <math>e^y\ge 1+y</math> where <math>y=p_i(e^\lambda-1)\ge 0</math>. (By doing this, we can transform the product to the sum of <math>p_i</math>, which is <math>\mu</math>.)

Therefore,
:<math>\begin{align}
\mathbf{E}\left[e^{\lambda X}\right]
&=
\prod_{i=1}^n \mathbf{E}\left[e^{\lambda X_i}\right]\\
&\le
\prod_{i=1}^n e^{p_i(e^\lambda-1)}\\
&=
\exp\left(\sum_{i=1}^n p_i(e^{\lambda}-1)\right)\\
&=
e^{(e^\lambda-1)\mu}.
\end{align}</math>
Thus, we have shown that for any <math>\lambda>0</math>,
:<math>\begin{align}
\Pr[X\ge (1+\delta)\mu]
&\le
\frac{\mathbf{E}\left[e^{\lambda X}\right]}{e^{\lambda (1+\delta)\mu}}\\
&\le
\frac{e^{(e^\lambda-1)\mu}}{e^{\lambda (1+\delta)\mu}}\\
&=
\left(\frac{e^{(e^\lambda-1)}}{e^{\lambda (1+\delta)}}\right)^\mu
\end{align}</math>.
For any <math>\delta>0</math>, we can let <math>\lambda=\ln(1+\delta)>0</math> to get
:<math>\Pr[X\ge (1+\delta)\mu]\le\left(\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\right)^{\mu}.</math>

<math>\square</math>

The idea of the proof is actually quite clear: we apply Markov's inequality to <math>e^{\lambda X}</math> and for the rest, we just estimate the moment generating function <math>\mathbf{E}[e^{\lambda X}]</math>. To make the bound as tight as possible, we minimized the <math>\frac{e^{(e^\lambda-1)}}{e^{\lambda (1+\delta)}}</math> by setting <math>\lambda=\ln(1+\delta)</math>, which can be justified by taking derivatives of <math>\frac{e^{(e^\lambda-1)}}{e^{\lambda (1+\delta)}}</math>.

----

We then proceed to the lower tail, the probability that the random variable deviates below the mean value:

{|border="1"
|'''Chernoff bound (the lower tail):'''
:Let <math>X=\sum_{i=1}^n X_i</math>, where <math>X_1, X_2, \ldots, X_n</math> are independent Poisson trials. Let <math>\mu=\mathbf{E}[X]</math>.
:Then for any <math>0<\delta<1</math>,
::<math>\Pr[X\le (1-\delta)\mu]\le\left(\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}\right)^{\mu}.</math>
|}
'''Proof:''' For any <math>\lambda<0</math>, by the same analysis as in the upper tail version,
:<math>\begin{align}
\Pr[X\le (1-\delta)\mu]
&=
\Pr\left[e^{\lambda X}\ge e^{\lambda (1-\delta)\mu}\right]\\
&\le
\frac{\mathbf{E}\left[e^{\lambda X}\right]}{e^{\lambda (1-\delta)\mu}}\\
&\le
\left(\frac{e^{(e^\lambda-1)}}{e^{\lambda (1-\delta)}}\right)^\mu.
\end{align}</math>
For any <math>0<\delta<1</math>, we can let <math>\lambda=\ln(1-\delta)<0</math> to get
:<math>\Pr[X\ge (1-\delta)\mu]\le\left(\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}\right)^{\mu}.</math>

<math>\square</math>

----

Some useful special forms of the bounds can be derived directly from the above general forms of the bounds. We now know better why we say that the bounds are exponentially sharp.

{|border="1"
|'''Useful forms of the Chernoff bound'''
:Let <math>X=\sum_{i=1}^n X_i</math>, where <math>X_1, X_2, \ldots, X_n</math> are independent Poisson trials. Let <math>\mu=\mathbf{E}[X]</math>. Then
:1. for <math>0<\delta\le 1</math>,
::<math>\Pr[X\ge (1+\delta)\mu]<\exp\left(-\frac{\mu\delta^2}{3}\right);</math>
::<math>\Pr[X\le (1-\delta)\mu]<\exp\left(-\frac{\mu\delta^2}{2}\right);</math>
:2. for <math>t\ge 2e\mu</math>,
::<math>\Pr[X\ge t]\le 2^{-t}.</math>
|}
'''Proof:''' To obtain the bounds in (1), we need to show that for <math>0<\delta< 1</math>, <math>\frac{e^{\delta}}{(1+\delta)^{(1+\delta)}}\le e^{-\delta^2/3}</math> and <math>\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}\le e^{-\delta^2/2}</math>. We can verify both inequalities by standard analysis techniques.

To obtain the bound in (2), let <math>t=(1+\delta)\mu</math>. Then <math>\delta=t/\mu-1\ge 2e-1</math>. Hence,
:<math>\begin{align}
\Pr[X\ge(1+\delta)\mu]
&\le
\left(\frac{e^\delta}{(1+\delta)^{(1+\delta)}}\right)^\mu\\
&\le
\left(\frac{e}{1+\delta}\right)^{(1+\delta)\mu}\\
&\le
\left(\frac{e}{2e}\right)^{2e\mu}\\
&\le
2^{-t}
\end{align}</math>

<math>\square</math>

== Applications of Chernoff Bounds ==
We now introduce some applications of Chernoff bounds in randomized algorithms.

=== Balls into bins ===
Throwing <math>m</math> balls uniformly and independently to <math>n</math> bins, what is the maximum load of all bins? In the last class, by using a counting argument, we proved that for the case that <math>m=n</math>, the maximum load is <math>O(\ln n\ln\ln n)</math> with high probability. Now we show that when there are more balls, the loads are more balanced.

For any <math>i\in[n]</math> and <math>j\in[m]</math>, let <math>X_{ij}</math> be the indicator variable for the event that ball <math>j</math> is thrown to bin <math>i</math>. Obviously
:<math>\mathbf{E}[X_{ij}]=\Pr[\mbox{ball }j\mbox{ is thrown to bin }i]=\frac{1}{n}</math>
Let <math>Y_i=\sum_{j\in[m]}X_{ij}</math> be the load of bin <math>i</math>.

Let us consider the case when <math>m=6n\ln n</math>. Then the expected load of bin <math>i</math> is
:<math>\mu=\mathbf{E}[Y_i]=\mathbf{E}\left[\sum_{j\in[m]}X_{ij}\right]=\sum_{j\in[m]}\mathbf{E}[X_{ij}]=m/n=6\ln n</math>.
Note that <math>Y_i</math> is a sum of <math>m</math> mutually independent indicator variable. Applying Chernoff bound, for any particular bin <math>i\in[n]</math>,
:<math>
\Pr[Y_i>12\ln n] =\Pr[Y_i>(1+1)\mu]\le e^{-\frac{\mu}{3}} = e^{-2\ln n}= \frac{1}{n^2}.
</math>
Applying the union bound, the probability that there exists a bin with load <math>>12\ln n</math> is
:<math>n\cdot \Pr[Y_1>12\ln n]\le \frac{1}{n}</math>.
Therefore, with probability at least <math>1-\frac{1}{n}</math>, the maximum load is within <math>12\ln n=O(m/n)</math>.

=== Set balancing ===
Supposed that we have an <math>n\times m</math> matrix <math>A</math> with 0-1 entries. We are looking for a <math>b\in\{-1,+1\}^m</math> that minimizes <math>\|Ab\|_\infty</math>.

Recall that <math>\|\cdot\|_\infty</math> is the infinity norm (also called <math>L_\infty</math> norm) of a vector, and for the vector <math>c=Ab</math>,
:<math>\|Ab\|_\infty=\max_{i=1,2,\ldots,n}|c_i|</math>.

We can also describe this problem as an optimization:
:<math>\begin{align}
\mbox{minimize }
&\quad
\|Ab\|_\infty\\
\mbox{subject to: }
&\quad
b\in\{-1,+1\}^m.
\end{align}</math>

{|border="1"
|The problem arises in designing statistical experiments. Suppose that we have <math>m</math> '''subjects''', each of which may have up to <math>n</math> '''features'''. This gives us an <math>n\times m</math> matrix <math>A</math>:
:<math>
\begin{array}{c}
\mbox{feature 1:}\\
\mbox{feature 2:}\\
\vdots\\
\mbox{feature n:}\\
\end{array}
\left[
\begin{array}{cccc}
a_{11} & a_{12} & \cdots & a_{1m}\\
a_{21} & a_{22} & \cdots & a_{2m}\\
\vdots & \vdots & \ddots & \vdots\\
a_{n1} & a_{n2} & \cdots & a_{nm}\\
\end{array}
\right],
</math>
where each column represents a subject and each row represent a feature. An entry <math>a_{ij}\in\{0,1\}</math> indicates whether subject <math>j</math> has feature <math>i</math>.

By multiplying a vector <math>b\in\{-1,+1\}^m</math>
:<math>
\left[
\begin{array}{cccc}
a_{11} & a_{12} & \cdots & a_{1m}\\
a_{21} & a_{22} & \cdots & a_{2m}\\
\vdots & \vdots & \ddots & \vdots\\
a_{n1} & a_{n2} & \cdots & a_{nm}\\
\end{array}
\right]
\left[
\begin{array}{c}
b_{1}\\
b_{2}\\
\vdots\\
b_{m}\\
\end{array}
\right]
=
\left[
\begin{array}{c}
c_{1}\\
c_{2}\\
\vdots\\
c_{n}\\
\end{array}
\right],
</math>
the subjects are partitioned into two disjoint groups: one for -1 and other other for +1. Each <math>c_i</math> gives the difference between the numbers of subjects with feature <math>i</math> in the two groups. By minimizing <math>\|Ab\|_\infty=\|c\|_\infty</math>, we ask for an optimal partition so that each feature is roughly as balanced as possible between the two groups.

In a scientific experiment, one of the group serves as a [http://en.wikipedia.org/wiki/Scientific_control control group] (对照组). Ideally, we want the two groups are statistically identical, which is usually impossible to achieve in practice. The requirement of minimizing <math>\|Ab\|_\infty</math> actually means the statistical difference between the two groups are minimized.
|}

We propose an extremely simple "randomized algorithm" for computing a <math>b\in\{-1,+1\}^m</math>: for each <math>i=1,2,\ldots, m</math>, let <math>b_i</math> be independently chosen from <math>\{-1,+1\}</math>, such that
:<math>b_i=
\begin{cases}
-1 & \mbox{with probability }\frac{1}{2}\\
+1 &\mbox{with probability }\frac{1}{2}
\end{cases}.
</math>

This procedure can hardly be called as an "algorithm", because its decision is made disregard of the input <math>A</math>. We then show that despite of this obliviousness, the algorithm chooses a good enough <math>b</math>, such that for any <math>A</math>, <math>\|Ab\|_\infty=O(\sqrt{m\ln n})</math> with high probability.
{|border="1"
|'''Theorem'''
:Let <math>A</math> be an <math>n\times m</math> matrix with 0-1 entries. For a random vector <math>b</math> with <math>m</math> entries chosen independently and with equal probability from <math>\{-1,+1\}</math>,
::<math>\Pr[\|Ab\|_\infty>2\sqrt{2m\ln n}]\le\frac{2}{n}</math>.
|}
'''Proof:'''
Consider particularly the <math>i</math>-th row of <math>A</math>. The entry of <math>Ab</math> contributed by row <math>i</math> is <math>c_i=\sum_{j=1}^m a_{ij}b_j</math>.

Let <math>k</math> be the non-zero entries in the row. If <math>k\le2\sqrt{2m\ln n}</math>, then clearly <math>|c_i|</math> is no greater than <math>2\sqrt{2m\ln n}</math>. On the other hand if <math>k>2\sqrt{2m\ln n}</math> then the <math>k</math> nonzero terms in the sum
:<math>c_i=\sum_{j=1}^m a_{ij}b_j</math>
are independent, each with probability 1/2 of being either +1 or -1.

Thus, for these <math>k</math> nonzero terms, each <math>b_i</math> is either positive or negative independently with equal probability. There are expectedly <math>\mu=\frac{k}{2}</math> positive <math>b_i</math>'s among these <math>k</math> terms, and <math>c_i<-2\sqrt{2m\ln n}</math> only occurs when there are less than <math>\frac{k}{2}-\sqrt{2m\ln n}=\left(1-\delta\right)\mu</math> positive <math>b_i</math>'s, where <math>\delta=\frac{2\sqrt{2m\ln n}}{k}</math>. Applying Chernoff bound, this event occurs with probability at most
:<math>\begin{align}
\exp\left(-\frac{\mu\delta^2}{2}\right)
&=
\exp\left(-\frac{k}{2}\cdot\frac{8m\ln n}{2k^2}\right)\\
&=
\exp\left(-\frac{2m\ln n}{k}\right)\\
&\le
\exp\left(-\frac{2m\ln n}{m}\right)\\
&\le n^{-2}.
\end{align}
</math>

The same argument can be applied to negative <math>b_i</math>'s, so that the probability that <math>c_i>2\sqrt{2m\ln n}</math> is at most <math>n^{-2}</math>. Therefore, by the union bound,
:<math>\Pr[|c_i|> 2\sqrt{2m\ln n}]\le\frac{2}{n^2}</math>.
Apply the union bound to all <math>n</math> rows.
:<math>\Pr[\|Ab\|_\infty>2\sqrt{2m\ln n}]\le n\cdot\Pr[|c_i|> 2\sqrt{2m\ln n}]\le\frac{2}{n}</math>.
<math>\square</math>

So how good is this randomized algorithm? In fact when <math>m=n</math> there exists a matrix <math>A</math> such that <math>\|Ab\|_\infty=\Omega(\sqrt{n})</math> for any choice of <math>b\in\{-1,+1\}^n</math>.