\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:  Exponential generating functions and structures.}
\end{center}

\noindent 1.  The concept of a structure.

\medskip

Consider the following counting problems: (1) to find for each $n$ the
number of partitions of an $n$-element set, (2) to find for each $n$
the number of permutations of an $n$-element set, (3) to find for each
$n$ the number of subsets of an $n$-element set, (4) to find for each
$n$ the number of ways of arranging the $n$ elements of an $n$-element
set to be the nodes of a tree.

The preceding problems are of a different nature than those we solve using
ordinary generating functions.  The difference is that the things to
be counted are tied to a specified $n$-element set for each $n$.  For
instance, if we wish to list all partitions of a $5$-element set, we
can do it only by introducing a particular $5$-element set to work
with.  Thus we might use the set $\{a,b,c,d,e \}$ and begin listing
the partitions $\{\{a,b \},\{c,d,e \} \}$, $\{\{c \},\{a,b,d,e \} \}$,
and so on.  On the other hand if we wish to list all partitions of the
{\it number} $5$, there is no underlying set of $5$ elements to be
introduced; we just list the possibilities: $(5)$, $(4,1)$ and so on.

What is common to the problems listed at the outset is that in each,
we begin for each $n$ with a set of $n$ elements, and then we are
asked to count all possible ways of imposing a certain {\it structure}
upon that given set.  Thus for a partition, we are to structure the
set by arranging its elements into blocks.  For a permutation, we are
to arrange them in some order.  For a subset, we are to arrange them
into those chosen to belong to the subset, and those not.  For a tree,
well, we are to arrange them into a tree.

The purpose of exponential generating functions is to solve counting
problems like those we have been discussing: problems in which some
kind of structure is given and we are asked to find for each $n$ the
number of ways to arrange the elements of an $n$-element set into such
a structure.

For such problems, we define the {\it exponential generating function}
to be
$$ F(x) = \sum _{n}f(n)\frac{x^{n}}{n!}, $$
where $f(n)$ is the
number of structures on an $n$-element set.  For the moment, we will
have to accept this as a good definition on faith.  Its justification
will be the fact that this definition leads to addition and
multiplication principles (and other principles, as we shall see) that
are appropriate to structure-counting problems.

\bigskip

\noindent 2.  Trivial structures.

\medskip

Before it is possible to work any examples with exponential generating
functions it is necessary to build a small repetoire of generating
functions for some seemingly stupid ``structures.''  We call them {\it
trivial} structures because the structures themselves have little
content.  Nevertheless we will find that their generating functions
are not in any sense ``trivial,'' but may be interesting functions.
Furthermore these structures are not at all ``trivial'' in their
usefulness, for every structure we consider will have these as
building blocks at some level.

We begin with {\it the trivial structure}, which is the structure of
``being a set.''  What we mean is that to impose the trivial structure
on a given set is to give the elements only that structure which they
already have: the structure of a set.  The point is, there is just one
such structure on every set.  Thus the number of trivial ``being a set''
structures on an $n$-element set is $f(n) = 1$ for every $n$.  The
exponential generating function for this trivial structure is
therefore 
$$ F(x) = \sum_{n=0}^{\infty } \frac{x^{n}}{n!}  = e^{x}. $$
Notice the generating function for this most trivial structure is not
a trivial function at all.

More generally, we can consider trivial structures that amount to
restrictions on the size of a set.  The simplest such restriction is
the structure of ``being a 1-element set.''  To impose this structure
on a 1-element set is to give it only the structure it already
has---but to impose it anything but a one element set is impossible.
In short, there is one strucutre of ``1-element set'' on every
1-element set, and none on any other set.  In other words, the number
of trivial ``1-element set'' structures on an $n$-element set is $f(n)
= 1$ if $n =1$, $0$ otherwise.  The corresponding generating function
is 
$$ F(x) = \sum _{n}f(n)\frac{x^{n}}{n!} = x. $$

