40.08.02 · combinatorics / analytic-combinatorics-asymptotics

The Symbolic Method for Labelled Structures

shipped3 tiersLean: none

Anchor (Master): Flajolet-Sedgewick 2009 *Analytic Combinatorics* (Cambridge) Ch. II in full — the labelled (partitional) product and its EGF translation, the SEQ/SET/CYC dictionary, the boxed product as the integral operator $\int_0^z (\partial_t A)\,B\,dt$, pointing and substitution, supercritical sequences and the exp-log schema (Theorems II.1-II.5, Propositions II.4-II.6); Stanley 1999 *Enumerative Combinatorics, Volume 2* (Cambridge) Ch. 5 (the exponential / compositional formulae, species); Joyal 1981 *Une théorie combinatoire des séries formelles* (Adv. Math. 42) for the functorial (species) foundation; Foata-Schützenberger 1970 for the labelled-product / shuffle calculus

Intuition Beginner

Some things you count carry name tags. A permutation of five people is not just a shape — each seat holds a specific named person, so two arrangements that look the same after erasing the names are still different arrangements. A way of partitioning the numbers $1$ through $n$ into groups, a graph drawn on numbered dots, a function on a numbered set: these are labelled objects, where the identities of the parts matter. Counting them is a different game from counting plain shapes, because when you join two labelled pieces you also have to decide which name tags go to which piece.

The symbolic method is a way to count such objects without ever counting by hand. You describe the object by a recipe — "a permutation is a collection of cycles", "a set partition is a set of nonempty blocks" — and the recipe translates, word for word, into an operation on a special bookkeeping function. The recipe word "collection of" becomes one specific algebraic move; the recipe word "sequence of" becomes another. Once you have written the recipe, the counting function falls out by reading the translation off a short table.

The right bookkeeping function for labelled objects is the exponential generating function. It is the plain generating function with one extra division: the count at size $n$ is divided by $n$ factorial before being hung on the bookkeeping symbol. That single change is exactly what is needed to handle the name tags. When you split a labelled object into two pieces, you choose which tags go left and which go right, and the factorial weighting builds that choice into the algebra for free.

This unit is the labelled half of the symbolic method. Its plain-shape twin handles objects without name tags; here every construction — sequence, set, cycle — gets a labelled translation, and the recipes for permutations, set partitions, surjections, and labelled trees all become one-line calculations.

Visual Beginner

Think of a labelled object as a handful of numbered cards arranged into a structure. To build a two-part object, you deal the cards into a left hand and a right hand, then arrange each hand on its own. The picture below shows the one move that makes the whole method work: the label-shuffle. You start with the cards $1$ through $n$ , choose a subset to send left, and the rest go right — every choice of subset is a different way to combine the two parts.

The table records the four basic recipes and what each one does to the bookkeeping function. Each row is a counting fact you can check on tiny cases, and the rest of the unit explains why each recipe translates to exactly its listed operation.

recipe in words	what the object is	operation on the EGF
lay an $A$ -part beside a $B$ -part, shuffling the labels	a labelled pair	multiply the two EGFs
an ordered list of any number of $A$ -parts	a labelled sequence	divide $1$ by ( $1$ minus the $A$ -EGF)
an unordered collection of any number of $A$ -parts	a labelled set	take the exponential of the $A$ -EGF
arrange $A$ -parts around a ring	a labelled cycle	take the logarithm of $1$ over ( $1$ minus the $A$ -EGF)

The headline cases live in these rows. A set partition is a set of blocks; a permutation is a set of cycles; a surjection is a sequence of nonempty blocks. Read the recipe, pick the row, write the answer.

Worked example Beginner

Let us count the surjections from a labelled set onto an unlabelled one: ways to sort the numbers $1, 2, 3$ into a list of nonempty groups where the order of the groups matters. (These are the same as ordered set partitions.) We will count by hand and then check against the recipe.

Step 1. A surjection of ${1, 2, 3}$ is a sequence of nonempty blocks whose blocks together use each of $1, 2, 3$ exactly once. List by the number of blocks.

Step 2. One block: the single block ${1, 2, 3}$ . That is $1$ arrangement.

Step 3. Two blocks: choose which numbers form the first block (the rest form the second), with both blocks nonempty. The first block can be ${1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}$ — six choices, and each fixes the second block. That is $6$ arrangements.

Step 4. Three blocks: each block is a single number, and the blocks are ordered, so this is just an ordering of $1, 2, 3$ into three slots: $3 \times 2 \times 1 = 6$ arrangements.

Step 5. Total: $1 + 6 + 6 = 13$ . So there are $13$ surjections from a $3$ -element set.

Step 6. Check against the recipe. A surjection is "a sequence of nonempty sets of labels". The EGF of nonempty labelled sets is $e^{z} - 1$ (the all-ones set count minus the empty set), and the sequence recipe divides $1$ by $1$ minus that, giving $\frac{1}{1 - ( e ^{z} - 1 )} = \frac{1}{2 - e ^{z}}$ . Expanding this to the $z^{3}$ term and multiplying by $3!$ gives the count $13$ , matching the hand count.

What this tells us: a one-line recipe — sequence of nonempty sets — reproduces a count that took five cases by hand, and the same recipe gives the count for every size at once.

Check your understanding Beginner

Exercise (easy, true-false).

True or false: for a labelled object, the exponential generating function divides the count at size $n$ by $n$ factorial before recording it.

Hint

Recall what makes the exponential generating function different from the plain one — it is one extra division by a factorial.

Answer

True. The exponential generating function records the count $a_{n}$ as $a_{n}$ divided by $n$ factorial on the bookkeeping symbol's $n$ -th power. That weighting is exactly what makes the label-shuffle (choosing which tags go where) come out of the algebra automatically. Feedback-correct: this is why the labelled product rule carries a binomial coefficient — the two factorials in the denominators recombine into " $n$ choose $k$ ". Feedback-wrong: the plain generating function (no factorial division) is the right tool for unlabelled shapes, not for labelled ones.

Formal definition Intermediate+

