Chapter 25: Combinatorial Species and Structured Enumeration

Why does a set of connected components lead to an exponential formula?

Suppose each of four named tasks is either left alone or paired with exactly one other task. A configuration is a partition of $[4]=\{1,2,3,4\}$ into blocks of size one or two. Its components have no order, and the two members of a pair have no order. Nevertheless, the tasks themselves remain distinguishable. Which divisions by factorials remove just the redundant orderings?

There is one configuration with no pairs, six with one pair, and three with two pairs. The total is $10$. More generally these structures correspond to involutions: permutations $\tau$ satisfying $\tau^2=\mathrm{id}$, whose cycles are singletons and transpositions. We will use $\mathcal I$ for their species and $a_n$ for their number on $[n]$.

The proposed exponential generating function, or EGF, is

$$ I(z)=\sum_{n\geq0}a_n\frac{z^n}{n!}=\exp\left(z+\frac{z^2}{2}\right). $$

The term $z$ represents a singleton; $z^2/2$ represents an unordered pair. The exponential represents an unordered set of these nonempty components. Our task is to justify all three statements through bijections, then determine what changes when labels disappear. A successful solution will also translate this grammar into a random generator with a proved distribution.

The chapter foundation consists of this finite example and the final investigation, which restates the needed grammar and distributions. Sections 25.1–25.10 are optional extensions: they supply a graduate treatment and a bridge to research. The published prerequisites Generating functions and recurrence relations and Group actions and symmetry provide coefficient extraction and orbit counting. Abstract algebra supplies useful language, but no category theory or later chapter is required to carry out the foundation investigation.

25.1 Combinatorial classes and structural decomposition

Optional advanced elective extension; not required to complete the chapter foundation. A class organized only by size records counts. A species also records what happens when labels change. This additional information lets structural identities remain valid for every finite label set, rather than depending on a preferred numbering.

A finite set species $F$ assigns a finite set $F[U]$ of structures to every finite set $U$. To each bijection $\sigma:U\to V$ it assigns a transport bijection $F[\sigma]:F[U]\to F[V]$, with

$$ F[\mathrm{id}_U]=\mathrm{id}_{F[U]},\qquad F[\rho\circ\sigma]=F[\rho]\circ F[\sigma]. $$

These are the identity and composition laws. In categorical language, $F$ is a functor on finite sets and bijections. The displayed laws are all the categorical machinery needed here. Size always means $|U|$, and every vertex or atom in our examples receives one label.

For involutions, $\mathcal I[U]$ is the set of partitions of $U$ into singleton and doubleton blocks. Transport sends each block $B$ to $\sigma(B)$. Equivalently, viewing a structure as a permutation, transport is conjugation:

$$ \mathcal I[\sigma]\bigl(\tau\bigr)=\sigma\tau\sigma^{-1}. $$

This preserves $\tau^2=\mathrm{id}$ because $(\sigma\tau\sigma^{-1})^2=\sigma\tau^2\sigma^{-1}$. It also satisfies both transport laws. Thus the description defines a species, not merely a numerical sequence.

Solved example. Let $U=\{a,b,c\}$ and take the blocks $\{a,c\}$ and $\{b\}$. Under $\sigma(a)=3$, $\sigma(b)=1$, $\sigma(c)=2$, the result has blocks $\{2,3\}$ and $\{1\}$. Renaming cannot turn a pair into two singleton blocks. The component sizes are a structural invariant.

A species isomorphism $F\cong G$ is a family of bijections $\alpha_U:F[U]\to G[U]$ satisfying $\alpha_VF[\sigma]=G[\sigma]\alpha_U$. This condition, called naturality, says that decomposing and renaming commute. A grammar becomes mathematically useful when its parsing and reconstruction maps give such an isomorphism.

Exercise. Show that simple graphs form a species when an edge is an unordered two-element subset of the label set. Hint: transport both endpoints of every edge. Solution: set $G[\sigma]\bigl(E\bigr)=\{\sigma(e):e\in E\}$. A bijection preserves distinct endpoints and distinct edges; its inverse transports back. Applying two transports sends an edge $e$ to $(\rho\circ\sigma)(e)$, proving the composition law.

25.2 Labeled versus unlabeled structures

Optional advanced elective extension; not required to complete the chapter foundation. Fix $[n]=\{1,\ldots,n\}$, with $[0]=\varnothing$. Write $f_n=|F[n]|$. The symmetric group $S_n$ acts through transport. Two structures are isomorphic when they lie in the same orbit; an unlabeled structure means one such orbit, rather than a labeled structure with its printed names erased arbitrarily.

Let $\widetilde f_n=|F[n]/S_n|$. We distinguish

$$ F(z)=\sum_{n\geq0}f_n\frac{z^n}{n!},\qquad \widetilde F(z)=\sum_{n\geq0}\widetilde f_nz^n. $$

The EGF counts labeled objects with a factorial normalization. The ordinary generating function, or OGF, on the right counts isomorphism classes. They generally have different coefficients.