In a similar way, corresponding to any restriction we might care to place
on the size of a set we can define a trivial structure reflecting that
restriction.  
By definition there is to be one such structure on an
set if it obeys the restricition, and none if it doesn't.  The number
$f(n)$ of our trivial structures on an $n$-element set is thus, by
definition, the {\it indicator function} that is $1$ for good values
of $n$ and $0$ for bad values.  The exponential generating function
$F(x) = \sum _{n}f(n)x^{n}/n!$ for our trivial structure is then
simply the sum of $x^{n}/n!$ taken over all allowed values of $n$.
Fortunately, in many cases this is simple to express in closed form,
as in the two examples we just did.

Here is a summary of some of the most useful trivial structures:

(1) The trivial structure of ``set'': $F(x) = e^{x}$.

(2) The trivial ``1-element set'' structure: $F(x) = x$.

(3) The trivial ``empty set'' structure: $F(x) = 1$.

(4) The trivial ``non-empty set'' structure: $F(x) = e^{x}-1$.

\bigskip

\noindent 3.  Addition and multiplication principles.

\medskip

To count things with exponential generating functions, we need to know
when to add and multiply them.  To state the relevant principles,
let's suppose that we have given names to some kinds of structures, say
$f$-structures, $g$-structures, and $h$-structures.  We let $f(n)$ be
the number of $f$-structures on an $n$-element set, so the exponential
generating function counting $f$-structures is $F(x) = \sum
f(n)x^{n}/n!$.  Similarly for $g$ and $h$.

\medskip

\noindent {\it Addition principle for exponential generating functions:}
Suppose that choosing an $h$-structure on a set corresponds to
choosing either an $f$- or a $g$-structure on the set, and the
possibilities are mutually exclusive.  Then
$$ H(x) = F(x) + G(x). $$

\medskip

\noindent {\it Multiplication principle for exponential generating
functions:}  Suppose that to choose an $h$-structure on a set $S$,
you first make an ordered partition of the set $S$ into two subsets
$A$ and $B$, then you choose an $f$-structure on $A$ and a
$g$-structure on $B$.  If there is no restriction on the partition into
$A$ and $B$, except that $f$-structures should
exist on $A$ and $g$-structures on $B$, and if the $f$-structure on
$A$ and the $g$-structure on $B$ may be chosen independently of each
other once the partition into $A$ and $B$ has been made, then 
$$ H(x) = F(x)G(x). $$

It is also useful to state the version of the multiplication
principle for multiplying three or more generating functions:  Suppose
that to choose an $h$-structure on a set $S$ you first make an ordered
partition of $S$ into three subsets $A,B,C$ and then
independently choose an $e$-structure on $A$, an $f$-structure on $B$,
and a $g$-structure on $C$.  Then $H(x) = E(x)F(x)G(x)$.  Similar
principles hold for multiplying more than three generating functions.

\bigskip

\noindent 4.  Some examples.

\medskip

(1) Let us find the exponential generating function for the number of
subsets of an $n$-element set.  To choose a subset of $S$ is to make
an ordered partition of $S$ into $A = $ the subset, and $B = $ the
complementary subset.  No further structure is imposed on $A$ or $B$,
which is to say we have the {\it trivial} structure on each of them.
Thus we apply the multiplication principle with $F(x)$ and $G(x)$ both
equal to the trivial structure generating function $e^{x}$ to come up
with 
$$ e^{x}e^{x} = e^{2x} = \sum _{n}\frac{(2x)^{n}}{n!} = \sum
_{n}2^{n}\frac{x^{n}}{n!} $$
as the generating function counting subsets.  Naturally this accords
perfectly with our prior knowledge that $2^{n}$ is the number of
subsets of an $n$-element set.

(2) Modifying the previous example a bit, let us find the generating function
counting {\it non-empty} subsets of an $n$-element set.  We still have
trivial structure on $B$, but we are now imposing the structure of
non-empty set on $A$.  Thus we get
$$ (e^{x}-1)e^{x} = e^{2x}-e^{x} = \sum _{n}(2^{n}-1)\frac{x^{n}}{n!}, $$
again finding the answer we expected.

