40.08.01 · combinatorics / analytic-combinatorics-asymptotics

The Symbolic Method for Unlabelled Structures

shipped3 tiersLean: none

Anchor (Master): Flajolet-Sedgewick 2009 *Analytic Combinatorics* (Cambridge) Ch. I-II and Ch. IV-VI (the symbolic method feeding singularity analysis); Bergeron-Labelle-Leroux 1998 *Combinatorial Species and Tree-like Structures* (Cambridge) Ch. 1-3 for the species-theoretic foundation of the unlabelled/labelled dictionary; Pólya 1937 *Acta Math.* 68 (the cycle-index origin of the multiset and cycle translations); Stanley 1999 *Enumerative Combinatorics, Volume 2* (Cambridge) Ch. 5 for the symbolic algebra of structures

Intuition Beginner

The previous unit taught a trick one problem at a time: write a recurrence, turn it into one equation in a series, divide, and read off the answer. The symbolic method removes the guessing entirely. You describe what your objects are made of — "a binary tree is either empty or a root with a left tree and a right tree", "a word is a row of letters", "a partition is a heap of parts" — and a fixed dictionary hands you the generating function with no algebra invented along the way.

The idea is that a small number of ways of building structures cover almost everything you want to count. You can take two kinds of object and allow either one (a choice). You can glue one object beside another (a pair). You can lay down a row of any length (a sequence). You can throw objects into an unordered heap (a multiset). Each of these building moves has one matching move on the generating function, and the matches never change. So counting becomes translation: you write the recipe for your objects in a tiny structural language, and the dictionary spells out the series.

Why does this matter beyond saving effort? Because once the generating function is written down by recipe, its shape tells you how fast the counts grow. A series that comes from a sequence-of-pieces recipe behaves one way; a series from a tree recipe behaves another. The later units in this chapter read that growth off the generating function directly. This unit builds the bridge: recipe to series. The next stage, singularity analysis, reads series to growth rate.

Visual Beginner

A generating function is still the clothesline of the previous unit: peg $z^{n}$ carries the count of objects of size $n$ . The new content is that each way of assembling objects is one operation on the line, fixed once and used forever. The table below is the start of the dictionary — the unlabelled version, where objects are plain (no name-tags on their pieces).

recipe (how you build the object)	operation on the generating function
use an A-object or a B-object (a choice)	add the two lines: $A (z) + B (z)$
an A-object beside a B-object (a pair)	multiply the two lines: $A (z) B (z)$
a row of any number of A-objects (a sequence)	divide: $1$ over $1 - A (z)$
an unordered heap of A-objects (a multiset)	the Euler product over sizes

Read a row left to right and you have translated a piece of a recipe into a piece of a formula. A full recipe is several rows chained together, and chaining the operations gives one equation for the whole generating function. The rest of the unit explains why each row is the exact bookkeeping for its building move, and works the dictionary on trees, compositions, partitions, and necklaces.

Worked example Beginner

Let us count compositions of a positive integer — the ways to write it as an ordered sum of positive parts. For $3$ the compositions are $3$ , $2 + 1$ , $1 + 2$ , and $1 + 1 + 1$ , so there are $4$ of them. We will get the count for every size at once from a one-line recipe.

Step 1. Name the pieces. A single part is just a positive integer $k$ , drawn as a row of $k$ dots, so it has size $k$ . The class of single parts has one object of each size $1, 2, 3, \dots$ , so its generating function is $z + z^{2} + z^{3} + \dots$ , which equals $z$ divided by $1 - z$ .

Step 2. Write the recipe. A composition is a sequence of parts: lay down one part after another, in order, any number of times (but at least one part for a positive total). The sequence row of the dictionary says: divide $1$ by $1$ minus the part-line.

Step 3. Apply the dictionary. The part-line is $z \div (1 - z)$ . The sequence operation gives $1 \div (1 - \frac{z}{1 - z})$ . Clear the inner fraction: $1 - \frac{z}{1 - z} = \frac{( 1 - z ) - z}{1 - z} = \frac{1 - 2 z}{1 - z}$ , so the whole thing is $\frac{1 - z}{1 - 2 z}$ .

Step 4. Read off counts. Expand $\frac{1 - z}{1 - 2 z}$ . Since $\frac{1}{1 - 2 z} = 1 + 2 z + 4 z^{2} + 8 z^{3} + \dots$ , multiplying by $1 - z$ gives $1 + z + 2 z^{2} + 4 z^{3} + 8 z^{4} + \dots$ . The peg $z^{3}$ carries $4$ , matching our hand count, and the peg $z^{n}$ for $n \geq 1$ carries $2^{n - 1}$ .

What this tells us: a one-clause recipe ("a sequence of parts") produced the closed count $2^{n - 1}$ with no recurrence guessed and no induction run. The dictionary did the counting.

Check your understanding Beginner

Formal definition Intermediate+

A combinatorial class is a finite or countable set $A$ equipped with a size function $∣ \cdot ∣ : A \to Z_{\geq 0}$ such that the number $A_{n} = # {α \in A : ∣ α ∣ = n}$ of objects of each size $n$ is finite. The sequence $(A_{n})_{n \geq 0}$ is the counting sequence, and the ordinary generating function (OGF) of $A$ is $$ A(z) = \sum_{n \ge 0} A_n z^n = \sum_{\alpha \in \mathcal{A}} z^{|\alpha|} \in \mathbb{Z}[[z]], $$ the second form being the combinatorial sum over objects, which collects $z^{∣ α ∣}$ once per object. The formal-power-series algebra (Cauchy product, the unit criterion, formal $exp$ and $lo g$ , formal convergence as coefficientwise stabilisation) is taken from 40.01.03; nothing analytic is assumed of $z$ here.

