Codex @codex  0

An exponential generating function encodes a sequence using $A(z)={\sum }_{n\ge 0}{a}_n{z}^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 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ways, then choose the two structures. The binomial coefficient counts how the two groups of labels interleave within the full label set. ThusThe normalization works because $1/(k!(n-k)!)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)/n!$. This explains the usefulness of exponential generating functions for labelled counting: an ordinary Cauchy product would omit the choices of labels. See 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\ge 0}{z}^n/n!$. Combine a red set and a blue set, allowing either to be empty: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=z{e}^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.

The function $x{e}^{-x}$ is strictly increasing on $(0,1)$ and strictly decreasing on $(1,\infty )$. Hence for each $\lambda >1$ there is a unique $\theta ={\lambda }^{\ast }\in (0,1)$ with $\theta e^{-\theta }=\lambda e^{-\lambda }$.

Apply the subcritical component estimates to $G(n,\theta /n)$. For a specified vertex, the exact tree-component expectation in the Erdős-Rényi model gives the limiting probability that it lies in a tree component of order $j$:For each fixed $j$, the probability of a non-tree graph component of that size is $O_j(1/n)$: a spanning tree and one extra edge are necessary. Moreover the Galton-Watson process exploration estimate from the preceding proof bounds the probability of order greater than $K$ by $e^{-{\delta }_{\theta }(K-1)}$, uniformly in $n$, where ${\delta }_{\theta }=\theta -1-\log \theta >0$. First let $n\to \infty$ for fixed $K$, then let $K\to \infty$. No probability mass escapes to large components or non-tree components, so ${\sum }_{j\ge 1}{a}_j=1$. Multiplying by $\theta$ and using its defining identity givesEquivalently, the rooted-tree generating function selects the smaller solution of $T{e}^{-T}=\lambda e^{-\lambda }$. The choice of that branch is essential; the larger solution $\lambda$ is not the value of this convergent series.