TCS Wiki - User contributions [en]

Combinatorics (Fall 2010)/Flow and matching

2010-12-24T12:43:13Z

172.21.3.81: /* The augmenting paths */

== Flow ==

=== The maximum flow problem ===
An instance of the maximum flow problem consists of:
* a directed graph <math>G(V,E)</math>;
* two distinguished vertices <math>s</math> (the '''source''') and <math>t</math> (the '''sink'''), where the in-degree of <math>s</math> and the out-degree of <math>t</math> are both 0;
* the '''capacity function''' <math>c:E\rightarrow\mathbb{R}^+</math> which associates each directed edge <math>(u,v)\in E</math> a nonnegative real number <math>c_{uv}</math> called the '''capacity''' of the edge.

The quadruple <math>(G,c,s,t)</math> is called a '''flow network'''.

A function <math>f:E\rightarrow\mathbb{R}^+</math> is called a '''flow''' (or an '''<math>s</math>-<math>t</math> flow''') in the network <math>G(V,E)</math> if it satisfies:
* '''Capacity constraint:''' <math>f_{uv}\le c_{uv}</math> for all <math>(u,v)\in E</math>.
* '''Conservation constraint:''' <math>\sum_{u:(u,v)\in E}f_{uv}=\sum_{w:(v,w)\in E}f_{vw}</math> for all <math>v\in V\setminus\{s,t\}</math>.

The '''value''' of the flow <math>f</math> is <math>\sum_{v:(s,v)\in E}f_{sv}</math>.

Given a flow network, the maximum flow problem asks to find the flow of the maximum value.

The maximum flow problem can be described as the following linear program.
:<math>
\begin{align}
\text{maximize} \quad& \sum_{v:(s,v)\in E}f_{sv}\\
\begin{align}
\text{subject to} \\
\\
\\
\\
\end{align}
\quad &
\begin{align} f_{uv}&\le c_{uv} &\quad& \forall (u,v)\in E\\
\sum_{u:(u,v)\in E}f_{uv}-\sum_{w:(v,w)\in E}f_{vw} &=0 &\quad& \forall v\in V\setminus\{s,t\}\\
f_{uv}&\ge 0 &\quad& \forall (u,v)\in E
\end{align}
\end{align}
</math>

=== Cuts ===
{{Theorem|Definition|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>S\subset V</math>. We call <math>(S,\bar{S})</math> an '''<math>s</math>-<math>t</math> cut''' if <math>s\in S</math> and <math>t\not\in S</math>.
:The '''value''' of the cut (also called the '''capacity''' of the cut) is defined as <math>\sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>.
}}

A fundamental fact in the theory of flow is that cuts always upper bound flows.

{{Theorem|Lemma|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>f</math> be an arbitrary flow in <math>G</math>, and let <math>(S,\bar{S})</math> be an arbitrary <math>s</math>-<math>t</math> cut. Then
::<math>\sum_{v:(s,v)}f_{sv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
:that is, the value of any flow is no greater than the value of any cut.
}}
{{Proof|By the definition of <math>s</math>-<math>t</math> cut, <math>s\in S</math> and <math>t\not\in S</math>.

Due to the conservation of flow,
:<math>\sum_{u\in S}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}+\sum_{u\in S\setminus\{s\}}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}\,.</math>
On the other hand, summing flow over edges,
:<math>\sum_{v\in S}\left(\sum_{u:(u,v)\in E}f_{uv}-\sum_{u:(v,u)\in E}f_{vu}\right)=\sum_{u\in S,v\in S\atop (u,v)\in E}\left(f_{uv}-f_{uv}\right)+\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\,.</math>
Therefore,
:<math>\sum_{v:(s,v)\in E}f_{sv}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\le\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}\,,</math>
}}

=== The augmenting paths ===
{{Theorem|Definition (Augmenting path)|
:Let <math>f</math> be a flow in <math>G</math>. An '''augmenting path to <math>u_k</math>''' is a sequence of distinct vertices <math>P=(u_0,u_1,\cdots, u_k)</math>, such that
:* <math>u_0=s\,</math>;
:and each pair of consecutive vertices <math>u_{i}u_{i+1}\,</math> in <math>P</math> corresponds to either a '''forward edge''' <math>(u_{i},u_{i+1})\in E</math> or a '''reverse edge''' <math>(u_{i+1},u_{i})\in E</math>, and
:* <math>f(u_i,u_{i+1})<c(u_i,u_{i+1})\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a forward edge <math>(u_{i},u_{i+1})\in E</math>, and
:* <math>f(u_{i+1},u_i)>0\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a reverse edge <math>(u_{i+1},u_{i})\in E</math>.
:If <math>u_k=t\,</math>, we simply call <math>P</math> an '''augmenting path'''.
}}

