Combinatorial Classes and the Symbolic Method: Examples and Counterexamples

The displayed list has $1$ word of length $0$, $2$ of length $1$, $4$ of length $2$, and $8$ of length $3$.

Expanding $1\mathrm{/}(1-2x)$ as $1+2x+4x^2+8x^3+\cdots$ gives the same initial coefficients, so the explicit list matches the theorem.

The displayed list contains every ordered positive-part sum of $4$: one with $1$ part, three with $2$ parts, three with $3$ parts, and one with $4$ parts.

The part-counts match [L1]: $\left(\genfrac{}{}{0px}{}{3}{0}\right)=1$, $\left(\genfrac{}{}{0px}{}{3}{1}\right)=3$, $\left(\genfrac{}{}{0px}{}{3}{2}\right)=3$, and $\left(\genfrac{}{}{0px}{}{3}{3}\right)=1$.

Applying [L1] to the Given class and multiplying the resulting factors to degree $5$ gives $(1-x{)}^{-1}(1-x^2{)}^{-1}(1-x^3{)}^{-1}=(1+x+x^2+x^3+x^4+x^5)(1+x^2+x^4)(1+x^3)=1+x+2x^2+3x^3+4x^4+5x^5+O(x^6)$.

The five displayed partitions of $5$ are exactly the partitions whose part sizes lie in $\{1,2,3\}$, so the coefficient $5$ has the advertised interpretation.

Solving $T=x\mathrm{/}(1-T)$ coefficientwise gives $T(x)=x+x^2+2x^3+5x^4+\cdots$, so the first four counts are $1,1,2,5$.

These are realized by the evident shapes: a single root; a root with one child; for three vertices, the chain and the root with two children; for four vertices, the chain of length four, the root with three children, the root with one child whose child has two children, and the two left-right orderings of a root with two children one of which has one child.

The corollary with $m=2$ and $n=6$ gives $(1\mathrm{/}6)(\phi (1)2^6+\phi (2)2^3+\phi (3)2^2+\phi (6)2^1)=(1\mathrm{/}6)(64+8+8+4)=14$.

Burnside gives the same value. The six rotations of a $6$-bead necklace fix $64,2,4,8,4,2$ colourings respectively, since the numbers of position-orbits are $6,1,2,3,2,1$. Their average is $(64+2+4+8+4+2)\mathrm{/}6=14$.

The cycle-construction count and the direct Burnside count therefore agree at length $6$.

Substituting each displayed iterate into $x\mathrm{/}(1-Y)$ and truncating modulo $x^7$ gives the next one in the list.

By the sixth iterate, every coefficient through degree $6$ has stabilized, so the unique fixed point begins $T(x)=x+x^2+2x^3+5x^4+14x^5+42x^6+\cdots$.

The size-$2$ level of the displayed family is ${\mathcal{A}}_2=\{a_0,a_1,a_2,\dots \}$, which is infinite.

This violates the defining finiteness condition on levels, so the family is not a combinatorial class.

The ordinary union $A\cup B$ has one object of size $1$, so its generating function is $x$.

The sum $\mathrm{OGF}(A)+\mathrm{OGF}(B)$ is $x+x=2x$, which is different from step 1.1. The failure is exactly the missing disjointness: the same object was counted twice on the right and once on the left.

The class $A\times B$ has two size-$2$ objects, namely $(a,b_0)$ and $(a,b_1)$, so its generating function is $2x^2$.

The collapsed construction $C$ has only one size-$2$ object, so its generating function is $x^2$. The missing factor of $2$ is exactly the loss of unique factorisation.

Let $\mathcal{A}=\{e\}$ with $\mathrm{\mid }e\mathrm{\mid }=0$. Then for every $r\ge 0$, the length-$r$ sequence $(e,\dots ,e)$ lies in $\mathrm{SEQ}(\mathcal{A})$ and has total size $0$.

These sequences are all distinct because their lengths differ, so the size-$0$ level of $\mathrm{SEQ}(\mathcal{A})$ is infinite. Hence $\mathrm{SEQ}(\mathcal{A})$ is not a combinatorial class.

The claim is therefore false, and the no-size-zero hypothesis in the sequence theorem is load bearing.

Let $\mathcal{A}$ have one object $z$ of size $0$ and one object $u$ of size $1$. Its positive-size counting sequence is $a_1=1$ and $a_n=0$ for $n>1$, so the displayed product is $(1-x{)}^{-1}$.

But $\mathrm{MSET}(\mathcal{A})$ has infinitely many size-$0$ objects: the multiplicity functions with $m(z)=0,1,2,\dots$ and $m(u)=0$ are all distinct and all have total size $0$. So the would-be multiset class is not locally finite in degree $0$, and [L1] does not license a generating function for it.

The displayed product therefore does not automatically encode a valid multiset construction from the bare positive-size sequence alone. The omitted no-size-zero hypothesis matters, so the claim is false.