\input lmacros
\documentstyle[12pt]{article}
\headheight 0in
\headsep 0in
\evensidemargin 1in
\oddsidemargin \evensidemargin
\textwidth 6.5in
\topmargin 1.25in
\textheight 8.7in
\begin{document}
\pagestyle{empty}

\begin{center}
{\bf Notes:  Ordinary generating functions and ``weighted'' counting.}
\end{center}

\noindent 1.  The idea of generating function.

\medskip

The idea behind ordinary generating functions, ``picture writing'', or
``weighted'' counting is this:  to count the elements of a set $X$ we
should attach a ``weight'', which in principle can be any abstract
quantity, to each element of $X$ and then sum up these weights.

In the simplest form of this, we would attach the weight $w(x) = 1$ to
every element $x\in X$.  Then summing this over all elements $x$ we of
course get the number of elements in $X$:
$$ |X| = \sum _{x\in X} w(x) = \sum _{x\in X} 1. $$

What makes this idea useful is the possibility that elements of $X$ might 
have different sizes, or values of some other attribute.  Then instead
of assigning each element the weight $1$, we may assign it a weight
reflecting its size.  Summing over all elements of $X$ we can solve
many, maybe even infinitely many, counting problems simultaneously.

Here is a simple example.  $X$ will be the set of all words of length
$n$ in symbols $0$ and $1$.  We know from elementary combinatorics
that $X$ has $2^{n}$ elements altogether, and for any given $k$,
${n\choose k}$ of the elements are words with $k$ $1$'s and $n-k$
$0$'s.

Let us assign to each word $a\in X$ the weight $w(a) = x^{k}$, where
$k$ is the number of $1$'s in $a$.  Here $x$ is just a variable, a
symbol for an abstract quantity as in algebra.  The sum of the weights over
all elements of $X$ is a sum of monomials $x^{k}$, each occuring
${n\choose k }$ times.  Thus this sum is 
$$ \sum _{k}{n\choose k } x^{k}, $$
and we call this the {\it generating function} counting the set $X$
with the weight $x^{k}$ assigned to a word with $k$ $1$'s.

By the binomial theorem, the above generating function equals 
$$ (1+x)^{n}. $$
Notice that if we set $x$ to $1$ then our generating function reduces
to a weighted count in which every element of $X$ gets weight $1$,
telling us that $X$ has $2^{n}$ elements altogether (which we knew).

\bigskip

\noindent 2.  Addition and multiplication principles.

\medskip

The generating function for words of $n$ $0$'s and $1$'s counted with
weight $x^{k}$ according to the number $k$ of $1$'s turned out to have
the simple form $(1+x)^{n}$.  Could we have obtained this directly?
Indeed we could have, using the addition and multiplication principles
of ordinary counting in a more general form for weight counting.

\medskip

{\it Addition principle:}  Suppose $X$ is the union of disjoint
subsets $X_{1}$ and $X_{2}$.  Then the generating function counting
elements of $X$ is the sum of the generating function for $X_{1}$ and
that for $X_{2}$.  This applies whatever the weights used for the
elements.

\medskip

{\it Multiplication principle:}  Suppose $X$ is a Cartesian product
$X_{1}\times X_{2}$ and the weights assigned to elements are
multiplicative.  This means elements of $X$ correspond bijectively to
pairs $(a,b)$ consisting of an element $a$ chosen from $X_{1}$
followed by $b$ chosen from $X_{2}$, and the weight $w(a,b)$ assigned
to each pair equals the product $w(a)w(b)$ of the weights assigned to
$a$ and $b$.  Then the generating function for $X$ is the product of
the generating functions for $X_{1}$ and $X_{2}$.

\medskip

Neither of these principles really demands much proof; they simply
follow from the definition of generating function and the rules of
algebra for adding and multiplying sums.  They may not seem obvious
to you, however, so you should stop a moment right now and think out
exactly what they mean and why they are true!

Now let's return to our example.  The set of words of length $n$ in
symbols $0$ and $1$ is nothing but the Cartesian product $X = Y\cdot
Y\cdots Y = Y^{n}$, where $Y = \{0,1 \}$.  We have assigned weight
$x^{k}$ to a word in $X$ with $k$ $1$'s.  Sure enough, these weights
are multiplicative, based on the assignment of weights $w(0) = 1$,
$w(1) = x$ to the elements of $Y$.  In fact that is why we used the weights
$x^{k}$, rather than separate variables $x_{0},x_{1},\ldots$, say, for
each $k$.  According to the multiplication principle, then, the
generating function for $X$ will be the $n$-th power of that for $Y$.
As for $Y$, it has one element of weight $1$ and one of weight $x$, so
its generating function is $1+x$, and the generating function for $X$
is $(1+x)^{n}$.

This time we have arrived at the generating function $(1+x)^{n}$
without using the binomial theorem.  Since we know that the
coefficient of $x^{k}$ in this generating function is the number of
words with $k$ $0$'s and $n-k$ $1$'s, which is ${n\choose k  }$ by
definition, we have just given a generating function {\it proof} of
the binomial theorem.

\bigskip

\noindent 3.  Generating functions solve infinitely many problems at
once.

