\input lmacros
\documentstyle[12pt]{article}
\newcommand{\cA}{{\cal A}}
\newcommand{\cB}{{\cal B}}
\newcommand{\cC}{{\cal C}}
\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:  Exponential generating functions.}
\end{center}

Let $\cA$ be some set of finite sequences of symbols, such that
for every $n$, $\cA$ contains only finitely many sequences of length $n$.
(We call the set of symbols that occur in $\cA$-sequences the {\it alphabet}
of $\cA$.)
If we let $a_n$ be the number of sequences of length $n$ in $\cA$,
then we define
$$A(x) = \sum_{n=0}^\infty a_n \frac{x^n}{n!}$$
to be the exponential generating function associated with the set $\cA$.

Examples:
\begin{itemize}
\item
$\cA$ = the set of sequences of R's and B's.
Then $a_n = 2^n$ and
$A(x) = \sum 2^n \frac{x^n}{n!} = \sum \frac{(2x)^n}{n!} = e^{2x}$.
\item
$\cB$ = the set of sequences of W's of even length.
Then $b_n = 1$ for $n$ even and 0 for $n$ odd,
so that
$B(x) = 1 + \frac{x^2}{2!} + \frac{x^4}{4!} + ... = \frac{e^x + e^{-x}}{2}$.
\item
$\cC$ = the set of sequences of R's, B's, and W's having an even number of W's.
Then Brualdi shows that $C(x) = \frac{e^{3x}+e^x}{2}$.
\end{itemize}

Note that in the above examples,
a sequence of length $n$ in $\cC$ is specified
by dividing $\{1,2,...,n\}$ into two subsets $I$ and $J$,
specifying an $\cA$-sequence on $I$,
and specifying a $\cB$-sequence on $J$.
(More precisely, if we have $I = \{i_1,i_2,...,i_r\}$
and $J = \{j_1,j_2,...,j_s\}$
with $i_1 < i_2 < ... < i_r$
and $j_1 < j_2 < ... < j_s$,
then an an $\cA$-sequence $\alpha_1,...,\beta_r$
and a $\cB$-sequence $\beta_1,...,\beta_s$
determine
a $\cC$-sequence $\gamma_1,...,\gamma_n$
via
$\gamma_{i_1} = \alpha_1, ... , \gamma_{i_r} = \alpha_r,
\gamma_{j_1} = \beta, ... , \gamma_{j_s} = \beta_s$.)
Note also that in the above examples $C(x) = A(x)B(x)$.
This is no accident,
but a special case of a general principle.

{\sc Multiplication Principle:}  Suppose $\cA$ and $\cB$ are sets of
finite sequences of the sort considered above.  Suppose for simplicity
that the symbols that occur in $\cA$-sequences are all distinct from
the symbols that occur in $\cB$-sequences.  Let $\cC$ be the set of
sequences obtained by interspersing an $\cA$-sequence with a 
$\cB$-sequence.  Then $C(x)=A(x)B(x)$, where $A(x)$, $B(x)$, and $C(x)$
are the exponential generating functions for $\cA$, $\cB$, and $\cC$
respectively.

Proof: Fix $n \geq 0$ and $0 \leq k \leq n$.  Then there are $n \choose k$
ways to divide $\{1,2,...,n\}$ into two subsets $I$ and $J$ (the former
of size $k$ and the latter of size $n-k$), $a_k$ ways to choose an
$\cA$-sequence of length $k$, and $b_{n-k}$ ways to choose a $\cB$-sequence
of length $n-k$.  Multiplying these numbers together and letting $k$ vary,
we see that 
$$c_n = \sum_{k=0}^n {n \choose k} a_k b_{n-k},$$
whence
$$\frac{c_n}{n!} = \sum_{k=0}^n \frac{a_k}{k!} \frac{b_{n-k}}{(n-k)!}.$$
But the right hand side is the coefficient of $x^n$ in $A(x)B(x)$.
Therefore $C(x) = A(x)B(x)$ as claimed.

What if some of the symbols that occur in the $\cA$-sequence also occur
in some $\cB$-sequences?  Then there may no longer be a way to uniquely
pull apart a $\cC$-sequence into an $\cA$-sequence and a $\cB$-sequence,
so the above principle may no longer apply.  However, in many cases we
can purposefully re-define $\cA$ and $\cB$ 
so that their underlying alphabets are disjoint.

Here is an example: Take $\cC$ as above.  Then $C(x)$ is the simultaneously the
exponential generating function for $\cC$ and the
exponential generating function for $\cC'$, where
$\cC'$ = the set of sequences of r's, b's, and w's having an even number of w's.
Hence $[C(x)]^2$ is the exponential generating function for
the set of sequences of R's, B's, W's, r's, b's, and w's having
an even number of W's and an even number of w's.

Here is an even simpler example: $e^x$ is the exponential generating function
for sequences of arbitrary length, with only one allowed symbol.  The allowed
symbol can be R, or it can be B.  If intersperse the two kinds of
sequences -- that is, if we allow both R's and B's -- then the exponential
generating function should be $e^x e^x = e^{2x}$, which it indeed is.

So much for the combinatorial significance of multiplying two
exponential generating functions.
Of course, we know the combinatorial significance of {\it adding}
two exponential generating functions; if $A(x)$ is the exponential
generating function for the set $\cA$ and $B(x)$ is the exponential
generating function for the set $\cB$, then $A(x)+B(x)$ is the
exponential generating function for the set $\cA \cup \cB$, assuming
that $\cA$ and $\cB$ are disjoint.

Now comes a surprising fact (which to my knowledge has no analogue
in the theory of ordinary generating functions): $e^{A(x)}$ has
a natural combinatorial interpretation!

Specifically, suppose $\cA$ is a collection of sequences, with
exponential generating function $A(x)$.  Assume that $\cA$ does
not contain the empty (length 0) sequence, so that $A(x)$ has no
constant term.  {\it (This hypothesis is crucial!)}
Then the coefficient of $x^n/n!$ in $e^{A(x)}$ is the
number of ways of dividing $\{1,2,...,n\}$ into non-empty blocks
and specifying an $\cA$-sequence on each block.

We will not prove this here, though if time permits we will prove it later
in the context of the ``theory of structures''.

\end{document}
