Applied Mathematics E-Notes, 5(2005), 60-65 c
Available free at mirror sites of http://www.math.nthu.edu.tw/∼amen/ISSN 1607-2510

NEW PROGRESS IN ENUMERATION OF MIXEDMODELS∗
Roman Bayon†, Nik Lygeros‡, Jean-Sébastien Sereni§
Received 9 September 2004

Abstract
A mixed model is said to be constrained if none of its fixed factors is nested
within a random factor. Hess and Iyer have asked the question of enumerating
non-isomorphic mixed models (with or without constraint), solving the problem
for mixed models of size at most 5. In this article, using previous results about
posets, we present a new algorithm, and obtain results for mixed models of size
at most 10.

1Introduction

The number of non-isomorphic fixed eﬀects ANOVA models is known for n ≤ 16 [2],since there is a one-to-one correspondence with posets. Hess and Iyer have worked on
the problem of enumerating non-isomorphic mixed models (with or without constraint).
A mixed model is said to be constrained if no fixed factor is nested with a random
factor. They obtained results for mixed models of size at most 5 [8], proving there are576 mixed models with constraint.
Mixed model is a special case of the general linear model, where both the meanfunction and covariance matrix for a data have a linear structure. More precisely, thevector of observations y is assumed to have moments:
E[y] = Xα

V ar[y] =φt Vttwhere α = (α1 , . . . , αp )t and φ = (φ1 , . . . , φq )t are unknown parameters and the matrices X, V1 , . . . , Vq are given. Any mean vector and covariance matrix can be written in∗ Mathematics Subject Classifications: 68R05, 62J12.

† INPG, 46 Avenue Félix Viallet, 38031 Grenoble, France‡ Institut Girard Desargues — Département de Mathématiques, Université Lyon I, 43 Bld du 11 Nov.
1918, 69622 Villeurbanne, France§ MASCOTTE Project — CNRS-INRIA-UNSA, BP 93, 2004 Route des lucioles, 06902 SophiaAntipolis, France60

Bayon et al.

61

this form, but we are interested in models in which the parameters α1 , . . . , αp , φ1 , . . . , φq
are functionally independent.
Hess and Iyer have written a SAS macro which allows to determine confidence
intervals so as to facilitate the calculations of the Satterwaite method using the implementation of Burdick and Graybill [3]. Eﬃciency domain of their macro is reduced
to models with at most 5 factors. We announced in [1] that we have succeeded inenumerating constrained and unconstrained mixed models up to 9 factors. We present
here our work, which uses previous works about posets [7, 4, 5], and we extend theresults, at the present time, to constrained mixed models with at most 10 factors.

2Propositions

We start with the following correspondence which was established in [8]:THEOREM 1. There exists a one-to-one correspondence between fixed eﬀects models and posets (P, <).
PROOF. Let us consider a poset P with n elements and a fixed eﬀects model F withn factors. Crossed factors of the mixed model correspond to incomparable elements ofthe poset. A factor j is nested within a factor i in the mixed model if, and only if, wehave j < i in the poset P .
Thanks to this correspondence, the number of non-isomorphic fixed eﬀects modelsof size at most n is known [2].
For mixed models, we introduce the notion of proset, which stands for Partially
Reflexive Ordered SET.
DEFINITION 1. A proset is a set with a transitive and anti-symmetric binary
relation.
REMARK 1. One can think a proset Pr as a poset P for which the order relation
has been slightly modified, so that it can be reflexive for some elements of P only. In
other words, we allow diagonal coeﬃcients of the incidence matrix of the proset Pr to
be one or zero. In this case, we shall say that the proset Pr induces the poset P .
THEOREM 2. There is a one-to-one correspondence between mixed models (without constraint) and prosets.
PROOF. Let us consider a proset P with n elements and a mixed model M withn elements. For distinct elements of the proset, it is the same situation as before.
A reflexive element of P corresponds to a random factor of M , and a non-reflexive
element of P corresponds to a fixed factor of M .
We have a natural notion of duality within prosets.
DEFINITION 2. A proset P is the dual of the proset P if, and only if:• P and P induce the same poset P .·• the reflexive elements of P are exactly the non-reflexive elements of P .
With incidence matrix, P is obtained from P by changing 0 into 1 and 1 into 0 on
the diagonal of the incidence matrix of P .

62