A labelled combinatorial class $A$ is a class of objects together with a size function $∣ \cdot ∣ : A \to Z_{\geq 0}$ such that an object of size $n$ carries a set of $n$ distinct atoms, bijectively labelled by ${1, \dots, n}$ , and such that finitely many objects have each size; $a_{n} = # {α \in A : ∣ α ∣ = n}$ is the counting sequence. The labelled atom $Z$ has one object of size $1$ . The exponential generating function (EGF) of $A$ is $$ A(z) = \sum_{n \ge 0} a_n \frac{z^n}{n!} \in \mathbb{Q}[[z]], $$ following the formal-power-series conventions of 40.01.03. Two labelled objects on the same atoms are equal only as labelled objects; relabelling by an order-isomorphism transports an object on an arbitrary $n$ -set to the canonical one on ${1, \dots, n}$ .

Definition (labelled product). The labelled product (partitional, or shuffle, product) $A ⋆ B$ has objects the pairs $(α, β)$ in which the atoms of $α$ and of $β$ form a disjoint partition of a common label set ${1, \dots, n}$ with $n = ∣ α ∣ + ∣ β ∣$ ; both components are then relabelled order-isomorphically to canonical form. The number of ways to split ${1, \dots, n}$ into an $∣ α ∣$ -subset and its complement is $(∣ α ∣ n)$ , so $$ (\mathcal{A} \star \mathcal{B})n = \sum{k=0}^{n} \binom{n}{k}, a_k, b_{n-k}, \qquad (A \star B)(z) = A(z),B(z), $$ the binomial convolution of 40.01.03. The empty labelled object $ϵ$ (size $0$ ) is the unit for $⋆$ .

Definition (labelled SEQ, SET, CYC). From a class $A$ with $a_{0} = 0$ (no object of size $0$ , so $A (0) = 0$ ) one forms three iterated products:

the sequence $SEQ (A) = {ϵ} + A + (A ⋆ A) + \dots$ of ordered tuples of $A$ -components, with EGF $\sum_{k \geq 0} A (z)^{k} = \frac{1}{1 - A ( z )}$ ;
the set $SET (A)$ of unordered collections of $A$ -components, the $k$ -component part being $A^{⋆ k} / k!$ , with EGF $\sum_{k \geq 0} \frac{A ( z ) ^{k}}{k !} = exp (A (z))$ ;
the cycle $CYC (A)$ of $A$ -components arranged around an oriented ring (sequences up to cyclic rotation), the $k$ -component part being $A^{⋆ k} / k$ , with EGF $\sum_{k \geq 1} \frac{A ( z ) ^{k}}{k} = lo g \frac{1}{1 - A ( z )}$ .

The SET translation is the exponential formula of 40.01.03 read as a construction. Restricted variants $SET_{= k}, SET_{\geq 1}, CYC_{= k}, SEQ_{\leq k}$ truncate or fix the number of components, with EGFs $\frac{A ^{k}}{k !}$ , $e^{A} - 1$ , $\frac{A ^{k}}{k}$ , $\sum_{j \leq k} A^{j}$ .

Definition (boxed product and pointing). The boxed product $A^{□} ⋆ B$ is the subclass of $A ⋆ B$ in which the least label of the whole object lies in the $A$ -component. Its EGF is the integral operator $$ \big(A^{\square}\star B\big)(z) = \int_0^z \big(\partial_t A(t)\big), B(t), dt, $$ and a least-label-in- $B$ variant integrates $A (t) \partial_{t} B (t)$ . Pointing $Θ A$ distinguishes one atom of each object; it has EGF $z \partial_{z} A (z)$ , since pointing multiplies the size- $n$ count by $n$ . The operators $\partial_{z}$ and $\int_{0}^{z}$ , the boxed product $□$ , and the pointing operator $Θ$ are recorded in _meta/NOTATION.md.

Counterexamples to common slips Intermediate+

"The labelled and unlabelled symbolic methods give the same translations." They do not. The unlabelled SEQ is $\frac{1}{1 - A}$ in both worlds, but unlabelled SET is the Euler transform $exp (\sum_{k \geq 1} \frac{1}{k} A (z^{k}))$ and unlabelled CYC carries the Euler totient $\sum_{k} \frac{φ ( k )}{k} lo g \frac{1}{1 - A ( z ^{k} )}$ ; the labelled SET and CYC collapse to the clean $exp (A)$ and $lo g \frac{1}{1 - A}$ precisely because distinct labels remove all symmetry.
" $SET (A)$ requires $A$ to have no empty object." It requires $A (0) = 0$ , i.e. $a_{0} = 0$ : otherwise $exp (A)$ has a divergent constant term and the construction admits infinitely many empty components. The same zero-constant-term condition governs SEQ and CYC.
"The boxed product is just an ordered version of the labelled product." The ordering is not arbitrary: $A^{□} ⋆ B$ pins the globally smallest label to $A$ . This is what makes the integral translation exact and is the device used to enumerate increasing/ordered structures (increasing trees, ordered set partitions read least-first) where a recursive "smallest element first" decomposition is natural.
" $CYC$ and $SEQ$ differ only by a constant." Over $k$ components, SEQ counts $A^{k}$ ordered tuples and CYC counts $A^{k} / k$ rings (dividing by the $k$ rotations), so the generating functions are $\frac{1}{1 - A}$ and $lo g \frac{1}{1 - A} = \sum_{k \geq 1} \frac{A ^{k}}{k}$ — genuinely different series, agreeing only at the one-component level.

Key theorem with proof Intermediate+

The signature theorem is the translation theorem for labelled constructions: it states that the labelled product, sequence, set, and cycle constructions are admissible — each translates to a fixed analytic operation on the EGF — so any specification built from $Z$ by these operations yields its EGF mechanically. This is the labelled half of the symbolic method, and every later enumeration in the chapter is one instance of it ^{[Flajolet-Sedgewick §II.2-II.3]}.

Theorem (labelled translation theorem). Let $A, B$ be labelled classes with EGFs $A (z), B (z)$ , and suppose $A (0) = 0$ where a construction requires it. Then:

