\documentclass[11pt,twoside]{article}
\usepackage{latex-macros/course}
%\usepackage{psfig}

\renewcommand{\coursecopyrightnames}{D. Karger \& F.T. Leighton}
\renewcommand{\coursecopyrightyear}{1995}

\begin{document}
\paper{f95-generating1}{Notes from November 3, 1995}{Generating Functions, I.}

\section{Generating Functions}

\begin{definition}
Let $<g_0,g_1,g_2,\ldots>$ be an infinite sequence.
The (ordinary) {\em generating function} of the
sequence is the formal power series
\[
G(x) = \sum_{n=0}^\infty g_n x^n \left( = \sum_n g_n x^n \mbox{ simplified
notation} \right).
\]
\end{definition}
Note that $x$ is formal, i.e. symbolic.  Do not actually
evaluate $G(x)$, just use its structure.  

Examples:

\[
G(x) = \frac{1}{1-x} = \sum_n 1\cdot x^n \longleftrightarrow <1,1,1,\ldots>
\]

\[
G(x) = 1+x \longleftrightarrow <1,1,0,0,0,\ldots>
\]

\[
G(x) = (1+x)^r = \sum_n \binom{r }{ n} x^n \longleftrightarrow 
<\binom{r }{ 0},\binom{r }{ 1},\binom{r }{ 2},\ldots,\binom{r }{ r},0,0,0,\ldots>
\]

\[
<1,a,a^2,a^3,\ldots> \longleftrightarrow \sum_n a^n x^n = \frac{1}{1-ax}
\]

\[
<1,-1,1,-1,1,-1,\ldots> \longleftrightarrow \frac{1}{1+x} \mbox{ ($a=-1$ above)}
\]

\[
<1,0,1,0,1,0,\ldots> \longleftrightarrow \sum_n a^n x^{2n}
= \sum_n a^n (x^2)^n = \frac{1}{1-x^2}
\]

Or,
\[
<1,0,1,0,1,0,\ldots> \longleftrightarrow \frac{1}{2} \left( \frac{1}{1-x}
+\frac{1}{1+x}\right) = \frac{1}{1-x^2}
\]

\[
<\underbrace{0,0,0,\ldots,0}_k,1,1,1,\ldots> \longleftrightarrow x^k \frac{1}{1-x}
\]

\[
<1,2,3,4,\ldots> \longleftrightarrow \sum_n (n+1)x^n = \frac{d}{dx}\sum_n x^n
= \frac{d}{dx}\frac{1}{1-x}=\frac{1}{(1-x)^2}
\]

Ordinary Generating Functions (OGF) represent all elements of a sequence as
a single formula.

Two useful rules are:

OGF's are can be combined in linear fashion.

\begin{eqnarray*}
& <f_0,f_1,f_2,\dots> \longleftrightarrow F(x) \mbox{ and }
<g_0,g_1,g_2,\dots> \longleftrightarrow G(x) \\ 
\Longrightarrow &
<\alpha f_0 + \beta g_0, \alpha f_1 + \beta g_2, \alpha f_2 + \beta g_2
,\dots> \longleftrightarrow \alpha F(x) + \beta G(x) 
\end{eqnarray*}

Derivatives of OGF are also OGF.

\[
<f_0,f_1,f_2,\dots> \longleftrightarrow F(x)
\Longrightarrow <f_1, 2f_2, 3 f_3, 4 f_4, \ldots> \longleftrightarrow F'(x)
\]