(3) Let us fix a number $k$ and count functions from an $n$-element
set to $\{1,\ldots,k \}$.  As a structure on the $n$-element set $S$,
choosing a function amounts to choosing for each $i = 1,\ldots,k$
which elements of $S$ map to $i$.  In other words we are choosing an
ordered partition of $S$ into $k$ blocks with no further structure on
the parts.  Therefore we should multiply together $k$
trivial-structure generating functions to get
$$ (e^{x})^{k} = e^{kx} = \sum _{n}k^{n}\frac{x^{n}}{n!} $$
as the generating function counting functions with values in $\{
1,\ldots,k \}$ on an $n$-element set.

(4) The last example might seem terribly elementary, but consider
this slight variation:  we will count {\it surjective} functions on an
$n$-element set
with values $\{1,\ldots,k \}$.  The only difference is that now for
each $i$ the block of elements in $S$ mapping to $i$ must be
non-empty.  In other words we are counting ordered partitions of $S$
into $k$ non-empty blocks.  This means blocks whose structure is that of
trivial non-empty set.  So we can do this problem as easily as the
last one; the generating function we want will be
$$ (e^{x}-1)^{k}. $$

Now we know already that the number of ordered partitions of an
$n$-element set into $k$ non-empty blocks is $k!S(n,k)$.  Therefore we
have 
$$ (e^{x}-1)^{k} = \sum _{n}k!S(n,k)\frac{x^{n}}{n!}, $$
or
$$ \frac{(e^{x}-1)^{k}}{k!} = \sum _{n}S(n,k)\frac{x^{n}}{n!}. $$
So we have come up with an exponential generating function for the
Stirling numbers $S(n,k)$ as $n$ varies, using only extremely simple
combinatorial considerations.  By contrast an ordinary generating
function for these same numbers can only be arrived at through a
tricky and subtle bijection.

(5) In the last part of example (4) we have found the exponential
generating function counting unordered partitions of an $n$-element
set into $k$
blocks (of which there are $S(n,k)$).  Summing for all $k$ we can
count {\it all} partitions of an $n$-element set; their exponential
generating function will be
$$ \sum _{k} \frac{(e^{x}-1)^{k}}{k!} = e^{e^{x}-1} = \sum
_{n}B_{n}\frac{x^{n}}{n!},$$
where 
% you will recall that 
the Bell number $B_{n}$ 
% was 
is
defined to be
the number of all partitions of an $n$-element set.

Notice a curious fact: the Bell number generating function we just
found turns out to have the form $F(G(x))$ with $F(x) = e^{x}$ the
generating function for the trivial structure and $G(x) = e^{x}-1$ the
generating function for the trivial non-empty structure.  We shall
explain this and much more later on.

(6) We now count permutations of an $n$-element set.  If $n=0$, so the
set is empty, we'll agree that there is 1 ``empty'' permutation.
Otherwise, we can choose a permutation recursively like this: first
decide the first element (this makes sense for a non-empty set), then
decide how to permute the rest (this works even when $n=1$ since we
agreed there is one permutation of an empty set).  Making these
decisions amounts to this: partition the set into $A$ and $B$, impose
the trivial 1-element set structure on $A$, and choose a permutation
of $B$.  If $F(x)$ stands for the generating function counting
permutations we get
$$ F(x) = 1 + xF(x), $$
where $1$, the trivial ``empty set'' generating function, counts the
empty permutation, and $xF(x)$ counts permutations of non-empty sets
by the multiplication principle.  By algebra we find
$$ F(x) = 1/(1-x) = \sum _{n}x^{n} = \sum _{n}n!\frac{x^{n}}{n!}, $$
in agreement with our knowledge that there are $n!$ permutations of an
$n$-element set.