(union, disjoint) $A + B$ has EGF $A (z) + B (z)$ ;
(labelled product) $A ⋆ B$ has EGF $A (z) B (z)$ ;
(sequence) $SEQ (A)$ has EGF $\frac{1}{1 - A ( z )}$ ;
(set) $SET (A)$ has EGF $exp (A (z))$ ;
(cycle) $CYC (A)$ has EGF $lo g \frac{1}{1 - A ( z )}$ .

Proof. Part (1) is the additivity of EGFs over a disjoint union, coefficientwise. For (2), an object of $A ⋆ B$ on ${1, \dots, n}$ is determined by a choice of $k$ -subset $S$ to carry the $A$ -component (the complement carrying $B$ ), an $A$ -object on $S$ relabelled canonically (there are $a_{k}$ of these), and a $B$ -object on the complement ( $b_{n - k}$ of these). Summing over $∣ S ∣ = k$ , $$ (\mathcal{A}\star\mathcal{B})n = \sum{k=0}^{n}\binom{n}{k}a_k, b_{n-k}, $$ whose EGF is the Cauchy product of $A$ and $B$ : $(\sum_{k} a_{k} \frac{z ^{k}}{k !}) (\sum_{j} b_{j} \frac{z ^{j}}{j !})$ has $z^{n}$ -coefficient $\sum_{k} \frac{a _{k}}{k !} \frac{b _{n - k}}{( n - k )!} = \frac{1}{n !} \sum_{k} (k n) a_{k} b_{n - k}$ , so $A (z) B (z) = \sum_{n} (A ⋆ B)_{n} \frac{z ^{n}}{n !}$ . This is the 40.01.03 product rule.

For (3), $SEQ (A) = \sum_{k \geq 0} A^{⋆ k}$ is a disjoint union of $k$ -fold labelled products, so by (1) and (2) its EGF is $\sum_{k \geq 0} A (z)^{k}$ . Since $A (0) = 0$ , the series $A (z)^{k}$ has lowest-order term of order $\geq k$ , so for each fixed $n$ only finitely many $k$ contribute to $[z^{n}]$ and the sum converges formally to $\frac{1}{1 - A ( z )}$ (the constant term of $1 - A$ is $1$ , a unit, by 40.01.03 Proposition 1).

For (4), an object of $SET (A)$ is an unordered collection of $k$ components. The ordered version is $A^{⋆ k}$ , and each unordered collection of distinct-label components arises from exactly $k!$ orderings (the components are pairwise distinguishable by their label sets, so no overcounting collapse occurs); hence the $k$ -component subclass has EGF $\frac{A ( z ) ^{k}}{k !}$ . Summing, $SET (A)$ has EGF $\sum_{k \geq 0} \frac{A ( z ) ^{k}}{k !} = exp (A (z))$ . This is the exponential formula of 40.01.03 presented as the SET construction.

For (5), a cycle on $k$ components is a sequence of $k$ components read up to cyclic rotation. The $k$ rotations of a $k$ -tuple of distinct-label components are all distinct (the label sets break the rotational symmetry, for $k \geq 1$ ), so the $k$ -component subclass has EGF $\frac{A ( z ) ^{k}}{k}$ , and $CYC (A)$ has EGF $\sum_{k \geq 1} \frac{A ( z ) ^{k}}{k} = lo g \frac{1}{1 - A ( z )}$ . $□$

Corollary (permutations and set partitions). Taking $A = CYC (Z)$ — a cyclic arrangement of labelled atoms, EGF $lo g \frac{1}{1 - z}$ — the class $SET (CYC (Z))$ of sets of cycles has EGF $exp (lo g \frac{1}{1 - z}) = \frac{1}{1 - z} = \sum_{n} n! \frac{z ^{n}}{n !}$ , recovering the $n!$ permutations. Taking $A = SET_{\geq 1} (Z)$ — a nonempty block of labels, EGF $e^{z} - 1$ — the class $SET (SET_{\geq 1} (Z))$ of sets of nonempty blocks has EGF $exp (e^{z} - 1) = \sum_{n} B_{n} \frac{z ^{n}}{n !}$ , the Bell-number EGF.

Bridge. This theorem builds toward the entire analytic machinery of the chapter and appears again in 40.08.01, where the same translation table is run for unlabelled classes with ordinary generating functions and the singularities of the resulting functions deliver asymptotics. The foundational reason the labelled SET collapses to the clean $exp (A)$ , whereas the unlabelled SET needs the Euler transform, is exactly that distinct labels destroy the automorphisms that the unlabelled count must mod out — this is the central insight separating the two halves of the method. The labelled product translating to plain multiplication of EGFs is dual to the unlabelled product translating to multiplication of OGFs: in both, juxtaposition becomes a product, but the EGF builds the label-shuffle into its factorial weighting. Putting these together, the permutation specification $SET (CYC (Z))$ and the set-partition specification $SET (SET_{\geq 1} (Z))$ are not separate tricks but two readings of one $exp$ -of-something table entry, and this generalises directly into the saddle-point asymptotics of 40.08.06, where the Bell and involution EGFs are extracted.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Using the boxed-product translation $(A^{□} ⋆ B) (z) = \int_{0}^{z} (\partial_{t} A) B d t$ , verify that pointing the smallest label of a labelled set reproduces the SET construction's derivative. Concretely, show $(Z^{□} ⋆ SET (Z)) (z) = \int_{0}^{z} 1 \cdot e^{t} d t = e^{z} - 1$ , and interpret the result.

Hint

$Z$ has EGF $z$ , so $\partial_{t} (t) = 1$ . $SET (Z)$ has EGF $e^{t}$ . Integrate.

Answer

With $A (t) = t$ (the atom) and $B (t) = e^{t}$ ( $SET (Z)$ ), $\partial_{t} A = 1$ , so $\int_{0}^{z} 1 \cdot e^{t} d t = e^{z} - 1$ . This is the EGF of nonempty labelled sets: a nonempty set of atoms is exactly "the smallest-labelled atom, then an arbitrary set of the remaining atoms". The boxed product pins the least label to a singleton atom and lets the rest form any set, and the integral records this least-first decomposition. The result $e^{z} - 1 = SET_{\geq 1} (Z)$ confirms the bookkeeping. Rubric: full credit for the integral evaluation and the least-label-decomposition interpretation.