\medskip

Up to now we considered the set of $0$--$1$ words of fixed length $n$
and counted them according to the number $k$ of $1$'s.  Let us now try
to solve such problems for all $n$ simultaneously.

For this purpose, we now let $X$ be the set of all words of $0$'s and
$1$'s of all lengths (including the empty word, of length zero).
Notice that $X$ is now an {\it infinite} set; that need not scare us,
however.

First let's just count words by their length.  Thus we assign weight
$x^{n}$ to a word of length $n$.  The generating function for $X$ will
now be a power series $f(x) = \sum c_{n}x^{n}$ in which the
coefficient $c_{n}$ of $x^{n}$ is the number of words of length $n$.
We already know this is $2^{n}$ but let's forget this for a moment.

We will find $f(x)$ by a little algebra.  First, $X$ consists of
$X_{1} = \{$the empty word$\}$ and $X_{2} = \{$all other words$\}$.
The empty word has weight $x^{0} = 1$, so $X_{1}$ has generating
function $f_{1} = 1$.  By the addition principle,
$$ f(x) = 1 + f_{2}(x), $$
where $f_{2}$ is the generating function for $X_{2}$.

Each word in $X_{2}$ has an initial symbol, being non-empty, and so we
can describe words in $X_{2}$ by pairs $(a,u)$ in which $a$
is the first symbol, and $u$ is the rest of the word.  As $a$ takes the
values $0$ and $1$, and $u$ ranges over all words, including the empty
word, the pair $(a,u)$ ranges over all non-empty words, giving each
just once, so we have a bijection $X_{2}\cong Y\times X$, where $Y =
\{0,1 \}$ as before.

  The length of the word $(a,u)$ is one more than
the length of $u$, so its weight is $x$ times the weight of $u$.  Thus
the weights are multiplicative if we assign weight $x$ to each element
of $Y$.  This gives $x+x = 2x$ for the generating function of $Y$.
The generating function for $X$ is $f(x)$ by definition.  By the
multiplication principle we conclude that
$$ f_{2}(x) = 2xf(x) $$
and hence that 
$$ f(x) = 1 + 2xf(x). $$
Doing the algebra you get
$$ f(x) = \frac{1}{1-2x}. $$

Now remember from calculus how to expand this as a power series: it
is a geometric series
$$ \frac{1}{1-2x} = \sum _{n = 0}^{\infty }(2x)^{n} = \sum
_{n}2^{n}x^{n}. $$
Thus the coefficient of $x^{n}$, which counts words of length $n$,
turns out to be  $2^{n}$, as it should be.

\bigskip

\noindent 4.  Generating functions with more than one variable.

\medskip

Let's retain the set $X$ of all $0$--$1$ words of every possible
length, but modify the weights so we can count words by not only their
length but also the number of $0$'s and $1$'s.  Thus instead of giving
$0$ and $1$ the weight $x$ each, let us give the word $1$ the weight
$x$ and $0$ the weight $y$.  For multiplicative weights, the general
word will then have weight $x^{k}y^{n-k}$ if it has $k$ $0$'s and
$n-k$ $1$'s.

Denoting the new generating function for $X$ by $g(x,y)$, we have 
$$ g(x,y) = 1+g_{2}(x,y),\quad  g_{2}(x,y) = (x+y)g(x,y) $$
exactly as before, where now $x+y$ is the generating function for the
set $Y = \{0,1 \}$.  From algebra we get
$$ g(x,y) = \frac{1}{1-(x+y)} = \sum _{n}(x+y)^{n}. $$
The coefficient of $x^{k} y^{n-k}$ in this power series is the number
of words with $k$ $1$'s and $n-k$ $0$'s, or ${n\choose k }$.  This
corresponds to the algebraic fact that 
$$ (x+y)^{n} = \sum _{k}{n\choose k}x^{k}y^{n-k}, $$
which is the binomial theorem in two variables.

\bigskip

\noindent 5.  The repetition principle.

\medskip

The examples in sections 3 and 4 are instances of a more general
principle which follows from the addition and multiplication
principles by the same algebraic calculation we made above.  We can state it
as follows.

\medskip

{\it Repetition principle.}  Suppose $X$ consists of all sequences of
every length (including zero) of independently chosen elements of $Y$.
If weights are multiplicative, so that the weight of a sequence
$(a_{1},\ldots,a_{n})$ is the product $w(a_{1})\cdots w(a_{n})$, then
the generating function for $X$ is $1/(1-g)$, where $g$ is the
generating function for $Y$.

\medskip

Proof:  let $f$ be the generating function for $X$.  Expressing $X$ as
the union of $X_{1}$ containing the empty sequence and $X_{2}$
containing all others, we get $f = 1+ f_{2}$ by addition and $f_{2} =
gf$ by multiplication, using the correspondence (non-empty sequence of
elements from $Y$)$\rightarrow $(initial element, rest of sequence).  Now $f
= 1/(1-g)$ follows from algebra.

\bigskip

\noindent 6.  Summary of the principles.

