Mosaics -- Enumeration formulae for mosaics

Enumeration formulae for mosaics

Enumeration formulae for mosaics

It is well known how to enumerate these orbits. When interpreting the bijections from Z_n to n as permutations of the n-set n then G-mosaics of type λ correspond to double cosets of the form

G\S_n/ H_λ.^._.

Theorem: The number of G-mosaics of type λ can be derived with the following formula due to de Bruijn [2]

Z(G,Z_n | x_i=^._. ∂

∂ x_i
)Z(H_λ, | x_i=ix_i)|_{x_i=0}.^._.

The Cauchy-Frobenius-Lemma [10] determines the number of orbits of bijections from Z_n to n under the action of G × H_λ by

^._. 1

|G||H_λ|
^._.
∑
(g,h)∈ G × H_λ, z(g)=z(h) ^._. n
∏
i=1 a_i(h)!i^a_i(g),^._.

where z(g) and z(h) are the cycle types of the permutations induced by the actions of g on the set Z_n and of h on n respectively, given in the form (a_i(g))_i∈
n or (a_i(h))_i∈
n. In other words we are summing over those pairs (g,h) such that g and h determine permutations of the same cycle type.

The double coset approach leads to an application of the Redfield cap-operator [10] or to Reads N(.*.) operator [12][13], and the number of G-mosaics of type λ is given by

Z(G,Z_n)∩ Z(H_λ,n) or N( Z(G,Z_n)*Z(H_λ,n)).^._.

harald.fripertinger "at" uni-graz.at, May 10, 2016

Enumeration formulae for mosaics