= Exponential generating function
{title2=$A(z)=\sum_{n\geq0}a_nz^n/n!$}
An <exponential generating function> encodes a <sequence> using $A(z)=\sum_{n\geq0}a_nz^n/n!$. For labelled counting, $a_n$ is the number of structures on a fixed <set> of $n$ distinct labels. Labels distinguish otherwise similar objects: changing which person belongs to a group can change the structure. Recover the count by <coefficient extraction> as $a_n=n![z^n]A(z)$. The raw <coefficient> is $a_n/n!$, not $a_n$.
The <factorial> makes <multiplication> account automatically for distributing labels. To combine an $A$-structure on $k$ labels and a $B$-structure on the remaining $n-k$, choose the first label <subset> in $\binom nk$ ways, then choose the two structures. The <binomial coefficient> counts how the two groups of labels interleave within the full label <set>. Thus
$$
A(z)B(z)=\sum_{n\geq0}c_n\frac{z^n}{n!},\qquad c_n=\sum_{k=0}^n\binom nk a_kb_{n-k}.
$$
The normalization works because $1/(k!(n-k)!)=\binom nk/n!$. This explains the usefulness of <exponential generating functions> for labelled counting: an ordinary <Cauchy product> would omit the choices of labels. See https://users.math.msu.edu/users/magyarp/Math482/Old.html[Peter Magyar, Math 482, notes for 2/7, labelled product principle].
For a concrete example, there is one undecorated <set> on any given collection of labels. Its <exponential generating function> is the <exponential function> $E(z)=e^z=\sum_{n\geq0}z^n/n!$. Combine a red <set> and a blue <set>, allowing either to be empty:
$$
E(z)E(z)=e^{2z}=\sum_{n\geq0}2^n\frac{z^n}{n!}.
$$
Every label independently receives one of two colours, giving $2^n$ assignments by the <rule of product>. With three labels, the counts by number of red labels are $1,3,3,1$, totalling eight. Choosing only the two group sizes would give the four possibilities $(0,3),(1,2),(2,1),(3,0)$; it would forget which labels are red.
Indeed, the <ordinary generating function> for the constant <sequence> $a_n=1$ is the <geometric series> $1/(1-z)$. Its square has <coefficient> $[z^n](1-z)^{-2}=n+1$, counting pairs of nonnegative sizes. Both encodings are correct for their respective questions. The decision is whether identity matters when objects are combined.
For unordered <sets> of labelled components of positive size, an <exponential generating function> $B(z)$ becomes $e^{B(z)}$: the term $B(z)^m/m!$ forgets the ordering of $m$ components. The existing <rooted-tree generating function> develops the richer example $T=ze^T$. A labelled <rooted tree> consists of its <root of a tree> and an unordered <set> of smaller labelled <rooted trees>, connecting the same label-distribution mechanism to recursive counting.
Back to article page