Let <math>f</math> be a flow in <math>G</math>. Suppose there is an augmenting path <math>P=u_0u_1\cdots u_k</math>, where <math>u_0=s</math> and <math>u_k=t</math>. Let <math>\epsilon>0</math> be a positive constant satisfying
*<math>\epsilon \le c(u_{i},u_{i+1})-f(u_i,u_{i+1})</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math>;
*<math>\epsilon \le f(u_{i+1},u_i)</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>.
Due to the definition of augmenting path, we can always find such a positive <math>\epsilon</math>.

Increase <math>f(u_i,u_{i+1})</math> by <math>\epsilon</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math> and decrease <math>f(u_{i+1},u_i)</math> by <math>\epsilon</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>. Denote the modified flow by <math>f'</math>. It is easy to see that <math>f'</math> satisfies the capacity constraint and conservation constraint thus is still a valid flow. On the other hand, the value of the new flow <math>f'</math>
:<math>\sum_{v:(s,v)\in E}f_{sv}'=\epsilon+\sum_{v:(s,v)\in E}f_{sv}>\sum_{v:(s,v)\in E}f_{sv}</math>.
Therefore, the value of the flow can be "augmented" by adjusting the flow on the augmenting path. This immediately implies that if a flow is maximum, then there is no augmenting path. Surprisingly, the converse is also true, thus maximum flows are "characterized" by augmenting paths.

{{Theorem|Lemma|
:A flow <math>f</math> is maximum if and only if there are no augmenting paths.
}}
{{Proof|We have already proved the "only if" direction above. Now we prove the "if" direction.

Let <math>S=\{u\in V\mid \exists\text{an augmenting path to }u\}</math>. Clearly <math>s\in S</math>, and since there is no augmenting path <math>t\not\in S</math>. Therefore, <math>(S,\bar{S})</math> defines an <math>s</math>-<math>t</math> cut.

We claim that
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
that is, the value of flow <math>f</math> approach the value of the cut <math>(S,\bar{S})</math> defined above. By the above lemma, this will imply that the current flow <math>f</math> is maximum.

To prove this claim, we first observe that
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}</math>.
This identity is implied by the flow conservation constraint, and holds for any <math>s</math>-<math>t</math> cut <math>(S,\bar{S})</math>.

We then claim that
*<math>f_{uv}=c_{uv}</math> for all <math>u\in S,v\not\in S, (u,v)\in E</math>; and
*<math>f_{vu}=0</math> for all <math>u\in S,v\not\in S, (v,u)\in E</math>.
If otherwise, then the augmenting path to <math>u</math> apending <math>uv</math> becomes a new augmenting path to <math>v</math>, which contradicts that <math>S</math> includes all vertices to which there exist augmenting paths.

Therefore,
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu} = \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>.
As discussed above, this proves the theorem.
}}

=== The max-flow min-cut theorem ===

== Unimodularity ==

=== Integrality of polytopes ===

=== Unimodularity and total unimodularity ===

Combinatorics (Fall 2010)/Flow and matching

2010-12-24T12:19:41Z

172.21.3.81: /* The augmenting paths */

== Flow ==

=== The maximum flow problem ===
An instance of the maximum flow problem consists of:
* a directed graph <math>G(V,E)</math>;
* two distinguished vertices <math>s</math> (the '''source''') and <math>t</math> (the '''sink'''), where the in-degree of <math>s</math> and the out-degree of <math>t</math> are both 0;
* the '''capacity function''' <math>c:E\rightarrow\mathbb{R}^+</math> which associates each directed edge <math>(u,v)\in E</math> a nonnegative real number <math>c_{uv}</math> called the '''capacity''' of the edge.

The quadruple <math>(G,c,s,t)</math> is called a '''flow network'''.

A function <math>f:E\rightarrow\mathbb{R}^+</math> is called a '''flow''' (or an '''<math>s</math>-<math>t</math> flow''') in the network <math>G(V,E)</math> if it satisfies:
* '''Capacity constraint:''' <math>f_{uv}\le c_{uv}</math> for all <math>(u,v)\in E</math>.
* '''Conservation constraint:''' <math>\sum_{u:(u,v)\in E}f_{uv}=\sum_{w:(v,w)\in E}f_{vw}</math> for all <math>v\in V\setminus\{s,t\}</math>.

The '''value''' of the flow <math>f</math> is <math>\sum_{v:(s,v)\in E}f_{sv}</math>.

Given a flow network, the maximum flow problem asks to find the flow of the maximum value.