Notice that this computation has {\it nothing} to do with the
``repetition principle'' for ordinary generating functions.  We are
dealing here with $1/(1-x)$ as an exponential generating function, and
it doesn't count repetitions of anything.

(7) Only one of the examples we mentioned at the start is not yet
done:  counting trees with nodes taken from an $n$-element set.  This
problem has many versions, which we can consider in detail elsewhere.
However, let us do one variant.  We will count  binary trees
whose nodes, including the root, come from an $n$-element set.  We
agree that there is one empty binary tree.

To choose a non-empty binary tree on a set $S$, we partition $S$ into
three parts: the root node, the left subtree, and the right subtree.
We just want one root node, so the structure for its part will be the
trivial 1-element set structure.  Each of the other parts will of
course have again the structure of binary tree, counted let us say
by $T(x)$.  Thus 
$$ T(x) = 1+xT(x)^{2}, $$
so
$$ T(x) = \frac{1-\sqrt{1-4x}}{2x} = \sum _{n}C_{n}x^{n} = \sum
_{n}n!C_{n}\frac{x^{n}}{n!}, $$
where $C_{n}$ is a Catalan number.

It might appear there is no difference between this example and our earlier
computation of the ordinary generating function for Catalan numbers.
But there is actually a profound difference.  What we counted here was
not abstract binary trees but binary tree stuctures on a set.  And
indeed we do {\it not} find $C_{n}$ of them but $n!C_{n}$ of them,
since this is an exponential generating function.  The confusion results
from the accident that the exponential generating function for
$n!C_{n}$ and the ordinary generating function for $C_{n}$ are the
same.  This accident happened because binary trees are ordered, and
indeed when we count unordered trees no such phenomenon will occur.

\bigskip

\noindent 5.  The functional composition principle.

\medskip

We are now going to discover the real power of exponential generating
functions.  This power comes from the fact that if $F(x)$ and $G(x)$
are exponential generating functions, then the functional composition
$F(G(x))$ has a combinatorial interpretation.

In order to form $F(G(x))$, $G(x)$ must be a {\it delta}
series, meaning a power series whose constant term is zero.
Combinatorially, that means that $G(x)$ must count structures that
exist only on non-empty sets, since it says $g(0)$, the number of
$g$-structures on the empty set, is zero.  Algebraically, the delta
series requirement is necessary for $F(G(x))$ to even make sense:
without introducing functions and convergence, you cannot even define
composition of formal power series unless $G(x)$ is a delta series.

\medskip

\noindent {\it Composition principle:}  Suppose an $h$-structure on
$S$ consists of (1) a partition of $S$ into any number of blocks, (2)
independently chosen $g$-structures on the various blocks, and (3) an
$f$-structure, chosen independently of the $g$-structures, on the set
of blocks.  If $G(x)$ is a delta series, then $H(x) = F(G(x))$.

There is an important point to be made about the way in which the
partition is to be chosen when applying the composition principle.
From the definition, the partition should be chosen freely first, and the
particular $f$- and $g$-structures chosen after that.  Thus it would
seem there could be no restrictions on the number of blocks or on the
block sizes.  However, there are always implicit restrictions imposed
by the necessity for the $f$- and $g$-structures to exist.  In
particular, we can create restrictions by using appropriate trivial
structures for $f$ or $g$.

A second point relates to the requirement that $G(x)$ be a delta
series.  Notice that in forming an $h$-structure, you choose
$g$-structures on the blocks, which are always non-empty.  Thus
combinatorially it makes no difference how many $g$-structures are
assumed to exist on the empty set.  So if we have obtained $G(x)$
combinatorially, and  it is not a delta series, we are free to first
modify it into a delta series by subtracting its constant term, and
then apply the composition principle.

\bigskip

\noindent 6.  Composition principle examples.

\medskip