A class operation is admissible when the counting sequence of the result depends only on the counting sequences of the operands, so that the operation descends to a fixed operation on OGFs. The basic admissible constructions on unlabelled classes, with $A_{0} = 0$ assumed wherever an unbounded construction is formed (no neutral object of size $0$ inside a sequence or multiset, so that formal convergence holds), translate as follows.

Disjoint union $A + B$ (objects of $A$ or of $B$ , kept disjoint, size preserved): $A (z) + B (z)$ .
Cartesian product $A \times B$ (ordered pairs $(α, β)$ with $∣ (α, β) ∣ = ∣ α ∣ + ∣ β ∣$ ): $A (z) B (z)$ , the convolution.
Sequence $SEQ (A) = {ε} + A + (A \times A) + \dots$ (ordered tuples of any length): $\frac{1}{1 - A ( z )}$ .
Multiset $MSET (A)$ (finite unordered collections, repetition allowed): $α \in A \prod \frac{1}{1 - z ^{∣ α ∣}} = n \geq 1 \prod (1 - z^{n})^{- A_{n}} = exp (k \geq 1 \sum \frac{1}{k} A (z^{k}))$ , the Euler transform.
Powerset $PSET (A)$ (finite unordered collections, no repetition): $α \prod (1 + z^{∣ α ∣}) = n \geq 1 \prod (1 + z^{n})^{A_{n}} = exp (k \geq 1 \sum \frac{( - 1 ) ^{k - 1}}{k} A (z^{k}))$ .
Cycle $CYC (A)$ (sequences up to cyclic rotation): $k \geq 1 \sum \frac{φ ( k )}{k} lo g \frac{1}{1 - A ( z ^{k} )}$ , with $φ$ Euler's totient.

Two further operators complete the calculus. Pointing $Θ A$ distinguishes one of the atoms of an object, with OGF $Θ A (z) = z \frac{d}{d z} A (z) = \sum_{n} n A_{n} z^{n}$ . Substitution (composition) $A \circ B = A [B]$ replaces each atom of an $A$ -object by a $B$ -object, with OGF $A (B (z))$ when $B_{0} = 0$ . The symbols $Θ$ , $[z^{n}]$ , $φ$ , $SEQ$ , $MSET$ , $PSET$ , $CYC$ are recorded in _meta/NOTATION.md.

A specification is a (possibly recursive) system of equations writing classes in terms of atoms and these constructions; applying the dictionary term by term turns a specification into a system of equations for the OGFs, which is the engine the rest of the chapter runs.

Counterexamples to common slips Intermediate+

" $SEQ (A)$ always has OGF $1/ (1 - A (z))$ ." It requires $A_{0} = 0$ . If $A$ has an object of size $0$ then $A (0) = A_{0} \neq = 0$ , the geometric series $\sum_{k} A (z)^{k}$ fails to converge formally (infinitely many empty parts can pad any object), and the count at each size is infinite. The same proviso governs $MSET$ , $PSET$ , and $CYC$ .
"Multiset and sequence give the same generating function." The sequence is ordered and gives $1/ (1 - A)$ ; the multiset is unordered and gives $exp (\sum_{k} A (z^{k}) / k)$ . They agree only in degenerate cases. For a single atom $A = {∙}$ ( $A (z) = z$ ), $SEQ \to 1/ (1 - z)$ but $MSET \to \prod_{n} (1 - z^{n})^{- [n = 1]} = 1/ (1 - z)$ coincide because one atom cannot be permuted; with two atom-types the unordered count is strictly smaller.
"The multiset OGF is $\prod_{α} (1 - z^{∣ α ∣})^{- 1}$ and the exponential form is a different rule." They are equal. Taking $lo g$ of the product, $\sum_{α} lo g \frac{1}{1 - z ^{∣ α ∣}} = \sum_{α} \sum_{k \geq 1} \frac{z ^{k ∣ α ∣}}{k} = \sum_{k \geq 1} \frac{1}{k} \sum_{α} z^{k ∣ α ∣} = \sum_{k} \frac{A ( z ^{k} )}{k}$ , so exponentiating recovers the product. The two forms are one translation read two ways.
"Pointing changes the class being counted." Pointing $Θ A$ counts $A$ -objects each carrying a marked atom, so $(Θ A)_{n} = n A_{n}$ : the total count is reweighted by size, not altered in kind. It is the combinatorial face of the operator $z d / d z$ and is the standard device for turning a recursive specification into one solvable by the pointing-and-substitution method.

Key theorem with proof Intermediate+

The signature theorem is the admissibility and OGF translation of the multiset construction, the Euler transform, because it is the first construction whose translation is not a one-line algebraic rule but a genuine combinatorial identity — the passage from an unordered infinite product to an exponential of size-substituted copies — and it is the unlabelled prototype of every later "set of components" translation ^{[Flajolet-Sedgewick Ch. I.2]}.

Theorem (multiset construction). Let $A$ be a combinatorial class with $A_{0} = 0$ and OGF $A (z) = \sum_{n \geq 1} A_{n} z^{n}$ . The multiset class $MSET (A)$ of finite unordered collections of $A$ -objects, with repetition allowed and the size of a collection equal to the sum of its members' sizes, is admissible, and its OGF is $$ M(z) = \prod_{\alpha \in \mathcal{A}}\frac{1}{1 - z^{|\alpha|}} = \prod_{n \ge 1}\frac{1}{(1 - z^n)^{A_n}} = \exp!\Big(\sum_{k \ge 1}\frac{1}{k}A(z^k)\Big). $$