The maximum flow problem can be described as the following linear program.
:<math>
\begin{align}
\text{maximize} \quad& \sum_{v:(s,v)\in E}f_{sv}\\
\begin{align}
\text{subject to} \\
\\
\\
\\
\end{align}
\quad &
\begin{align} f_{uv}&\le c_{uv} &\quad& \forall (u,v)\in E\\
\sum_{u:(u,v)\in E}f_{uv}-\sum_{w:(v,w)\in E}f_{vw} &=0 &\quad& \forall v\in V\setminus\{s,t\}\\
f_{uv}&\ge 0 &\quad& \forall (u,v)\in E
\end{align}
\end{align}
</math>

=== Cuts ===
{{Theorem|Definition|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>S\subset V</math>. We call <math>(S,\bar{S})</math> an '''<math>s</math>-<math>t</math> cut''' if <math>s\in S</math> and <math>t\not\in S</math>.
:The '''value''' of the cut (also called the '''capacity''' of the cut) is defined as <math>\sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>.
}}

A fundamental fact in the theory of flow is that cuts always upper bound flows.

{{Theorem|Lemma|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>f</math> be an arbitrary flow in <math>G</math>, and let <math>(S,\bar{S})</math> be an arbitrary <math>s</math>-<math>t</math> cut. Then
::<math>\sum_{v:(s,v)}f_{sv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
:that is, the value of any flow is no greater than the value of any cut.
}}
{{Proof|By the definition of <math>s</math>-<math>t</math> cut, <math>s\in S</math> and <math>t\not\in S</math>.

Due to the conservation of flow,
:<math>\sum_{u\in S}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}+\sum_{u\in S\setminus\{s\}}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}\,.</math>
On the other hand, summing flow over edges,
:<math>\sum_{v\in S}\left(\sum_{u:(u,v)\in E}f_{uv}-\sum_{u:(v,u)\in E}f_{vu}\right)=\sum_{u\in S,v\in S\atop (u,v)\in E}\left(f_{uv}-f_{uv}\right)+\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\,.</math>
Therefore,
:<math>\sum_{v:(s,v)\in E}f_{sv}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\le\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}\,,</math>
}}

=== The augmenting paths ===
{{Theorem|Definition (Augmenting path)|
:Let <math>f</math> be a flow in <math>G</math>. An '''augmenting path to <math>u_k</math>''' is a sequence of distinct vertices <math>P=(u_0,u_1,\cdots, u_k)</math>, such that
:* <math>u_0=s\,</math>;
:and each pair of consecutive vertices <math>u_{i}u_{i+1}\,</math> in <math>P</math> corresponds to either a '''forward edge''' <math>(u_{i},u_{i+1})\in E</math> or a '''reverse edge''' <math>(u_{i+1},u_{i})\in E</math>, and
:* <math>f(u_i,u_{i+1})<c(u_i,u_{i+1})\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a forward edge <math>(u_{i},u_{i+1})\in E</math>, and
:* <math>f(u_{i+1},u_i)>0\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a reverse edge <math>(u_{i+1},u_{i})\in E</math>.
:If <math>u_k=t\,</math>, we simply call <math>P</math> an '''augmenting path'''.
}}

Let <math>f</math> be a flow in <math>G</math>. Suppose there is an augmenting path <math>P=u_0u_1\cdots u_k</math>, where <math>u_0=s</math> and <math>u_k=t</math>. Let <math>\epsilon>0</math> be a positive constant satisfying
*<math>\epsilon \le c(u_{i},u_{i+1})-f(u_i,u_{i+1})</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math>;
*<math>\epsilon \le f(u_{i+1},u_i)</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>.
Due to the definition of augmenting path, we can always find such a positive <math>\epsilon</math>.

Increase <math>f(u_i,u_{i+1})</math> by <math>\epsilon</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math> and decrease <math>f(u_{i+1},u_i)</math> by <math>\epsilon</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>. Denote the modified flow by <math>f'</math>. It is easy to see that <math>f'</math> satisfies the capacity constraint and conservation constraint thus is still a valid flow. On the other hand, the value of the new flow <math>f'</math>
:<math>\sum_{v:(s,v)\in E}f_{sv}'=\epsilon+\sum_{v:(s,v)\in E}f_{sv}>\sum_{v:(s,v)\in E}f_{sv}</math>.
Therefore, the value of the flow can be "augmented" by adjusting the flow on the augmenting path. This immediately implies that if a flow is maximum, then there is no augmenting path. Surprisingly, the converse is also true, thus maximum flows are "characterized" by augmenting paths.