{\em Solving recurrenences using OGF's.}

We can use OGF to solve many recurrences.  For example, the Fibanocci
recurrence is 
\[
<0,1,1,2,3,5,8,11,\ldots> \longleftrightarrow \frac{x}{1-x-x^2}
\]

Recall, the Fibanocci recurrence is defined as
\[
a_n = \left\{ \begin{array}{ll}
		0 & \mbox{if $n=0$} \\
		1 & \mbox{if $n=1$} \\
		a_{n-1} + a_{n-2} & \mbox{if $n\geq 2$}
	      \end{array}
      \right. 
\]

1.  Define sequence and OGF of sequence.

$<a_0, a_1, a_2, \ldots>$

\[
A(x) = \sum_n a_n x^n
\]

2.  Multiply both sides of recurrence by $x^n$ and sum over
valid indices.

\[
\sum_{n=2}^\infty a_n x^n = \sum_{n=2}^\infty (a_{n-1}+a_{n-2})x^n
\]

3.  Express in terms of OGF

\[
LHS = A(x) -a_0 - a_1x = A(x)-x, \mbox{ since $a_0=0$ and $a_1=1$}
\]

\begin{eqnarray*}
RHS & = & \sum_{n=0}^\infty (a_n+a_{n+1})x^{n+2} \\
&=& x^2 \sum_n a_nx^n+x\sum_n a_{n+1}x^{n+1} \\
&=& x^2A(x) + x (\sum_n a_n x^n - a_0)\\
&=& x^2A(x) + xA(x)
\end{eqnarray*}

Therefore,
\[
A(x) -x = x^2 A(x) +xA(x)
\]

4.  Solve for $A(x)$

\[
A(x)(1-x-x^2)=x \Longrightarrow A(x) =\frac{x}{(1-x-x^2)}
\]

5.  Solve for $a_n$ = coefficient of $x^n$ in $A(x)$.
	(Often use partial fractions if rational functions) 

Using partial fraction decompositon, we see
\[
A(x)  = \frac{1}{\sqrt{5}}\left(\frac{1}{1-\alpha_1x} - \frac{1}{1-\alpha_2x}
\right)
\]
where $\alpha_1=\frac{1+\sqrt{5}}{2}$ and $\alpha_2=\frac{1-\sqrt{5}}{2}$.

Coeff of $x^n$ in $\frac{1}{1-\alpha_1x}$ is $\alpha_1^n$.

Coeff of $x^n$ in $\frac{1}{1-\alpha_2x}$ is $\alpha_2^n$.

Therefore, 
\[
a_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n
+ \left(\frac{1-\sqrt{5}}{2}\right)^n\right].
\]


\section{OGF's for Combinations}
Recall, 
\[
<\binom{r }{ 0},\binom{r }{ 1},\binom{r }{ 2},\ldots,\binom{r }{ r},0,0,0,\ldots>
\longleftrightarrow (1+x)^r
\]

Suppose we have $r$ distinguishable objects $\{a_1,\ldots,a_r\}$.

What is the OGF of the number of ways to choose objects from $\{a_1\}$?

$g_0 =1$

$g_1 =1$

$g_2 =0$

$g_3 =0$

$g_4 =0$

etc.

$G(x) = 1+x$

What is the OGF of the number of ways to choose objects from $\{a_2\}$?
Also, $1+x$.

What is the OGF of the number of ways to choose objects from $\{a_1,a_2\}$?

$(1+x)(1+x) = (1+x)^2= 1+2x+x^2$

In $(1+x)$, the 1 represents not choosing $a_i$, the $x$ represents
choosing $a_i$.

Thus, we have 1 way to choose 0 elements, 2 ways to choose 1 element,
and 1 way to choose two elements.  The coefficient of $x^n$ is
the number of ways to choose $n$ elements.

In general, $(1+x)^r$ is the OGF for the number of ways to choose
from $\{a_1,\ldots,a_r\}$.

\begin{theorem}
Let $A(x)$ and $B(x)$ be OGF's for the number of ways to choose
objects from sets ${\cal A}$ and ${\cal B}$, where ${\cal A} \cap
{\cal B} = \emptyset$.  Then, the OGF for the number of ways of
choosing objects from ${\cal A} \cup {\cal B}$ is $A(x) \cdot B(x)$.
\end{theorem}

\begin{proof}
Let $A(x) = \sum_n a_n x^n, B(x) = \sum_n b_n x^n$.

Let $C(x)  = A(x) B(x) =\sum_n c_n x^n$.

What is $c_n$?

\[ 
c_n = \sum_{k=0}^n a_k b_{n-k}
\]

$<c_0,c_1,\ldots>$ is the {\em convolution sequence} of $<a_0,a_1,\ldots>$
and $<b_0,b_1,\ldots>$.

Now, how many ways is there to choose $n$ objects from ${\cal A} \cup {\cal B}$?
For $k=0,1,2,\ldots,n$, pick $k$ objects from ${\cal A}$ and 
$n-k$ objects from ${\cal B}$. Rule of product $\Longrightarrow$ $a_kb_{n-k}$ ways
for a given $k$.

Total = $\sum_{k=0}^n a_k b_{n-k} = c_n$.
\end{proof} 

{\bf Fruit example;}
Consider choosing a bag of $n$ fruits such
that 
\begin{itemize}
\item No. of apples is even
\item No. of bananas is a multiple of 5
\item No. of oranges is less than or equal to 4
\item No. of pears is either 0 or 1.
\end{itemize}
How many different bags of fruit are there?

For $n=6$, we can list the ways.
\begin{tabular}{l|lllllll}
A & 6 & 4 & 4 & 2 & 2 & 0 & 0 \\
B & 0 & 0 & 0 & 0 & 0 & 5 & 5 \\
O & 0 & 2 & 1 & 4 & 3 & 1 & 0 \\
P & 0 & 0 & 1 & 0 & 1 & 0 & 1
\end{tabular}

For arbitrary $n$, we can compute the generating function for each 
fruit and then multiply.

Apples:
$A(x) = 1+ x^2 +x^4 + \dots = \frac{1}{1-x^2}$.

Bananas:
$B(x) = 1+ x^5 +x^{10} + \dots = \frac{1}{1-x^5}$.

Oranges:
$O(x) = 1+ x +x^2 + x^3 +x^4 = \frac{1-x^5}{1-x}$.

Pears:
$P(x) = 1+ x = \frac{1-x^2}{1-x}$.

Total OGF:
\[ 
F(x)  = A(x) B(x) O(x) P(x) = \frac{1}{1-x^2}\cdot\frac{1}{1-x^5}
\cdot\frac{1-x^5}{1-x}\cdot\frac{1-x^2}{1-x} = \frac{1}{(1-x)^2}
=\sum_n (n+1)x^n
\]

The answer is $(n+1)$ ways for a bag of $n$ fruits.

Another example:  ${\cal A}$ has $\infty$ red objects.
${\cal B}$ has $\infty$ blue objects.  Count the number
of ways of picking $n$ objects from ${\cal A}$ and ${\cal B}$.

OGF for the number of ways of picking red (blue) objects is
$1+x+x^2+\dots =\frac{1}{1-x}$.

OGF for the number of ways of picking red or blue objects is
\[
\frac{1}{1-x} \cdot \frac{1}{1-x} = \frac{1}{1-x^2} = \sum_n (n+1)x^n
\]

Example:   What is the OGF of the number of ways to choose objects from $k$
types, where repeated types are allowed?

The OGF is $(1+x+x^2+\dots)^k = (1-x)^{-k}$

We can evaulate the coefficients two ways.  One way is to use the
generalized binomial theorem.

\begin{eqnarray*}
(1-x)^{-k} 
&=& \sum_n \binom{{-k}}{ n} (-1)^n x^n \\
&=& \sum_n \frac{(-k)(-k-1) \dots (-k-n+1)}{n!} (-1)^n x^n \\
&=& \sum_n \frac{(k)(k+1) \dots (k+n-1)}{n!} x^n \\
&=& \sum_n \binom{{k+n-1}}{ n} x^n
\end{eqnarray*}

Another way is to evaulate the terms in the Taylor series using derivatives.
Recall, from Calculus, that the $nth$ term of Taylor series, $f_n$, of the 
function $F(x)$ around
0 is $F^{(n)}(0)/n!$.

In our case, 
\[
F(x) = (1-x)^{-k}
\]

Thus,

$f_0= F(0)/0! = 1$

$F'(x) = k (1-x)^{-(k+1)} \Longrightarrow
f_1 = F'(0)/1! = k $

$F'' (x) = k(k+1) (1-x)^{-(k+2)}\Longrightarrow
f_2 = F'(0)/2! = k(k+1)/2$

In general, 

\begin{eqnarray*}
& F^{(n)} (x) =  k(k+1)\ldots (k+n-1) (1-x)^{-(k+n)}  \\
\Longrightarrow &
f_n = F'(0)/n! = k(k+1)\ldots (k+n-1)/n! = \binom{{k+n-1} }{ n}.
\end{eqnarray*}

\end{document}
