Mosaics -- Enumeration formulae for mosaics

Enumeration formulae for mosaics

Enumeration formulae for mosaics

It is well known [2],[3] how to enumerate G-mosaics (G-orbits of partitions) by identifying them with G × S_n-orbits on the set of all functions from Z_n to n := {1,...,n}. (The symmetric group of the set n is denoted by S_n.) Furthermore G-mosaics of size k correspond to G × S_k-orbits on the set of all surjective functions from Z_n to k. We want to express the number of G-mosaics using the cycle index notion: The cycle index of G acting on a set X is the following polynomial Z(G,X) in the indeterminates x₁,x₂,...,x_|X| over Q, the set of rationals, defined by

Z(G,X) := ^._. 1
|G|
^._.
∑
g∈ G ^._. |X|
∏
i=1 x_i^a_i(g),^._.

where (a₁(g),...,a_|X| (g)) is the cycle type of the permutation induced by the action of g∈ G. This means that the induced permutation decomposes into a_i(g) disjoint cycles of length i for i=1,...,|X|. Furthermore Z(G,X | x_i=f(i)) means that the variables x_i in Z(G,X) must be replaced by the expression f(i). Now we can apply theorems from [2] to compute the number of orbits of all (surjective) functions under the group action of G × S_n (or G × S_k respectively).

Theorem: For 1≤ k≤ n let

M_k := Z(G,Z_n | x_i=^._. ∂
∂ x_i
) Z(S_k,k | x_i=e^s_i)|_{x_i=0},^._.

where s_i := i(x_i+x_2i+...+x_{i[^._.n
i
]}) and where [^._.n
i
] is the greatest integer less or equal to (n)/(i). This cycle index expression indicates that the operators of the first cycle index must be applied to the polynomial given by the substitution into the second cycle index and finally all indeterminates that haven't vanished so far must be set to 0. The number of G-mosaics in Z_n is given by M_n, and the number of G-mosaics of size k is given by M_k-M_k-1, where M₀ := 0.
The Cauchy-Frobenius-Lemma [10] computes M_k as
M_k=^._. 1
|G||S_k|
^._.
∑
(g,h)∈ G × S_k ^._. n
∏
i=1 a₁(hⁱ)^a_i(g),^._.
where a_i(g) (or a_i(h)) are the numbers of i-cycles in the cycle decomposition of g (or h respectively).
Finally the number of G-mosaics of size k could be derived by the Cauchy-Frobenius-Lemma [10] as
^._. 1
|G||S_k|
^._.
∑
(g,h)∈ G × S_k ^._. c(h)
∑
ℓ=1 (-1)^c(h)-ℓ ^._.
∑
a ^._. k
∏
i=1 a_i(h) a_i ^._. n
∏
j=1 ( ^._.
∑
d |j d ⋅ a_d )^a_j(g), ^._.
where the inner sum is taken over the sequences a=(a₁, …, a_k) of nonnegative integers a_i such that ∑_i=1^k a_i=ℓ, and where c(h) is the number of all cycles in the cycle decomposition of h.

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

Enumeration formulae for mosaics