{{Theorem|Lemma|
:A flow <math>f</math> is maximum if and only if there are no augmenting paths.
}}
{{Proof|We have already proved the "only if" direction above. Now we prove the "if" direction.

Let <math>S=\{u\in V\mid \exists\text{an augmenting path to }u\}</math>. Clearly <math>s\in S</math>, and since there is no augmenting path <math>t\not\in S</math>. Therefore, <math>(S,\bar{S})</math> defines an <math>s</math>-<math>t</math> cut.

We claim that
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
that is, the value of flow <math>f</math> approach the value of the cut <math>(S,\bar{S})</math> defined above. By the above lemma, this will imply that the current flow <math>f</math> is maximum.

}}

=== The max-flow min-cut theorem ===

== Unimodularity ==

=== Integrality of polytopes ===

=== Unimodularity and total unimodularity ===

Combinatorics (Fall 2010)/Flow and matching

2010-12-24T12:06:22Z

172.21.3.81: /* The augmenting paths */

== Flow ==

=== The maximum flow problem ===
An instance of the maximum flow problem consists of:
* a directed graph <math>G(V,E)</math>;
* two distinguished vertices <math>s</math> (the '''source''') and <math>t</math> (the '''sink'''), where the in-degree of <math>s</math> and the out-degree of <math>t</math> are both 0;
* the '''capacity function''' <math>c:E\rightarrow\mathbb{R}^+</math> which associates each directed edge <math>(u,v)\in E</math> a nonnegative real number <math>c_{uv}</math> called the '''capacity''' of the edge.

The quadruple <math>(G,c,s,t)</math> is called a '''flow network'''.

A function <math>f:E\rightarrow\mathbb{R}^+</math> is called a '''flow''' (or an '''<math>s</math>-<math>t</math> flow''') in the network <math>G(V,E)</math> if it satisfies:
* '''Capacity constraint:''' <math>f_{uv}\le c_{uv}</math> for all <math>(u,v)\in E</math>.
* '''Conservation constraint:''' <math>\sum_{u:(u,v)\in E}f_{uv}=\sum_{w:(v,w)\in E}f_{vw}</math> for all <math>v\in V\setminus\{s,t\}</math>.

The '''value''' of the flow <math>f</math> is <math>\sum_{v:(s,v)\in E}f_{sv}</math>.

Given a flow network, the maximum flow problem asks to find the flow of the maximum value.

The maximum flow problem can be described as the following linear program.
:<math>
\begin{align}
\text{maximize} \quad& \sum_{v:(s,v)\in E}f_{sv}\\
\begin{align}
\text{subject to} \\
\\
\\
\\
\end{align}
\quad &
\begin{align} f_{uv}&\le c_{uv} &\quad& \forall (u,v)\in E\\
\sum_{u:(u,v)\in E}f_{uv}-\sum_{w:(v,w)\in E}f_{vw} &=0 &\quad& \forall v\in V\setminus\{s,t\}\\
f_{uv}&\ge 0 &\quad& \forall (u,v)\in E
\end{align}
\end{align}
</math>

=== Cuts ===
{{Theorem|Definition|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>S\subset V</math>. We call <math>(S,\bar{S})</math> an '''<math>s</math>-<math>t</math> cut''' if <math>s\in S</math> and <math>t\not\in S</math>.
:The '''value''' of the cut (also called the '''capacity''' of the cut) is defined as <math>\sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>.
}}

A fundamental fact in the theory of flow is that cuts always upper bound flows.

{{Theorem|Lemma|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>f</math> be an arbitrary flow in <math>G</math>, and let <math>(S,\bar{S})</math> be an arbitrary <math>s</math>-<math>t</math> cut. Then
::<math>\sum_{v:(s,v)}f_{sv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
:that is, the value of any flow is no greater than the value of any cut.
}}
{{Proof|By the definition of <math>s</math>-<math>t</math> cut, <math>s\in S</math> and <math>t\not\in S</math>.

Due to the conservation of flow,
:<math>\sum_{u\in S}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}+\sum_{u\in S\setminus\{s\}}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}\,.</math>
On the other hand, summing flow over edges,
:<math>\sum_{v\in S}\left(\sum_{u:(u,v)\in E}f_{uv}-\sum_{u:(v,u)\in E}f_{vu}\right)=\sum_{u\in S,v\in S\atop (u,v)\in E}\left(f_{uv}-f_{uv}\right)+\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\,.</math>
Therefore,
:<math>\sum_{v:(s,v)\in E}f_{sv}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\le\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}\,,</math>
}}