Proof. Choose any enumeration $α_{1}, α_{2}, \dots$ of the objects of $A$ . A multiset over $A$ is determined by, for each object $α_{i}$ , a multiplicity $m_{i} \in Z_{\geq 0}$ recording how many copies of $α_{i}$ it contains, with only finitely many $m_{i}$ nonzero. Its size is $\sum_{i} m_{i} ∣ α_{i} ∣$ , so the contribution of $α_{i}$ across all multiplicities is $\sum_{m_{i} \geq 0} z^{m_{i} ∣ α_{i} ∣} = \frac{1}{1 - z ^{∣ α_{i} ∣}}$ . Because each object of size $n \geq 1$ contributes a factor of order $\geq n$ , every coefficient of the formal product is determined by finitely many factors, so the product converges formally and $$ M(z) = \sum_{\text{multisets}} z^{\text{size}} = \prod_{i}\frac{1}{1 - z^{|\alpha_i|}} = \prod_{n \ge 1}\Big(\frac{1}{1 - z^n}\Big)^{A_n}, $$ collecting the $A_{n}$ objects of each size $n$ into a common exponent. This already shows admissibility: $M (z)$ depends only on the counts $A_{n}$ . For the exponential form, take the formal logarithm and expand each factor by the series $lo g \frac{1}{1 - u} = \sum_{k \geq 1} \frac{u ^{k}}{k}$ with $u = z^{n}$ : $$ \log M(z) = \sum_{n \ge 1} A_n \log\frac{1}{1 - z^n} = \sum_{n \ge 1} A_n \sum_{k \ge 1}\frac{z^{nk}}{k} = \sum_{k \ge 1}\frac{1}{k}\sum_{n \ge 1}A_n (z^k)^n = \sum_{k \ge 1}\frac{1}{k}A(z^k), $$ where interchanging the two sums is valid coefficientwise because for fixed total degree only finitely many pairs $(n, k)$ contribute. Exponentiating gives $M (z) = exp (\sum_{k \geq 1} \frac{1}{k} A (z^{k}))$ . $□$

Corollary (integer partitions). Take $A = Z_{\geq 1}$ , one object of each size $n \geq 1$ , so $A (z) = \sum_{n \geq 1} z^{n} = \frac{z}{1 - z}$ and $A_{n} = 1$ . A multiset of positive integers is exactly an integer partition, so the partition OGF is $P (z) = \prod_{n \geq 1} \frac{1}{1 - z ^{n}} = exp (\sum_{k \geq 1} \frac{1}{k} \frac{z ^{k}}{1 - z ^{k}})$ , the Euler product foreshadowed at 40.01.06.

Bridge. This theorem is the foundational reason the unlabelled dictionary closes: the multiset translation shows that an unordered construction, where the naive product would overcount by the symmetries of repeated parts, is still admissible, and the device that absorbs those symmetries — the substitution $z \mapsto z^{k}$ summed with weight $1/ k$ — is exactly the Pólya cycle-index of the symmetric group acting on the copies, which builds toward the cycle construction's totient sum $\sum_{k} \frac{φ ( k )}{k} lo g \frac{1}{1 - A ( z ^{k} )}$ where the cyclic group replaces the symmetric one. This is exactly the unlabelled counterpart of the labelled exponential formula of 40.01.03: there a set of labelled components gives $exp (C (z))$ with no symmetry correction because labels break all symmetry, and the central insight is that the $z^{k}$ -substitutions here are precisely the price of having no labels. The multiset translation appears again in 40.06.10 as Pólya-Redfield enumeration and generalises to the species-level statement that the unlabelled OGF is the cycle-index series evaluated on the diagonal; putting these together, the symbolic method is one calculus with two specialisations, unlabelled OGF and labelled EGF, and the bridge is the cycle index that interpolates between them.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Binary trees (each internal node has an ordered left and right child; size = number of internal nodes) satisfy $B = {ε} + Z \times B \times B$ . Translate and solve for $B (z)$ , and confirm $[z^{n}] B = C_{n}$ , the Catalan number.

Hint

The empty tree contributes $1$ ; a nonempty tree is a root atom (OGF $z$ ) times two subtrees. Translate to $B = 1 + z B^{2}$ .

Answer

The disjoint union and product translate the specification to $B (z) = 1 + z B (z)^{2}$ . Solving the quadratic $z B^{2} - B + 1 = 0$ and choosing the root with $B (0) = 1$ gives $B (z) = \frac{1 - 1 - 4 z}{2 z}$ , whose coefficients are $[z^{n}] B = \frac{1}{n + 1} (n 2 n) = C_{n}$ . The recipe alone — "empty, or a root with two subtrees" — delivered the Catalan generating function. Rubric: full credit for the union-plus-product translation, the quadratic, and the Catalan closed form.

Exercise 6 (medium, symbolic).

Prove that the multiset and powerset OGFs of a class $A$ (with $A_{0} = 0$ ) satisfy $MSET (A)$ has OGF $exp (\sum_{k} A (z^{k}) / k)$ and $PSET (A)$ has OGF $exp (\sum_{k} (- 1)^{k - 1} A (z^{k}) / k)$ .

Hint

For $PSET$ each object appears at most once, contributing a factor $(1 + z^{∣ α ∣})$ ; take logs and use $lo g (1 + u) = \sum_{k} (- 1)^{k - 1} u^{k} / k$ .

Answer