Enumeration of Mixed Models

REMARK 2. Let n be an odd integer. By duality, we can say that the number of
mixed models of size n without constraint is even.
Hess and Iyer managed to enumerate non-isomorphic mixed models of size at most5, with and without constraint. Our algorithm has allowed us to extend these results
for n ≤ 10.

3

Enumeration of mixed models
2We represent a proset M = (x1 , x2 , ..., xn , ≺) by its incidence matrix (mij ) ∈ {0, 1}nwith mij = 1 if, and only if, xi ≺ xj . Not only is this a good representation in termsof implementation, but also it leads us to index and sort the vertices. Our algorithm
aims at minimising the number of permutations of the vertices to detect isomorphic
prosets.
Hess and Iyer algorithm:
1. Generation of adjacency matrices of posets of size n.
2. For each poset, construction of the set of matrix obtained by all possible combinations of 0 and 1 on the diagonal.
3. If only constrained mixed models are wanted, suppression of any matrices A
which violates the constraint, by computing A = i=n−1
Ak and by checking whether
i=0
A (i, j) ≥ 1 for any couple (i, j) such as A(i, i) = 1 and A(j, j) = 0.
4. Suppression of isomorphic models.
Our algorithm:
1. Generation of adjacency matrices of posets of size n with the algorithm ofenumeration of Chaunier and Lygeros [4, 5].
2. For each poset, construction of the incidence matrix A obtained by putting 0
and 1 on the diagonal such as the number of 1 is at most n2 . This way, we generate only
one proset for each couple of dual prosets, thus reducing the number of isomorphism
ntests. Note that there are 2n−1 such matrices if n is odd and 2n−1 + n if n is even.
2

3. Elimination of all isomorphic prosets.
4. Incrementing by 2 the number of mixed models without constraint. Then wecheck whether the mixed model, and its dual, satisfy the constraint or not.
REMARK 3. So as to check whether a proset validates the constraint or not, it issuﬃcient to check whether a reflexive element is adjacent to a non-reflexive element.
As our algorithm creates canonical prosets (via the generation algorithm of posets),
this test is elementary.
REMARK 4. If only the number of constrained mixed models is wanted, one caneliminate mixed models that violate the constraint before doing the isomorphism test.

4Results and interpretation.

First we remind known results about the enumeration of non-isomorphic posets, andthen we give the results obtained for mixed models.

Bayon et al.

63

Table 1: Number of fixed eﬀects models
Factors
n=1
n=2
n=3
n=4
n=5
n=6
n=7
n=8
n=9n = 10n = 11n = 12n = 13n = 14n = 15n = 16

Fixed eﬀects models
12
5
16
63
318
2.045
16.999183.2312.567.284
46.749.427
1.104.891.746
33.823.827.452
1.338.193.159.771
68.275.077.901.156
44.831.306.651.195.087

Names and years

Wright 1972
Das 1977
Mohring 1984
Culberson, Rawlins 1990Culberson, Rawlins 1990
C. Chaunier, N. Lygeros 1991
C. Chaunier, N. Lygeros 1994
N. Lygeros, P. Zimmermann 2000
G. Brinkmann, B. D. McKay 2002
G. Brinkmann, B. D. McKay 2002

Table 2: Number of mixed models (Not Constrained)
Factors
n=1
n=2
n=3
n=4
n=5
n=6
n=7n=8n=9Mixed models (Not Constrained)
27321921.490
15.067198.296
3.398.105
75.784.592

Names and years
A. Hess, H. Iyer 1999
A. Hess, H. Iyer 1999
A. Hess, H. Iyer 1999
A. Hess, H. Iyer 1999
A. Hess, H. Iyer 1999
R. Bayon, N. Lygeros, J.-S. Sereni 2002
R. Bayon, N. Lygeros, J.-S. Sereni 2002
R. Bayon, N. Lygeros, J.-S. Sereni 2002
R. Bayon, N. Lygeros, J.-S. Sereni 2002

64

Enumeration of Mixed Models

Table 3: Number of constrained mixed models
Factorsn=1
n=2n=3n=4n=5n=6n=7n=8n=9n = 10

Mixed models (Constrained)
2622101576
4.162
38.280451.411
6.847.662
133.841.440