=== The augmenting paths ===
{{Theorem|Definition (Augmenting path)|
:Let <math>f</math> be a flow in <math>G</math>. An '''augmenting path to <math>u_k</math>''' is a sequence of distinct vertices <math>P=(u_0,u_1,\cdots, u_k)</math>, such that
:* <math>u_0=s\,</math>;
:and each pair of consecutive vertices <math>u_{i}u_{i+1}\,</math> in <math>P</math> corresponds to either a '''forward edge''' <math>(u_{i},u_{i+1})\in E</math> or a '''reverse edge''' <math>(u_{i+1},u_{i})\in E</math>, and
:* <math>f(u_i,u_{i+1})<c(u_i,u_{i+1})\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a forward edge <math>(u_{i},u_{i+1})\in E</math>, and
:* <math>f(u_{i+1},u_i)>0\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a reverse edge <math>(u_{i+1},u_{i})\in E</math>.
:If <math>u_k=t\,</math>, we simply call <math>P</math> an '''augmenting path'''.
}}

Let <math>f</math> be a flow in <math>G</math>. Suppose there is an augmenting path <math>P=u_0u_1\cdots u_k</math>, where <math>u_0=s</math> and <math>u_k=t</math>. Let <math>\epsilon>0</math> be a positive constant satisfying
*<math>\epsilon \le c(u_{i},u_{i+1})-f(u_i,u_{i+1})</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math>;
*<math>\epsilon \le f(u_{i+1},u_i)</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>.
Due to the definition of augmenting path, we can always find such a positive <math>\epsilon</math>.

Increase <math>f(u_i,u_{i+1})</math> by <math>\epsilon</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math> and decrease <math>f(u_{i+1},u_i)</math> by <math>\epsilon</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>. Denote the modified flow by <math>f'</math>. It is easy to see that <math>f'</math> satisfies the capacity constraint and conservation constraint thus is still a valid flow. On the other hand, the value of the new flow <math>f'</math>
:<math>\sum_{v:(s,v)\in E}f_{sv}'=\epsilon+\sum_{v:(s,v)\in E}f_{sv}>\sum_{v:(s,v)\in E}f_{sv}</math>.
Therefore, the value of the flow can be "augmented" by adjusting the flow on the augmenting path. This immediately implies that if a flow is maximum, then there is no augmenting path. Surprisingly, the converse is also true, thus maximum flows are "characterized" by augmenting paths.

{{Theorem|Lemma|
:A flow <math>f</math> is maximum if and only if there are no augmenting paths.
}}
{{Proof|We have already proved the "only if" direction above. Now we prove the "if" direction.

Let <math>S=\{u\in V\mid \exists\text{an augmenting path to }u\}</math>. Clearly <math>s\in S</math>, and since there is no augmenting path <math>t\not\in S</math>. Therefore, <math>(S,\bar{S})</math> defines an <math>s</math>-<math>t</math> cut.
}}

=== The max-flow min-cut theorem ===

== Unimodularity ==

=== Integrality of polytopes ===

=== Unimodularity and total unimodularity ===

Combinatorics (Fall 2010)/Flow and matching

2010-12-24T12:05:34Z

172.21.3.81: /* The augmenting paths */

== Flow ==

=== The maximum flow problem ===
An instance of the maximum flow problem consists of:
* a directed graph <math>G(V,E)</math>;
* two distinguished vertices <math>s</math> (the '''source''') and <math>t</math> (the '''sink'''), where the in-degree of <math>s</math> and the out-degree of <math>t</math> are both 0;
* the '''capacity function''' <math>c:E\rightarrow\mathbb{R}^+</math> which associates each directed edge <math>(u,v)\in E</math> a nonnegative real number <math>c_{uv}</math> called the '''capacity''' of the edge.

The quadruple <math>(G,c,s,t)</math> is called a '''flow network'''.

A function <math>f:E\rightarrow\mathbb{R}^+</math> is called a '''flow''' (or an '''<math>s</math>-<math>t</math> flow''') in the network <math>G(V,E)</math> if it satisfies:
* '''Capacity constraint:''' <math>f_{uv}\le c_{uv}</math> for all <math>(u,v)\in E</math>.
* '''Conservation constraint:''' <math>\sum_{u:(u,v)\in E}f_{uv}=\sum_{w:(v,w)\in E}f_{vw}</math> for all <math>v\in V\setminus\{s,t\}</math>.

The '''value''' of the flow <math>f</math> is <math>\sum_{v:(s,v)\in E}f_{sv}</math>.

Given a flow network, the maximum flow problem asks to find the flow of the maximum value.

The maximum flow problem can be described as the following linear program.
:<math>
\begin{align}
\text{maximize} \quad& \sum_{v:(s,v)\in E}f_{sv}\\
\begin{align}
\text{subject to} \\
\\
\\
\\
\end{align}
\quad &
\begin{align} f_{uv}&\le c_{uv} &\quad& \forall (u,v)\in E\\
\sum_{u:(u,v)\in E}f_{uv}-\sum_{w:(v,w)\in E}f_{vw} &=0 &\quad& \forall v\in V\setminus\{s,t\}\\
f_{uv}&\ge 0 &\quad& \forall (u,v)\in E
\end{align}
\end{align}
</math>

