Exponential generating functions

Let $a_n$ count structures on a specified n-element label set, with relabeling transporting structures consistently. Define its EGF using coefficients $a_n/n!$. This is not the number of unlabeled isomorphism classes. A labeled graph can have many labelings of the same underlying shape, and internal automorphisms affect their number. Dividing labeled counts by n factorial therefore does not generally count unlabeled shapes. The factorial denominator is an algebraic normalization for manipulating label allocations.

If an object consists of an A-structure and a B-structure on disjoint complementary label sets, first choose which k labels belong to A, then choose each component. This introduces a binomial factor absent from an ordinary size-only product. After dividing by the total-size factorial, the factor separates into the two component factorial denominators. Thus the ordinary multiplication of the two EGFs automatically performs the required labeled counting. Components must still be ordered by their roles; swapping A and B is not silently identified.

Suppose a structure is an unordered set of j nonempty labeled components, each from one component class. Temporarily order the components, use the labeled product rule, and divide by j factorial. This division is valid because the disjoint nonempty label sets distinguish all component positions: permuting the order has no fixed ordered tuple except the identity permutation. The argument would fail for indistinguishable empty components, which is why the component class must have no zero-size object.

Summing over all j gives the exponential formula $A(x)=\exp(B(x))$. At a fixed total degree only finitely many component counts contribute when $B(0)=0$, so the identity is formal over a characteristic-zero coefficient field. For set partitions, a single block is a nonempty set of labels with one structure on each label set. Its EGF is $e^x-1$, and a set of blocks consequently has EGF $\exp(e^x-1)$. The two exponentials represent two distinct structural levels, not an arbitrary algebraic trick.

Formal differentiation shifts coefficients in a useful labeled way: differentiating an EGF describes a structure with one additional distinguished label outside the ordinary label set. By contrast multiplying by the bookkeeping symbol after differentiating marks one of the labels already present. These interpretations differ by a size shift, so the meaning of a mark should be stated explicitly. Such operations can derive recurrences without ever assigning a numerical value to the series.

An EGF may have a positive, zero, or infinite radius of analytic convergence depending on coefficient growth after normalization. The formal exponential formula remains a coefficient identity wherever the finite labeled construction applies. If one later evaluates it numerically, exchanges limits, or uses complex singularities for asymptotics, convergence must be established separately. This distinction is particularly important for graph classes, whose labeled counts can grow faster than the factorial normalization removes. A symbolic equality is not permission to sum a divergent numerical series.