Names and years
A. Hess, H. Iyer 1999
A. Hess, H. Iyer 1999
A. Hess, H. Iyer 1999A. Hess, H. Iyer 1999
A. Hess, H. Iyer 1999
R. Bayon, N. Lygeros, J.-S. Sereni 2002
R. Bayon, N. Lygeros, J.-S. Sereni 2002
R. Bayon, N. Lygeros, J.-S. Sereni 2002
R. Bayon, N. Lygeros, J.-S. Sereni 2002
R. Bayon, N. Lygeros, J.-S. Sereni 2003

Now, we underline the relation between the number of fixed eﬀects ANOVA models
with n elements and the order of the automorphism group of the associated poset [6, 9].
In the following, MPm × K means that there are M posets with automorphism groupsof order m, each generating K mixed models (without constraint).
M1 = 2 = 1P1 × 2
M2 = 7 = 1P1 × 4 + 1P2 × 3
M3 = 32 = 2P1 × 8 + 2P2 × 6 + 1P6 × 4
M4 = 192 = 5P1 × 16 + (6P2 × 12 + 1P2 × 10) + 1P4 × 9 + 2P6 × 8 + 1P24 × 5
We see here that the order of the automorphism group of the poset is not suﬃcient
to know the number of mixed models generated. The smallest posets to illustrate thishave 4 elements:
00P0 = 00000001001000 P =0 1 00000000000

110
0Both have an automorphism group of order 2, but P0 generates 10 mixed models
whereas P1 generates 12. This is due to the structure of the automorphism group:
A(P0 ) = {id, (12)(34)} whereas A(P1 ) = {id, (12)}.
More precisely:
PROPOSITION 1. Let (P, <) be a poset of size n with automorphism group G oforder a.
(i) If a = 1 then P generates 2n mixed models (without constraint).
(ii) If a = n! then P generates n + 1 mixed models (without constraint).
(iii) If we know the composition of G, we can compute the number of mixed models(without constraint) generated by P , thanks to Pólya Theorem [10]. This numberis:

Bayon et al.

65

ZG (2) =1a

2λ1 (g)+λ2 (g)+···+λn (g)g∈G

where λi (g) is the number of disjoint cycles of size i in the decomposition of g indisjoint cycles.
Last, the result of Prömel [11] on rigid posets, that is almost all posets have trivial
automorphism group, explicitly shows us the eﬃciency of our method. By a structure
isomorphism, it is easily seen that almost all prosets are rigid, and that proportionally,
prosets have an eﬀective density which is superior for a given n.

References[1] R. Bayon, N. Lygeros and J.-S. Sereni, Nouveaux progrès dans l’énumération
des modèles mixtes, Knowledge discovery and discrete mathematics (Proc. Conf.
JIM’2003), 243—246.
[2] G. Brinkmann and B. D. McKay, Posets on up to 16 Points, Order 19(2)(2002),
147—179.
[3] R. K. Burdick and F. A. Graybill, Confidence intervals on variance components,Marcel Dekker Inc., New-York, 1992.
[4] C. Chaunier and N. Lygeros, The number of orders with thirteen elements, Order9(1992), 203—204.
[5] C. Chaunier and N. Lygeros, Le nombre de posets à isomorphie près ayant 12éléments, Theoret. Comput. Sci. 123(1994), 89—94.
[6] C. Chaunier and N. Lygeros, Posets minimaux ayant un groupe d’automorphismesd’ordre premier, C. R. Acad. Sci. Paris t.318 s.I(1994), 695—698.
[7] R. Fraïssé and N. Lygeros, Petits posets : dénombrement, représentabilité parcercles et compenseur, C. R. Acad. Sci. Paris t.313 s.I(1991), 417—420.
[8] A. Hess and H. Iyer, Enumeration of mixed linear models and SAS macro forcomputation of confidence intervels for variance components, Applied Statistics inAgriculture Conference at Kansas State University, 2001.
[9] N. Lygeros and M. Mizony, Construction de posets dont le grouped’automorphismes est isomorphe à un groupe donné, C. R. Acad. Sci. Paris t.322s.I(1996), 203—206.
[10] G. Pólya, Kombinatorische Anzahlbestimmungen für Gruppen, Graphen, undchemische Verbindungen, Acta Math. 68(1937), 145—254.
[11] H. J. Prömel, Counting unlabeled structures, J. Comb. Theory, Ser. A 44(1987),
83—93.