= Unlabelled combinatorial structure
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^{\binom32}=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.
Back to article page