=== Cuts ===
{{Theorem|Definition|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>S\subset V</math>. We call <math>(S,\bar{S})</math> an '''<math>s</math>-<math>t</math> cut''' if <math>s\in S</math> and <math>t\not\in S</math>.
:The '''value''' of the cut (also called the '''capacity''' of the cut) is defined as <math>\sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>.
}}

A fundamental fact in the theory of flow is that cuts always upper bound flows.

{{Theorem|Lemma|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>f</math> be an arbitrary flow in <math>G</math>, and let <math>(S,\bar{S})</math> be an arbitrary <math>s</math>-<math>t</math> cut. Then
::<math>\sum_{v:(s,v)}f_{sv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
:that is, the value of any flow is no greater than the value of any cut.
}}
{{Proof|By the definition of <math>s</math>-<math>t</math> cut, <math>s\in S</math> and <math>t\not\in S</math>.

Due to the conservation of flow,
:<math>\sum_{u\in S}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}+\sum_{u\in S\setminus\{s\}}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}\,.</math>
On the other hand, summing flow over edges,
:<math>\sum_{v\in S}\left(\sum_{u:(u,v)\in E}f_{uv}-\sum_{u:(v,u)\in E}f_{vu}\right)=\sum_{u\in S,v\in S\atop (u,v)\in E}\left(f_{uv}-f_{uv}\right)+\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\,.</math>
Therefore,
:<math>\sum_{v:(s,v)\in E}f_{sv}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\le\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}\,,</math>
}}

=== The augmenting paths ===
{{Theorem|Definition (Augmenting path)|
:Let <math>f</math> be a flow in <math>G</math>. An '''augmenting path to <math>u_k</math>''' is a sequence of distinct vertices <math>P=(u_0,u_1,\cdots, u_k)</math>, such that
:* <math>u_0=s\,</math>;
:and each pair of consecutive vertices <math>u_{i}u_{i+1}\,</math> in <math>P</math> corresponds to either a '''forward edge''' <math>(u_{i},u_{i+1})\in E</math> or a '''reverse edge''' <math>(u_{i+1},u_{i})\in E</math>, and
:* <math>f(u_i,u_{i+1})<c(u_i,u_{i+1})\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a forward edge <math>(u_{i},u_{i+1})\in E</math>, and
:* <math>f(u_{i+1},u_i)>0\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a reverse edge <math>(u_{i+1},u_{i})\in E</math>.
:If <math>u_k=t\,</math>, we simply call <math>P</math> an '''augmenting path'''.
}}

Let <math>f</math> be a flow in <math>G</math>. Suppose there is an augmenting path <math>P=u_0u_1\cdots u_k</math>, where <math>u_0=s</math> and <math>u_k=t</math>. Let <math>\epsilon>0</math> be a positive constant satisfying
*<math>\epsilon \le c(u_{i},u_{i+1})-f(u_i,u_{i+1})</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math>;
*<math>\epsilon \le f(u_{i+1},u_i)</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>.
Due to the definition of augmenting path, we can always find such a positive <math>\epsilon</math>.

Increase <math>f(u_i,u_{i+1})</math> by <math>\epsilon</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math> and decrease <math>f(u_{i+1},u_i)</math> by <math>\epsilon</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>. Denote the modified flow by <math>f'</math>. It is easy to see that <math>f'</math> satisfies the capacity constraint and conservation constraint thus is still a valid flow. On the other hand, the value of the new flow <math>f'</math>
:<math>\sum_{v:(s,v)\in E}f_{sv}'=\epsilon+\sum_{v:(s,v)\in E}f_{sv}>\sum_{v:(s,v)\in E}f_{sv}</math>.
Therefore, the value of the flow can be "augmented" by adjusting the flow on the augmenting path. This immediately implies that if a flow is maximum, then there is no augmenting path. Surprisingly, the converse is also true, thus maximum flows are "characterized" by augmenting paths.

{{Theorem|Lemma|
:A flow <math>f</math> is maximum if and only if there are no augmenting paths.
}}
{{Proof|We have already proved the "only if" direction above. Now we prove the "if" direction.

Let <math>S=\{u\in V\mid \exists\text{an augmenting path to }u\}</math>. Clearly <math>s\in S</math>, and since there is no augmenting path <math>t\not\in S</math>. Therefore,
}}

=== The max-flow min-cut theorem ===

== Unimodularity ==

=== Integrality of polytopes ===

=== Unimodularity and total unimodularity ===

Combinatorics (Fall 2010)/Flow and matching