For the multiset, each object $α$ contributes $\sum_{m \geq 0} z^{m ∣ α ∣} = (1 - z^{∣ α ∣})^{- 1}$ , so $M (z) = \prod_{n} (1 - z^{n})^{- A_{n}}$ ; taking $lo g$ and expanding $lo g \frac{1}{1 - u} = \sum_{k} u^{k} / k$ with $u = z^{n}$ gives $lo g M = \sum_{n} A_{n} \sum_{k} \frac{z ^{nk}}{k} = \sum_{k} \frac{1}{k} A (z^{k})$ . For the powerset, each object contributes $(1 + z^{∣ α ∣})$ , so $S (z) = \prod_{n} (1 + z^{n})^{A_{n}}$ ; taking $lo g$ and expanding $lo g (1 + u) = \sum_{k} \frac{( - 1 ) ^{k - 1}}{k} u^{k}$ gives $lo g S = \sum_{n} A_{n} \sum_{k} \frac{( - 1 ) ^{k - 1}}{k} z^{nk} = \sum_{k} \frac{( - 1 ) ^{k - 1}}{k} A (z^{k})$ . Exponentiating both yields the claimed forms. Rubric: full credit for both infinite products, both logarithmic expansions, and the interchange of summation.

Exercise 7 (hard, symbolic).

The relation $MSET (A)$ vs $PSET (A)$ has a clean form: prove that $M (z) = S (z) \cdot M (z^{2})$ , i.e. every multiset is a powerset of "odd-multiplicity cores" times a multiset of "doubled" objects, and read this as a generating-function identity.

Hint

Use the per-object factorisation $\frac{1}{1 - z ^{n}} = (1 + z^{n}) \cdot \frac{1}{1 - z ^{2 n}}$ and take the product over objects with multiplicity $A_{n}$ .

Answer

For a single size $n$ the identity $\frac{1}{1 - z ^{n}} = (1 + z^{n}) \cdot \frac{1}{1 - z ^{2 n}}$ holds since $(1 + z^{n}) (1 - z^{n}) = 1 - z^{2 n}$ . Raising to the power $A_{n}$ and taking the product over $n \geq 1$ , $$ M(z) = \prod_n (1 - z^n)^{-A_n} = \prod_n (1 + z^n)^{A_n}\prod_n (1 - z^{2n})^{-A_n} = S(z)\cdot M(z^2), $$ where the second product is $M$ evaluated at $z^{2}$ because $\prod_{n} (1 - (z^{2})^{n})^{- A_{n}} = M (z^{2})$ . Combinatorially: in a multiset, splitting each object's multiplicity as (parity bit) plus (twice a remaining multiplicity) writes the multiset as a set of objects taken an odd number of times (a powerset choice, $S (z)$ ) superimposed on a multiset of doubled objects ( $M (z^{2})$ ). This is the multiset analogue of the binary expansion of multiplicities, and iterating $M (z) = S (z) S (z^{2}) S (z^{4}) \dots$ recovers the Euler "distinct equals odd-doubling" partition identity when $A_{n} \equiv 1$ . Rubric: full credit for the per-size factorisation, the product manipulation to $S (z) M (z^{2})$ , and the combinatorial reading.

Exercise 8 (hard, symbolic).

A supercritical sequence is a class $SEQ (A)$ where $A (z)$ has radius of convergence $ρ > 0$ and $A (ρ) > 1$ . Show that the OGF $\frac{1}{1 - A ( z )}$ then has its dominant singularity at the unique $σ \in (0, ρ)$ with $A (σ) = 1$ , a simple pole, and explain (without proving the asymptotic) why this forces the count $[z^{n}] \frac{1}{1 - A ( z )}$ to grow like a constant times $σ^{- n}$ .

Hint

$A$ is increasing and continuous on $[0, ρ)$ with $A (0) = 0$ and $A (ρ^{-}) > 1$ , so by the intermediate value theorem there is a unique $σ$ with $A (σ) = 1$ ; the denominator $1 - A (z)$ vanishes there.

Answer