Most of the time ordinary generating functions are used in a context
where things are being counted according to their ``size'' $n$, using
the weight $x^{n}$, which will be multiplicative if sizes are additive
in forming pairs and sequences.  It may be helpful to summarize the
principles in informual language for this situation.

\medskip

Suppose we want to count ``$f$-things,'', ``$g$-things'',
``$h$-things'', according to their ``size.''  Let $f_{n}$, $g_{n}$,
$h_{n}$ be the number of the respective things of size $n$.  Thus
$F(x) = \sum f_{n}x^{n}$, $G(x) = \sum g_{n}x^{n}$, $H(x) = \sum
h_{n}x^{n}$ are the generating functions counting the various things.

\medskip

{\it Addition principle:}  If the set of $f$-things
corresponds to the disjoint union of the $g$-things and the
$h$-things, with the same ``size'' function, then $F(x) = G(x) +
H(x)$.

\medskip

{\it Multiplication principle:}  If to choose an $f$-thing of
unrestricted size we can independently choose first a $g$-thing and
then an $h$-thing, and if the size of the resulting $f$-thing is the
sum of the sizes of the chosen $g$-thing and $h$-thing, then $F(x) =
G(x)H(x)$.

\medskip

{\it Repetition principle:} If $f$-things correspond to sequences of
any number (including zero) of independently chosen $g$-things, and
the size of such a sequence is the sum of the sizes of its elements,
then $F(x) = 1/(1-G(x))$.

\bigskip

\noindent 7.  Some more examples.

\medskip

Fix a set $N$ with $n$ elements.  We will count all subsets of $N$
according to their size $k$.  We can independently choose whether to
include each element $a\in N$ or not.  If we do, it contributes $1$ to
the size of the final set, if not it contributes $0$.  The generating
function for each such choice is $1+x$ and we get the generating
function for all subsets by multiplying these together for 
$$ (1+x)^{n} = \sum {n\choose k }x^{k}. $$
This is the of course the same thing we did with $0$--$1$ words, in
slightly different language.

\medskip

Next we will count all multichooses from $N$ according to their total size
$k$.  We can independently select how many copies of each element $a$ to
include in our multichoose.  Our choice contributes to the total size the
number of $a$'s we select.  Note that this amounts to choosing
a sequence of $a$'s of any length, where the size of each $a$ is $1$.  By
repetition, the generating function for the choice of any number of
$a$'s is $1/(1-x)$.  The generating function for all multichooses
comes from multiplying these together for
$$ \frac{1}{(1-x)^{n}} = \sum {n\atopwithdelims\langle  \rangle k }x^{k}. $$

With this simple example we have accomplished something we were unable
to do before: give a {\it direct} combinatorial enumeration of
multichooses.  Remember that we were only able to compute
${n\atopwithdelims\langle  \rangle k }$ before by using a tricky
bijection to get ${n+k-1\choose k }$.  No such trick is
needed to compute the generating function.

These two examples also explain the mystical relationship
$$ {n\atopwithdelims\langle  \rangle k} = (-1)^{k}{-n\choose k }. $$
Namely, 
$$ \frac{1}{(1-x)^{n}} = (1+(-x))^{-n} = \sum _{k}{-n\choose
k}(-x)^{k} = \sum _{k}(-1)^{k}{-n\choose k }x^{k} $$
by the binomial theorem.  From the generating function point of view,
the expression $(-1)^{k}{-n\choose k }$ is really the most natural
formula for ${n\atopwithdelims\langle  \rangle k}$.  Note that
${-n\choose k} = (-n)_{k}/k! = (-n)(-n-1)\cdots (-n-k+1)/k! =
(-1)^{k}n(n+1)\cdots (n+k-1) = (-1)^{k}{n+k-1\choose k}$, so the new formula is
equivalent to our earlier one.

\medskip

In your textbook, the use of generating functions to solve recurrences
is explained.  An example discussed there is the Fibonacci numbers
$f_{n}$ defined by $f_{0} = 0$, $f_{1} = 1$, $f_{n} = f_{n-1}+f_{n-2}$
for $n\geq 2$.  The Fibonacci number generating function $F(x) = \sum
f_{n}x^{n}$ is then computed to be $F(x) = x/(1-x-x^{2})$.

Let us do an example of a combinatorial problem that leads to
Fibonacci numbers.  We shall count words of $0$'s and $1$'s in which
every $1$ is followed by a $0$.  We count them by their size $n$ =
length of the word.  Since every $1$ must have a $0$ after it we can
construct our words by putting together the words $0$ and $10$ in any
number and any order.  In short, what we are counting is equivalent to
sequences from the set $Y = \{0, 10 \}$.  The set $Y$ has one element
of size $1$ and one of size $2$, so its generating function is $x +
x^{2}$.  By the repetition principle, the generating function for all
our words is $G(x) = 1/(1-x-x^{2})$.

The fact that $xG(x) = F(x)$ means the coefficient of $x^{n}$ in
$G(x)$ is that of $x^{n+1}$ in $F(x)$, namely $f_{n+1}$.  We conclude that
the number  of $0$--$1$ words of length $n$ in which every $1$ has a
$0$ following it is equal to the Fibonacci number $f_{n+1}$.

\end{document}