For a structure $s$, its automorphism group is $\operatorname{Aut}(s)=\{\sigma\in S_n:F[\sigma]\bigl(s\bigr)=s\}$. Orbit–stabilizer gives

$$ |\operatorname{Orb}(s)|=\frac{n!}{|\operatorname{Aut}(s)|},\qquad \frac{f_n}{n!}=\sum_{[s]}\frac1{|\operatorname{Aut}(s)|}. $$

Thus dividing the labeled count by $n!$ yields a sum weighted by inverse symmetry, not a count of shapes. It counts shapes only when every automorphism group is trivial.

Exercise. Repeat the classification for $n=3$. Hint: the only possibilities are three singletons or a singleton plus a pair. Solution: their automorphism group sizes are $6$ and $2$, so their orbit sizes are $1$ and $3$. Hence $a_3=4$ and $\widetilde a_3=2$. More generally an involution shape is determined by $j\in\{0,\ldots,\lfloor n/2\rfloor\}$, so $\widetilde a_n=\lfloor n/2\rfloor+1$.

25.3 Species of sets, sequences, cycles, and trees

Optional advanced elective extension; not required to complete the chapter foundation. The same labels can carry very different structures. We use $\mathbf1$ for the species with one empty structure and no nonempty structures, and $X$ for the species with one structure on a singleton and none at other sizes. Their EGFs are $1$ and $z$.

The species $\mathcal E$ has one set structure on every finite label set. The species $\mathcal L$ consists of linear orders, including the empty order. The species $\mathcal C$ consists of nonempty cyclic orders: rotations of a word are identified, but reversal is not additionally identified. In particular, the two cyclic orders on three labels have opposite orientations. Cyclic orders of sizes one and two are allowed; they are not simple graph cycles.

The species $\mathcal A$ consists of nonempty rooted, nonplane trees: finite simple connected acyclic graphs with a distinguished vertex, whose children have no left-to-right order. All vertices, including the root, are labeled.

For cyclic orders, every orbit of rotations of a word of $n$ distinct labels has exactly $n$ words, giving $n!/n$. For sets, orders, and cyclic orders there is one unlabeled object at every admissible size. The tree formulas will be derived in Section 25.7; the table anticipates that derivation.

Solved example and diagram. Each panel below uses exactly $\{1,2,3\}$ and displays one structure. The set panel has no edges. The sequence panel records the two successive comparisons $1\to2$ and $2\to3$. The cycle panel adds $3\to1$. The tree panel has the two undirected edges $\{1,2\}$ and $\{1,3\}$; the highlighted vertex $1$ is the root. The totals under the panels count all structures on this label set, not just the depicted examples.

The rooted-tree total is $3\cdot3=9$: choose one of the three possible two-edge trees, then one of its three roots. Reversing the cyclic-order arrows gives its other labeled structure. Exchanging vertices $2$ and $3$ in the depicted tree is an automorphism, illustrating why a root does not always remove every symmetry.

Exercise. Count each of these species on two labels. Hint: a cyclic order is not an undirected simple cycle. Solution: there are $1$ set, $2$ linear orders, $1$ cyclic order, and $2$ rooted trees. The latter share the unique edge and differ by their root.

25.4 Sum, product, and composition of species

Optional advanced elective extension; not required to complete the chapter foundation. Grammar operations describe exactly how labels are allocated. Throughout, species isomorphisms are understood to commute with transport.

The sum $(F+G)[U]$ is the disjoint union of $F[U]$ and $G[U]$, with a tag recording the chosen alternative. The product allocates labels to an ordered pair of disjoint supports:

$$ (FG)[U]=\bigsqcup_{U=S\sqcup T}F[S]\times G[T]. $$

Here $S$ and $T$ may be empty. This product differs from the Cartesian product $F[U]\times G[U]$ of two structures using the same labels. If $h_n=|(FG)[n]|$, choosing $S$ proves

$$ h_n=\sum_{k=0}^n\binom nk f_kg_{n-k},\qquad (F+G)(z)=F(z)+G(z),\qquad(FG)(z)=F(z)G(z). $$

Solved product example. An $X\mathcal E$-structure is a set with one distinguished member. On $[3]$, choose that member in three ways; the other two labels carry their unique set structure. Its EGF is $ze^z$, whose $z^3$ coefficient is $1/2$; multiplying by $3!$ gives $3$.

Composition replaces each outer atom by an entire nonempty inner structure. Assume $G[\varnothing]=\varnothing$. If $\operatorname{Part}(U)$ denotes all partitions into nonempty blocks, define

$$ (F\circ G)[U]=\bigsqcup_{\pi\in\operatorname{Part}(U)} F[\pi]\times\prod_{B\in\pi}G[B]. $$

The set $\pi$ of blocks is the outer label set. Empty blocks are forbidden; our nonempty-inner hypothesis also ensures that $G(z)$ has zero constant term, so ordinary formal-series composition $F(G(z))$ is well-defined. Counting ordered block supports, then removing their arbitrary order, gives