(1) Consider again the Bell number generating function $e^{e^{x}-1}$
which counts all partitions of an $n$-element set.  Using composition
we can get this directly.  To choose a partition, we choose a
partition.  There is no additional structure within the blocks or
among the blocks, so $F(x)$ and $G(x)$ should count trivial
structures.  However, $G(x)$ must be a delta series, so it should be
the trivial non-empty structure $e^{x}-1$.  $F(x)$ will be $e^{x}$
(since we allow the unique empty partition of the empty set), and the
composition is $F(G(x)) = e^{e^{x}-1}$.

(2)  The previous example admits all manner of modifications.  For
instance, we can count partitions of an $n$-element set into blocks of
more than one element as 
$$ e^{e^{x}-1-x} $$
using $F(x)=e^{x}$ for trivial structure among the blocks and $G(x) =
e^{x}-1-x$ for the trivial ``set of more than one element'' structure
in each block.  Or we can count partitions into more than one block by
using $F(x) = e^{x}-1-x$ and $G(x) = e^{x}-1$ to get 
$$ e^{e^{x}-1}-1-(e^{x}-1) = e^{e^{x}-1}-e^{x}. $$
Notice that every set has one partition into one block, so a partition
into one block is the same as the trivial structure.  Thus the second
expression above can also be interpreted as (all partitions) $-$ (partitions
into one block).

(3)  Suppose you are asked to rate your preferences among $n$ different
foods, or sports, or whatever.  You may prefer some to others, but
there might also be ones you like equally well.  Thus your ranking of
them all may not be a total ordering of them, but just a partition of
them into groups with an ordering, or equivalently a permutation, of
the set of groups.  Thus a preference order is a composite structure
consisting of a partition, a total ordering or permutation structure
on the set of blocks, and a trivial  structure within each
block.   By composition with $F(x) = 1/(1-x)$ from section 4, example
(6) and $G(x) = e^{x}-1$, the delta series for the trivial non-empty
set structure, we get 
$$ \frac{1}{1-(e^{x}-1)} = \frac{1}{2-e^{x}} $$
as the exponential generating function counting preference orders.

It's worth checking a few terms of this:
$$ \frac{1}{2-e^{x}} = \frac{1}{1-x-x^{2}/2-x^{3}/6-\cdots } = 1 + x
+ 3x^{2}/2 + 13x^{3}/6+\cdots  $$
by long division, so there is 1 empty preference order, 1 pref.\ order
of one thing, 3 possible pref.\ orders among 2 things ($\{a \}\{b \}$,
$\{b \}\{a \}$, and $\{ab \}$), and 13 among 3 things (list them and
check).

(4) Here is a different approach to counting permutations.  Let $L(x)$ be the
generating function counting arrangements of an $n$-element set into a
cycle.  There are $(n-1)!$ cyclic orderings of an $n$-element set.  We
agree there is no empty cyclic ordering, so $L(x)$ will be a delta
series, and
$$ L(x) = \sum _{n=1}^{\infty }(n-1)!\frac{x^{n}}{n!} =
\sum_{n=1}^{\infty } x^{n}/n. $$

Consider a permutation of $S = \{1,\ldots,n \}$ expressed in cycle
notation.  To choose a permutation we partition $S$, and arrange each
block into a cycle.  Among the blocks there is no further structure.
Since our cycle generating function $L(x)$  is a delta series we can
apply composition, with $F(x) = e^{x}$ and $G(x) = L(x)$, and get the
permutation generating function
$$ e^{L(x)}. $$
Now, we already know that the permutation generating function is
$1/(1-x)$, so we get
$$ e^{L(x)} = 1/(1-x), $$
$$ L(x) = \log 1/(1-x) = -\log (1-x). $$
As a result, we have come up with the power series expansion
$$ -\log(1-x)= \sum _{n} x^{n}/n = x+\frac{x^{2}}{2}+\frac{x^{3}}{3}+\cdots  $$
by pure combinatorics and formal algebra, without using any calculus
whatsoever.

\bigskip

