Complete Enumeration and Properties of binary Pseudo -Youden Designs PYD(9, 6, 6)

John P. McSorley Nicholas C. Phillips (ret.) Department of Mathematics Mailcode 4408 Southern Illinois University Carbondale. IL 62901-4408 mcsorley60@hotmail.com ncpk@siu.edu

Abstract

A binary pseudo -Youden design PYD(9, 6, 6) is a 6 × 6 array in which each cell contains one element from the set V = {1, 2, …, 9}, and each element from V occurs 4 times. Every row of the array contains distinct elements and every column contains distinct elements. The rows and columns, when taken together, are pairwise balanced and form a (9, 12, 8, 6, 5)-BIBD. In Preece (1968) and (1976) a total of 345 species of binary PYD(9, 6, 6) were found. Here we complete this enumeration and find 348 species of binary PYD(9, 6, 6). We give a complete set of invariants for these species based upon the numbers of intercalates and anti-intercalates that they contain; and discuss some of their properties. We also show that there are 696 non-isomorphic binary PYD(9, 6, 6), and give a complete set of invariants for these arrays.

AMS (2000) subject classification. Primary 05B05, 05B30, 51E05; secondary 62K10. Keywords. pseudo -Youden design, row-column design, species, family, domain.

1 Introduction, Species

A binary pseudo -Youden design PYD(9, 6, 6) is a 6 × 6 array in which each cell contains one element from the set V = {1, 2, …, 9}, and each element from V occurs 4 times. Every row of the array contains distinct elements and every column contains distinct elements. The rows and columns, when taken together, are pairwise balanced and form a (9, 12, 8, 6, 5)-BIBD. We refer to such a design as D.

Two binary PYD(9, 6, 6)’s D and D′ belong to the same isomorphism class, or are isomorphic (D ∼ D′), if D can be moved to D′ by a permutation of its elements, rows, or columns. And D and D′ belong to the same species if D can be moved to D′ by taking transposes, or permuting its elements, rows, or columns; i.e., if D ∼ D′ or D ∼ D′^{T}.

Starting with Kshirsagar’s binary PYD(9, 6, 6) (see Kshirsagar (1957) and Example 4 of this paper) and continually interchanging rows of rowintercalates or columns of column-intercalates, Preece (1968) found 344 different species of binary PYD(9, 6, 6). Each of these species contains at least one intercalate. He found a further species in Preece (1976), containing no intercalates. Hence, up to 1976, there were 345 different species of binary PYD(9, 6, 6) known.

In Section 2 we produce a complete enumeration of species, and of isomorphism classes, of binary PYD(9, 6, 6). We find exactly 348 species of binary PYD(9, 6, 6), and exactly 696 isomorphism classes of binary PYD(9, 6, 6). Thus we find 3 new species of binary PYD(9, 6, 6), each containing no intercalates. So 344 species of binary PYD(9, 6, 6) contain at least one intercalate and 4 species contain no intercalates.

In Section 3 we present the 3 new species found. In Section 4 we give a complete set of invariants for all 348 species based upon the numbers of intercalates and anti-intercalates that they contain. In Section 5 we consider miscellaneous properties of the species. Finally, in Section 6, we find a complete set of invariants for the 696 isomorphism classes.

Generally speaking, a row-column design is a Youden design if its rows are pairwise balanced, and its columns are pairwise balanced. And a rowcolumn design is a pseudo -Youden design (PYD) if its rows and columns, when taken together, are pairwise balanced. This terminology follows that of Cheng (1981), where Kshirsagar’s binary PYD(9, 6, 6) is discussed. See also Section IV.54 of Colburn and Dinitz (1996). Recently binary pseudo - Youden designs have been studied under the name ‘Balanced Grids’, a binary PYD(9, 6, 6) corresponds to a BG(9, 4, 5 : 6 × 6); see McSorley et al (2005), and McSorley (2005).

2 Complete enumeration of binary PYD(9, 6, 6)

In this Section we construct all binary PYD(9, 6, 6)’s. First we require some definitions.

Let V = {1, 2, …, v} be a set and let B be a BIBD based on V with replication number m, so each element of V occurs m times in B. An aparallel class in B is a collection of blocks of B in which each element from V occurs exactly a times. A 1-parallel class is simply called a parallel class.