$$ (F\circ G)(z)=F(G(z)). $$

Let $\mathcal E_2$ be the species of two-element sets and $\mathcal B=X+\mathcal E_2$. An involution decomposes uniquely into a set of $\mathcal B$-blocks. Thus $\mathcal I\cong\mathcal E\circ\mathcal B$ and $I(z)=\exp(z+z^2/2)$.

Unlabeled composition needs symmetry information: generally $\widetilde{F\circ G}(z)\neq\widetilde F(\widetilde G(z))$. For example, take $G=\mathcal E_+$, the species of nonempty sets. Then $\mathcal E\circ\mathcal E_+$ describes set partitions. Their unlabeled shapes are integer partitions, so

$$ \widetilde{\mathcal E\circ\mathcal E_+}(z)=\prod_{r\geq1}\frac1{1-z^r}. $$

Each factor chooses how many blocks have size $r$. Naive composition would instead give $1/(1-z/(1-z))$, with coefficient $4$ at $z^3$, whereas the actual shapes $3$, $2+1$, and $1+1+1$ number $3$.

Exercise. Specify an unordered pair of nonempty set blocks and compute its EGF. Hint: use $\mathcal E_2\circ\mathcal E_+$. Solution: the EGF is $(e^z-1)^2/2$. On three labels its coefficient is $1/2$, giving three structures; choose which label forms the singleton block. The factor $1/2$ removes the ordering of the two disjoint, nonempty blocks.

25.5 Exponential formula and connected components

Optional advanced elective extension; not required to complete the chapter foundation. Let $\mathcal K$ be a species of possible nonempty components, with $k_n=|\mathcal K[n]|$ and $K(0)=0$. Suppose each object of a species $\mathcal F$ decomposes uniquely into an unordered set of $\mathcal K$-structures on disjoint label supports, and this decomposition commutes with relabeling. These hypotheses give

$$ \mathcal F\cong\mathcal E\circ\mathcal K,\qquad F(z)=e^{K(z)}. $$

This is the labeled exponential formula. The word connected may mean graph-connected, or an indecomposable block in another grammar. The structural hypothesis, rather than the terminology, determines whether the formula applies.

Proof. First order the $r$ components temporarily. If their positive sizes are $n_1,\ldots,n_r$ with sum $n$, distributing labels and choosing structures gives

$$ \frac{n!}{n_1!\cdots n_r!}\prod_{i=1}^r k_{n_i}. $$

Summing over the sizes counts $n![z^n]K(z)^r$. Every unordered assembly is represented by exactly $r!$ orderings: the components are distinct as structures on disjoint nonempty supports, even when they have the same isomorphism type. Dividing by $r!$ and summing over $r\geq0$ proves the formula. The empty assembly contributes $1$.

Solved example. For singletons and pairs, fixing $j$ pairs leaves $n-2j$ singletons. Ordering all labels, then removing singleton order, pair order, and the two orientations of every pair gives

$$ a_n=\sum_{j=0}^{\lfloor n/2\rfloor} \frac{n!}{(n-2j)!\,2^j j!}. $$

The first values, including the empty object, are $1,1,2,4,10,26,76$. An independent proof partitions according to the block containing label $1$. It is either a singleton, leaving $a_{n-1}$ choices, or a pair with one of $n-1$ possible partners, leaving $a_{n-2}$ choices. Hence

$$ a_0=a_1=1,\qquad a_n=a_{n-1}+(n-1)a_{n-2}\quad(n\geq2). $$

For simple graphs, connected components satisfy the same hypotheses. If $g_n=2^{\binom n2}$ and $c_n$ counts connected graphs, then $G(z)=e^{C(z)}$. These series can be used formally; their analytic convergence is not asserted. On three labels, $g_3=8$ and $c_3=4$: three two-edge paths and the triangle. The remaining graphs have three isolated vertices or one edge and an isolated vertex, contributing $1+3$.

Exercise. Find the EGF for permutations using their disjoint cycles. Hint: a cycle of size $r$ has $(r-1)!$ labeled realizations, including $r=1,2$. Solution: the component EGF is $\sum_{r\geq1}z^r/r=\log(1/(1-z))$. Its exponential is $1/(1-z)$, so the labeled count is $n!$. This proof explains why the cycle components form a set even though each component itself has cyclic order.

25.6 Cycle index series

Optional advanced elective extension; not required to complete the chapter foundation. An EGF sees the identity relabeling. Unlabeled counting must also see nonidentity relabelings that fix structures. A cycle index records all of them simultaneously.

For $\sigma\in S_n$, let $c_i(\sigma)$ be its number of permutation cycles of length $i$, and let $\operatorname{fix}_F(\sigma)=|\{s\in F[n]:F[\sigma]\bigl(s\bigr)=s\}|$. Introduce formal variables $p_i$ with weighted degree $i$. Define