Exercise 5 (medium, numeric).

The number of permutations of ${1, \dots, n}$ with exactly $k$ cycles is the unsigned Stirling number $[k n]$ , with bivariate EGF $\sum_{n, k} [k n] u^{k} \frac{z ^{n}}{n !} = (1 - z)^{- u}$ . Use this to compute the number of permutations of $4$ elements with exactly $2$ cycles.

Hint

Marking cycles by $u$ turns $SET (CYC (Z))$ into $exp (u lo g \frac{1}{1 - z}) = (1 - z)^{- u}$ . Extract $[u^{2}]$ then $4! [z^{4}]$ ; or use $[2 4] = 11$ .

Answer

$11$ . Marking each cycle by $u$ gives $exp (u lo g \frac{1}{1 - z}) = (1 - z)^{- u}$ ; the $u^{2}$ -coefficient is $\frac{1}{2} (lo g \frac{1}{1 - z})^{2}$ , whose $z^{4}$ EGF coefficient times $4!$ is $[2 4] = 11$ . Directly: permutations of $4$ elements with $2$ cycles are the $(3, 1)$ cycle types ( $(1 4) \cdot 2 = 8$ , choosing the fixed point and one of the $2$ orientations of the $3$ -cycle) plus the $(2, 2)$ types ( $\frac{1}{2} (2 4) = 3$ ), totalling $11$ . Rubric: full credit for either the bivariate extraction or the cycle-type enumeration.

Exercise 6 (medium, symbolic).

Show that the labelled tree function $T (z) = \sum_{n} n^{n - 1} \frac{z ^{n}}{n !}$ satisfies $T = z e^{T}$ by reading off the specification "a rooted labelled tree is a root atom together with a set of rooted-tree subtrees", and explain which construction supplies the $exp$ .

Hint

The root is $Z$ (EGF $z$ ); the subtrees form $SET (T)$ . Multiply by the labelled product.

Answer

The specification is $T = Z ⋆ SET (T)$ : a rooted tree is the root atom $Z$ joined (by the labelled product, distributing the labels) to a set of rooted subtrees. The SET construction supplies the $exp$ by part (4) of the translation theorem, since the subtrees hanging off the root are an unordered collection. Translating, $T (z) = z \cdot exp (T (z))$ , i.e. $T = z e^{T}$ . By Lagrange inversion (developed at 40.01.07) this gives $[z^{n}] T = \frac{n ^{n - 1}}{n !}$ , hence $n^{n - 1}$ rooted labelled trees. Rubric: full credit for the $Z ⋆ SET (T)$ specification, naming SET as the source of $exp$ , and the functional equation $T = z e^{T}$ .

Exercise 7 (hard, symbolic).

A fragmented permutation (or "labelled linear forest") is a set of nonempty sequences of labels. Derive its EGF, and a closed form for the count $f_{n}$ .

Hint

A nonempty sequence of atoms $SEQ_{\geq 1} (Z)$ has EGF $\frac{z}{1 - z}$ . The whole object is $SET$ of these. Then relate $f_{n}$ to the Laguerre/ $(k n)$ -type sum.

Answer

A nonempty linearly ordered block of labels is $SEQ_{\geq 1} (Z)$ with EGF $\frac{1}{1 - z} - 1 = \frac{z}{1 - z}$ . A fragmented permutation is a set of these, so by SET its EGF is $$ F(z) = \exp!\Big(\frac{z}{1-z}\Big). $$ The count is $f_{n} = n! [z^{n}] exp (\frac{z}{1 - z}) = \sum_{k = 0}^{n} (k n) \frac{n !}{k !} \cdot \frac{1}{( n - k )!} \dots$ — more cleanly, grouping by the number $j$ of blocks, $f_{n} = \sum_{j \geq 0} \frac{n !}{j !} \sum_{m_{1} + \dots + m_{j} = n m_{i} \geq 1} \prod_{i} \frac{1}{m _{i} !} \cdot m_{i}! \cdot \frac{1}{?}$ ; the direct route is $f_{n} = \sum_{k = 0}^{n} (k n) \frac{n !}{( n - k )!} \frac{1}{k !} L$ -type, and one verifies $f_{0} = 1, f_{1} = 1, f_{2} = 3, f_{3} = 13, f_{4} = 73$ (OEIS A000262) directly: a fragmented permutation on ${1, \dots, n}$ is "the smallest label heads some block; choose the rest of that block as an ordered string and recurse", giving the recurrence $f_{n} = \sum_{k = 1}^{n} (k - 1 n - 1) k! f_{n - k} / k$ — equivalently $f_{n} = (2 n - 1) f_{n - 1} - (n - 1) (n - 2) f_{n - 2}$ . Rubric: full credit for the EGF $exp (\frac{z}{1 - z})$ and any correct extraction giving $f_{n}$ (the values $1, 1, 3, 13, 73$ or the recurrence).

Exercise 8 (hard, symbolic).

Prove the cycle translation $CYC (A) \to lo g \frac{1}{1 - A ( z )}$ directly, taking care to justify why the $k$ rotations of a $k$ -tuple of components are distinct, and contrast with the unlabelled cycle construction.

Hint

A $k$ -component cycle is an orbit of a $k$ -tuple under the cyclic group $C_{k}$ . Show the action is free on tuples of distinct-label components.

Answer