\noindent 7.  The derivative principle.

\medskip

\noindent {\it Derivative principle:}  Suppose an $h$-structure on a
set $S$ is the same as an $f$-structure on the set formed by
augmenting  $S$ with an extra element.  Then 
$$ H(x) = F'(x). $$

Here are some examples:

(1) Suppose we arrange the elements of $S$ plus an extra element $*$
into a permutation.  The position of $*$ cuts $S$ into two subsets, so
such a structure is equivalent to partitioning $S$ into blocks $A$ and
$B$, and arranging each into a permutation.  Writing $F(x)$ for the
permutation generating function we obtain 
$$ F'(x) = F(x)^{2}, $$
in accord with the fact that $F(x) = 1/(1-x)$.

(2) We arrange the elements of $S$ into a binary tree with a
distinguished node.  To build this structure, we could first split $S$
into $A = $ the distinguished node and $B = $ the others.  We would
put the trivial ``one-element set'' structure on $A$.  On $B$ we must
put a structure that amounts to arranging $B$ and the additional
distinguished node into a binary tree.  By the derivative principle,
this structure would have generating function $T'(x)$, where $T(x)$ is
the binary tree generating function from section 4, example (7).  By
multiplication we get the generating function $xT'(x)$ for counting
binary tree structures with distinguished node on an $n$-element set.

More generally, if $F(x)$ counts any kind of structure, $xF'(x)$
counts the same structure with a distinguished element.

(3) We will count {\it alternating permutations} of $\{1,\ldots,n \}$
for every $n$.  Alternating means that the permutation has the form
$$ a_{1}<a_{2}>a_{3}<a_{4}>\cdots <a_{n-1}>a_{n}. $$
Note that for this pattern to hold, with a decrease at the last stage,
$n$ must necessarily be odd.  Thus we agree that there is no empty
alternating permutation, and that $1$ is alternating.
Let $F(x)$ be the exponential generating function counting these.
Observe that 
$$ F(x) = x + 2x^{3}/6 + 16x^{5}/120 +\cdots  $$
since there are 2 alternating permutations of $\{ 1,2,3\}$ (namely $132$
and $231$) and 16 of $\{1,2,3,4,5 \}$ (list them and count).

Now consider the problem of arranging into an alternating permuation
the numbers $1,\ldots,n$ plus the extra number $n+1$.  Of course you
can only do this when $n$ is even.  The generating function for this
will be $F'(x)$, which contains only even powers of $x$, as it should.

When $n = 0$ the only number is $n+1=1$ and that by itself is an
alternating permuation.  So $F'(x)$ will have an $x^{0}$ term of $1$.

When $n>0$, you have to put some of the numbers $1,\ldots,n$ before
$n+1$ and the rest after.  Since an alternating permutation begins
with $<$ and ends with $>$, $n+1$ can't be at either end.  Thus the
portions before and after $n+1$ must both be non-empty (it's in this respect
that $n>0$ differs from $n=0$).  In the portion before $n+1$ the last
step must be $>$, since the step to $n+1$ is automatically $<$.  Thus
the first portion is an alternating permutation.  By similar
reasoning, so is the second.  Thus the set $1,\ldots,n$ gets a product
structure: it is divided into a first and second portion and each
portion is arranged into an alternating permutation.  Clearly the
correspondence between such structures on $1,\ldots,n$ and alternating
permutatons on $1,\ldots,n+1$ is bijective.  By the multiplication
principle, the generating function for this structure is $F(x)^{2}$,
and adding $1$ for the case $n=0$ we arrive at
$$ F'(x) = F(x)^{2} + 1. $$
Once we specify the initial value $F(0)$, this equation determines $F(x)$.
In this problem we have $F(0) = 0$.  From calculus you can check that
the solution of our equation with $F(0)=0$ is $F(x) = \tan x$.

Thus we have found a combinatorial interpretation of the coefficients
of the power series for $\tan x$---it is the exponential generating
function for (odd) alternating permutations.