$$ Z_F(p_1,p_2,\ldots)=\sum_{n\geq0}\frac1{n!} \sum_{\sigma\in S_n}\operatorname{fix}_F(\sigma) \prod_{i\geq1}p_i^{c_i(\sigma)}. $$

Every degree has finitely many terms. Setting $p_1=z$ and all other variables to zero keeps only the identity permutation. Setting $p_i=z^i$ makes every degree-$n$ monomial become $z^n$, and Burnside's lemma averages its fixed-point counts. Therefore

$$ F(z)=Z_F(z,0,0,\ldots),\qquad \widetilde F(z)=Z_F(z,z^2,z^3,\ldots). $$

Solved fixed-point example. On two labels, the involutions are the identity and the transposition. Both commute with either relabeling in $S_2$, so both are fixed by both relabelings. The degree-two cycle-index contribution is $(2p_1^2+2p_2)/2=p_1^2+p_2$. Its EGF specialization gives coefficient $1$, hence labeled count $2!\cdot1=2$; its unlabeled specialization gives coefficient $2$.

For the set species every relabeling fixes its unique structure. A permutation with $m_i$ cycles of length $i$ occurs in $n!/\prod_i i^{m_i}m_i!$ ways. Summing independently over the $m_i$ gives

$$ Z_{\mathcal E}=\exp\left(\sum_{i\geq1}\frac{p_i}{i}\right),\qquad Z_{\mathcal E_2}=\frac{p_1^2+p_2}{2},\qquad Z_X=p_1. $$

For nonempty inner species $G$, the composition rule is plethystic substitution:

$$ Z_{F\circ G}=Z_F\bigl(Z_G(p_1,p_2,\ldots), Z_G(p_2,p_4,\ldots),Z_G(p_3,p_6,\ldots),\ldots\bigr). $$

Proof mechanism sketch. A relabeling that fixes an assembly permutes its blocks. Along a cycle of $k$ blocks, transporting an inner structure all the way around multiplies the relevant label-cycle lengths by $k$; this accounts for replacing $p_i$ by $p_{ki}$. Averaging over these block cycles produces the outer cycle index. A complete counting proof requires tracking centralizers of permutations and is omitted here. This is an established theorem, not an inference from small examples; Gessel, Counting tanglegrams with species, Section 2 states the convention and composition rule.

Applying the rule to our involutions gives an explicit series:

$$ Z_{\mathcal I}=\exp\left(\sum_{k\geq1}\frac1k \left(p_k+\frac{p_k^2+p_{2k}}2\right)\right). $$

The labeled specialization gives $e^{z+z^2/2}$. In the unlabeled specialization, $p_k^2$ and $p_{2k}$ both become $z^{2k}$, so

$$ \widetilde I(z)=\exp\left(\sum_{k\geq1}\frac{z^k+z^{2k}}k\right) =\frac1{(1-z)(1-z^2)}. $$

Its $z^n$ coefficient counts nonnegative solutions of $s+2j=n$, recovering $\lfloor n/2\rfloor+1$ without any labeling bias.

Exercise. Compute the degree-three part of $Z_{\mathcal I}$ directly. Hint: classify relabelings as identity, transposition, or three-cycle, and count commuting involutions. Solution: their fixed counts are $4,2,1$, with class sizes $1,3,2$. The contribution is $(2/3)p_1^3+p_1p_2+(1/3)p_3$. Its two specializations recover labeled count $4$ and unlabeled count $2$.

25.7 Recursive and implicit species

Optional advanced elective extension; not required to complete the chapter foundation. A recursive specification describes an object through smaller objects. To justify it, identify a canonical decomposition, its inverse construction, and why recursion decreases size. A formal equation alone need not define a unique family.

A linear order is empty or has a first label followed by a linear order. Thus $\mathcal L\cong\mathbf1+X\mathcal L$. The equation $L(z)=1+zL(z)$ determines coefficients successively and gives $L(z)=1/(1-z)$.

For a rooted nonplane tree, delete its root. Each remaining connected component is a tree rooted at the unique vertex formerly adjacent to that root. The collection of these rooted trees is unordered. Conversely, join the root to each child-tree root. These inverse constructions yield

$$ \mathcal A\cong X(\mathcal E\circ\mathcal A),\qquad A(z)=ze^{A(z)},\qquad A(0)=0. $$

The outer atom contributes one vertex, so every child tree is strictly smaller. The coefficient of $z^n$ on the right depends only on coefficients of $A$ through degree $n-1$. Starting from zero and repeatedly substituting stabilizes each coefficient, proving uniqueness as a formal series.

Solved coefficient derivation. The Lagrange inversion identity for $A=z\phi(A)$ with $\phi(0)\neq0$ states $[z^n]A=(1/n)[u^{n-1}]\phi(u)^n$ for $n\geq1$. This coefficient theorem is used here without proof; its formal-series proof is an omitted prerequisite of this extension. Taking $\phi(u)=e^u$ gives