2010-12-24T12:02:56Z

172.21.3.81: /* Cuts */

== Flow ==

=== The maximum flow problem ===
An instance of the maximum flow problem consists of:
* a directed graph <math>G(V,E)</math>;
* two distinguished vertices <math>s</math> (the '''source''') and <math>t</math> (the '''sink'''), where the in-degree of <math>s</math> and the out-degree of <math>t</math> are both 0;
* the '''capacity function''' <math>c:E\rightarrow\mathbb{R}^+</math> which associates each directed edge <math>(u,v)\in E</math> a nonnegative real number <math>c_{uv}</math> called the '''capacity''' of the edge.

The quadruple <math>(G,c,s,t)</math> is called a '''flow network'''.

A function <math>f:E\rightarrow\mathbb{R}^+</math> is called a '''flow''' (or an '''<math>s</math>-<math>t</math> flow''') in the network <math>G(V,E)</math> if it satisfies:
* '''Capacity constraint:''' <math>f_{uv}\le c_{uv}</math> for all <math>(u,v)\in E</math>.
* '''Conservation constraint:''' <math>\sum_{u:(u,v)\in E}f_{uv}=\sum_{w:(v,w)\in E}f_{vw}</math> for all <math>v\in V\setminus\{s,t\}</math>.

The '''value''' of the flow <math>f</math> is <math>\sum_{v:(s,v)\in E}f_{sv}</math>.

Given a flow network, the maximum flow problem asks to find the flow of the maximum value.

The maximum flow problem can be described as the following linear program.
:<math>
\begin{align}
\text{maximize} \quad& \sum_{v:(s,v)\in E}f_{sv}\\
\begin{align}
\text{subject to} \\
\\
\\
\\
\end{align}
\quad &
\begin{align} f_{uv}&\le c_{uv} &\quad& \forall (u,v)\in E\\
\sum_{u:(u,v)\in E}f_{uv}-\sum_{w:(v,w)\in E}f_{vw} &=0 &\quad& \forall v\in V\setminus\{s,t\}\\
f_{uv}&\ge 0 &\quad& \forall (u,v)\in E
\end{align}
\end{align}
</math>

=== Cuts ===
{{Theorem|Definition|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>S\subset V</math>. We call <math>(S,\bar{S})</math> an '''<math>s</math>-<math>t</math> cut''' if <math>s\in S</math> and <math>t\not\in S</math>.
:The '''value''' of the cut (also called the '''capacity''' of the cut) is defined as <math>\sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>.
}}

A fundamental fact in the theory of flow is that cuts always upper bound flows.

{{Theorem|Lemma|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>f</math> be an arbitrary flow in <math>G</math>, and let <math>(S,\bar{S})</math> be an arbitrary <math>s</math>-<math>t</math> cut. Then
::<math>\sum_{v:(s,v)}f_{sv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
:that is, the value of any flow is no greater than the value of any cut.
}}
{{Proof|By the definition of <math>s</math>-<math>t</math> cut, <math>s\in S</math> and <math>t\not\in S</math>.

Due to the conservation of flow,
:<math>\sum_{u\in S}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}+\sum_{u\in S\setminus\{s\}}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}\,.</math>
On the other hand, summing flow over edges,
:<math>\sum_{v\in S}\left(\sum_{u:(u,v)\in E}f_{uv}-\sum_{u:(v,u)\in E}f_{vu}\right)=\sum_{u\in S,v\in S\atop (u,v)\in E}\left(f_{uv}-f_{uv}\right)+\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\,.</math>
Therefore,
:<math>\sum_{v:(s,v)\in E}f_{sv}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\le\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}\,,</math>
}}

=== The augmenting paths ===
{{Theorem|Definition (Augmenting path)|
:Let <math>f</math> be a flow in <math>G</math>. An '''augmenting path to <math>u_k</math>''' is a sequence of distinct vertices <math>P=(u_0,u_1,\cdots, u_k)</math>, such that
:* <math>u_0=s\,</math>;
:and each pair of consecutive vertices <math>u_{i}u_{i+1}\,</math> in <math>P</math> corresponds to either a '''forward edge''' <math>(u_{i},u_{i+1})\in E</math> or a '''reverse edge''' <math>(u_{i+1},u_{i})\in E</math>, and
:* <math>f(u_i,u_{i+1})<c(u_i,u_{i+1})\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a forward edge <math>(u_{i},u_{i+1})\in E</math>, and
:* <math>f(u_{i+1},u_i)>0\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a reverse edge <math>(u_{i+1},u_{i})\in E</math>.
:If <math>u_k=t\,</math>, we simply call <math>P</math> an '''augmenting path'''.
}}