By similar reasoning you can show that $\sec x$ is the exponential
generating function for even alternating permutations (which start and
end with an increasing step, and including the empty permutation).

\bigskip

\noindent A.  Appendix: proof of the principles.

\medskip

In the following, $n$ stands for the number of elements of the set $S$
on which we are choosing a structure.

\medskip

\noindent {\it Addition principle: } To choose an $h$-structure is to choose
either an $f$-structure or a $g$-structure.  Therefore $h(n) =
f(n)+g(n)$, and hence $H(x) = F(x) + G(x)$.

\medskip

\noindent {\it Multiplication principle:}  To choose an $h$-structure
is to choose a partition into $A$ and $B$, with $f$-structure on $A$
and $g$-structure on $B$.  If $|A| = k$, there are ${n\choose k }$
choices of the partition, $f(k)$ choices of $f$-structure, and
$g(n-k)$ choices of $g$-structure.  Summing over $k$ we have 
$$ h(n) = \sum _{k=0}^{n}{n\choose k }f(k)g(n-k) = \sum
_{k=0}^{n}n!\frac{f(k)}{k!}\frac{g(n-k)}{(n-k)!}, $$
so 
$$ h(n)/n! = \sum
_{k=0}^{n}\frac{f(k)}{k!}\frac{g(n-k)}{(n-k)!}. $$
This last sum is precisely the coefficient of $x^{n}$ in $F(x)G(x)$,
showing $H(x) = F(x)G(x)$.

\medskip

\noindent {\it Multiplication principle for more than two factors:}
Assume it works for $k-1$ factors.  Now we want to multiply $k$ factors
$F_{1}(x)$ through $F_{k}(x)$.  By the inductive assumption,
$F_{1}(x)\cdots F_{k-1}(x)$ counts structures consisting of $k-1$
ordered blocks with $f_{i}$-structure on the $i$-th block.
Multiplying by $F_{k}$ with the two factor principle, $F_{1}(x)\cdots
F_{k}(x)$ counts structures consisting of a partition of $S$ into $A$
and $B$, with a further partition of $A$ into $k-1$ ordered blocks
carrying structures $f_{1},\ldots,f_{k-1}$, and an $f_{k}$-structure
on $B$.  But that is equivalent to partitioning $S$ into $k$ ordered
blocks with an $f_{i}$-structure on the $i$-th block.

\medskip

\noindent {\it Composition principle:}  We are to choose a partition with
$f$-structure on the set of blocks and $g$-structure within each
block.  First let's pick $k$, the number of blocks.  Then there will
be $f(k)$ choices for the $f$-structure on the set of blocks.
Moreover, for partitioning $S$ into $k$ ordered blocks and choosing
$g$-structures on each, multiplication gives the generating function
$G(x)^{k}$.  Note that the fact $G(x)$ is a delta series means the
only partitions that count will be those into $k$ non-empty ordered
blocks.  To each partition into $k$ unordered blocks, there are $k!$
ways of ordering the blocks, and the number of ways to choose
$g$-structures within each block is unaffected by whether we assign an
order among the blocks or not.  Therefore the generating function for
partitioning $S$ into $k$ unordered blocks with $g$-structures on each
is $G(x)^{k}/k!$.  Incorporating the further choice of an $f$-structure
on the set of blocks gives $f(k)G(x)^{k}/k!$.  Finally, summing over
all $k$ we obtain the composite 
$$ \sum _{k}f(k)\frac{G(x)^{k}}{k!} = F(G(x)). $$

\medskip

\noindent {\it Derivative principle:}  The derivative of $x^{n}/n!$ is
$x^{n-1}/(n-1)!$.  Therefore if $F(x) = \sum f(n)x^{n}/n!$ then the
coefficient of $x^{n}/n!$ in $F'(x)$ is $f(n+1)$, the number of
$f$-structures on $S$ augmented by an extra element.


\end{document}
