Mazzola, Guerino / Noll, Thomas / Lluis-Puebla, Emilio: Perspectives in Mathematical and Computational Music Theory

2 Enumeration of Non-Isomorphic Mosaics

In Isihara and Knapp (1993) it was stated that the enumeration of mosaics is an open research problem communicated by Robert Morris from the Eastman School of Music. More information about mosaics can be found in Alegant (1992). Here some results from Fripertinger (1999) are presented.

Let $p$ be a partition of a set $X$ . If $p$ consists of exactly $k$ non-empty, disjoint subsets of $X$ , then $p$ is called a partition of size $k$ . A partition of the set $Zn$ is called a mosaic. Let $TTn$ denote the set of all mosaics of $Zn$ , and let $TTn,k$ be the set of all mosaics of $Zn$ of size $k$ .

A group action of a group $G$ on the set $Zn$ induces the following group action of $G$ on $TTn$ :

G × TTn --> TTn, g* p := {gP |P (- p},

where $gP := {gx|x (- P}$ . This action can be restricted to an action of $G$ on $TTn,k$ . Two mosaics are called $G$ -isomorphic if they belong to the same $G$ -orbit on $TTn$ , in other words, $p1,p2 (- TTn$ are isomorphic if $gp1 = p2$ for some $g (- G$ .

As was already indicated, in music theory the groups $Cn$ , $Dn$ , or $Af f1(Zn)$ are candidates for the group $G$ .

It is well known (see de Bruijn, 1964, 1979) how to enumerate $G$ -isomorphism classes of mosaics (i.e. $G$ -orbits of partitions) by identifying them with $Sn× G$ -orbits on the set of all functions from $Zn$ to $n-$ . (The symmetric group of the set $n-$ is denoted by $Sn-$ .) Furthermore, $G$ -mosaics of size $k$ correspond to $Sk× G$ -orbits on the set of all surjective functions from $Zn$ to $k-$ .

In Fripertinger (1999) the following theorem is proved.

Theorem 5. Let $Mk$ be the number of $Sk× G$ -orbits on $kZn$ . Then the number of $G$ -isomorphism classes of mosaics of $Zn$ is given by $Mn$ , and the number of $G$ -isomorphism classes of mosaics of size $k$ is given by $Mk - Mk -1$ , where $M0 := 0$ .

Using the Cauchy-Frobenius-Lemma, we have

sum n prod Mk = |--1|--- a1(si)ai(g), |Sk||G |(s,g) (- Sk×G i=1

where $ai(g)$ or $ai(s)$ are the numbers of $i$ -cycles in the cycle decomposition of $g$ or $s$ respectively.

Finally, the number of $G$ -isomorphism classes of mosaics of size $k$ can also be derived by the Cauchy-Frobenius-Lemma for surjective functions by

( )a (g) 1 sum c sum (s) sum prod k (a (s)) prod n s um j ||--||--- (-1)c(s)-l i d.ad , Sk-|G| (s,g) (- Sk×Gl=1 a i=1 ai j=1 d|j

where the third sum is taken over the sequences $a = (a1,...,ak)$ of nonnegative integers $ai$ such that $sum k ai = l i=1$ , and where $c(s)$ is the number of all cycles in the cycle decomposition of $s$ .