A $k$ -component labelled cycle is a $C_{k}$ -orbit of the $k$ -tuples in $A^{⋆ k}$ . The cyclic shift $(γ_{1}, \dots, γ_{k}) \mapsto (γ_{2}, \dots, γ_{k}, γ_{1})$ has a fixed tuple only if all components coincide with the same labels; but the components partition a common label set into disjoint nonempty blocks, so distinct positions carry distinct label sets and no nontrivial rotation fixes a tuple. The action of $C_{k}$ is therefore free, every orbit has exactly $k$ elements, and the $k$ -component subclass has EGF $\frac{1}{k} A (z)^{k}$ . Summing over $k \geq 1$ (with $A (0) = 0$ ensuring formal convergence), $CYC (A)$ has EGF $\sum_{k \geq 1} \frac{A ( z ) ^{k}}{k} = lo g \frac{1}{1 - A ( z )}$ . Contrast: in the unlabelled world the components can repeat, the $C_{k}$ -action need not be free, and Burnside's count introduces the Euler totient, giving $\sum_{k \geq 1} \frac{φ ( k )}{k} lo g \frac{1}{1 - A ( z ^{k} )}$ — the labelling is exactly what removes the totient. Rubric: full credit for the free-action argument, the $\frac{1}{k} A^{k}$ term, the sum to $lo g \frac{1}{1 - A}$ , and the unlabelled contrast.

Advanced results Master

The translation theorem is the elementary stratum; its reach extends through the boxed product as an integral calculus, pointing-and-substitution, the supercritical-sequence and exp-log schemas governing component counts, and the species-level functoriality that unifies the labelled and unlabelled dictionaries.

Theorem 1 (boxed product as integral operator). For labelled classes $A, B$ the least-label-in- $A$ boxed product has EGF $$ \big(A^{\square}\star B\big)(z) = \int_0^z \big(\partial_t A(t)\big),B(t),dt . $$ Iterating the boxed product builds structures with a prescribed order on a distinguished chain of labels: $SEQ^{□}$ (the smallest-label-first sequence) generates increasing/ordered constructions, and increasing trees arise as $T = Z^{□} ⋆ SET (T)$ , whose EGF solves $\partial_{z} T = \frac{1}{1 - T}$ -type ODEs ^{[Flajolet-Sedgewick §II.4]}. The integral form is exact because constraining the least of $n$ labels to $A$ multiplies the size- $n$ partitional count by the probability $∣ α ∣/ n$ that the global minimum lands in the $A$ -component, and $\partial_{t}$ on $A$ together with $\int_{0}^{z}$ implements exactly this size-weighting.

Theorem 2 (pointing, substitution, and the compositional formula). Pointing $Θ A$ translates to $z \partial_{z} A (z)$ . Labelled substitution $B \circ A$ — replacing each atom of a $B$ -object by an $A$ -object on a disjoint label block — translates to functional composition $B (A (z))$ provided $A (0) = 0$ ; this is the compositional formula of 40.01.03 in construction form. The set construction is the case $B = SET$ ( $B = exp$ ), recovering $exp (A)$ ; the sequence construction is $B = SEQ$ ( $B = \frac{1}{1 - w}$ ), recovering $\frac{1}{1 - A}$ . Pointing and substitution together give the "pointing-and-rooting" calculus: $Θ (SET (C)) = C^{∙} ⋆ SET (C)$ , the standard root-extraction identity ^{[Flajolet-Sedgewick §II.4]}.

Theorem 3 (supercritical sequence schema). Let $F = SEQ (A)$ with $A (z)$ having radius of convergence $ρ > 0$ and $A (ρ^{-}) > 1$ (the supercritical case). Then the equation $A (ζ) = 1$ has a unique root $ζ < ρ$ , $F (z) = \frac{1}{1 - A ( z )}$ has a simple pole at $ζ$ , and the number of $A$ -components in a random size- $n$ $F$ -object is asymptotically Gaussian with mean $\sim κn$ and variance $\sim ν n$ for constants $κ, ν$ depending on $A$ at $ζ$ ^{[Flajolet-Sedgewick §V, IX]}. This is the labelled-sequence component-count limit law, the mechanism behind surjection block-counts; the analytic extraction belongs to the singularity/quasi-powers analysis of 40.08.01 and 40.08.06.

Theorem 4 (exp-log schema). Let $F = SET (C)$ where $C$ has EGF $C (z) = lo g \frac{1}{1 - z / ρ} +$ (analytic at $ρ$ ) of logarithmic singular type — as for permutation cycles ( $C = lo g \frac{1}{1 - z}$ , $ρ = 1$ ). Then the number of $C$ -components in a random size- $n$ $F$ -object is asymptotically Gaussian with mean and variance both $\sim lo g n$ . For permutations this is the Goncharov-Erdős-Turán theorem that a random permutation of $n$ elements has $\sim lo g n$ cycles with $lo g n$ fluctuations; the schema isolates the logarithmic singularity of $C$ as the cause ^{[Flajolet-Sedgewick §II.5, IX]}. The exp-log schema is the SET analogue of the supercritical-sequence schema, the SET versus SEQ distinction reappearing at the level of limit laws.

Theorem 5 (species and functoriality). A labelled class is, in Joyal's framework, a functor $F : B \to FinSet$ from the groupoid of finite sets and bijections; its EGF is the generating series of the sequence $f_{n} = ∣ F [{1, \dots, n}] ∣$ . The operations $+, ⋆, SET, CYC, \circ$ are functorial operations on species (sum, product, the " $E$ " species composed on the right, the cyclic species, substitution), and the EGF is a ring homomorphism from the species semiring (with $+$ and $⋆$ ) to $Q [[z]]$ ^{[Stanley §5.1, citing Joyal]}. Two species can have the same EGF yet differ as functors; the EGF forgets the bijection-action and retains only cardinalities, which is why it is a complete invariant for counting but not for structure.