$$ [z^n]A(z)=\frac1n[u^{n-1}]e^{nu} =\frac{n^{n-1}}{n!}. $$

Hence $A(z)=z+z^2+(3/2)z^3+(8/3)z^4+\cdots$, corresponding to $1,2,9,64$ labeled rooted trees. The earlier direct count of nine at size three checks this calculation independently.

For unlabeled trees, a set of children is a multiset of rooted-tree types; equal child types can be exchanged. If $t_m$ is the number of rooted types of size $m$, each of these types can occur any number of times, giving

$$ \widetilde A(z)=z\prod_{m\geq1}(1-z^m)^{-t_m} =z\exp\left(\sum_{k\geq1}\frac{\widetilde A(z^k)}k\right). $$

The product derivation proves the equation directly: taking formal logarithms expands $-\log(1-z^m)=\sum_{k\geq1}z^{mk}/k$. Again the root guarantees coefficientwise uniqueness. Simply writing $\widetilde A=ze^{\widetilde A}$ would miss the exchangeable equal children.

Exercise. List the rooted unlabeled trees with four vertices. Hint: distribute the three vertices below the root among its child trees. Solution: one child of size three has two possible rooted types; children of sizes one and two give one type; three children of size one give one type. Thus $t_4=2+1+1=4$. This argument also gives $t_1=1,t_2=1,t_3=2$ and explains the OGF in the table.

25.8 Dissymmetry theorem for trees

Optional advanced elective extension; not required to complete the chapter foundation. Rooted trees decompose easily. Removing a root from an unlabeled tree requires accounting for automorphisms: a tree type with $n$ vertices need not yield $n$ distinct rooted types.

Let $\mathcal T$ be the species of nonempty unrooted nonplane trees. Write $\mathcal T^\bullet$ for a tree with a marked vertex, $\mathcal T^-$ for a tree with a marked undirected edge, and $\mathcal T^\to$ for a tree with a marked directed edge. A directed edge is an edge with its two endpoints ordered, not an orientation of every edge. The dissymmetry theorem states

$$ \mathcal T+\mathcal T^\to\cong\mathcal T^\bullet+\mathcal T^-. $$

These are ordinary finite trees with all vertices labeled; tree-connectedness and acyclicity are essential. The identity holds naturally under relabeling and consequently also at the level of unlabeled types. See Gessel, Section 5 for the established general formulation.

Center-based bijection. Repeatedly remove all leaves until a single vertex or a single edge remains; this is the unique center, preserved by every automorphism. Regard an edge center as its midpoint when comparing distances.

Start from a vertex-marked or edge-marked tree. If the mark is the center, erase it and output an unrooted tree. If the marked vertex $v$ is not central, direct the first edge on the path from $v$ toward the center, with tail $v$. If the marked edge is not central, direct it from its nearer endpoint to its farther endpoint, away from the center.

To invert, an unrooted tree receives its center mark, of whichever kind the center has. A directed noncentral edge pointing toward the center produces a vertex mark at its tail; one pointing away produces an edge mark. Either orientation of a central edge produces a vertex mark at its tail. These cases are exclusive and exhaustive. A singleton tree has only the center vertex case. This proves the bijection, and its reliance on the intrinsic center proves naturality.

Cutting the marked edge separates two rooted trees. Its undirected version gives an unordered pair; its directed version gives an ordered pair. Therefore

$$ \mathcal T^\bullet=\mathcal A,\qquad \mathcal T^-=\mathcal E_2\circ\mathcal A,\qquad \mathcal T^\to=\mathcal A\mathcal A. $$

Translating the additive identity yields

$$ T(z)=A(z)-\frac12A(z)^2, $$

and, writing $R(z)=\widetilde A(z)$ to shorten notation,

$$ \widetilde T(z)=R(z)+\frac{R(z)^2+R(z^2)}2-R(z)^2 =R(z)-\frac{R(z)^2-R(z^2)}2. $$

The $R(z^2)$ term records unordered pairs of equal rooted types. The species theorem is an additive bijection; subtraction occurs only after passing to series.

Solved example. With $R=z+z^2+2z^3+4z^4+\cdots$, the $z^4$ coefficient of $R^2$ is $2\cdot1\cdot2+1^2=5$, and that of $R(z^2)$ is $1$. Hence the number of unrooted types at size four is $4-(5-1)/2=2$: the path and the star. For labeled trees the corresponding coefficient is $8/3-2=2/3$, giving $4!\cdot2/3=16$.

Exercise. Check dissymmetry on the path $1-2-3-4$, with center edge $\{2,3\}$. Hint: list all directed-edge outputs of noncentral marks. Solution: vertex marks $1,2,3,4$ give $1\to2,2\to3,3\to2,4\to3$. Marks on edges $\{1,2\}$ and $\{3,4\}$ give $2\to1$ and $3\to4$. The center-edge mark gives the unrooted path. Thus $4+3=6+1$. Up to the path's reflection, the vertex, edge, and directed-edge marks have $2,2,3$ types respectively, so the unlabeled check is $2+2=3+1$.