We say that B has type [a_{1}, a_{2}, …, a_{t}] if the blocks of B can be partitioned into t parts such that, for every 1 ≤ s ≤ t, the blocks in the s-th part form an a_{s}-parallel class. Note that ∑_{s=1}^{t} a_{s} = m and that a given B can have different types corresponding to different block partitions. We also say that the block partition itself has type [a_{1}, a_{2}, …, a_{t}]. This definition of type is a generalization of resolvability since B is resolvable if and only if it has type

\underbrace{[1, 1, …, 1]}_{m}.

Recall that the complement of B, denoted by \overline{B}, is obtained by replacing each block B in B with its complement \overline{B} = V \B.

Let A be a 6×6 array which contains each element from V = {1, 2, …, 9} exactly 4 times. Let R denote the set of rows of A and let C denote the set of columns of A. Then P(A) = R ∪ C is a block structure based on V with 12 blocks of size 6.

Theorem 2.1 Let A be as above. Then A is a binary PYD(9, 6, 6) if and only if P(A) is a (9, 12, 8, 6, 5)-BIBD with type [4, 4].

Proof. First, if A is a binary PYD(9, 6, 6) then, by definition, P(A) is a (9, 12, 8, 6, 5)-BIBD. The blocks R of P(A) form a 4-parallel class, as do the blocks C. Using the block partition {R, C}, we see that P(A) has type [4, 4].

For the backward implication suppose we have a (9, 12, 8, 6, 5)-BIBD with type [4, 4] which is a P(A) for some array A. Then, by the construction of P(A) from A, we see that A is binary and is a PYD(9, 6, 6).

Now we are ready to construct all binary PYD(9, 6, 6)’s:

Let D be a binary PYD(9, 6, 6). From Theorem 2.1 we know that P(D) is a (9, 12, 8, 6, 5)-BIBD with type [4, 4]. Up to isomorphism there is only one (9, 12, 8, 6, 5)-BIBD, (its complement \overline{P(D)} is a (9, 12, 4, 3, 1)-BIBD and is given as 1.15 Example, p. 5 of Colbourn et al (1996)).

This (9, 12, 8, 6, 5)-BIBD P(D) is given below, its blocks have been partitioned into 4 parts, {A, B, C, D}; each part is a 2-parallel class. Hence P(D) has type [2, 2, 2, 2]. From p. 14 of Colbourn et al (1996) there exists a unique resolution of \overline{P(D)}, so the block partition \{A, B, C, D\} of P(D) shown below is the unique one with type [2, 2, 2, 2]. (Indeed \overline{P(D)} is the unique Kirkman Triple System on 9 elements.)

\begin{aligned}A & 1 & 2 & 3 & 4 & 5 & 6 \\ & 1 & 2 & 3 & 7 & 8 & 9 \\ & 4 & 5 & 6 & 7 & 8 & 9 \end{aligned} \begin{aligned}B & 1 & 2 & 4 & 5 & 7 & 8 \\ & 1 & 3 & 4 & 6 & 7 & 9 \\ & 2 & 3 & 5 & 6 & 8 & 9 \end{aligned}

\begin{aligned}C & 1 & 2 & 5 & 6 & 7 & 9 \\ & 1 & 3 & 4 & 5 & 8 & 9 \\ & 2 & 3 & 4 & 6 & 7 & 8 \end{aligned} \begin{aligned}D & 1 & 2 & 4 & 6 & 8 & 9 \\ & 1 & 3 & 5 & 6 & 7 & 8 \\ & 2 & 3 & 4 & 5 & 7 & 9 \end{aligned}

So there are \binom{4}{2} = 6 block partitions of P(D) with type [4, 4]. Hence D must be obtained by permuting elements in the rows of one of the following

6 starters: A B, A C, A D, B C, B D, or C D. However the permutation (456)(798) is an automorphism of P(D), and it induces the permutation (A)(BCD) on {A, B, C, D}, similarly (24)(37)(68) induces (AB)(C)(D) on {A, B, C, D}.

So starter A B can be mapped to each of the other starters using a combination

of these two automorphisms. Hence we may use A B to construct all binary PYD(9, 6, 6)’s, up to isomorphism, by permuting elements within its rows

(different permutations are allowed for different rows). Starter A B is shown below:

A B = 1 2 3 4 5 6 1 2 3 7 8 9 4 5 6 7 8 9 1 2 4 5 7 8 1 3 4 6 7 9 2 3 5 6 8 9