Synthesis. The labelled symbolic method is the foundational reason that "describe the object, read off the count" is a theorem rather than a slogan: every labelled construction — product, sequence, set, cycle, boxed product, pointing, substitution — is a fixed analytic operation on the exponential generating function, so a specification built from the atom $Z$ emits its own EGF. The central insight is that the factorial weighting makes the label-shuffle automatic: the labelled product becomes plain multiplication, and putting these together with the iterated-product definitions, SET becomes $exp$ and CYC becomes $lo g \frac{1}{1 - A}$ because distinct labels make the symmetric and cyclic group actions free — exactly where the unlabelled method instead pays the Euler-transform and totient tolls. This is dual to the unlabelled dictionary of 40.08.01 construction by construction, the two halves differing only where automorphisms survive. The boxed product is the one genuinely new labelled device, an integral operator recording a least-label-first recursion that reaches increasing structures no product alone can build. The bridge to asymptotics is that the supercritical-sequence and exp-log schemas read the shape of the component-count distribution off the type of singularity of $A$ or $C$ — a pole for SEQ, a logarithm for SET — so the same EGF the symbolic method produces exactly will, under the singularity analysis of 40.08.01 and the saddle-point method of 40.08.06, surrender its asymptotic growth and its limit laws. The construction calculus and the analytic calculus are one method read at two resolutions.

Full proof set Master

Proposition 1 (labelled product translation). The EGF of $A ⋆ B$ is $A (z) B (z)$ , with $(A ⋆ B)_{n} = \sum_{k} (k n) a_{k} b_{n - k}$ .

Proof. An object of $A ⋆ B$ on the label set ${1, \dots, n}$ is a triple: a subset $S \subseteq {1, \dots, n}$ of size $k$ designating the $A$ -atoms, an $A$ -object on $S$ , and a $B$ -object on the complement, where each component is read in canonical labelling via the order-isomorphism of its label set with ${1, \dots, ∣ S ∣}$ (respectively ${1, \dots, n - k}$ ). The subset is chosen in $(k n)$ ways, the $A$ -object in $a_{k}$ ways, the $B$ -object in $b_{n - k}$ ways; summing over $k$ gives $(A ⋆ B)_{n} = \sum_{k = 0}^{n} (k n) a_{k} b_{n - k}$ . The Cauchy product of the EGFs has $z^{n}$ -coefficient $$ \sum_{k=0}^{n}\frac{a_k}{k!}\cdot\frac{b_{n-k}}{(n-k)!} = \frac{1}{n!}\sum_{k=0}^{n}\frac{n!}{k!(n-k)!}a_k b_{n-k} = \frac{1}{n!}\sum_{k=0}^n\binom{n}{k}a_k b_{n-k}, $$ so $A (z) B (z) = \sum_{n} (A ⋆ B)_{n} \frac{z ^{n}}{n !}$ . $□$

Proposition 2 (SET, SEQ, CYC translations). For $A$ with $A (0) = 0$ : $SEQ (A)$ has EGF $\frac{1}{1 - A}$ , $SET (A)$ has EGF $e^{A}$ , and $CYC (A)$ has EGF $lo g \frac{1}{1 - A}$ .

Proof. By Proposition 1 iterated, $A^{⋆ k}$ has EGF $A (z)^{k}$ . The sequence $SEQ (A) = ⨆_{k \geq 0} A^{⋆ k}$ (ordered $k$ -tuples) has EGF $\sum_{k \geq 0} A^{k}$ ; since $A (0) = 0$ , $A^{k}$ has order $\geq k$ , so each $[z^{n}]$ is a finite sum and $\sum_{k} A^{k} = \frac{1}{1 - A}$ , $1 - A$ being a unit. For SET, the $k$ -component subclass is the quotient $A^{⋆ k} / S_{k}$ by the symmetric group permuting the components. The action of $S_{k}$ on $k$ -tuples of components with pairwise disjoint nonempty label sets is free: a permutation fixing a tuple would have to fix each component's label set, but distinct components occupy distinct positions with distinct label sets, so only the identity fixes the tuple. Hence every orbit has size $k!$ and the $k$ -component subclass has EGF $\frac{A ^{k}}{k !}$ ; summing, $SET (A)$ has EGF $\sum_{k \geq 0} \frac{A ^{k}}{k !} = e^{A}$ . For CYC, the cyclic group $C_{k}$ acts on $k$ -tuples by rotation; the same disjoint-label-set argument makes the action free for $k \geq 1$ , so each orbit (cycle) has size $k$ and the $k$ -component subclass has EGF $\frac{A ^{k}}{k}$ , giving $\sum_{k \geq 1} \frac{A ^{k}}{k} = lo g \frac{1}{1 - A}$ . $□$

Proposition 3 (boxed-product integral translation). The least-label-in- $A$ boxed product $A^{□} ⋆ B$ has EGF $\int_{0}^{z} (\partial_{t} A) B d t$ .

Proof. Write $c_{n} = (A^{□} ⋆ B)_{n}$ . An object of $A ⋆ B$ on ${1, \dots, n}$ with the $A$ -component of size $k \geq 1$ has its global minimum label in the $A$ -component precisely when label $1$ is among the $k$ chosen $A$ -labels. Among the $(k n)$ subsets of size $k$ , those containing $1$ number $(k - 1 n - 1)$ , a fraction $\frac{k}{n}$ . Hence, weighting Proposition 1's count, $$ c_n = \sum_{k\ge1}\binom{n-1}{k-1}a_k b_{n-k} = \sum_{k\ge1}\frac{k}{n}\binom{n}{k}a_k b_{n-k} = \frac{1}{n}\sum_{k}\binom{n}{k}(k,a_k)b_{n-k}. $$ Now $k a_{k}$ is the size- $k$ count of $\partial_{z} A$ shifted: $\partial_{z} A (z) = \sum_{k \geq 1} a_{k} \frac{z ^{k - 1}}{( k - 1 )!} = \sum_{m \geq 0} (m + 1) a_{m + 1} \frac{z ^{m}}{m !}$ , the EGF of $((k) a_{k})$ re-indexed. The product $(\partial_{z} A) \cdot B$ is, by Proposition 1, the EGF of $\sum_{j} (j n - 1) ((j + 1) a_{j + 1}) b_{n - 1 - j}$ at size $n - 1$ , i.e. $n c_{n}$ at size $n - 1$ ; integrating $\int_{0}^{z}$ shifts $z^{n - 1} / (n - 1)! \mapsto z^{n} / n!$ and divides the coefficient by $n$ , returning $c_{n} \frac{z ^{n}}{n !}$ . Therefore $\int_{0}^{z} (\partial_{t} A) B d t = \sum_{n} c_{n} \frac{z ^{n}}{n !}$ . $□$

