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
fn(z)
fn(z)=
g(z)n | |
|G| |
.
In particular, if G is the symmetric group of order n (hence, |G| = n!), the functions
fn(z)
F(z,t)=
infty | |
\sum | |
n=0 |
fn(z)tn=
infty | |
\sum | |
n=0 |
g(z)n | |
n! |
tn=eg(z)t
which is exponential w.r.t. the variable z and ordinary w.r.t. the variable t.
We assume that an object
\omega
|\omega|
z|\omega|/|\omega|!
|\omega|=m
|G|
|G|
r1
r2
r1+r2+ … +rn=k.
The re-labelling process works as follows: choose one of
{k\chooser1,r2,\ldots,rn}
partitions of the set of k labels into subsets of size
r1,r2,\ldotsrn.
[k]
It follows from the re-labelling construction that there are
1 | |
|G| |
\sum | |
r1+r2+ … +rn=k |
{k\chooser1,r2,\ldots,rn} r1!
r1 | |
[z |
]g(z) r2!
r2 | |
[z |
]g(z) … rn!
rn | |
[z |
]g(z)
or
k! | |
|G| |
\sum | |
r1+r2+ … +rn=k |
r1 | |
[z |
]
r2 | |
g(z) [z |
]
rn | |
g(z) … [z |
]g(z) =
k! | |
|G| |
[zk]g(z)n
different configurations of total size k. The formula evaluates to an integer because
[zk]g(z)n
k\gen
n!|k!
|G|
Sn
n!
fn(z)=\sumk\left(
k! | |
|G| |
[zk]g(z)n\right)
zk | = | |
k! |
1 | |
|G| |
\sumkzk[zk]g(z)n=
g(z)n | |
|G| |
.
This formula could also be obtained by enumerating sequences, i.e. the case when the slots are not being permuted, and by using the above argument without the
1/|G|
g(z)n
|G|
g(z)n/|G|.