 |
 |
 |
Enumeration by
block-type |
Enumeration by block-type
If π∈ Πn consists of
λi blocks of size i for i∈
n then π is said to be of block-type
λ=(λ1,..., λn).
From the definition it is obvious that ∑iiλi =n, which
will be indicated by λ ⊩ n. Furthermore it is
clear that π is a partition of size ∑i λi. In this
section the number of G-mosaics of type λ
(i.e. G-patterns of partitions of block-type
λ) shall be derived. For doing that let
λ be
any partition of type λ. (For instance
λ can
be defined such that the blocks of λ of size 1 are
given by {1}, {2}, ...,
{λ1}, the blocks of λ of size 2 are
given by {λ1 +1,λ1+2}
{λ1 +3,λ1+4},
..., {
λ1+2λ2-1,λ1+2λ2},
and so on.) According to [10]
the stabilizer Hλ of
λ in
the symmetric group Sn
(Hλ is the set of all permutations
σ∈ Sn such that
σλ=λ) is
similar to the direct sum
of compositions of symmetric groups, which is a
permutation representation of the direct product
of wreath products of symmetric groups. The wreath product
defined by
|
Si≀Sj= {(ψ,σ) |
σ∈ Sj, ψ: j→
Si}.. |
together with the multiplication
|
(ψ,σ)(ψ',σ')=(ψψσ',σσ'),.. |
where
ψψσ'(i)=ψ(i)ψσ'(i)
and ψσ'(i)=
ψ'(σ-1i) is a semidirect product. The
composition Sλi
[Si] is the following permutation
representation of Si≀Sλi on
the set i × λi
|
((ψ,σ),(r,s))↦
(ψ(σ(s))r,σ(s))... |
In other words Hλ is the set of all
permutations σ∈ Sn, which map
each block of the partition λ again onto a block
(of the same size) of the partition. It is well known that the
cycle index of the composition of two groups can be determined from
the cycle indices of the two groups, so we know how to compute the
cycle index of Hλ.
All partitions of Zn of type λ
can be derived in the form {f-1(P) | P∈
λ},
where f is running through the set of all bijective mappings
from Zn to n. Two such bijections
f and f' define the same partition of
Zn, if and only if f'=f o σ, where
σ is an element of the stabilizer
Hλ of λ. This induces a
group action of Hλ on the set of all
bijections from Zn to n
| Hλ ×
nZnbij
→nZnbij,
(σ,f)↦ f o
σ-1,.. |
such that the Hλ-orbits correspond to the
partitions of Zn of type λ.
Since the action of G on Πn can be
restricted to an action of G on
Πλ, the set of all partitions of type
λ, we have the following action on the set of all
bijections from Zn to n:
| G ×
nZnbij
→nZnbij,
(g,f)↦ g o f... |
Two bijections f and f' from Zn to
n define G-equivalent partitions of type
λ, if and only if there is some g∈ G such
that g o f and f' define the same partition, which
implies that there is some σ∈
Hλ such that g o f o
σ-1=f'. In conclusion we can say that
G-mosaics of type λ correspond to G ×
Hλ-orbits of bijections from
Zn to n under the following group
action:
| (G × Hλ) ×
nZnbij
→nZnbij,
((g,σ),f)↦ g o f o
σ-1... |
harald.fripertinger "at" uni-graz.at, May 10,
2016
|
|
|
 |
 |
 |
Enumeration by
block-type |
 |
 |