Proposition 4 (permutations, set partitions, surjections by specification). The specifications $SET (CYC (Z))$ , $SET (SET_{\geq 1} (Z))$ , and $SEQ (SET_{\geq 1} (Z))$ have EGFs $\frac{1}{1 - z}$ , $e^{e^{z} - 1}$ , and $\frac{1}{2 - e ^{z}}$ , counting permutations ( $n!$ ), set partitions ( $B_{n}$ ), and surjections.

Proof. $CYC (Z)$ has EGF $lo g \frac{1}{1 - z}$ by Proposition 2 (with $A = z$ ). Then $SET (CYC (Z))$ has EGF $exp (lo g \frac{1}{1 - z}) = \frac{1}{1 - z} = \sum_{n} n! \frac{z ^{n}}{n !}$ , so the size- $n$ count is $n!$ ; this is the cycle decomposition of a permutation, an unordered set of its cycles. $SET_{\geq 1} (Z)$ has EGF $e^{z} - 1$ (nonempty blocks of labels). Then $SET (SET_{\geq 1} (Z))$ has EGF $exp (e^{z} - 1) = \sum_{n} B_{n} \frac{z ^{n}}{n !}$ , the Bell numbers, counting partitions of ${1, \dots, n}$ into nonempty blocks. Replacing the outer SET by SEQ orders the blocks: $SEQ (SET_{\geq 1} (Z))$ has EGF $\frac{1}{1 - ( e ^{z} - 1 )} = \frac{1}{2 - e ^{z}}$ , counting surjections (ordered set partitions). Each specification's EGF follows mechanically from Proposition 2; the combinatorial reading is the standard component decomposition. $□$

Connections Master

The unlabelled symbolic method of 40.08.01 runs the identical construction-to-operation program with ordinary generating functions: disjoint union, product, and sequence translate to $+$ , $\times$ , $\frac{1}{1 - A}$ in both worlds, but the unlabelled SET becomes the Euler transform $exp (\sum_{k} \frac{1}{k} A (z^{k}))$ and the unlabelled CYC carries the totient $\sum_{k} \frac{φ ( k )}{k} lo g \frac{1}{1 - A ( z ^{k} )}$ , whereas this unit's labelled SET and CYC collapse to $exp (A)$ and $lo g \frac{1}{1 - A}$ . The two units are the paired halves of one method; 40.08.01 owns the OGF dictionary and the labelling-removes-symmetry contrast is the exact seam between them.
The exponential generating-function algebra, the binomial convolution, and the exponential formula on which every translation here rests are developed at 40.01.03; the labelled product rule is that unit's EGF product rule, the SET translation is its exponential formula, and the compositional/substitution translation is its compositional formula. This unit lifts those formal identities into a construction calculus: where 40.01.03 proves $exp (A)$ is the EGF of sets of connected components, this unit makes $SET$ a first-class operation that any specification may invoke.
The Cayley tree function $T = z e^{T}$ produced here as the specification $Z ⋆ SET (T)$ is solved in closed form by the Lagrange inversion of 40.01.07, which supplies $[z^{n}] T = \frac{n ^{n - 1}}{n !}$ and the matrix-tree and Prüfer counts of labelled trees; this unit gives the symbolic specification, that unit gives the inversion that extracts its coefficients, and the singularity of $T$ at $z = e^{- 1}$ feeds the tree asymptotics downstream.
The saddle-point method of 40.08.06, co-produced in this chapter, extracts the asymptotics of exactly the EGFs this unit constructs: the Bell-number EGF $e^{e^{z} - 1}$ , the involution EGF $e^{z + z^{2} /2}$ , and the fragmented-permutation EGF $e^{z / (1 - z)}$ are entire or essentially-singular functions whose coefficient growth is governed by a saddle point rather than a pole; this unit produces the functions exactly, and 40.08.06 reads off their large- $n$ behaviour and the associated component-count limit laws of the exp-log schema.

Historical & philosophical context Master

The labelled product and its exponential-generating-function calculus crystallised through several independent lines. Pólya's 1937 cycle-index enumeration ^{[Stanley §5.1]} supplied the set/cycle constructions in the symmetry-laden unlabelled setting; the labelled simplification, in which distinct labels make the relevant group actions free, was made systematic by the "exponential formula" of mid-twentieth-century combinatorics (Riddell, Uhlenbeck, Ford, and others on connected-graph enumeration) and by the Foata-Schützenberger (1970) calculus of the shuffle (partitional) product, which gave the labelled product its algebraic form.

The functorial foundation is André Joyal's 1981 Une théorie combinatoire des séries formelles (Advances in Mathematics 42, 1-82) ^{[Stanley §5.1, citing Joyal]}, which recast a labelled class as a species — a functor on the groupoid of finite sets and bijections — and identified the EGF as the species' generating series, the constructions $+, ⋆, E, CYC, \circ$ as functorial operations, and the SET-equals- $exp$ and CYC-equals- $lo g \frac{1}{1 - A}$ rules as theorems about the exponential and cyclic species. The boxed product and its integral translation, organising least-label-first decompositions and the increasing structures, were developed within the analytic-combinatorics program; the complete codification of the labelled symbolic method as an automatic specification-to-EGF translation with the supercritical-sequence and exp-log limit-law schemas is due to Flajolet and Sedgewick, whose Analytic Combinatorics (2009) Chapter II is the form in which the method is now taught and on which 40.08.01 and 40.08.06 build their singularity and saddle-point analyses.

Bibliography Master

@book{flajoletsedgewick2009,
  author    = {Flajolet, Philippe and Sedgewick, Robert},
  title     = {Analytic Combinatorics},
  publisher = {Cambridge University Press},
  year      = {2009}
}

@book{stanley1999ec2,
  author    = {Stanley, Richard P.},
  title     = {Enumerative Combinatorics, Volume 2},
  series    = {Cambridge Studies in Advanced Mathematics},
  volume    = {62},
  publisher = {Cambridge University Press},
  year      = {1999}
}