By exhaustive search we found 49600 different binary PYD(9, 6, 6)’s. We divided these 49600 arrays into 696 isomorphism classes. We observed that when a choice of 696 representative arrays was chosen (one from each isomorphism class), no representative was ever isomorphic to its transpose. Hence the 696 isomorphism classes split into \frac{696}{2} = 348 species. Thus we found 3 new species of binary PYD(9, 6, 6), and exactly 348 species in all. The enumeration of binary PYD(9, 6, 6)’s is now complete.

Theorem 2.2

(i) There are exactly 348 species of binary PYD(9, 6, 6)’s.

(ii) There are exactly 696 isomorphism classes of binary PYD(9, 6, 6)’s.

(iii) A member of each isomorphism class can be obtained from starter A B above by permuting elements within its rows, different permutations being allowed for different rows.

Example 1 The following binary PYD(9, 6, 6) was constructed from A B by permuting elements within its rows.

1 2 3 4 5 6
7 8 9 1 2 3
5 4 7 9 6 8
8 1 2 5 7 4
6 9 4 3 1 7
3 6 5 8 9 2

This array has been given in standard form; namely the first row is 123456 and then, moving from left to right in successive rows, the three new elements are introduced as 7, 8, and 9.

Such binary PYD(9, 6, 6) are universally optimal in the sense of Keifer (1975) amongst all designs for 9 treatments in a 6 × 6 array.

Furthermore, it is statistically useful to know all binary PYD(9, 6, 6) because:

• they provide a large randomization set, and provide all required knowledge should anyone wish to construct valid restricted randomization sets in the sense of Bailey (1983).

• they allow investigations of secondary statistical properties: non-isomorphic designs will generally differ in their robustness (Singh, Gupta, and Singh (1987)), and in their neighbor properties (see Morgan and Uddin (1991) for examples with these parameters).

3 Three new species

Representatives from each of the three new species of binary PYD(9, 6, 6) are given below. For an explanation of the 8-tuples below them and the numbers 002, 003, and 004 above them, refer to Section 4 and Section 5 respectively. Also for further properties of these species, in particular 002, see Section 5. Species 002 has the corners property, the generalized corners property, and has automorphism group of size 3.

002  003  004
1 2 3 4 5 6  1 2 3 4 5 6  1 2 3 4 5 6
2 3 7 8 9 1  2 3 7 1 8 9  2 3 7 8 9 1
6 7 8 9 4 5  8 6 9 5 7 4  9 4 6 5 7 8
4 8 1 5 7 2  5 7 1 9 4 2  7 8 5 1 4 2
9 4 6 1 3 7  7 4 6 8 3 1  6 7 1 9 3 4
8 6 5 3 2 9  6 9 5 3 2 8  5 6 8 3 2 9

(0, 0, 0, 0, 27, 12, 4, 12) (0, 0, 0, 0, 33, 14, 2, 18) (0, 0, 0, 0, 37, 13, 3, 17)

4 348 species, invariant 8-tuple

In this Section we find a complete set of invariants for the 348 species based upon the numbers of intercalates and anti-intercalates that they contain. As usual, we require some preliminary results and definitions.

In a n × m sub-array inside an array D the n rows and m columns of the sub-array need not be consecutive.

Let D be a binary PYD(9, 6, 6), often called simply an array. Consider the pair {x, y} (x ≠ y) from V. Suppose this pair occurs in ℓ ≥ 0 rows of D then it must occur in 5 − ℓ columns. We say that it has type \underbrace{RR ⋯ R}_{ℓ} \underbrace{CC ⋯ C}_{5−ℓ}.

There are 4 occurrences of x in D, and 4 occurrences of y in D. Since D has 6 rows these 8 occurrences must overlap in at least 2 rows. Hence {x, y} has type RR ∗ ∗ ∗. Similarly for the 6 columns of D, so pair {x, y} has type ∗ ∗ ∗ CC. Hence every pair {x, y} has type RRCCC or RRRCC. Definition: Intercalates

Let m ≥ n ≥ 2. A n × m row-intercalate of D is a n × m Latin rectangle sub-array in D, (each row contains the same elements). And a n×m columnintercalate is the transpose of a m×n row-intercalate. When discussing rowand column- intercalates we often omit the words ‘row’ and ‘column’.

Theorem 4.1 Let D be a binary PYD(9, 6, 6). Then D can only contain intercalates with sizes: 2 × 2, 2 × 3, 3 × 2, 2 × 4, or 4 × 2.