25.9 Boltzmann sampling

Optional advanced elective extension; not required to complete the chapter foundation. A Boltzmann sampler draws objects of varying size. Its parameter controls the size distribution; conditioning on a particular size gives a uniform distribution in the chosen labeled or unlabeled model. The framework and construction rules are established in Duchon, Flajolet, Louchard, and Schaeffer, Boltzmann Samplers for the Random Generation of Combinatorial Structures (2004). The following formulas prove the involution case directly.

In the labeled model choose $x\gt0$ with $0\lt F(x)\lt\infty$. For each particular $s\in F[n]$, use

$$ \Pr_x(s)=\frac{x^n}{n!F(x)},\qquad \Pr_x(N=n)=\frac{f_nx^n}{n!F(x)}. $$

This defines a distribution on the disjoint union of the sets $F[n]$ with canonical labels $[n]$. Conditional on $N=n$, every structure has probability $1/f_n$. In the unlabeled model replace the EGF by $\widetilde F$ and assign each type $[s]$ probability $x^n/\widetilde F(x)$. Conditional uniformity then applies to types. Analytic finiteness is a real requirement here, unlike purely formal coefficient identities.

Labeled involution sampler. Since $I(x)=e^{x+x^2/2}$ is finite for every finite positive $x$, proceed as follows.

1. Draw independent counts $S\sim\operatorname{Poisson}(x)$ and $P\sim\operatorname{Poisson}(x^2/2)$; a Poisson variable of mean $\lambda$ has probability $e^{-\lambda}\lambda^k/k!$ at $k\geq0$.
2. Set $N=S+2P$. Uniformly shuffle the labels $[N]$.
3. Make the first $S$ labels singleton blocks. Divide the remaining labels into consecutive pairs. Forget singleton order, pair order, and order within each pair.

Correctness proof. A particular configuration with $s$ singletons and $p$ pairs has exactly $s!p!2^p$ shuffled-word representations. Its probability is therefore

$$ \left(e^{-x-x^2/2}\frac{x^s}{s!}\frac{(x^2/2)^p}{p!}\right) \frac{s!p!2^p}{(s+2p)!} =\frac{x^{s+2p}}{(s+2p)!I(x)}. $$

This is the required labeled probability, including the empty configuration. Uniform relabeling is essential for the proof.

The independent counts also give

$$ \mathbb E_xN=x+x^2,\qquad \operatorname{Var}_x(N)=x+2x^2. $$

To target mean size $n\gt0$, choose $x=(\sqrt{1+4n}-1)/2$. This tunes the mean; it does not guarantee size $n$. Rejecting draws with $N\neq n$ is exact, with expected trial count $1/\Pr_x(N=n)$. There is no general constant-trial guarantee. Conditional on a produced size $N$, constructing and shuffling the object takes $O(N)$ elementary operations, apart from the cost of generating the two count variables.

Solved trace. At $x=1$, the expected size is $2$ and the variance is $3$. Counts $(S,P)=(2,1)$ produce $N=4$. A shuffled word $(3,1,4,2)$ gives singleton blocks $\{3\},\{1\}$ and pair $\{2,4\}$. This particular configuration has unconditional probability $1/(24e^{3/2})$, the same as each other particular four-label involution. Summing over all ten gives $\Pr(N=4)=10/(24e^{3/2})$.

Unlabeled involution sampler. A shape is completely determined by counts $(s,p)$. For $0\lt x\lt1$, draw independent geometric counts with

$$ \Pr(S=s)=(1-x)x^s,\qquad \Pr(P=p)=(1-x^2)x^{2p}\quad(s,p\geq0). $$

Output the shape with those counts. Its probability is $(1-x)(1-x^2)x^{s+2p}=x^N/\widetilde I(x)$, proving uniformity over types conditional on size. The means give $\mathbb E N=x/(1-x)+2x^2/(1-x^2)$, which is $5/3$ at $x=1/2$. Forgetting labels in the labeled sampler would give a different distribution.

Exercise. Compare the two samplers conditional on $N=3$. Hint: use the orbit counts in Section 25.2. Solution: the labeled sampler gives the three-singleton shape probability $1/4$ and the singleton-plus-pair shape probability $3/4$. The unlabeled sampler gives each probability $1/2$. These conditional distributions do not depend on $x$ within each sampler's valid range.

25.10 Species and combinatorial Hopf algebra connections

Optional research specialization extension; not required to complete the chapter foundation. A species supplies transport and enumeration. A Hopf structure additionally supplies compatible ways to combine and split structures. Those operations must be specified and checked; they do not arise from an EGF alone.

