1 Enumeration of non-isomorphic mosaics

In [8] 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 [1]. Here I present some results from [6].

A partition of a set X is a collection of subsets of X such that the empty set is not an element of and such that for each x X there is exactly one P with x P. If consists of exactly k subsets, then is called a partition of size k. Let n > 1 be an integer. A partition of the set Z_n := /n is called a mosaic. Let _n denote the set of all mosaics of Z_n, and let _n,k be the set of all mosaics of Z_n of size k.

A group action of a group G on the set Z_n induces the following group action of G on _n:

where gP := . This action can be restricted to an action of G on _n,k. Two mosaics are called G-isomorphic if they belong to the same G-orbit on _n, in other words, ₁,_{2 n} are isomorphic if g₁ = ₂ for some g G. Usually the cyclic group C_n := <(0, 1,...,n- 1)>, the dihedral group D_n := <(0, 1,...,n- 1), (0,n- 1)(1,n- 2)...>, or the group of all affine mappings on Z_n are candidates for the group G. If G acts on a set X, then for each g G the permutation xgx is indicated by . It is called the permutation representation of g. A detailed introduction to combinatorics under finite group actions can be found in [9, 10].

It is well known (see [4, 5]) how to enumerate G-isomorphism classes of mosaics (i.e. G-orbits of partitions) by identifying them with G×S_n-orbits on the set of all functions from Z_n to 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.

Theorem 1. Let M_k be the number of G × S_k-orbits on k^Z_n, then the number of G-isomorphism classes of mosaics of Z_n is given by M_n, and the number of G-isomorphism classes of mosaics of size k is given by M_k - M_k-1, where M₀ := 0.

Using the Cauchy-Frobenius-Lemma, we have

where a_i( ) or a_i() are the numbers of i-cycles in the cycle decomposition of or 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

where the inner sum is taken over the sequences a = (a₁,...,a_k) of nonnegative integers a_i such that _i=1^ka _i = , and where c() is the number of all cycles in the cycle decomposition of .

If _n consists of _i blocks of size i for i n , then is said to be of block-type = (₁,...,_n). From the definition it is obvious that _i=1ⁿi _i = n, which will be indicated by n. Furthermore, it is clear that is a partition of size _i=1ⁿ _i. The set of mosaics of block-type will be indicated as . Since the action of G on _n can be restricted to an action of G on , we want to determine the number of G-isomorphism classes of mosaics of type . 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 , , ..., , the blocks of of size 2 are given by , , ..., , and so on.) According to [9, 10], the stabilizer H of in the symmetric group S_n 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. In other words H is the set of all permutations S_n, which map each block of the partition again onto a block (of the same size) of the partition.

Hence, the G-isomorphism classes of mosaics of type can be described as G × H-orbits of bijections from Z_n to n under the following group action:

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 (cf. [9, 10]) of the form

Theorem 2. The number of G-isomorphism classes of mosaics of type is given by

where z( ) and z() are the cycle types of and of respectively, given in the form (a_i( ))_in or (a_i())_in. In other words we are summing over those pairs (g,) such that and determine permutations of the same cycle type.

2 Enumeration of non-isomorphic canons

The present concept of a canon is described by G. Mazzola in [11] and was presented by him to the author in the following way: A canon is a subset K Z_n together with a covering of K by pairwise different subsets V _iØ for 1 < i < t, the voices, where t > 1 is the number of voices of K, in other words

such that for all i,j

1. the set V _i can be obtained from V _j by a translation of Z_n,
2. there is only the identity translation which maps V _i to V _i,
3. the set of differences in K generates Z_n, i.e. <K - K> := <k - l | k,l K> = Z_n.

We prefer to write a canon K as a set of its subsets V _i. Two canons K = and L = are called isomorphic if s = t and if there exists a translation T of Z_n and a permutation in the symmetric group S_t such that T(V _i) = W_(i) for 1 < i < t. Then obviously T(K) = L.

Here we present some results from [7]. The cyclic group C_n acts on the set of all functions from Z_n to by

As the canonical representative of the orbit C_n(f) = we choose the function f₀ C_n(f), such that f₀ < h for all h C_n(f).

A function f ^Z_n (or the corresponding vector (f(0),f(1),...,f(n - 1))) is called acyclic if C_n(f) consists of n different objects. The canonical representative of the orbit of an acyclic function is called a Lyndon word.

As usual, we identify a subset A of Z_n with its characteristic function _A : Z_n given by

Following the ideas of [7] and the notion of [3], a canon can be described as a pair (L,A), where L is the inner and A the outer rhythm of the canon. In other words, the rhythm of one voice is described by L and the distribution of the different voices is described by A, i.e. the onsets of the different voices are a + L for a A. In the present situation, L0 is a Lyndon word of length n over the alphabet , and A is a t-subset of Z_n. But not each pair (L,A) describes a canon. More precisely we have:

An application of the principle of inclusion and exclusion allows to enumerate the number of non isomorphic canons.

Theorem 4. The number of isomorphism classes of canons in Z_n is

where is the Moebius function, (1) = 1,

and

