Introduction
The methods and results presented in this paper
are interesting in the framework of
classification of discrete structures
[13],[10].
Very often discrete
structures can be described as equivalence classes of certain objects.
If these equivalence classes can be expressed as orbits under
a group G acting on a set X -- i.e. there is a mapping
G´X -> X, (g,x) -> gx such that g1(g2x)=(g1g2)x and
1x=x -- then there exist some combinatorial and algebraic methods
for the classification of these structures.
For instance each element in the discrete structure
of unlabelled graphs can be considered as the set of all
possible labellings of a given graph which is the orbit of a labelled
graph under the action of the symmetric group;
or the isometry classes
of block-codes are orbits of special wreath-products.
In a first step one can enumerate these structures
by applying the Cauchy-Frobenius-Lemma, which says that the
number of G-orbits is the average number of fixed points
|
|
1
| G|
|
|
å
g Î G
|
| Xg|, Xg: = { x Î X | gx = x} . |
|
In a second step certain properties of these structures can be
described by weight functions or by their stabilizer (the stabilizer of
xÎX is the subgroup Gx:={gÎG | gx=x} of G)
and the numbers of structures with these additional properties can be
computed by the Pólya-de Bruijn-Redfield-Theory or by
Burnsides Lemma.
The more details of a structure are
specified and prescribed by parameters the closer comes
the enumeration procedure
to the construction of all structures with given properties. The
most ambitious task is the computation of complete lists
of representatives of a discrete structure, which can be done by
arranging both algebraic and combinatorial algorithms in a very
tricky way. Having computed these lists we can investigate each
representative for its properties.
When the numbers of representatives get too large in
order to compute complete lists, it is useful, helpful
and makes sense to
compute representatives uniformly at random. This way we can produce
unprejudiced lists of representatives which can be used to check
hypotheses on them and afterwards we can try to prove the valid ones.
Let A be a finite alphabet, then
an [n,m] block code C over A is an
m-subset of An.
In order to describe the isometry classes of block codes we need
the notion of wreath products. The wreath product
SA wr Sn is a group formed by a set
{(y,p) | yÎSAn, pÎSn } with
multiplication
(y,p)(y', p')=(yy'p, pp'),
where yy'p(i):=y(i)y'p(i)
and y'p(i):=y'(p-1i).
(For more details on group actions and
wreath products cf. [12].)
Two [n,m] codes C1 and
C2 will be called equivalent, if and only if there is some
(y,p) in the full monomial group SA wr Sn such that
|
C1 = (y,p)(C2): = { (y,p)f | f Î C2} , |
|
where (y,p)f(i)=y(i)f(p-1i).
(I.e. SA wr Sn
acts in form of the exponentiation on An which
induces an action on the set of all subsets of An.)
The equivalence classes under this group action are exactly the
isometry classes of [n,m] codes.
In previous papers [6][4][3][5]
we were dealing with the enumeration
of isometry classes of linear (n,k) codes over a finite field GF(q).
In this situation we had to determine the number of isometry classes of
k-dimensional subspaces of GF(q)n, which can be described as orbits
under the action of GF(q)* wr Sn.
Of course, each linear (n,k)-code over GF(q) is an
[n,qk] block code.
harald.fripertinger@kfunigraz.ac.at,
last changed: January 23, 2001