On $[0, ρ)$ the series $A (z) = \sum_{n \geq 1} A_{n} z^{n}$ has nonnegative coefficients (not all zero), so $A$ is continuous and strictly increasing with $A (0) = 0$ ; the supercritical hypothesis $A (ρ^{-}) > 1$ then gives, by the intermediate value theorem, a unique $σ \in (0, ρ)$ with $A (σ) = 1$ . At $z = σ$ the denominator of $F (z) = \frac{1}{1 - A ( z )}$ vanishes while the numerator is $1$ , and $A^{'} (σ) > 0$ (strict monotonicity / positive coefficients), so $1 - A (z)$ has a simple zero and $F$ a simple pole at $σ$ . Since $σ < ρ$ , this pole is closer to the origin than any singularity of $A$ itself, so it is the dominant singularity of $F$ . A simple pole at $σ$ contributes a term $\frac{c}{1 - z / σ}$ to the partial-fraction/local expansion, whose coefficients are $c σ^{- n}$ ; the principle that the coefficient asymptotics are governed by the dominant singularity (the content of the singularity-analysis units 40.08.04) then forces $[z^{n}] F \sim c σ^{- n}$ . The exponential growth rate is the reciprocal of the smallest positive root of $A (z) = 1$ . Rubric: full credit for the existence/uniqueness of $σ$ by monotonicity, the simple-pole identification, the dominance $σ < ρ$ , and the heuristic for $σ^{- n}$ growth.

Advanced results Master

The dictionary is closed under the constructions and the two operators, and its reach extends through recursive specifications, the supercritical schema, the pointing-and-substitution solution of tree recursions, and the cycle-index unification that places the unlabelled OGF and the labelled EGF inside one species-theoretic framework.

Theorem 1 (closure and the symbolic transfer). The class of OGFs obtainable from finite sets of atoms by finitely many applications of $+$ , $\times$ , $SEQ$ , $MSET$ , $PSET$ , $CYC$ , pointing $Θ$ , and substitution is exactly the family solving a finite constructible system. Each construction is admissible — its result-counting sequence depends only on the operand sequences — so a specification $S = Φ (S; Z)$ in these constructions translates termwise to a fixed-point system $S (z) = Ψ (S (z); z)$ for the OGFs, where $Ψ$ is built from $+, \times, \frac{1}{1 -\cdot}, exp (\sum_{k} \cdot (z^{k}) / k)$ , and composition. When the system is proper (no $ε$ -cycle), it has a unique formal-power-series solution computable coefficient by coefficient ^{[Flajolet-Sedgewick Ch. I]}.

Theorem 2 (iterated multiset and the Euler transform). For a class $A$ with counting sequence $(A_{n})_{n \geq 1}$ , the multiset $MSET (A)$ has counting sequence $(M_{n})$ given by the Euler transform: $\prod_{n \geq 1} (1 - z^{n})^{- A_{n}} = \sum_{n} M_{n} z^{n}$ , equivalently $lo g \sum_{n} M_{n} z^{n} = \sum_{k \geq 1} \frac{1}{k} A (z^{k})$ . The unlabelled enumeration of rooted unordered trees ( $T = Z \times MSET (T)$ ), of forests, of multigraphs by their connected components, and of integer partitions are all instances; the recursion $T (z) = z exp (\sum_{k} T (z^{k}) / k)$ has no closed form but is computable to any order and has a determinable exponential growth rate $\approx 2.955 7^{n}$ (Otter's constant) by singularity analysis ^{[Flajolet-Sedgewick Ch. I.5, VII]}.

Theorem 3 (cycle construction and the totient sum). The cycle class $CYC (A)$ of nonempty sequences modulo cyclic rotation has OGF $$ \mathrm{CYC}(A)(z) = \sum_{k \ge 1}\frac{\varphi(k)}{k}\log\frac{1}{1 - A(z^k)}, $$ obtained from the Pólya cycle index of the cyclic group $C_{n}$ , $Z (C_{n}) = \frac{1}{n} \sum_{d ∣ n} φ (d) p_{d}^{n / d}$ , substituted with the figure-counting series $A$ . For a finite alphabet of $m$ letters ( $A (z) = m z$ ) this gives the necklace OGF $\sum_{n \geq 1} \frac{1}{n} \sum_{d ∣ n} φ (d) m^{n / d} z^{n}$ , the Moreau/Pólya necklace count; the full Pólya-Redfield theory of counting under a group action is developed at 40.06.10 ^{[Pólya 1937]}.

Theorem 4 (pointing-substitution and the tree dictionary). Pointing $Θ$ and substitution interact through the chain rule: $Θ (A \circ B) = (Θ A \circ B) \cdot \frac{Θ B}{B}$ at the level of OGFs reflects marking an atom inside a substituted structure. For a simple variety of trees specified by $Y = Z \times ϕ (Y)$ with $ϕ$ a construction (sequence, multiset, set of children), the OGF satisfies $Y = z ϕ (Y)$ , and the smooth implicit-function / inversion schema applies: $Y (z)$ has a square-root singularity at the value $ρ$ where $1 = ρ ϕ^{'} (Y (ρ))$ with $Y (ρ)$ the corresponding critical value, yielding the universal $n^{- 3/2} ρ^{- n}$ tree asymptotic. This is the analytic destination of the Lagrange-inversion algebra of 40.01.07 ^{[Flajolet-Sedgewick Ch. VI-VII]}.

Theorem 5 (supercritical sequence schema). If $F = SEQ (A)$ with $A (z)$ having radius of convergence $ρ > 0$ and $A (ρ) > 1$ (the supercritical condition), then $F (z) = \frac{1}{1 - A ( z )}$ has a simple pole at the unique root $σ \in (0, ρ)$ of $A (σ) = 1$ , and $[z^{n}] F \sim \frac{σ ^{- n}}{σ A ^{'} ( σ )}$ . The mean number of $A$ -components in a random size- $n$ object is asymptotically linear in $n$ , with the Gaussian limit law of the supercritical-composition scheme. The schema covers compositions, surjections (in the labelled mirror), and walks returning to a finite state space, and is the cleanest meeting point of the symbolic method and singularity analysis ^{[Flajolet-Sedgewick Ch. V]}.

Synthesis. The symbolic method is the foundational reason combinatorial enumeration is a calculus rather than a catalogue of tricks: a class becomes a generating function, a way of building objects becomes a fixed operation on generating functions, and a structural recipe becomes a system of equations solved once. The central insight is that one dictionary governs everything — disjoint union to $+$ , product to $\times$ , sequence to $\frac{1}{1 - A}$ , multiset to the Euler transform $exp (\sum_{k} A (z^{k}) / k)$ , powerset to its alternating-sign cousin, and cycle to the totient sum — and the unordered constructions differ from the ordered ones by exactly the cycle-index symmetry corrections, so the multiset and cycle rows are the Pólya cycle indices of the symmetric and cyclic groups substituted into the figure series. This is exactly dual to the labelled EGF dictionary of 40.01.03, where labels destroy all symmetry and the set construction collapses to $exp (C)$ with no $z^{k}$ -substitution; putting these together, the unlabelled OGF and the labelled EGF are two evaluations of one species, the type series and the exponential series, and the bridge is the cycle index that interpolates between them. Every closed or recursive OGF the dictionary produces — $\frac{1 - z}{1 - 2 z}$ for compositions, $\frac{1 - 1 - 4 z}{2}$ for plane trees, $\prod (1 - z^{n})^{- 1}$ for partitions, $z exp (\sum_{k} T (z^{k}) / k)$ for unordered trees — carries its growth rate in its dominant singularity, which generalises the partial-fraction asymptotics of 40.01.04 to the algebraic and transcendental singularities of this chapter. The formal recipe and the analytic growth rate are one object read at two resolutions.

Full proof set Master

Proposition 1 (admissibility of union, product, sequence). For unlabelled classes with $A_{0} = B_{0} = 0$ in the sequence case: $A + B$ has OGF $A + B$ ; $A \times B$ has OGF $A B$ ; $SEQ (A)$ has OGF $\frac{1}{1 - A}$ .

Proof. For the disjoint union, the objects of size $n$ are the $A_{n}$ objects from $A$ together with the $B_{n}$ from $B$ , with no overlap, so the count is $A_{n} + B_{n}$ and the OGF is $A (z) + B (z)$ . For the product, an object of size $n$ is a pair $(α, β)$ with $∣ α ∣ + ∣ β ∣ = n$ ; the number of such pairs is $\sum_{k = 0}^{n} A_{k} B_{n - k}$ , the Cauchy convolution, so the OGF is $A (z) B (z)$ by the definition of the product in $Z [[z]]$ (from 40.01.03). For the sequence, $SEQ (A) = ⨆_{r \geq 0} A^{r}$ with $A^{0} = {ε}$ the empty tuple of size $0$ ; since $A_{0} = 0$ , the $r$ -fold product $A^{r}$ has OGF $A (z)^{r}$ with lowest term of order $\geq r$ , so for fixed $n$ only $r \leq n$ contribute and $\sum_{r \geq 0} A (z)^{r}$ converges formally to $\frac{1}{1 - A ( z )}$ (the constant term of $1 - A$ is $1$ , a unit). $□$

Proposition 2 (multiset, exponential form). With $A_{0} = 0$ , $MSET (A)$ has OGF $\prod_{n \geq 1} (1 - z^{n})^{- A_{n}} = exp (\sum_{k \geq 1} \frac{1}{k} A (z^{k}))$ .

Proof. As established in the Key theorem, indexing a multiset by the multiplicity function $α \mapsto m_{α} \in Z_{\geq 0}$ (finitely supported) gives $M (z) = \prod_{α} \sum_{m \geq 0} z^{m ∣ α ∣} = \prod_{α} (1 - z^{∣ α ∣})^{- 1} = \prod_{n \geq 1} (1 - z^{n})^{- A_{n}}$ , the product converging formally because the factor for an object of size $n$ is $1 + O (z^{n})$ . Apply formal $lo g$ (well-defined since the product has constant term $1$ ): $lo g M = \sum_{n \geq 1} A_{n} lo g (1 - z^{n})^{- 1} = \sum_{n \geq 1} A_{n} \sum_{k \geq 1} \frac{z ^{nk}}{k}$ . The double series is summable coefficientwise: the coefficient of $z^{N}$ receives contributions only from pairs with $nk = N$ , finitely many. Reindexing by $k$ first, $lo g M = \sum_{k \geq 1} \frac{1}{k} \sum_{n \geq 1} A_{n} z^{nk} = \sum_{k \geq 1} \frac{1}{k} A (z^{k})$ , and $M = exp (lo g M)$ because $M$ has constant term $1$ . $□$

Proposition 3 (cycle construction). With $A_{0} = 0$ , $CYC (A)$ , the nonempty sequences modulo cyclic rotation, has OGF $\sum_{k \geq 1} \frac{φ ( k )}{k} lo g \frac{1}{1 - A ( z ^{k} )}$ .

Proof. A length- $r$ sequence of $A$ -objects (with multiplicities) has a cyclic symmetry group; by Burnside's lemma the number of cyclic classes weights each sequence by the reciprocal of its orbit size. The cyclic group $C_{r}$ acting on $r$ -tuples has cycle index $Z (C_{r}) = \frac{1}{r} \sum_{d ∣ r} φ (d) p_{d}^{r / d}$ , where $p_{d}$ is the power-sum placeholder; substituting the figure series so that $p_{d} \mapsto A (z^{d})$ and summing the generating function over all $r \geq 1$ gives, after collecting by $d = k$ and using $\sum_{r : k ∣ r} \frac{1}{r} A (z^{k})^{r / k} = \frac{1}{k} \sum_{j \geq 1} \frac{1}{j} A (z^{k})^{j} = \frac{1}{k} lo g \frac{1}{1 - A ( z ^{k} )}$ , the total $\sum_{k \geq 1} \frac{φ ( k )}{k} lo g \frac{1}{1 - A ( z ^{k} )}$ . The interchange and the geometric resummation are valid coefficientwise because $A (z^{k})^{j}$ has order $\geq j k$ , so each coefficient is a finite sum. $□$

Proposition 4 (substitution and pointing). If $B_{0} = 0$ , the substituted class $A [B]$ (each atom of an $A$ -object replaced by a $B$ -object) has OGF $A (B (z))$ ; and the pointed class $Θ A$ (one atom distinguished) has OGF $z A^{'} (z) = \sum_{n} n A_{n} z^{n}$ .

Proof. For substitution, an $A$ -object of size $r$ has $r$ atoms; replacing each by a $B$ -object independently and summing sizes, the contribution of that object is $B (z)^{r}$ , so $A [B]$ has OGF $\sum_{r} A_{r} B (z)^{r} = A (B (z))$ , convergent formally because $B_{0} = 0$ makes $B (z)^{r}$ of order $\geq r$ . For pointing, an object of size $n$ admits $n$ choices of distinguished atom, so the pointed class has $n A_{n}$ objects of size $n$ , OGF $\sum_{n} n A_{n} z^{n} = z \frac{d}{d z} \sum_{n} A_{n} z^{n} = z A^{'} (z)$ . The chain rule $\frac{d}{d z} A (B (z)) = A^{'} (B (z)) B^{'} (z)$ then expresses $Θ (A [B])$ through $Θ A$ and $Θ B$ , the recursion-unwinding identity used to solve pointed tree specifications. $□$

Connections Master

The unlabelled OGF dictionary is the exact mirror of the labelled EGF dictionary built in 40.01.03: there the set construction of labelled components gives $exp (C (z))$ with no symmetry correction because labels break every symmetry, while here the multiset gives $exp (\sum_{k} A (z^{k}) / k)$ with the $z^{k}$ -substitutions supplying precisely the missing symmetry corrections. The labelled exponential formula and the unlabelled Euler transform are the two evaluations — exponential series and type series — of one combinatorial species, and the co-produced labelled-EGF symbolic-method unit 40.08.02 develops the labelled half of this dictionary in the analytic-combinatorics framing.
The cycle and multiset constructions are the generating-function image of Pólya-Redfield enumeration: the totient sum $\sum_{k} \frac{φ ( k )}{k} lo g \frac{1}{1 - A ( z ^{k} )}$ is the cyclic-group cycle index substituted with the figure series, and the Euler transform is the symmetric-group cycle index. The full theory of counting orbits under a group action — the cycle-index polynomial, Burnside's lemma, and the pattern inventory — is owned by 40.06.10; this unit uses its two most common specialisations (necklaces and multisets) as dictionary entries, and the forward link is exact: every unlabelled construction is a cycle-index evaluation.
The integer-partition generating function $\prod_{n \geq 1} (1 - z^{n})^{- 1}$ produced here as $MSET (Z_{\geq 1})$ is the entry point to the $q$ -series and partition theory of 40.01.06, where the same product is read as a $q$ -analogue, refined by largest part and number of parts, and connected to Gaussian binomials and the Rogers-Ramanujan identities. The multiset-vs-powerset identity $M (z) = S (z) M (z^{2})$ proved in the exercises is the symbolic-method shadow of Euler's "partitions into distinct parts equal partitions into odd parts".
The whole point of writing generating functions by recipe is to feed them to singularity analysis: the location and nature of the dominant singularity of $A (z)$ determine the asymptotic growth of $[z^{n}] A$ . The co-produced unit 40.08.04 develops the singularity-analysis transfer theorems (the $Θ$ -class functions, the standard-function scale $\sim n^{α - 1} ρ^{- n}$ ), and the supercritical-sequence and simple-variety-of-trees schemas previewed here in Theorems 4-5 are the cleanest applications; this unit supplies the generating functions whose singularities those units dissect.

Historical & philosophical context Master

The systematic translation of structural descriptions into generating functions has roots in Euler's 1748 Introductio, where the partition product $\prod_{n} (1 - z^{n})^{- 1}$ first appears as the generating function of a multiset of integers, and in the nineteenth-century use of generating functions for trees and graphs by Cayley and Sylvester. The decisive structural step — recognising that a fixed dictionary of constructions translates automatically — came with George Pólya's 1937 cycle-index paper ^{[Pólya 1937]}, which gave the substitution of a figure-counting series into the cycle index of a permutation group and thereby produced the multiset and cycle translations in their general form, applied to counting chemical isomers, graphs, and trees up to symmetry.

The recasting of this into a fully compositional symbolic method, with an explicit OGF/EGF dictionary closed under sum, product, sequence, set/multiset, and cycle, and with the constructions treated as admissible operators, is due to the school of Philippe Flajolet and his collaborators from the 1980s onward, consolidated in Flajolet and Sedgewick's Analytic Combinatorics (2009) ^{[Flajolet-Sedgewick Ch. I]}. The categorical foundation — a species as a functor from finite sets and bijections to finite sets, whose exponential and type generating series are the EGF and OGF — was supplied by André Joyal's 1981 theory of species and developed by Bergeron, Labelle, and Leroux ^{[Bergeron-Labelle-Leroux 1998]}, who proved that the symbolic constructions are the generating-series images of categorical operations on species, explaining structurally why the dictionary closes. The unlabelled OGF is the species' type series, the diagonal evaluation of its cycle-index series.

Bibliography Master

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

@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{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{bll1998species,
  author    = {Bergeron, Fran\c{c}ois and Labelle, Gilbert and Leroux, Pierre},
  title     = {Combinatorial Species and Tree-like Structures},
  series    = {Encyclopedia of Mathematics and its Applications},
  volume    = {67},
  publisher = {Cambridge University Press},
  year      = {1998}
}

@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}
}

@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}
}

@book{euler1748introductio,
  author    = {Euler, Leonhard},
  title     = {Introductio in analysin infinitorum},
  volume    = {1},
  publisher = {Marcum-Michaelem Bousquet},
  address   = {Lausanne},
  year      = {1748}
}

Prerequisites

40.01.03

Tier anchors

beginner: Flajolet-Sedgewick 2009 *Analytic Combinatorics* (Cambridge) Ch. I.1-I.2 (combinatorial classes, the size function, and the first constructions — union and product — read on words, trees, and compositions); Wilf 2006 *generatingfunctionology* 3e (A K Peters) Ch. 1-2 for the sequence-to-series bookkeeping that the symbolic method automates
intermediate: Flajolet-Sedgewick 2009 *Analytic Combinatorics* (Cambridge) Ch. I (Combinatorial Structures and Ordinary Generating Functions): admissible constructions $+, \times, \mathrm{SEQ}, \mathrm{MSET}, \mathrm{PSET}, \mathrm{CYC}$ and their OGF images, pointing and substitution, the dictionary as a compositional calculus; Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e (Cambridge) §1.1-1.2, §3.14 for the multiset/Euler-transform and Pólya-cycle viewpoint
master: Flajolet-Sedgewick 2009 *Analytic Combinatorics* (Cambridge) Ch. I-II and Ch. IV-VI (the symbolic method feeding singularity analysis); Bergeron-Labelle-Leroux 1998 *Combinatorial Species and Tree-like Structures* (Cambridge) Ch. 1-3 for the species-theoretic foundation of the unlabelled/labelled dictionary; Pólya 1937 *Acta Math.* 68 (the cycle-index origin of the multiset and cycle translations); Stanley 1999 *Enumerative Combinatorics, Volume 2* (Cambridge) Ch. 5 for the symbolic algebra of structures

References

Flajolet, P. & Sedgewick, R. — Analytic Combinatorics · Cambridge University Press (2009). Chapter I 'Combinatorial Structures and Ordinary Generating Functions' is the source for this unit. §I.1 defines a combinatorial class as a finite-or-countable set $\mathcal{A}$ with a size function $|\cdot| : \mathcal{A} \to \mathbb{Z}_{\ge 0}$ such that each size has finitely many objects, its counting sequence $A_n = \#\{\alpha \in \mathcal{A} : |\alpha| = n\}$, and its ordinary generating function $A(z) = \sum_n A_n z^n = \sum_{\alpha \in \mathcal{A}} z^{|\alpha|}$. §I.2 develops the admissible unlabelled constructions and their OGF translations: combinatorial sum (disjoint union) $\mathcal{A} + \mathcal{B} \to A(z) + B(z)$; cartesian product $\mathcal{A} \times \mathcal{B} \to A(z)B(z)$; sequence $\mathrm{SEQ}(\mathcal{A}) \to 1/(1 - A(z))$ valid when $A_0 = 0$; multiset $\mathrm{MSET}(\mathcal{A}) \to \prod_{\alpha}(1 - z^{|\alpha|})^{-1} = \exp\big(\sum_{k \ge 1} A(z^k)/k\big)$ (the Euler transform); powerset $\mathrm{PSET}(\mathcal{A}) \to \prod_\alpha (1 + z^{|\alpha|}) = \exp\big(\sum_{k \ge 1}(-1)^{k-1}A(z^k)/k\big)$; cycle $\mathrm{CYC}(\mathcal{A}) \to \sum_{k \ge 1}\frac{\varphi(k)}{k}\log\frac{1}{1 - A(z^k)}$. §I.3-I.4 add pointing $\Theta$ (the operator $z\,d/dz$) and substitution (composition) and tabulate the dictionary; §I.5-I.6 give the worked specifications: binary and general plane trees (Catalan), integer compositions and partitions, necklaces, words avoiding patterns, and the supercritical-sequence schema. The asymptotic extraction is deferred to Part B (singularity analysis, Ch. IV-VI).
Stanley, R. P. — Enumerative Combinatorics, Volume 1 and Volume 2 · Cambridge University Press (Vol. 1, 2e 2012; Vol. 2, 1999). Vol. 1 §1.1-1.2 builds the ordinary generating function and the product/sum dictionary for unlabelled enumeration; §3.14-3.15 develop the multiset construction and the Euler transform $\prod_n (1 - z^n)^{-A_n}$ alongside the cycle-index machinery, and the partition generating function $\prod_{n \ge 1}(1 - z^n)^{-1}$ as the canonical multiset of positive integers. Vol. 2 Ch. 5 treats the symbolic algebra of labelled and unlabelled structures, the exponential and the multiset/Pólya passage, and the species-level unification of the OGF and EGF dictionaries.
Bergeron, F., Labelle, G. & Leroux, P. — Combinatorial Species and Tree-like Structures · Cambridge University Press, Encyclopedia of Mathematics and its Applications 67 (1998). Chapters 1-3 give the species-theoretic foundation: a species is a functor from finite sets and bijections to finite sets, its exponential generating series and its type generating series (the unlabelled / isomorphism-type count) are the EGF and OGF of the symbolic method, and the operations sum, product, substitution, and the pointing derivative are the categorical operations whose generating-series images are exactly the admissible-construction translations. The multiset (abelian / symmetric) construction and its cycle-index image is the Pólya-theoretic content; this is the structural source for why the unlabelled OGF dictionary closes under the constructions.
Pólya, G. — Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen · Acta Mathematica 68 (1937), 145-254. The originating paper of the cycle-index method: the count of orbits of a permutation group acting on functions is the cycle-index polynomial evaluated at the figure-counting series, which specialises to the multiset $\mathrm{MSET}$ translation $\exp(\sum_k A(z^k)/k)$ (the symmetric group, Euler transform) and the cycle $\mathrm{CYC}$ translation $\sum_k \frac{\varphi(k)}{k}\log\frac{1}{1-A(z^k)}$ (the cyclic group, necklaces). The substitution-into-cycle-index structure is exactly the unlabelled multiset/cycle rows of the symbolic dictionary.

Estimated time

beginner: 20m
intermediate: 50m
master: 90m