where is the Euler totient function.

3 Enumeration of rhythmic tiling canons

There exist more complicated definitions of canons. A canon described by the pair (R,A) of inner and outer rhythm defines a rhythmic tiling canon in Z_n with voices V _a for a A if and only if

1. the voices V _a cover entirely the cyclic group Z_n,
2. the voices V _a are pairwise disjoint.

Rhythmic tiling canons with the additional property

0. both R and A are aperiodic,

are called regular complementary canons of maximal category.

Hence, rhythmic tiling canons are canons which are also mosaics. More precisely, if = t, then they are mosaics consisting of t blocks of size n/t, whence they are of block-type where

This block-type will be also indicated as = ((n/t)^t). So far the author did not find a characterization of those mosaics of block-type describing canons, which could be used in order to apply enumeration formulae similar to those for the enumeration of non-isomorphic mosaics. Applying Theorem 2 the numbers of C_n-isomorphism classes of mosaics presented in table 1 were computed.

Table 1: Number of mosaics in Zn of block-type ((n/t)t)

There exist fast algorithms for computing all Lyndon words of length n over and all C_n-orbit representatives of subsets of Z_n. For finding regular tiling canons with t voices (where t is necessarily a divisor of n), we can restrict to Lyndon words L with exactly n/t entries 1 and to representatives A₀ of the C_n-orbits of t-subsets of Z_n. Then each pair (L,A₀) must be tested whether it is a regular tiling canon. In this test we only have to test whether the voices described by (L,A₀) determine a partition on Z_n, because in this case it is obvious that (L,A₀) does not satisfy the assumptions of Lemma 3.

For finding the number of regular tiling canons, we make use of still another result. In [13, 2] it is shown that regular complementary canons of maximal category occur only for certain values of n, actually only for non-Hajós-groups Z_n (cf. [12]). The smallest n for which Z_n is not a Hajós-group is n = 72 which is still much further than the scope of our computations. Hence, we deduce that for all n such that Z_n is a Hajós-group the following is true:

This reduces dramatically the number of pairs which must be tested.

By applying Theorem 4 we computed K_n, the numbers of non-isomorphic canons of length n, given in the third column of table 2. The construction described above yields a list of all regular tiling canons, which also yields T_n, the number of regular tiling canons of length n, given in the second column of table 2.

for distinct primes p, q, r and s, then Z_n is a Hajós group and Vuza proved in [13, 14] that for these n there do not exist regular complementary canons of maximal category. Moreover, he described a method how to construct such canons for all Z_n which are not Hajós groups. If Z_n is not a Hajós group, then n can be expressed in the form p₁p₂n₁n₂n₃ with p₁, p₂ primes, n_i > 2 for 1 < i < 3, and gcd(n₁p₁,n₂p₂) = 1. Vuza presents an algorithm for constructing two aperiodic subsets L and A of Z_n, such that = n₁n₂, = p₁p₂n₃, and L + A = Z_n. Hence, L or A can serve as the inner rhythm and the other set as the outer rhythm of such a canon. Moreover, it is important to mention that there is some freedom for constructing these two sets, and each of these two sets can be constructed independently from the other one. He also proves that when L and A satisfy L + A = Z_n, then also (kL,A), (kL,kA) have this property for all k Z_n^*.

So the first step in enumeration of regular complementary canons of maximal category is to determine the number of non-isomorphic canons which can be constructed by this method. (Actually, I wanted to do it this week, but finally there was not enough time to do so.)

4 Some interesting open problems

1. In his papers, Vuza did not prove that each regular complementary canon of maximal category can be constructed with his method. Is it possible to find regular complementary canons of maximal category which cannot be produced by Vuza’s approach?
2. Is there a more elegant method for enumerating regular tiling canons?
3. When enumerating isomorphism classes of mosaics in Z_n, we could apply groups different from the cyclic group C_n. How to do this for canons? For the group C_n, a canon was given as a pair (L,A) with certain properties. L was an acyclic vector, so probably in all generalizations we must assume that L does not have cyclic symmetries. A was considered to be a subset of Z_n, but actually A describes the onset distribution of the different voices, whence it is actually a subset of the acting group C_n. When considering the group Aff ₁(Z_n), consisting of all affine mappings _a,b : Z_n Z_n, iai + b, for a Z_n^* and b Z _n, acting on Z_n, then A must be considered as a subset of this group. If L has just the trivial symmetry, then each _a,b(L) describes another voice of the canon. If the stabilizer U of L is non-trivial, but it does not contain symmetries of the form _1,b for b0, then A must be considered as a subset of the right-cosets of U in Aff ₁(Z_n). When computing the number of non-isomorphic canons in this setting, we get a much bigger number of different canons, since usually many different voices start at the same onset. So maybe in this situation we should restrict to canons, such that different voices have different onsets in Z_n. But when speaking of onsets of voices we can get some problems with symmetries _a,b of L for a1 and b0. So maybe we should not allow any symmetries of L. But then we will not get a complete overview over all canons in Z_n. Still the property that K - K generates Z_n was not considered for these generalizations.

References