Labelled enumeration theorem

rdf:langString Labelled enumeration theorem

rdf:langString In combinatorial mathematics, the labelled enumeration theorem is the counterpart of the Pólya enumeration theorem for the labelled case, where we have a set of labelled objects given by an exponential generating function (EGF) g(z) which are being distributed into n slots and a permutation group G which permutes the slots, thus creating equivalence classes of configurations. There is a special re-labelling operation that re-labels the objects in the slots, assigning labels from 1 to k, where k is the total number of nodes, i.e. the sum of the number of nodes of the individual objects. The EGF of the number of different configurations under this re-labelling process is given by In particular, if G is the symmetric group of order n (hence, |G| = n!), the functions can be further combined into a single generating function: which is exponential w.r.t. the variable z and ordinary w.r.t. the variable t.