The general theory of Hopf monoids in vector species, its connected antipode theorem, and the simple-graph example are established results; see Aguiar and Mahajan, Hopf monoids in the category of species (2012), Sections 2, 5, and 9.4. This section specializes that framework to matchings with isolated vertices and computes its small algebra explicitly. No conjecture or claim about current optimal bounds is needed. Later Section 44.2 is recommended for the full algebraic treatment; it is optional background, not an entry requirement here. The linked source provides a complete independent treatment.

Over $\mathbb Q$, replace each finite set $\mathcal I[U]$ by the vector space $H[U]=\mathbb Q\mathcal I[U]$ having those involutions as a basis. View a pair block as a graph edge and a singleton as an isolated vertex. For disjoint supports $U=S\sqcup T$, define a product and a coproduct by

$$ \mu_{S,T}(m_S\otimes m_T)=m_S\sqcup m_T,\qquad \Delta_{S,T}(m)=m|_S\otimes m|_T. $$

Restriction means induced graph restriction: a pair split between $S$ and $T$ disappears as an edge, leaving its endpoints as singletons in their respective restrictions. Thus matchings remain matchings. There is one empty basis structure, which supplies the unit, and $H[\varnothing]=\mathbb Q$; the latter property is called connectedness in this algebraic setting, and is unrelated to graph-connectedness.

Compatibility proof sketch. Disjoint union is associative. Restricting to successively smaller subsets is independent of the order of restriction, which gives coassociativity. Restricting a disjoint union to any subset yields the disjoint union of the restrictions to the two intersected supports. This is the product–coproduct compatibility. All operations commute with bijections. These observations check the combinatorial identities; their formulation with tensor permutations in a monoidal category is omitted. The connected antipode theorem then supplies the convolution inverse of the identity.

An associated graded Hopf algebra can be described without categorical notation. Take basis vectors given by unlabeled matchings; multiply by disjoint union. If $x$ is a singleton and $y$ is one pair, every basis vector is $x^s y^p$, with degrees $1$ and $2$ for $x$ and $y$. Thus the algebra is $\mathbb Q[x,y]$. Its degree-$n$ dimension is $\lfloor n/2\rfloor+1$, and its dimension series is exactly $\widetilde I(z)$.

Define the coproduct by summing over every split of the vertex set into an ordered pair of subsets. Relabeling carries subsets bijectively to subsets, so this sum is well-defined on isomorphism classes, keeping multiplicities. On the generators,

$$ \Delta(x)=x\otimes1+1\otimes x,\qquad \Delta(y)=y\otimes1+1\otimes y+2x\otimes x. $$

Solved example. The coefficient $2$ comes from the two ways to put one endpoint of the pair on each side. Splitting a disjoint union is equivalent to splitting each component separately; hence $\Delta$ is multiplicative. The counit $\varepsilon$ sends $1$ to $1$ and all positive-degree basis elements to $0$.

The antipode $\mathsf S$ is characterized by $\mu(\mathsf S\otimes\mathrm{id})\Delta(h)=\varepsilon(h)1$ and the corresponding identity with the two factors reversed. Applying the first identity to the generators gives

$$ \mathsf S(x)=-x,\qquad \mathsf S(y)=-y+2x^2. $$

Indeed, for $y$ the left side is $\mathsf S(y)+y+2\mathsf S(x)x=0$. The result is a signed linear combination of structures, not a probabilistic distribution. Since the algebra is commutative, extending these formulas multiplicatively verifies both antipode identities on all monomials.

Exercise. Show that $q=y-x^2$ is primitive, meaning $\Delta(q)=q\otimes1+1\otimes q$, and compute $\mathsf S(q)$. Hint: square $\Delta(x)$. Solution: $\Delta(x^2)=x^2\otimes1+2x\otimes x+1\otimes x^2$, so the middle terms cancel after subtraction. Therefore $\mathsf S(q)=-q$, also obtained directly from $\mathsf S(y)-\mathsf S(x)^2=-y+x^2$. This is a concrete connection between component grammar, unlabeled enumeration, and algebraic cancellation.

Specify a species and derive both a generating function and a sampler

The investigation revisits isolated tasks and paired tasks. It is self-contained: a structure is a partition into unordered singleton and doubleton blocks, and labels identify the tasks. The grammar is $\mathcal I=\mathcal E\circ(X+\mathcal E_2)$. The exponential formula counts its labeled assemblies; its unlabeled types are determined by two nonnegative component counts.

Part A: warm-up calculations, 35 points. Specify transport under a bijection and derive

$$ I(z)=e^{z+z^2/2},\qquad \widetilde I(z)=\frac1{(1-z)(1-z^2)}. $$

Compute the labeled counts through size six and explain why they differ from unlabeled counts. Hint: classify by the number of pairs, and use the equation $s+2p=n$ for types.

Worked solution. Transport applies the bijection to every member of every block and has an inverse. For $p$ pairs, ordering labels and removing redundant orders gives $n!/((n-2p)!2^pp!)$ structures. Summing over $p$ and dividing by $n!$ factors as $\sum_s z^s/s!$ times $\sum_p z^{2p}/(2^pp!)$, proving the EGF. For types there is one object per count pair, so summing $z^{s+2p}$ gives the OGF.

