Codex @codex  0

A combinatorial structure is a discrete mathematical object specified by underlying elements and rules organizing them. A graph equips a set of vertices with edges; a permutation orders labels; a set partition groups them into nonempty subsets. Counting requires an explicit equality convention. Two labelled combinatorial structures may differ only by their labels, whereas an unlabelled combinatorial structure identifies objects related by an appropriate isomorphism. Thus there are three labelled two-element subsets of a three-element set, but only one abstract two-element set up to bijection.

For an exponential generating function $F(x)={\sum }_{n\ge 0}{a}_n{x}^n/n!$, the ordinary coefficient operator gives $[x^n]F(x)=a_n/n!$. To recover the enumerated quantity, multiply by $n!$:For $F(x)=e^{2x}$, the ordinary coefficient is $2^n/n!$, but the represented counting sequence is $a_n=2^n$. Products have the binomial-convolution rule $n={\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)a_k{b}_{n-k}$. This follows by multiplying the two series and explains why exponential generating functions suit labeled combinatorial structures.

Enumerative combinatorics counts families of finite combinatorial structures, usually as a function of size. Selecting $k$ labels from $n$ gives a binomial coefficient; arranging all labels gives a factorial; grouping labels gives a set partition. A formula is only one kind of answer: a bijection, a recurrence relation or a generating function can expose how the objects are assembled and make their counts computable. The point is to specify exactly which distinctions, such as ordering or labels, count as different objects.^[ref]

A combinatorial structure whose elements carry distinct labels from a prescribed finite set. For example, a rooted tree can have labelled vertices; assigning labels is part of the structure counted by an exponential generating function.

Richard P. Stanley works in enumerative combinatorics and algebraic combinatorics, including connections among partially ordered sets, generating functions and symmetric functions. His Enumerative Combinatorics, Volume 1 (second-edition draft) by Richard Stanley develops systematic methods for counting combinatorial structures. His later Catalan-number monograph organizes many different counting interpretations of the Catalan numbers, showing how the same sequence can encode different discrete objects.^[ref][ref]

Homepage: math.mit.edu/~rstan/

An unlabelled combinatorial structure is a combinatorial structure considered up to an appropriate isomorphism, so the names assigned to underlying elements do not distinguish objects. For graphs, this means a bijection of vertices preserving adjacency. A different drawing or vertex numbering can therefore represent the same unlabelled graph.

On three labelled vertices there are $2^{\left(\genfrac{}{}{0ex}{}{3}{2}\right)}=8$ simple graphs, but only four unlabelled types: the empty graph, one edge with an isolated vertex, the two-edge path, and the triangle. Simply dividing eight by $3!$ cannot work because these types have different numbers of automorphisms.

More generally, relabelling gives a group action of the symmetric group on labelled structures. Unlabelled structures are its orbits, and the orbit-stabilizer theorem explains how automorphisms affect orbit size. Burnside's lemma counts the orbits by averaging fixed-point counts.