Let <math>f</math> be a flow in <math>G</math>. Suppose there is an augmenting path <math>P=u_0u_1\cdots u_k</math>, where <math>u_0=s</math> and <math>u_k=t</math>. Let <math>\epsilon>0</math> be a positive constant satisfying
*<math>\epsilon \le c(u_{i},u_{i+1})-f(u_i,u_{i+1})</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math>;
*<math>\epsilon \le f(u_{i+1},u_i)</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>.
Due to the definition of augmenting path, we can always find such a positive <math>\epsilon</math>.

Increase <math>f(u_i,u_{i+1})</math> by <math>\epsilon</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math> and decrease <math>f(u_{i+1},u_i)</math> by <math>\epsilon</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>. Denote the modified flow by <math>f'</math>. It is easy to see that <math>f'</math> satisfies the capacity constraint and conservation constraint thus is still a valid flow. On the other hand, the value of the new flow <math>f'</math>
:<math>\sum_{v:(s,v)\in E}f_{sv}'=\epsilon+\sum_{v:(s,v)\in E}f_{sv}>\sum_{v:(s,v)\in E}f_{sv}</math>.
Therefore, the value of the flow can be "augmented" by adjusting the flow on the augmenting path. This immediately implies that if a flow is maximum, then there is no augmenting path. Surprisingly, the converse is also true, thus maximum flows are "characterized" by augmenting paths.

{{Theorem|Lemma|
:A flow <math>f</math> is maximum if and only if there are no augmenting paths.
}}
{{Proof|We have already proved the "only if" direction above. Now we prove the "if" direction.

}}

=== The max-flow min-cut theorem ===

== Unimodularity ==

=== Integrality of polytopes ===

=== Unimodularity and total unimodularity ===

Combinatorics (Fall 2010)/Generating functions

2010-09-12T02:19:06Z

172.21.3.5: /* 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 ===

=== Pólya's problem of changing money ===

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

Combinatorics (Fall 2010)/Generating functions

2010-09-12T02:18:48Z

172.21.3.5: /* 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>.
}}

Combinatorics (Fall 2010)/Generating functions

2010-09-12T01:42:03Z

172.21.3.5: /* Fibonacci numbers */

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

== Pólya's problem of changing money ==

== 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-12T01:37:02Z

172.21.3.5: /* Solving recurrences */

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

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

== Pólya's problem of changing money ==

== 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-12T01:32:14Z

172.21.3.5: /* Solving recurrences */

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

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

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

== Pólya's problem of changing money ==

== 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-12T01:24:04Z

172.21.3.5: /* Solving recurrences */

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

=== 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 ==
In the above analysis of Fibonacci numbers, we apply the following general methodology of solving recurrences by generating functions.
:1. Give a recursion that computes <math>a_n</math>, such as
::<math>a_n=f(a_0,a_1,\ldots,a_{n-1})</math> for some function <math>f</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}f(a_0,a_1,\ldots,a_{n-1})x^n</math>.
:: And manipulate the right hand side of the equation so that it becomes some other expression involving <math>G(x)</math>.
:3. Solve the resulting equation to derive an explicit formula for <math>G(x)</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>.

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

== Pólya's problem of changing money ==

== 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-12T01:21:08Z

172.21.3.5: /* Fibonacci numbers */

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

=== 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 ==
In the above analysis of Fibonacci numbers, we apply the following general methodology of solving recurrences by generating functions.
:1. Give a recursion that computes <math>a_n</math>; that is, an equation expressing <math>a_n</math> in terms of other elements of the sequence, such as
::<math>a_n=f(a_0,a_1,\ldots,a_{n-1})</math> for some function <math>f</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}f(a_0,a_1,\ldots,a_{n-1})x^n</math>.
:: And manipulate the right hand side of the equation so that it becomes some other expression involving <math>G(x)</math>.
:3. Solve the resulting equation to derive an explicit formula for <math>G(x)</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>.

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

== Pólya's problem of changing money ==

== 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-12T01:20:45Z

172.21.3.5: /* Fibonacci numbers */

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

=== 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 several 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 ==
In the above analysis of Fibonacci numbers, we apply the following general methodology of solving recurrences by generating functions.
:1. Give a recursion that computes <math>a_n</math>; that is, an equation expressing <math>a_n</math> in terms of other elements of the sequence, such as
::<math>a_n=f(a_0,a_1,\ldots,a_{n-1})</math> for some function <math>f</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}f(a_0,a_1,\ldots,a_{n-1})x^n</math>.
:: And manipulate the right hand side of the equation so that it becomes some other expression involving <math>G(x)</math>.
:3. Solve the resulting equation to derive an explicit formula for <math>G(x)</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>.

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

== Pólya's problem of changing money ==

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