The recurrence $a_n=a_{n-1}+(n-1)a_{n-2}$ checks the labeled row independently. The distinction is that labeled realizations of different shapes have different orbit sizes.

Part B: prove a generator, 25 points. Draw independent counts $S$ and $P$ from Poisson distributions of means $x$ and $x^2/2$. Uniformly shuffle $[S+2P]$, make the first $S$ labels singletons, and pair the remaining labels consecutively; discard all writing order. Prove that every particular output of size $n$ receives probability $x^n/(n!I(x))$. Tune the mean to $4$ and state how to obtain exact size four. Hint: count how many shuffled words represent one fixed partition.

Solution outline. A partition with $s$ singletons and $p$ pairs has $s!p!2^p$ word representations. Multiplying their fraction of the $n!$ shuffles by the joint Poisson probability cancels all three redundancy factors and leaves $x^n/(n!e^{x+x^2/2})$. Summing over outputs proves normalization and conditional uniformity. The mean equation is $x+x^2=4$, so $x=(\sqrt{17}-1)/2$. Reject other sizes; success probability is $10x^4/(24e^{x+x^2/2})$. The expected number of trials is its reciprocal, not automatically one.

Part C: compare type sampling, 15 points. Prove that independent geometric counts with probabilities $(1-x)x^s$ and $(1-x^2)x^{2p}$ generate the unlabeled Boltzmann law. Determine the size-four conditional probabilities of the three shapes for each sampler. Hint: one type corresponds to one count pair.

Worked solution. The joint probability is $x^{s+2p}/\widetilde I(x)$. At fixed size four all three count pairs have equal probability, so each type receives $1/3$. In the labeled sampler they receive $1/10,6/10,3/10$. A test that expects thirds after merely erasing labels from the labeled sampler uses the wrong target distribution.

Part D: finite computational or visual exploration, 15 points. Enumerate the objects on $[4]$ recursively: choose the least unused label; either leave it alone or pair it with each remaining label; recurse on the unused labels. Store each completed partition with sorted members and sorted blocks. Record a histogram by pair count. Optionally run a seeded experiment with $10{,}000$ accepted size-four outputs from each sampler, retaining the seed, trial count, and implementation conventions.

Expected exact output and solution outline. The enumeration histogram is $(1,6,3)$ for zero, one, and two pairs, and there are ten distinct canonical partitions. No branch duplicates another because its choice of the block containing the least unused label differs. This gives an inductive correctness proof of enumeration. For the optional experiment, expected labeled histogram counts are $(1000,6000,3000)$ and expected unlabeled counts are $(10000/3,10000/3,10000/3)$; observed counts fluctuate. For any category of probability $p$, its empirical proportion has standard deviation $\sqrt{p(1-p)/10000}$. Deviations of several standard deviations invite implementation checks, but passing such a check remains experimental evidence rather than a proof of uniformity.

Part E: structure, algebra, and application, 10 points. Interpret pairs as graph edges. Define disjoint union and restriction to two complementary subsets, including what happens to a pair that crosses the split. Compute the coproduct and antipode of one pair in the unlabeled algebra.

Worked solution. A crossing edge disappears, leaving one singleton on each side. There are two ordered endpoint assignments, so $\Delta(y)=y\otimes1+1\otimes y+2x\otimes x$. With $\mathsf S(x)=-x$, the inverse identity gives $\mathsf S(y)=-y+2x^2$. The component grammar accounts for the polynomial basis $x^sy^p$ and its dimension series $1/((1-z)(1-z^2))$; the restriction rule supplies additional Hopf structure that enumeration alone cannot determine. Here $x$ in the algebra is a formal singleton generator, distinct from the real sampling parameter also denoted $x$ in Parts B and C.

A relevant application is generating test configurations for a scheduling system that permits unassigned tasks and disjoint task pairs. For $n$ named tasks with no compatibility restrictions, conditioning the labeled generator on size $n$ tests every legal configuration with equal probability. If the goal is to test abstract component shapes equally, the unlabeled generator serves that goal instead. Compatibility constraints between particular tasks require a new counting model; this grammar assumes every pair is permitted.

Optional open-ended extension, ungraded. Allow blocks of sizes one, two, and three. Specify the species, derive $\exp(z+z^2/2+z^3/6)$ and $1/((1-z)(1-z^2)(1-z^3))$, and construct independent Poisson counts with means $x,x^2/2,x^3/6$ for labeled generation. Prove the shuffled-word cancellation using $s!p!t!2^p6^t$. Then choose a restriction convention for split triples: as set-partition blocks, their intersections remain blocks, so a split triple may become a pair and a singleton. Investigate the resulting coproduct by enumerating all subset splits. This is a design and proof exercise, not a claim of an unresolved research problem; a satisfactory extension explicitly states its restriction rule and verifies compatibility with disjoint union.