Proof. Let I be a 2 × 5 intercalate in D. Without loss of generality, let I be based on the elements {1, 2, 3, 4, 5} and let it occur in rows 1 − 2, and columns 1 − 5 of D. Let the (1, 6) element of D be 6 and the (2, 6) element be 7. Now the elements 8 and 9 ∈ V must each occur 4 times in D. Hence both 8 and 9 each occur in the remaining 4 rows. Thus pair {8, 9} has type RRRR∗, a contradiction. So D doesn’t contain a 2 × 5 intercalate, similarly for a 2 × 6 intercalate.

In any 3 × 3 intercalate I based on {1, 2, 3} the pair {1, 2} occurs in all 3 rows and all 3 columns of I, for a total of ≥ 6 times in the array D, a contradiction. So D doesn’t contain a 3 × 3 intercalate.

Let I be a 3 × 4 intercalate based on {1, 2, 3, 4} occurring in rows 1 − 3 and columns 1−4 of D. Each of the pairs {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, and {3, 4} occur in all 3 rows of I. But each of the elements 1, 2, 3, and 4 must occur one more time amongst the three rows 4 − 6 of D. Hence, by the pigeon-hole-principle, some two elements, say 1 and 2, must occur in the same row again. Thus pair {1, 2} is of type RRRR∗, a contradiction. So D doesn’t contain a 3 × 4 intercalate.

All possible larger intercalates are disposed of in a similar fashion, or by other straightforward arguments.

Call a 2 × 4 intercalate irreducible if it is not a pair of 2 × 2 intercalates, and reducible if it is a pair of 2×2 intercalates. Similarly for 4×2 intercalates.

Example 2 An isomorph of Kshirsagar’s array is given twice below: first showing in bold an irreducible 2 × 4 intercalate, then a reducible 2 × 4 intercalate.

1 2 3 4 5 6  1 2 3 4 5 6
2 1 7 8 9 3  2 1 7 8 9 3
9 6 8 5 7 4  9 6 8 5 7 4
4 7 5 1 2 8  4 7 5 1 2 8
6 9 1 3 4 7  6 9 1 3 4 7
8 5 6 9 3 2  8 5 6 9 3 2

Let

inm be the number of n × m intercalates in an array (nm ≠ 24 or 42);

ii24 (ii42) be the number of 2 × 4 (4 × 2) irreducible intercalates in an array;

ri24 (ri42) be the number of 2 × 4 (4 × 2) reducible intercalates in an array.

Definition: Anti-intercalates

For n ≥ 2 and m ≥ 2 consider a n × m sub-array inside an array D. Let nm = 9s + t, where s ≥ 0 and 0 ≤ t < 9.

A n × m sub-array is called an anti-intercalate if each of the 9 elements from V occurs either s or s+1 times in it. (In fact in a n×m anti-intercalate 9 − t elements occur s times and t elements s + 1 times.)

Example 3 So a 2 × 4 anti-intercalate of D contains 8 distinct elements from V; a 5 × 2 anti-intercalate of D contains 8 elements from V once and 1 element twice; and a 4 × 4 anti-intercalate of D contains 2 elements from V once and 7 elements twice. See below for examples where D is the isomorph of Kshirsagar’s array.

1 2 3 4 5 6  1 2 3 4 5 6  1 2 3 4 5 6
2 1 7 8 9 3  2 1 7 8 9 3  2 1 7 8 9 3
9 6 8 5 7 4  9 6 8 5 7 4  9 6 8 5 7 4
4 7 5 1 2 8  4 7 5 1 2 8  4 7 5 1 2 8
6 9 1 3 4 7  6 9 1 3 4 7  6 9 1 3 4 7
8 5 6 9 3 2  8 5 6 9 3 2  8 5 6 9 3 2

Let anm be the number of n × m anti-intercalates in an array.

The numbers a22 and i22 are related:

Theorem 4.2 Let D be a binary PYD(9, 6, 6). Then a22 = i22 + 171.

Proof. In the following description of all possible different forms of 2 × 2 sub-arrays in D, distinct symbols in the sub-array represent distinct elements

in D. There are four forms of 2 × 2 sub-arrays: {xy \atop zt} (a 2 × 2 anti-intercalate),

{xy \atop zx}, {xy \atop yz}, or {xy \atop yx} (a 2 × 2 intercalate).

Let s22 be the number of 2 × 2 sub-arrays of the form {xy \atop zx} or {xy \atop yz}. Then counting all 2 × 2 sub-arrays in two different ways gives a22 + s22 + i22 = \binom{6}{2}^{2} = 225.

Each element x ∈ V occurs 4 times in D, so there are \binom{4}{2} = 6 2 × 2 sub-

arrays of the form {x∗ \atop ∗x} or {∗x \atop x∗}. Now there are 9 elements in V giving a total of 6 × 9 = 54 2 × 2 sub-arrays of the form {x∗ \atop ∗x} or {∗x \atop x∗}. Each 2 × 2 intercalate will occur twice amongst these 54 sub-arrays, so 2i22 + s22 = 54.

Solving the above two equations simultaneously gives the result.

We can also determine the numbers anm in which n = 6 or m = 6:

Theorem 4.3 Let D be a binary PYD(9, 6, 6). Then

(i) a26 = a62 = 6,

(ii) a36 = a63 = 2,

(iii) a46 = a64 = 6,

(iv) a56 = a65 = 6,

(v) a66 = 1.

Proof. (i) Let R and R′ be two distinct rows of D. Then clearly |R∪R′| ≤ 9. And so from |R ∪ R′| = |R| + |R′| − |R ∩ R′| = 12 − |R ∩ R′|, we have |R ∩ R′| ≥ 3. Clearly |R ∩ R′| ≤ 6.

Now if |R∩R′| = 6 then R and R′ form a 2×6 intercalate, a contradiction to Theorem 4.1. And |R ∩ R′| = 5 is excluded by a similar argument to that used to show the non-existence of a 2×5 intercalate. Hence |R ∩ R′| = 3 or 4.

Now let r_{3} be the number of pairs {R, R′} of distinct rows R and R′ with |R ∩ R′| = 3, and r_{4} be the number of pairs {R, R′} of distinct rows R and R′ with |R ∩ R′| = 4. Now there are \binom{6}{2} = 15 pairs of distinct rows of D hence r_{3} + r_{4} = 15. Also any x ∈ V will occur \binom{4}{2} = 6 times amongst the 15 sets R ∩ R′, for all distinct pairs {R, R′}. So, counting elements in these 15 sets, we have 3r_{3} + 4r_{4} = 9 × 6 = 54. Solving these two equations gives r_{3} = 6 and r_{4} = 9.

Now R and R′ form a 2 × 6 anti-intercalate if and only if |R ∩ R′| = 3. Hence a26 = r_{3} = 6. Similarly, working with columns, we have a62 = 6. (ii) The 6 rows of D when considered as blocks of P(D) form a 4-parallel class. But, from the discussion after Theorem 2.1, each 4-parallel class has a unique decomposition into two 2-parallel classes. Hence a36 = 2. Similarly a63 = 2. (iii) Clearly the complement of any 2 × 6 anti-intercalate is a 4 × 6 antiintercalate, and vice versa. Hence a46 = a26 = 6. Also a64 = a62 = 6.

The proofs of (iv) and (v) are straightforward.

We choose a representative array from each of the 348 species of binary PYD(9, 6, 6), and often identify a species with its representative array.

How different are any two species of the 348 from each other?

Table 1 of Preece (1968) counts the number of species containing a fixed number of n × m and m × n intercalates for various values of n and m, (although when counting 2 × 4 and 4 × 2 intercalates only irreducible ones were considered). We decided to extend this work by finding a M-tuple containing counts of intercalates and anti-intercalates, each species having a different M-tuple; thus finding a ‘complete set of invariants’ for the 348 species.

For each of the 348 species we define the following 8-tuple

(i22, i23 + i32, ii24 + ii42, ri24 + ri42, a24 + a42, a25 + a52, a33, a44).

It is clear that every array from a fixed species has the same 8-tuple.

We omit using a22 because of Theorem 4.2, and a26 + a62 because of Theorem 4.3(i), and we found that a23 + a32 was not useful.

Computer checking shows that each species has a distinct 8-tuple, hence the set of these 8-tuples constitute a complete set of invariants for the 348 species.

Theorem 4.4 Each of the 348 species of binary PYD(9, 6, 6) has a distinct 8-tuple (i22, i23 + i32, ii24 + ii42, ri24 + ri42, a24 + a42, a25 + a52, a33, a44).

Example 4 The isomorph of Kshirsagar’s species has 8-tuple (4, 0, 3, 2, 53, 16, 5, 21). Its i22 = 4 2 × 2 intercalates are shown below to the right of the species.

1 2 3 4 5 6  1 2  1 4  9 6  7 4
2 1 7 8 9 3  2 1  4 1  6 9  4 7
9 6 8 5 7 4
4 7 5 1 2 8
6 9 1 3 4 7
8 5 6 9 3 2

It has no 2 × 3 or 3 × 2 intercalates, hence i23 + i32 = 0.

It has ii24 = 3 irreducible 2 × 4 intercalates (see below) and ii42 = 0 irreducible 4 × 2 intercalates. Hence ii24 + ii42 = 3 for the 3-rd entry in its 8-tuple.

2 3 5 6  2 8 9 3  9 6 8 5 5 6 3 2  8 9 3 2  8 5 6 9

It has ri24 = 1 reducible 2 × 4 intercalate and ri42 = 1 reducible 4 × 2 intercalate, see below. Hence ri24 + ri42 = 2 for the 4-th entry.

9 6 7 4  1 2
6 9 4 7  2 1
9 6
6 9

Finally we give its a33 = 5 3 × 3 anti-intercalates which is the 7-th entry in its 8-tuple.

2 3 4  1 2 3  2 3 5  1 5 6 8 5 4
1 7 8  9 6 8  6 8 7  9 7 4 1 3 7
5 6 9  4 7 5  9 1 4  8 3 2 6 9 2

5 Miscellaneous properties of species

Numbering

We have produced a list of the 348 species according to the lexicographic ordering of their 8-tuples. The first species in this list, number 001, is the single species from Preece (1976), it has 8-tuple (0, 0, 0, 0, 9, 0, 4, 0). The next 3 species, 002, 003, and 004 are the 3 new species of this paper, see Section 3. Then come the 344 species of Preece (1968). The last, 348, has 8-tuple (7, 3, 1, 2, 56, 20, 9, 20). In this ordering the isomorph to Kshirsagar’s species is number 219. The first and last species in this list, with their 8-tuples underneath, are shown below.

001 348

1 2 3 4 5 6  1 2 3 4 5 6
7 8 9 3 1 2  2 1 7 3 8 9
6 4 5 7 8 9  5 4 6 8 9 7
2 5 7 1 9 4  7 9 2 5 4 1
4 9 1 8 6 3  8 6 4 7 1 3
8 3 6 5 2 7  6 8 9 2 3 5

(0,0,0,0,9,0,4,0) (7,3,1,2,56,20,9,20)

Families

As defined in Preece (1968) (see also Norton (1939)) two species D and D′ belong to the same family if D can be moved to D′ by a succession of row or column interchanges of 2×2 intercalates. The 348 species form 42 families of species. There are 38 families from Preece (1968); the single species 001 of Preece (1976) forms another family; as do each of the 3 new species 002, 003, and 004 of this paper. The 38 families of Preece (1968) were numbered (i)–(xxxviii). In Table 1 we extend this numbering and number the single species of Preece (1976) as family (xxxix), and the 3 new species of this paper as families (xxxx), (xxxxi), and (xxxxii). We also give the lowest numbered species in the family as a representative species (rep.). For example, family (xxxii) contains the 9 species 023, 087, 092, 113, 183, 185, 193, 197, and 208.

family rep. size  family rep. size  family rep. size
(i)  018 1  (xv)  020 1  (xxix)  070 4
(ii)  006 1  (xvi)  016 1  (xxx)  034 5
(iii)  007 1  (xvii) 025 2  (xxxi)  036 7
(iv)  008 1  (xviii) 031 2  (xxxii) 023 9
(v)  010 1  (xix)  039 2  (xxxiii) 049 9
(vi)  011 1  (xx)  030 2  (xxxiv) 042 10
(vii) 017 1  (xxi)  041 2  (xxxv) 056 14
(viii) 019 1  (xxii) 054 2  (xxxvi) 022 17
(ix)  005 1  (xxiii) 051 3  (xxxvii) 021 59
(x)  009 1  (xxiv) 048 3  (xxxviii) 026 163
(xi)  012 1  (xxv) 046 3  (xxxix) 001 1
(xii) 015 1  (xxvi) 032 3  (xxxx) 002 1
(xiii) 013 1  (xxvii) 024 3  (xxxxi) 003 1
(xiv) 014 1  (xxviii) 143 4  (xxxxii) 004 1

Table 1. The 42 families of species of binary PYD(9, 6, 6), a representative species from each family and the family size.

Domains

Similarly two species D and D′ belong to the same domain if D can be moved to D′ by a succession of row or column interchanges of row- or columnn×m intercalates, for any n×m. The 348 species form 5 domains of species. The 344 species of Preece (1968) form 1 domain; the single species 001 of Preece (1976) forms another domain; and each of the 3 new species 002, 003, and 004 of this paper forms a new domain. This information is summarized in Table 2. We give a species in the domain as a representative species; for domain (I) we give the isomorph of Kshirsagar’s species.

domain rep. size
(I)  219 344
(II)  001 1
(III)  002 1
(IV)  003 1
(V)  004 1

Table 2. The 5 domains of species of binary PYD(9, 6, 6), a representative species from each domain and the domain size.

Corners property

A species has the corners property (see Preece (1976)) if its rows and columns can be permuted so that each of its 3 × 3 corners is a 3 × 3 antiintercalate. As computed in Preece (1976) exactly 35 of the 345 species of Preece (1968) and (1976) have the corners property. One of our new species, 002, also has this property. Thus there are a total of 36 species of the 348 with the corners property. They are spread amongst 6 families: family (i): 018; family (xxviii): 143, 163, 172, 200; from family (xxxii): 023, 113, 185; from family (xxxviii): 124, 135, 147, 151, 159, 177, 190, 205, 237, 244, 251, 273, 278, 288, 289, 300, 301, 304, 314, 316, 320, 325, 326, 335, 339, 341; family (xxxix): 001; family (xxxx): 002.

The rows and columns of species 002 from Section 3 have been permuted to illustrate its corners, see below.

Generalized corners property

A species has the generalized corners property if it has four 3 × 3 antiintercalates which cover all 36 cells in the species. There are 82 species with this property. Clearly any species with the corners property also has the generalized corners property. Of the 46 species with the generalized corners property but not the corners property, species 017 has the lowest number.

We have shown it below with its top-left and bottom-left corners as 3×3 antiintercalates; this is the closest it can be to a ‘corners’ form. Its 2 right-hand 3 × 3 anti-intercalates are shown in bold, and in italics.

002 017

1 3 5 4 2 6 2 7 9 8 3 1 6 8 4 9 7 5 4 1 7 5 8 2 9 6 3 1 4 7 8 5 2 3 6 9  1 3 6 2 4 5 4 2 7 8 5 1 8 9 5 6 3 2 2 7 1 3 8 9 6 5 8 4 9 7 9 4 3 7 1 6

corners generalized corners

Types

At the beginning of Section 4 we noted that in any binary PYD(9, 6, 6) each of the \binom{9}{2} = 36 pairs \{x, y\} from V must have type RRCCC or RRRCC. In fact we can say more:

Theorem 5.1 Let D be a binary PYD(9, 6, 6). Then D has 18 pairs of type RRCCC and 18 pairs of type RRRCC.

Proof. Let n_{2} be the number of pairs {x, y} of type RRCCC and n_{3} the number of pairs of type RRRCC. Then clearly n_{2} + n_{3} = 36. Now pairs of type RRCCC occur in 2 rows and pairs of type RRRCC occur in 3 rows. Hence 2n_{2} + 3n_{3} equals the number of pairs covered in all rows, i.e., 2n_{2} + 3n_{3} = 6\binom{6}{2} = 90. Solving these equations gives n_{2} = n_{3} = 18 as required.

Automorphism groups

There are just 5 species which have automorphism group of size greater than 1. They are: species 001 with automorphism group of size 9; and species 002, 018, 143, and 200 with automorphism groups of size 3.

Oddities

The only species with no 3 × 3 anti-intercalates (i.e., with a33 = 0) is species 040.

The only species with no 4 × 4 anti-intercalates (a44 = 0) is species 001, this is also the only species with automorphism group of size 9. Otherwise a44 ≥ 12 for all other species. There are exactly 4 species with a44 = 12, namely species 002, 018, 019, and 143. All of these, except 019, have automorphism group of size 3. The remaining species with automorphism group of size 3, species 200, has a44 = 18.

6 696 isomorphism classes, invariant 10-tuple

We choose a representative array from each of the 696 isomorphism classes of binary PYD(9, 6, 6), and often identify an isomorphism class with its representative array. For each of the 696 isomorphism classes we define the following 10-tuple

(i22, i23, i32, ii24, ii42, ri24, ri42, a23, a34, a42).

It is clear that every array from a fixed isomorphism class has the same 10tuple. Again, computer checking shows that each isomorphism class has a distinct 10-tuple, hence the set of these 10-tuples constitute a complete set of invariants for the 696 isomorphism classes of binary PYD(9, 6, 6).

Theorem 6.1 Each of the 696 isomorphism classes of binary PYD(9, 6, 6) has a distinct 10-tuple (i22, i23, i32, ii24, ii42, ri24, ri42, a23, a34, a42).

Example 5 The isomorph of Kshirsagar’s array has 10-tuple (4, 0, 0, 3, 0, 1, 1, 129, 70, 25).

As the 696 arrays come in 348 ‘array–array transpose’ pairs we number them as ∗ ∗ ∗ and ∗ ∗ ∗T where ∗ ∗ ∗ ranges from 001 to 348, and T denotes transpose. We have produced a file with the 696 arrays in the order: 001, 002, …, 348, 001T, 002T, …, 348T. Thus the first 348 arrays in this file coincide exactly with the species file. The first array 001 and the last array 348T are shown below with their 10-tuples underneath.

001 348T

1 2 3 4 5 6  1 2 3 4 5 6
7 8 9 3 1 2  2 1 7 8 6 5
6 4 5 7 8 9  9 4 6 2 7 8
2 5 7 1 9 4  7 9 5 3 4 2
4 9 1 8 6 3  3 5 8 7 1 9
8 3 6 5 2 7  6 8 4 1 9 3

(0,0,0,0,0,0,0,111,48,0) (7,3,0,1,0,1,1,134,81,25)

Available files

Various files are available for the interested reader by contacting the authors. Namely: fileS1 which contains the 348 species of binary PYD(9, 6, 6) numbered 001....348; fileS2 which contains the 348 species, each species followed by a complete list of the intercalates and anti-intercalates that make up its 8-tuple; fileS3 which contains the 42 families of species; fileI1 which contains the 696 isomorphism classes of binary PYD(9, 6, 6) numbered 001....348T; and fileI2 containing the 696 isomorphism classes, each isomorphism class followed by a complete list of the intercalates and anti-intercalates that make up its 10-tuple.

Acknowledgment

We would like to thank Donald Preece for his help and encouragement in preparing this paper. All data in Preece (1968) and (1976) has been checked and found to be correct. We would also like to thank the Associate Editor for useful comments and relevant references pertaining to earlier work in the literature.

References Bailey, R.A., 1983. Restricted randomization. Biometrika.70, no.1, 183–198. Cheng, C-S., 1981. Optimality and construction of pseudo-Youden designs. Ann.Statist. 9, no.1, 201–205.

Colbourn, C.J., Dinitz, J.H., 1996. The CRC Handbook of Combinatorial Designs. CRC Press.

Keifer, J., 1975. Construction and optimality of generalized Youden designs. In: A survey of statistical design and linear models. J.N.Srivastava, ed.. (Proc. Internat. Sympos., Colorado State University, Ft. Collins, Colo., 1973). North-Holland, Amsterdam, 333–353.

Kshirsagar, A.M., 1957. On balancing in designs in which heterogeneity is eliminated in two directions, Calcutta Statist. Assoc. Bull. 7, 161–166.

McSorley, J.P., 2005. Double Arrays, Triple Arrays, and Balanced Grids with v = r + c − 1, Designs, Codes, and Cryptography. 37, 313–318.

McSorley, J.P., Phillips, N.C.K., Wallis, W.D., Yucas, J.L., 2005. Double Arrays, Triple Arrays, and Balanced Grids, Designs, Codes, and Cryptography. 35, 21–45.

Morgan, J.P., Uddin, N., 1991. Two-dimensional design for correlated errors. Ann. Statist. 19, no.4, 2160–2182.

Norton, H.W., 1939. The 7×7 squares, Ann. Eugenics, IX, part III, 269–307. Preece, D.A., 1968. Balanced 6 × 6 designs for 9 treatments, Sankhyā, series B, 30, 443–446.

Preece, D.A., 1976. A second domain of balanced 6 × 6 designs for nine equally-replicated treatments, Sankhyā, series B, 38, pt.2, 192–194.

Singh, G., Gupta, S., Singh, M., 1987. Robustness of row-column designs. Statist. Probab. Lett., 5, no.6, 421–424.