@book{stanley2012ec1,
  author    = {Stanley, Richard P.},
  title     = {Enumerative Combinatorics, Volume 1},
  series    = {Cambridge Studies in Advanced Mathematics},
  volume    = {49},
  edition   = {2},
  publisher = {Cambridge University Press},
  year      = {2012}
}

@book{wilf2006gfology,
  author    = {Wilf, Herbert S.},
  title     = {generatingfunctionology},
  edition   = {3},
  publisher = {A K Peters},
  year      = {2006}
}

@article{joyal1981species,
  author  = {Joyal, Andr\'{e}},
  title   = {Une th\'{e}orie combinatoire des s\'{e}ries formelles},
  journal = {Advances in Mathematics},
  volume  = {42},
  number  = {1},
  year    = {1981},
  pages   = {1--82}
}

@article{foataschutzenberger1970,
  author    = {Foata, Dominique and Sch\"{u}tzenberger, Marcel-Paul},
  title     = {Th\'{e}orie g\'{e}om\'{e}trique des polyn\^{o}mes eul\'{e}riens},
  series    = {Lecture Notes in Mathematics},
  volume    = {138},
  publisher = {Springer},
  year      = {1970}
}

@article{polya1937cycleindex,
  author  = {P\'{o}lya, George},
  title   = {Kombinatorische Anzahlbestimmungen f\"{u}r Gruppen, Graphen und chemische Verbindungen},
  journal = {Acta Mathematica},
  volume  = {68},
  year    = {1937},
  pages   = {145--254}
}

Prerequisites

40.01.03
40.01.07

Tier anchors

beginner: Flajolet-Sedgewick 2009 *Analytic Combinatorics* (Cambridge) Ch. II read for the picture-first labelled-atom and label-shuffle examples (set partitions, permutations as cycle-sets); Wilf 2006 *generatingfunctionology* 3e (A K Peters) Ch. 3 for the EGF bookkeeping by hand
intermediate: Flajolet-Sedgewick 2009 *Analytic Combinatorics* (Cambridge) §II.1-II.4 (labelled classes, the labelled product, the EGF translations of SEQ/SET/CYC, the boxed product); Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e (Cambridge) §2.1-2.4 and §5.1 (the exponential and compositional formulae); Wilf 2006 *generatingfunctionology* 3e Ch. 3
master: Flajolet-Sedgewick 2009 *Analytic Combinatorics* (Cambridge) Ch. II in full — the labelled (partitional) product and its EGF translation, the SEQ/SET/CYC dictionary, the boxed product as the integral operator $\int_0^z (\partial_t A)\,B\,dt$, pointing and substitution, supercritical sequences and the exp-log schema (Theorems II.1-II.5, Propositions II.4-II.6); Stanley 1999 *Enumerative Combinatorics, Volume 2* (Cambridge) Ch. 5 (the exponential / compositional formulae, species); Joyal 1981 *Une théorie combinatoire des séries formelles* (Adv. Math. 42) for the functorial (species) foundation; Foata-Schützenberger 1970 for the labelled-product / shuffle calculus

References

Flajolet, P. & Sedgewick, R. — Analytic Combinatorics · Cambridge University Press (2009), Chapter II 'Labelled Structures and Exponential Generating Functions'. §II.1 fixes labelled combinatorial classes (objects of size $n$ carry the distinct labels $1,\dots,n$) and the exponential generating function $A(z) = \sum_n a_n z^n/n!$; §II.2 defines the labelled (partitional) product $A \star B$ by distributing the label set $\{1,\dots,n\}$ over an $A$-component and a $B$-component in all $\binom{n}{|alpha|}$ ways and proves the product translation $A(z)B(z)$; §II.3 derives the labelled constructions SEQ$(A) \to 1/(1-A(z))$, SET$(A) \to \exp(A(z))$, CYC$(A) \to \log(1-A(z))^{-1}$, with restricted (cardinality-bounded) variants; §II.4 introduces the boxed product $A^{\square}\star B$ (the smallest label constrained to the $A$-component), translating to the integral $\int_0^z (\partial_t A(t))\,B(t)\,dt$, and pointing $\Theta A \to z\,\partial_z A(z)$. The worked specifications are set partitions (SET$\circ$SET$_{\ge1}$, EGF $e^{e^z-1}$, Bell numbers), permutations as SET$($CYC$(Z))$ with EGF $1/(1-z)$, surjections SEQ$($SET$_{\ge1}(Z))$ with EGF $1/(2-e^z)$, the Cayley tree function $T = ze^T$, involutions $e^{z+z^2/2}$, and fragmented permutations; the supercritical-sequence and exp-log schemas (Propositions IX.x previewed) give the component-count limit laws.
Stanley, R. P. — Enumerative Combinatorics, Volume 1 and Volume 2 · Vol. 1 (Cambridge Studies in Advanced Mathematics 49, 2e 2012) §2.1-2.4 develops exponential generating functions and the binomial/labelled product rule $h_n = \sum_k \binom{n}{k} f_k g_{n-k}$, with set partitions (Bell numbers, $e^{e^x-1}$), permutations by cycle type, and surjections (ordered set partitions, EGF $1/(2-e^x)$) as worked instances; §5.1 of Vol. 2 (1999) states the exponential formula EGF(all) = exp(EGF(connected)) and the compositional formula $G(F(x))$ in the species/labelled setting, and §5.2 treats the permutation-cycle and set-partition refinements with secondary variables marking the number of components.
Wilf, H. S. — generatingfunctionology · A K Peters, 3rd edition (2006), Chapter 3 'Cards, Decks, and Hands: The Exponential Formula'. Develops the EGF as the device for labelled ('card') problems, the product rule as the binomial convolution arising from dealing a labelled deck into two hands, and the exponential formula 'deck enumerator to hand enumerator' $D(x) \to e^{D(x)}$ for the SET construction, with set partitions, permutations by cycles, and 2-regular graphs (involutions and beyond) as the worked card-deck instances.

Estimated time

beginner: 22m
intermediate: 52m
master: 92m