TIGHT SINGLE-CHANGE COVERING DESIGNS

D. A. PREECE

Institute of Mathematics and Statistics, The University, Canterbury, Kent CT2 7NF, England

R. L. CONSTABLE Mathematical Institute, University of St Andrews, Fife KY16 9SS, Scotland.

G. ZHANG Department of Mathematics,

University of Alabama, Huntsville, AL 35899.

J. L. YUCAS, W. D. WALLIS and J. P. McSORLEY Department of Mathematics, Southern Illinois University, Carbondale, IL 62901-4408.

N. C. K. PHILLIPS Department of Computer Science,

Southern Illinois University, Carbondale, IL 62901-4511.

Abstract

A ‘tight single-change covering design’ (tsccd) is an ordered set of blocks, each block comprising k distinct elements taken from the set S = {1, 2, ..., v}, v > k , with the properties that (i) any two members of S occur together in at least one block, (ii) each block after the first is obtained from the previous block by changing just one element, and (iii) the newly introduced element in any block B after the first has not previously appeared in the same block as any of the other elements from B. Existence results for tsccd’s are reviewed, many examples of tsccd’s with k = 2, 3, and 4 are given, and properties of some tsccd’s are examined. For k = 2, 3, and 4, a tsccd can now be constructed for any value of v that is consistent with known existence results. For k = 4, the least such value is v = 12. Tsccd’s with (v, k) = (12, 4) are partially enumerated, and tsccd’s with (v, k) = (15, 4) and (18, 4) are given. A method is presented for using some of these to construct tsccd’s with k = 4 and v equal to any value from the sequence 12, 13, 15, 16, 18, 19, 21, 22, ... . ‘Row-regular’ and ‘element-regular’ tsccd’s are defined; a particularly remarkable tsccd with (v, k) = (12, 4) is presented that is regular in both senses. No tsccd with k > 4 has yet been found.

1 Definitions, notation and background

You can’t invent a design.

You recognise it, in the fourth dimension.

That is, with your blood and your bones, as well as with your eyes.

D. H. Lawrence [4]

We follow Wallis, Yucas and Zhang [6] in defining a ‘tight single-change covering design’ (tsccd) as an ordered set of blocks, each block comprising k distinct elements taken from the set S = {1, 2, ..., v}, v > k , with the properties that (i) any two members of S occur together in at least one block, (ii) each block after the first is obtained from the previous block by changing just one element, and (iii) the newly introduced element in any block B after the first has not previously appeared in the same block as any of the other elements from B. The term ‘covering’ connotes that all pairs of elements from S are ‘covered’ within blocks. For convenience we write blocks as columns, we take the sequence as running from left to right, and we leave a block’s unchanged elements in the same positions as they had in the previous block. An example of a tsccd with (v, k) = (6, 3) is therefore the following [6], where each changed element and each element of the first block is marked with an asterisk:

∗1 1 1 1 ∗3 3 ∗2
∗2 2 ∗5 ∗6 6 6 6  (1.1)
∗3 ∗4 4 4 4 ∗5 5

A tsccd is a special type from amongst the block sequences considered by Gower and Preece [2] in response to a combinatorial problem posed by Nelder [5]. Although tsccd’s are mathematically of great interest in their own right, motivation for their discovery came originally from practical applications in statistical computing (see [5] and [2]) and in the testing of electrical components (see [6]).

A tsccd with k = 3 differs radically from a minimal-change (i.e. singlechange) twofold triple system as defined by Colbourn and Johnstone [1], where any two elements are paired together in exactly 2 blocks of size 3. Nor is a tsccd analogous to an optimal single-change scheme as described by Garside [3] for multiple regression analysis; in such a scheme, the change from one model to the next is made by either (a) adding a variate to the model or (b) dropping a variate from the model, not by (c) replacing one variate by another, as would be required if the number of variates were to be a constant k.

We use the notation tsccd(v, k) for a tsccd that has S = {1, 2, ..., v} and block size k.

We define a ‘standardised’ tsccd(v, k) as a tsccd(v, k) in which (a) the elements of the first block are 1, 2, ..., k , in that order, (b) the other elements are initially introduced in the order k + 1, k + 2, ..., v, and (c) the elements of the first block are changed initially in the order k, k − 1, ..., 2, 1. Thus the tsccd(6, 3) given as (1.1) is standardised. This form of standardisation is consistent with the algorithm given by Nelder [5]; a block-sequence generated by that algorithm is a standardised tsccd(v, k) if k = 2, but is not in general a tsccd; indeed, Nelder’s algorithm is not in general a single-change algorithm for all blocks.

In the terminology of Nelder [5], each initial appearance of an element in the first block, and each subsequent replacement of an element, is a ‘transfer’; thus each transfer in (1.1) is marked by an asterisk. We use T to denote the total number of transfers in a tsccd and b to denote the total number of blocks; thus

T = k+(b−1) = (k−1)+b. (1.2)

A ‘tight double-change covering design’ (tdccd) could be defined similarly to a tsccd, with the requirement that each block after the first must contain exactly two elements that are absent from the previous block. For k = 3, such a design is merely a Steiner triple system with the blocks ordered so that any two consecutive blocks have an element in common, that element being in the same position in each of the two blocks. A tdccd with (v, k) = (9, 3) is

\begin{matrix}∗1 & 1 & 1 & 1 & ∗4 & ∗3 & ∗2 & ∗3 & ∗8 & 8 & 8 & ∗2 \\ ∗2 & ∗4 & ∗5 & ∗6 & 6 & 6 & 6 & ∗5 & ∗9 & ∗2 & ∗3 & ∗9 (1.3) \\ ∗3 & ∗7 & ∗9 & ∗8 & ∗5 & ∗9 & ∗7 & 7 & 7 & ∗5 & ∗4 & 4 \end{matrix}

Tdccd’s are not considered further in this paper.

2 The ‘reverse’ of a tight single-change covering design

If the blocks of a tsccd are written in reverse order, to give the ‘reverse’ of the initial tsccd, the resultant sequence of blocks is still a tsccd. For example, the reverse of (1.1) is

∗2 ∗3 3 ∗1 1 1 1
∗6 6 6 6 ∗5 ∗2 2  (2.1)
∗5 5 ∗4 4 4 4 ∗3

By taking the rows in the order 2, 3, 1 and then relabelling the elements, (2.1) can be converted into the following standardised form (2.2), which is not the same as (1.1):

\begin{matrix}∗1 & 1 & 1 & 1 & ∗2 & ∗3 & 3 \\ ∗2 & 2 & ∗5 & 5 & 5 & 5 & ∗4 (2.2) \\ ∗3 & ∗4 & 4 & ∗6 & 6 & 6 & 6 \end{matrix}

A standardised tsccd may however be identical to its standardised reverse, as is illustrated by the sole standardised tsccd(3, 2):

\begin{matrix}∗1 & 1 & ∗2 \\ ∗2 & ∗3 & 3 (2.3) \end{matrix}

3 Admissible pairs of values of v and k

The number of pairs of the integers 1, 2, ..., v is \binom{v}{2}, the number of pairs in the first block of a tsccd(v, k) is \binom{k}{2}, and the number of new pairs in each subsequent block is k − 1, so a tsccd(v, k) must have

\binom{v}{2} = \binom{k}{2} + (b − 1)(k − 1).  (3.1)

Thus, for k = 3, the integer \binom{v}{2} must be odd, so v is restricted on criterion (3.1) to the values 6, 7, 10, 11, 14, 15, .... For k = 4, we have v similarly restricted to the values 6, 7, 9, 10, 12, 13, ...; for k = 5, we have v restricted to 12, 13, 20, 21, 28, 29, ...; and for k = 6 we have v restricted to 10, 11, 15, 16, 20, 21, ....

When the last element appears for the first time in a tsccd(v, k), at least v transfers have already occurred; this element is paired at that time with k − 1 other elements, so at least v − k further transfers must occur before it has been paired with all the other elements. Therefore

T ≥ 2v − k,

i.e.

b − 1 ≥ 2(v − k),

as established in Theorem 2 of Wallis, Yucas and Zhang [6]. Using (3.1) we therefore have

\binom{v}{2} − \binom{k}{2} ≥ 2(v − k)(k − 1).

i.e.

(v − k){v − 3(k − 1)} ≥ 0.

Thus a tsccd(v, k) must have

v ≥ 3(k − 1).  (3.2)

Theorem 3.3 of Zhang [7] shows that relationship (3.2) can be sharpened for k > 3, to become

v > 3k − 2 for k > 3.  (3.3)

From (3.1) and (3.3), a tsccd(v, 4) must have v ≥ 12, and a tsccd(v, k) with k = 5 or 6 must have v ≥ 20.

Theorem 3.3 of Zhang [7] also shows that we must have

b ≥ 3v − 4k + 1,

i.e.

v(v − 1) ≥ (6v − 7k)(k − 1).  (3.4)

For k = 5, this criterion is satisfied by v = 20; for k = 6 it excludes v = 20 but not v = 21.

Table 1 uses asterisks to indicate which pairs of values of v and k (v ≤ 21, k ≤ 6) are admissible on criteria (3.1), (3.2), (3.3) and (3.4).

Combining equations (1.2) and (3.1) we have

v(v − 1) = (2T − k)(k − 1).  (3.5)

k\v 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
2 ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗
3  - - ∗ ∗ - - ∗ ∗ - - ∗ ∗ - - ∗ ∗ - -
4  - - - - - - - ∗ ∗ - ∗ ∗ - ∗ ∗ - ∗
5  - - - - - - - - - - - - - - ∗ ∗
6  - - - - - - - - - - - - - - ∗

Table 1. Values of (v, k) that are admissible (denoted by ∗) or inadmissible (denoted by -) on criteria (3.1), (3.2), (3.3) and (3.4) for the existence of a tsccd(v, k), (v ≤ 21, k ≤ 6).

4 The numbers of transfers of individual elements

At each transfer of any element in a tsccd(v, k), that element occurs with k − 1 of the other v − 1 elements. The maximum number A of transfers of any element must therefore satisfy

A ≤ (v − 1)/(k − 1).  (4.1)

Following Wallis, Yucas and Zhang [6], we write t_{i} for the number of elements in a tsccd that are transferred i times. As all the elements that are transferred just once must occur together in some block, we have t_{1} ≤ k. Accordingly the constraints on the values t_{i} are

t_{1} ≤ k, ∑_{i=1}^{A} t_{i} = v, ∑_{i=1}^{A} it_{i} = T.  (4.2)

Thus, for v = 6 and k = 3, we must have t_{1} = t_{2} = 3, as in (1.1) and (2.2).

We define a tsccd(v, k) to be ‘element-regular’ if it has each element transferred the same number of times, say μ times, so that

t_{μ} = t_{T/v} = v

for some μ from {1, 2, ...}. Then we have, from equation (3.5), the relationship

v^{2} − (2ku − 2u + 1)v + k(k − 1) = 0.  (4.3)

For v > k , the solutions to this have v = k(k − 1) and k = 2μ; they are

(v, k, μ) = (12, 4, 2), (30, 6, 3), ....

Indeed Section 7 below gives element-regular tsccd(12, 4)’s, each element in each of these tsccd’s being transferred just twice.

We write f_{i} for the number of blocks in a tsccd that contain any particular element that is transferred i times (i = 1, 2, ..., A). Each time such an element is transferred, it appears with k − 1 other elements, so

f_{i} = i + {(v − 1) − i(k − 1)}

i.e.

f_{i} = (v − 1) − i(k − 2).  (4.4)

Thus

f_{1} > f_{2} > ⋯ > f_{A} if k > 2

and

f_{1} = f_{2} = ⋯ = f_{A} = v − 1 if k = 2.

Also for any tsccd(v, k), we write p_{i} for the number of pairs of elements such that each pair occurs together in i successive blocks (i = 1, 2, ..., I, where I = f_{1} − 1 = v − k). The basic constraints on the values p_{i} are

∑_{i=1}^{v−k} p_{i} = \binom{v}{2}, ∑_{i=1}^{v−k} ip_{i} = b\binom{k}{2}.  (4.5)

For k = 2,

p_{1} = \binom{v}{2}, p_{i} = 0 for i > 1.

For any tsccd(v, k) with k even, p_{1} is odd or even according as b is odd or even, respectively. For k > 2 , this is because k − 1 of the pairs from the first block occur in that block only, k − 1 of the pairs from the last block occur in that block only, and either 1 or k − 1 of the pairs in any other block occur in that block only.

To obtain a general inequality for p_{v−k}, we now define a pair (x, y) of elements from a tsccd(v, k) to be ‘persistent’ if x and y occur together in v − k successive blocks, and we define the set of v − k successive blocks to be a ‘long run’; blocks 2, 3 and 4 of (1.1) constitute a long run for the pair (1,4).

Throughout a long run for a persistent pair (x, y), each of x and y occurs with (k−1)+(v−k−1) = v−2 other elements, and only some single element z is lacking from the long run; in order that each of x and y can occur with z in some block, z must occur in the ‘fence’ blocks, i.e. the block immediately before and the block immediately after the long run. We shall then say that z ‘brackets’ the long run; in (1.1), the element 3 brackets the long run for the persistent pair (1, 4). As a long run for a persistent pair (x, y) must be bracketed by some element z, a long run cannot begin in the first block or end in the last block of the tsccd; also, as each of x and y occurs with every other element in at least one block from amongst the long run and its fences, each element from a persistent pair is transferred only once. Consequently, no element can be common to 2 different persistent pairs, i.e. persistent pairs must be disjoint. As there must be at least one block containing all the elements from all the persistent pairs, the total number p_{v−k} of persistent pairs must satisfy

p_{v−k} ≤ k/2.  (4.6)

A tsccd and its reverse have the same set of values {t_{i}}, the same set of values {f_{i}}, and the same set of values {p_{i}}.

We write s_{j} for the number of transfers in row j of a standardised tsccd(v, k) (j = 1, 2, ..., k). Clearly

∑_{j=1}^{k} s_{i} = T.  (4.7)

We define a tsccd(v, k) to be ‘row-regular’ if it has

s_{1} = s_{2} = ⋯ = s_{k} = T/k.  (4.8)

and to be ‘row-irregular’ otherwise. From (1.2) it follows that, for a rowregular tsccd(v, k), the block size k must be a factor of b − 1. Thus, for a row-regular tsccd(v, k) with 2 ≤ k ≤ 4, values of v are restricted as follows:

k = 2 : v = 2, 3 (mod 4), v ≥ 3;
k = 3 : v = 3, 6, 7, 10 (mod 12), v ≥ 6;
k = 4 : v = 4, 12, 13, 21 (mod 24), v ≥ 12.

The tsccd(6, 3) given as (1.1) above is row-regular. The tsccd(12, 4) labelled A in Table 8 below is both row-regular and element-regular.

5 Tight single-change covering designs with k = 2

As mentioned in Section 1 above, the algorithm of Nelder [5] produces a standardised tsccd if k = 2; this tsccd(v, 2) has

b = \binom{v}{2}, T = \binom{v}{2} + 1.

The nature of the algorithm is exemplified by the following tsccd(7, 2):

{∗1 \atop ∗2} {1 \atop ∗3} {1 \atop ∗4} {1 \atop ∗5} {1 \atop ∗6} {1 \atop ∗7} {∗6 \atop 7} {∗5 \atop 7} {∗4 \atop 7} {∗3 \atop 7} {∗2 \atop 7} {2 \atop ∗3} {2 \atop ∗4} {2 \atop ∗5} {2 \atop ∗6} {∗5 \atop 6} {∗4 \atop 6} {∗3 \atop 6} {3 \atop ∗4} {3 \atop ∗5} {∗4 \atop 5} (5.1)

Following the serpentine sequence of asterisks from left to right in (5.1) will make the method of generation clear; formal details are in [5]. For k = 2 and an even value of v we have

s_{1} = (v^{2} − 2v + 4)/4 and s_{2} = v^{2}/4,

whereas for k = 2 and an odd value of v we have

s_{1} = (v − 2v + 5)/4 and s_{2} = (v + 1)(v − 1)/4.

Thus Nelder’s algorithm produces a row-regular tsccd(v, 2) only if v = 3, in which case the tsccd is (2.3).

For (v, k) = (4, 2), Nelder’s algorithm gives

\begin{matrix}∗1 & 1 & 1 & ∗3 & ∗2 & 2 \\ ∗2 & ∗3 & ∗4 & 4 & 4 & ∗3 & (5.2) \end{matrix}

However, there are easily seen to be 10 standardised tsccd(4, 2)’s; these also include

\begin{matrix}∗1 & 1 & 1 & ∗2 & ∗3 & 3 \\ ∗2 & ∗3 & ∗4 & 4 & 4 & ∗2 & (5.3) \end{matrix}

\begin{matrix}∗1 & 1 & 1 & ∗2 & 2 & ∗4 \\ ∗2 & ∗3 & ∗4 & 4 & ∗3 & 3 & (5.4) \end{matrix}

\begin{matrix}∗1 & 1 & 1 & ∗3 & 3 & ∗4 \\ ∗2 & ∗3 & ∗4 & 4 & ∗2 & 2 & (5.5) \end{matrix}

and

\begin{matrix}∗1 & 1 & ∗4 & 4 & 4 & ∗3 \\ ∗2 & ∗3 & 3 & ∗1 & ∗2 & 2 & (5.6) \end{matrix}

The other 5 standardised tsccd(4, 2)’s may be obtained by standardising the reverses of (5.2), (5.3), (5.4), (5.5) and (5.6). For (v, k) = (4, 2), the equations (4.2) have only 2 sets of solutions, namely

{(t_{1}, t_{2}, t_{3}) = (2, 1, 1), \atop (T 1)} {(1, 3, 0) \atop (T 2)} (5.7)

and each of the 10 standardised tsccd(4, 2)’s satisfies one or other of the following:

{(s_{1}, s_{2}) = (3, 4), \atop (S1)} {(4, 3) \atop (S2)} (5.8)

For the standardised tsccd’s (5.2) and (5.3) and their standardised reverses, the sets of solutions satisfied are (T 1) and (S1); for (5.4), (5.5) and (5.6) we have (T 2) and (S1); and for the standardised reverses of (5.4), (5.5) and (5.6) we have (T 2) and (S2). For no standardised tsccd(4,2) can we have (T 1) and (S2).

For k = 2, the number of solutions of (4.2) increases as v increases. Even for (v, k) = (5, 2) there are five solutions of equations (4.2), namely

{(t_{1}, t_{2}, t_{3}, t_{4}) = (0, 4, 1, 0), \atop (T 1)} {(1, 2, 2, 0), \atop (T 2)} {(2, 0, 3, 0), \atop (T 3)} {(1, 3, 0, 1), \atop (T 4)} {(2, 1, 1, 1) \atop (T 5)} (5.9)

Also, every standardised tsccd(5,2) satisfies one of the following:

{(s_{1}, s_{2}) = (4, 7), \atop (S1)} {(5, 6), \atop (S2)} {(6, 5), \atop (S3)} {(7, 4) \atop (S4)} (5.10)

Of the 20 possible combinations obtainable from (5.9) and (5.10), there are standardised tsccd’s for only 15, as in Table 2. For economy and clarity, only the transfers in each tsccd(5, 2) in Table 2 are printed, their asterisks being suppressed. (This form of printing will be used henceforth without further comment.) The tsccd(5, 2)’s in Table 2 clearly have little combinatorial interest in themselves, but the Table well illustrates the intricacies associated with establishing the existence of tsccd’s with particular properties.

Standardized tsccd’s each  Standardized tsccd’s each
having a reverse that is  having a reverse that is
of a different type S1,  of the same type S1,
S2, S3, S4 from itself  S2, S3, S4 from itself
(last transfer in first row)  (last transfer in first row)
(T 1)  (t_{1}, t_{2}, t_{3}, t_{4}) = (0, 4, 1, 0)
(S1) 1 . . 5 . . 3 . . 2 1 . 4 . 5 . . 2 . .
2 3 4 . 1 2 . 5 4 .  2 3 . 1 . 4 3 . 4 5
(S2) 1 . 4 . 5 . 2 . . 4 1 . 4 . 1 . 2 . 3 .
2 3 . 1 . 3 . 4 5 .  2 3 . 5 . 4 . 5 . 2
(S3) 1 . 2 4 . 5 . 4 . 3 1 . 4 5 . 4 . 3 5 .
2 3 . . 1 . 2 . 5 .  2 3 . . 1 . 2 . . 4
(S4) 1 . 4 2 . 5 1 . 3 2 No example
2 3 . . 4 . . 5 . .  exists
(T 2)  (t_{1}, t_{2}, t_{3}, t_{4}) = (1, 2, 2, 0)
(S1) 1 . 4 . . 5 … 2 1 . . 2 3 . 5 …
2 3 . 1 2 . 1 4 3 .  2 3 4 . . 2 . 1 3 4
(S2) 1 . 2 4 . 5 … 1 1 … 2 3 . 5 2 .
2 3 . . 2 . 1 3 4 .  2 3 4 5 . . 4 . . 3
(S3) 1 . 4 2 5 . 4 . . 5 1 . 4 2 5 . 4 . 2 .
2 3 … 1 . 5 2 .  2 3 … 1 . 5 . 4
(S4) 1 . 4 5 2 . 5 1 . 2 No example
2 3 … 4 . . 5 .  exists
(T 3)  (t_{1}, t_{2}, t_{3}, t_{4}) = (2, 0, 3, 0)
(S2) No example 1 … 4 3 2 . 3 .
exists  2 3 4 5 … 4 . 2
(T 4)  (t_{1}, t_{2}, t_{3}, t_{4}) = (1, 3, 0, 1)
(S1) 1 . 4 . . 5 … 2 1 … 2 . . 4 5 .
2 3 . 2 1 . 4 2 3 .  2 3 4 5 . 4 3 . . 4
(S2) 1 … 2 3 . . 2 5 1 . 2 4 5 . . 4 . .
2 3 4 5 . . 2 4 . .  2 3 … 2 1 . 2 5
(S3) 1 . . 3 2 . . 1 4 3 1 . 2 4 5 . . 2 1 .
2 3 4 . . 3 5 …  2 3 … 2 4 . . 5
(S4) 1 . 2 4 5 . 2 1 . 2 No example
2 3 … 4 . . 5 .  exists
(T 5)  (t_{1}, t_{2}, t_{3}, t_{4}) = (2, 1, 1, 1)
(S2) 1 … 4 3 2 . . 3 1 . 2 4 5 … 4 .
2 3 4 5 … 3 4 .  2 3 … 4 2 1 . 2
(S3) 1 . 2 4 … 1 2 3 No example
2 3 . . 2 1 5 …  exists

Table 2. Standardized tsccd(5,2)’s for each of the 5 solutions of equations (4.2) (b = 10, T = 11)

Procedures are available for obtaining a standardised row-regular tsccd(v′+ 4, 2) from a standardised row-regular tsccd(v′, 2). Thus the degenerate standardised tsccd(2, 2) consisting of the single block

1 2

and, separately, the standardised row-regular tsccd(3, 2) given as (2.3) are all that we need to obtain a standardised row-regular tsccd(v, 2) for any v = 2, 3 (mod 4), v ≥ 3. To describe such procedures, of which we give just two, we use the letters A, B, C, D to denote the elements v′ +1, v′ +2, v′ +3, v′ +4. We let X and Y denote the elements in rows 1 and 2 respectively of the last block of the standardised row-regular tsccd(v′, 2), and we write z for any sequence of the remaining v′ − 2 elements from that tsccd(v′, 2). Then, for our first procedure, the standardised row-regular tsccd(v′ + 4, 2) consists of the standardised row-regular tsccd(v′, 2) with the following sequence of 4v′+6 further blocks appended:

\begin{matrix}. & . & C & D & . & C & . & D & . & Y & . & z & A & . & . & z & D & . \\ A & B & . & . & Y & . & X & . & A & . & B & . & . & z & C & . & . & z (5.11) \end{matrix}

where each of the notations

\begin{matrix}z & and & . \\ . & & z \end{matrix}

represents a succession of v′ − 2 blocks. With v′ = 2, this procedure gives the first and fourth of the tsccd’s in Table 3.

v = 6 (b = 15, T=16, T/k = 8)

(t_{1}, t_{2}, …, t_{5}) = (0, 2, 4, 0, 0)

1 . . 5 6 . 5 . 6 . 2 . 3 . 6 2 3 4 . . 2 . 1 . 3 . 4 . 5 . (t_{1}, t_{2}, …, t_{5}) = (0, 4, 1, 0, 1) 1 . . 2 5 6 . . 2 4 5 . . 6 . 2 3 4 … 2 3 … 2 1 . 5 (t_{1}, t_{2}, …, t_{5}) = (2, 0, 3, 0, 1) 1 . 2 4 . . 5 …. 4 3 2 1 2 3 . . 2 1 . 2 3 4 6 ….

v = 7 (b = 21, T=22, T/k = 11) (t_{1}, t_{2}, …, t_{6}) = (0, 1, 5, 0, 1, 0) 1 . 2 . . 6 7 . 6 . 7 . 3 . 1 4 . . 1 7 . 2 3 . 4 5 . . 3 . 2 . 4 . 5 . . 1 6 . . 1 (t_{1}, t_{2}, …, t_{6}) = (0, 4, 1, 0, 1, 1) 1 . 2 4 5 …. 1 4 …. 2 1 3 . 2 6 2 3 … 2 1 6 7 . . 2 1 5 6 … 7 . . (t_{1}, t_{2}, …, t_{6}) = (2, 0, 2, 1, 2, 0) 1 . 2 . 1 3 5 … 6 . . . . . 5 4 3 2 1 2 3 . 4 … 3 2 1 . 2 3 4 5 7 . . . . .

Table 3. Some standardized row-regular tsccd(v, 2)’s with v = 6, 7. ——————————————————————————— A perhaps more systematic procedure can readily be presented if we in-

troduce the following further notation for sequences of elements, where the superscript R denotes reversal of the natural order of the elements in the sequence:

w_{−X} = 1, 2, ..., X − 1, X + 1, ..., v′ − 1, v′
w_{+A}^{R} = A, v′, v′ − 1, ..., 2, 1
w_{+AB} = 1, 2, ..., v′ − 1, v′, A, B
w_{+ABC}^{R} = C, B, A, v′, v′ − 1, ..., 2, 1

Then, for our second procedure, we obtain a standardised row-regular tsccd(v′+ 4, 2) by appending the following sequence of 4v′+6 blocks to the standardised tsccd(v′, 2):

\begin{matrix}. & w − X & B & C & w_{+ABC}^{R} \\ A & . & w_{+A}^{R} & w_{+AB} & D (5.12) \end{matrix}

With v′ = 2, this procedure gives the third and sixth of the tsccd’s in Table 3. The second and fourth of the tsccd’s in the Table are not obtainable by either of our procedures, and were obtained by trial-and-error to provide solutions for further sets of values of (t_{1}, t_{2}, ...).

6 Tight single-change covering designs with k = 3

A tsccd(v, 3) exists for each of the values v = 6, 7, 10, 11, 14, 15, 18, 19, ... (see Table 1). Standardised examples with v = 6 are (1.1) and (2.2) above. Gower and Preece [2] gave non-standardised examples with v = 7, one of which was Preece’s original example as quoted by Nelder [5], and indicated that various examples with v = 10 had been found.

Lemma 5 of Wallis, Yucas and Zhang [6] provides a recursive method for obtaining a tsccd(v′ + 4, 3) from a tsccd(v′, 3). Thus, tsccd(v, 3)’s for all possible values of v are immediately obtainable if we have tsccd(v, 3)’s with v = 6 and 7. Indeed, if a single block containing merely the elements 1, 2, 3 is regarded as a degenerate tsccd(v, k) with v = k = 3, the recursive construction can be used to convert this single block to a tsccd(v, 3) with v = 3 + 4 = 7. So, the construction and a tsccd(6, 3) are all that is needed to provide us with a tsccd(v, 3) for any of the possible values 6, 7, 10, 11, 14, 15, ... for v.

Wallis, Yucas and Zhang’s construction [6] can readily be modified to produce only standardised tsccd(v, 3)’s from starter tsccd(v, 3)’s that are themselves standardised. The modified algorithm is most easily illustrated by using it with v′ = 6 to obtain a standardised tsccd(10, 3) from a standardised tsccd(6, 3). The blocks of the tsccd(10, 3) fall into 5 sets A, B, C, D, E as follows:

\begin{matrix}A & B & C & D & E \\ 1 … 3 . 2 & …. 6 . & 1 3 4 5 & . & . 4 3 1 \\ 2 . 5 6 … & . 8 . 10 . . & …. & . & 9 … \\ 3 4 … 5 . & 7 . 9 . . 8 & …. & 7 & …. \end{matrix}

The set A is the standardised tsccd with v = v′. We denote the first two elements of the last block of A as x and y respectively; here x = 2 and y = 6. The set B successively introduces the elements v′ + 1, v′ + 2, v′ + 3, v′ + 4, y and v′ + 2 into rows 3, 2, 3, 2, 1 and 3 respectively. The set C introduces into row 1 all elements from {1, 2, ..., v′} except x and y. The set D is a single block with element v′ + 1 in row 3. The set E mirrors set C, with elements v′ + 3 and v′ + 1 in rows 2 and 3 respectively. When the modified algorithm is used to produce a tsccd(7, 3), it produces the first design of Table 4 below.

In a standardised tsccd produced by this modified algorithm when v′ > 3, element v′ + 4 is transferred only once but each other element is transferred more than once. However, standardised tsccd(v, 3)’s with v > 7 (i.e. v ≥ 10), do not necessarily have exactly one element that is transferred just once.

If the starter tsccd for the modified algorithm has

T = T′, (s_{1}, s_{2}, s_{3}) = (s′_{1}, s′_{2}, s′_{3}),

then the tsccd that is generated has

T = T′ + 2v′ + 3, (s_{1}, s_{2}, s_{3}) = (s′_{1} + 2v′ − 4, s′_{2} + 3, s′_{3} + 4).

Thus the modified algorithm, used recursively, forces most transfers into the first row.

For a tsccd(6, 3) the only set of solutions of equations (4.2) is, as stated in Section 4 above, t_{1} = t_{2} = 3, whereas the equations (4.5) and inequality (4.6) have 2 solutions, namely

(p_{1}, p_{2}, p_{3}) = (9, 6, 0) and (10, 4, 1).  (6.1)

The tsccd(6, 3)’s (1.1) and (2.2) satisfy the second of these 2 solutions. Indeed, systematic trial of possibilities shows that there are no tsccd(6, 3)’s for the first solution, and that (1.1) and (2.2) are the only standardised tsccd(6, 3)’s.

For a tsccd(7, 3), the equations (4.2) have just 2 sets of solutions, namely

{(t_{1}, t_{2}, t_{3}) = (2, 5, 0), \atop (T 1)} {(3, 3, 1), \atop (T 2)}  (6.2)

whereas the equations (4.5) have 12 sets of solutions. Systematic trial of possibilities leads to the rejection of 7 of the 12, leaving us with

{(p_{1}, p_{2}, p_{3}, p_{4}) = (12, 9, 0, 0), \atop (P 1)} {(13, 7, 1, 0), \atop (P 2)} {(14, 5, 2, 0), \atop (P 3)} {(14, 6, 0, 1), \atop (P 4)} {(15, 4, 1, 1) \atop (P 5)}

(6.3)

Further systematic exploration of possibilities shows that, if a tsccd(7, 3) satisfies the first of the solutions (6.2), then it may satisfy any of the first 4 of the solutions (6.3), whereas if it satisfies the second of the solutions (6.2), then it may satisfy either the third or fifth of the solutions (6.3). Table 4 gives a standardised row-irregular tsccd(7, 3) for each of these 6 combinations. Systematic trial of possibilities (checked independently by computer search) has shown that no row-regular tsccd(7, 3) exists.

(T 1)  (t_{1}, t_{2}, t_{3}) = (2, 5, 0)
(P 1)  (p_{1}, p_{2}, p_{3}, p_{4}) = (12, 9, 0, 0)

1 …. 2 . 3 . . 2 . 5 . 7 …. 6 3 4 . 6 . . 5 . 4 .

(P 2)  (p_{1}, p_{2}, p_{3}, p_{4}) = (13, 7, 1, 0)

1 …. 2 . 3 . . 2 . 5 6 …. 7 . 3 4 . . 7 . 5 . . 4

(P 3)  (p_{1}, p_{2}, p_{3}, p_{4}) = (14, 5, 2, 0)

1 …. 3 . . 7 . 2 . . 6 7 . 4 . . 2 3 4 5 …. 6 . .

(P 4)  (p_{1}, p_{2}, p_{3}, p_{4}) = (14, 6, 0, 1)

* *

1 . . 3 . . 4 1 2 . 2 . 5 . . 7 …. 3 4 . . 6 …. 5

(T 2)  (t_{1}, t_{2}, t_{3}) = (3, 3, 1)
(P 3)  (p_{1}, p_{2}, p_{3}, p_{4}) = (14, 5, 2, 0)

1 …. 3 2 . 4 . 2 . 5 …. 6 . . 3 4 . 6 7 …. 3

(P 5)  (p_{1}, p_{2}, p_{3}, p_{4}) = (15, 4, 1, 1)

* * 1 . . 3 6 7 …. 2 . 5 …. 6 . . 3 4 …. 2 . 3 1

Table 4. Standardized row-irregular tsccd(7,3)’s for each of the 6 possible combinations of solutions of equations (4.2) and (4.5) (b = 10, T = 12). The start and end of each long run are indicated by asterisks.

For (v, k) = (10, 3) there are 14 sets of values of {t_{1}, t_{2}, t_{3}, t_{4}} that satisfy equations (4.2). These 14 sets are listed in Table 5, which updates a Table of Gower and Preece [2] by giving a single standardised tsccd(10, 3) for each set. The claim of Gower and Preece [2] (p. 86) that no tsccd(10, 3) can be constructed for either of the last two of the sets is thus false. Every tsccd(10,3) from Table 5 is row-irregular and has p_{6} = 0 ; a row-irregular tsccd(10, 3) with p_{6} = 1 is in Table 15 below. A row-regular tsccd(10, 3) is in Table 6.

1.  (t_{1}, t_{2}, t_{3}, t_{4}) = (0, 6, 4, 0), (p_{1}, p_{2}, …, p_{7}) = (27, 15, 3, 0, 0, 0, 0).
1 … 7 3 . . 4 9 . . 8 . . 7 9 … 10 .
2 . 5 … 8 … 2 . . 10 …. 4 . . 2
3 4 . 6 … 7 … 5 . . 1 . . 3 . 6 . .
2.  (t_{1}, t_{2}, t_{3}, t_{4}) = (1, 4, 5, 0), (p_{1}, p_{2}, …, p_{7}) = (29, 12, 3, 1, 0, 0, 0).
1 … 7 …. 3 … 2 . 4 . 8 . 1 7 .
2 . . 6 . . 2 1 4 . . 5 6 … 5 . 9 . . 3
3 4 5 . . 8 …. 9 … 10 . . . . . . .
3.  (t_{1}, t_{2}, t_{3}, t_{4}) = (2, 2, 6, 0), (p_{1}, p_{2}, …, p_{7}) = (31, 11, 2, 0, 0, 0, 1).
*  *
1 . . . . . . . 3 . . 5 . 8 . 2 …. 3 .
2 . 5 6 7 8 9 10 …. 7 … 6 10 . 5 . .
3 4 . . . . . . . 7 6 … 9 … 8 . . 9
4.  (t_{1}, t_{2}, t_{3}, t_{4}) = (3, 0, 7, 0), (p_{1}, p_{2}, …, p_{7}) = (33, 8, 2, 1, 0, 0, 1).
*  *
1 . . . . . . . 3 … 2 . 9 … 6 …
2 . 5 6 7 8 9 10 . . . . . . . 3 7 . . 8 2 .
3 4 . . . . . . . 5 6 7 . 8 … 5 … 9
5.  (t_{1}, t_{2}, t_{3}, t_{4}) = (0, 7, 2, 1), (p_{1}, p_{2}, …, p_{7}) = (29, 12, 3, 1, 0, 0, 0).
1 …. 8 … 3 7 10 … 2 …. 3 .
2 . 5 6 …. 4 … 1 . 5 … 10 . . 5
3 4 . . 7 . 3 9 . . . . . 8 . . 9 6 . 7 . .
6.  (t_{1}, t_{2}, t_{3}, t_{4}) = (1, 5, 3, 1), (p_{1}, p_{2}, …, p_{7}) = (32, 8, 3, 1, 1, 0, 0).
1 . . . . . 2 . . 3 9 10 . . . . . . . 3 . 7
2 . 5 6 … 5 . . . . . 3 9 . . . . . 8 .
3 4 . . 7 8 . . 7 … 6 . . 8 2 1 4 …
7.  (t_{1}, t_{2}, t_{3}, t_{4}) = (2, 3, 4, 1), (p_{1}, p_{2}, …, p_{7}) = (33, 5, 5, 2, 0, 0, 0).
1 …. 8 9 10 . . . . . . . 8 … 7 . .
2 . . 6 7 … 3 4 … 2 1 . 3 6 … 4
3 4 5 . . . . . . . 6 8 9 . . . . . 2 . 3 .
8.  (t_{1}, t_{2}, t_{3}, t_{4}) = (3, 1, 5, 1), (p_{1}, p_{2}, …, p_{7}) = (34, 6, 2, 1, 2, 0, 0).
1 . . . . . . . 4 5 6 3 . . 2 . 4 … 5 .
2 …. 8 9 10 . . . . . . . 9 … 3 . 8
3 4 5 6 7 . . . . . . . 9 8 … 5 6 …
9.  (t_{1}, t_{2}, t_{3}, t_{4}) = (0, 8, 0, 2), (p_{1}, p_{2}, …, p_{7}) = (30, 11, 2, 2, 0, 0, 0).
1 …. 8 … 3 7 10 … 5 . . . . . 7
2 . 5 6 …. 4 … 1 . 2 …. 10 . .
3 4 . . 7 . 3 9 . . . . . 8 . . 9 7 6 . 3 .

10.  (t_{1}, t_{2}, t_{3}, t_{4}) = (1, 6, 1, 2), (p_{1}, p_{2}, …, p_{7}) = (31, 9, 3, 2, 0, 0, 0).
1 . . . . . 2 . 7 3 9 . 10 . . . . . . . 7 .
2 . 5 6 … 5 . . . . . 3 . 8 7 9 ….
3 4 . . 7 8 . . . . . 6 . . 4 … 1 2 . 3
11.  (t_{1}, t_{2}, t_{3}, t_{4}) = (2, 4, 2, 2), (p_{1}, p_{2}, …, p_{7}) = (34, 8, 0, 1, 1, 0, 1).
*  *
1 . . . . . . . 3 . 2 . . 3 5 9 . . . . . 7
2 . 5 6 7 8 9 10 …. 7 … 8 . . . . .
3 4 . . . . . . . 5 . 6 . . . . . 2 3 5 10 .
12.  (t_{1}, t_{2}, t_{3}, t_{4}) = (3, 2, 3, 2), (p_{1}, p_{2}, …, p_{7}) = (31, 11, 0, 2, 1, 0, 0).
1 . . 6 . 3 8 9 10 . . . . . . . 2 3 1 . 5 .
2 . 5 . 7 . . . . . . . 3 . 6 …. 9 . .
3 4 . . . . . . . 2 1 5 . 9 . 8 . . . . . 2
13.  (t_{1}, t_{2}, t_{3}, t_{4}) = (2, 5, 0, 3), (p_{1}, p_{2}, …, p_{7}) = (31, 10, 2, 1, 1, 0, 0).
1 … 2 3 7 . . 9 . . 8 …. 7 … 4
2 . 5 …. 4 8 . 10 . . . . . . . 9 …
3 4 . 6 . . . . . . . 5 . 2 3 4 1 . . 2 3 .
14.  (t_{1}, t_{2}, t_{3}, t_{4}) = (3, 3, 1, 3), (p_{1}, p_{2}, …, p_{7}) = (34, 5, 3, 2, 1, 0, 0).
1 … 2 3 7 . . . . . . . 1 5 6 . . 2 3 .
2 . 5 . . . . . 1 9 . . . . . . . 4 8 …
3 4 . 6 … 8 . . 2 3 4 10 . . . . . . . 4

Table 5. Standardized row-irregular tsccd(10,3)’s for each of the 14 solutions (t_{1}, t_{2}, t_{3}, t_{4}) of equation (4.2) (b = 22, T = 24). The start and end of each long run are indicated by asterisks.

————————————————————————————

A procedure is available for obtaining a row-regular tsccd(v′ + 12, 3) from a row-regular tsccd(v′, 3). Thus the degenerate tsccd(3, 3), the row-regular tsccd(6, 3) given as (1.1), and the row-regular tsccd(v, 3)’s given in Table 6 for v = 10 and v = 19 are all that we need to obtain a row-regular tsccd(v, 3) for any v = 3, 6, 7, 10 (mod 12), v ≥ 6, except for v = 7. To describe this procedure, we use the letters A, B, ..., L to denote the elements v′ + 1, v′ + 2, ..., v′ + 12, and we use the following notation for certain sequences of elements:

x = 4 5 6 … v′ − 1 v′
y = 2 3 4 … v′ − 1 v′ A B
z = 1 2 3 … v′ − 1 v′ A B C D E

The procedure then consists merely of taking the unstandardised reverse of a standardised tsccd(v′, 3) and appending to it the following extra blocks:

v = 10 (b = 22, T = 24, T/k = 8) (t_{1}, t_{2}, …, t_{4}) = (0, 6, 4, 0),

(p_{1}, p_{2}, …, p_{7}) = (29, 12, 3, 1, 0, 0, 0).
1 … 7 3 . . 4 9 2 …. 4 . . 10 …
2 . 5 … 8 . . . . . 9 10 . . 9 … 7 8
3 4 . 6 … 7 … 5 . . 6 . . 3 . 1 . .

v = 19 (b = 85,T=87, T/k = 29) (t_{1}, t_{2}, …, t_{9}) = (3, 2, 3, 1, 3, 1, 3, 2, 1),

(p_{1}, p_{2}, …, p_{16}) = (147, 11, 1, 1, 2, 2, 2, 2, 3, 0, 0, 0, 0, 0, 0, 0).
1 . . . . . . . . . . . . . . . .  cont’d
2 . . . . . . . . 12 13 14 15 16 17 18 19  below
3 4 5 6 7 8 8 10 11 . . . . . . . .
3 4 5 6 7 8 9 10 . . . . . . . 2 . . . . . . cont’d
. . . . . . . . . . . . . . . . 12 13 14 15 16 17 below
. . . . . . . . 12 13 14 15 16 17 18 . . . . . . .
3 4 5 6 7 8 9 . . . . . . . . . . . . 3 4 5 6 7 cont’d
. . . . . . . . . . . . 3 4 5 6 7 8 . . . . . . below
. . . . . . . 12 13 14 15 16 . . . . . . 10 . . . . .
. . . . . . . . 12 . 16 . . 3 4 5 . 13 … 3
…. 3 4 5 6 . 13 . 14 . . . . . . 3 4 . .
12 13 14 15 . . . . . . . . 12 … 6 … 5 .

Table 6. Standardized row-regular tsccd(v,3)’s with v = 10, 19. ————————————————————————————-

A . . . . . 2 . 3 x 1 E C . . . . . G . . . . . z I . K . . . . . . B . . . . . F . . . . . G H . y 1 . . y F L . . . . . J . I . . . . 1 x F D . . . . . . . . . E … H … J . . F . . H . G z

This procedure could, of course, be reformulated to produce a standardised tsccd(v′ + 12, k) from a non-reversed standardised tsccd(v′, k), but we omit this here as the notational difficulties would merely obscure what is going on.

Apart from the row-regular tsccd(v, 3)’s obtainable by the procedure just described, we have made no attempt to obtain even a small selection of tsccd(v, 3)’s with v ≥ 11. We now merely give Table 7, which contains a single standardised row-irregular tsccd(v, 3) for each of v = 11, 14, 15, 18, 19. These examples are unobtainable by the modified algorithm described above for obtaining a tsccd(v′+4, 3) from a tsccd(v′, 3), and have strong similarities to one another in that the opening blocks of each were similarly generated; however, each solution had to be completed by trial and error. We hope that an algorithm can be found that will formalise and tidy the method of

v = 11 (b = 27, T = 29).

(t_{1}, t_{2}, …, t_{5}) = (0, 5, 5, 1, 0),

(s_{1}, s_{2}, s_{3}) = (10, 8, 11).

(p_{1}, p_{2}, …, p_{8}) = (37, 13, 2, 3, 0, 0, 0, 0).

1 …. 4 8 . . 4 . . 7 8 …. 7 . 10 … 3 . 11
2 … 7 … 9 . 10 … 11 . . . . . . 1 2 6 …
3 4 5 6 … 5 … 3 … 4 1 2 . 9 . . . . . 5 .

v = 14 (b = 45, T = 47) (t_{1}, t_{2}, …, t_{6}) = (3, 2, 3, 0, 5, 1), (s_{1}, s_{2}, s_{3}) = (12, 17, 18). (p_{1}, p_{2}, …, p_{11}) = (75, 7, 2, 1, 3, 1, 1, 1, 0, 0, 0).

1 . . . . . . . . . . . 3 4 5 6 . . . . . .  cont’d
2 …. 8 9 10 11 12 13 14 . . . . . . . . . .  below
3 4 5 6 7 . . . . . . . . . . . 8 9 10 11 12 13
2 . . . . . 3 4 5 . . . . . . . 3 … 4 11 .
. 8 9 10 11 12 . . . . . . . 3 4 … 10 … 8
. . . . . . . . . 8 9 10 11 . . 6 . 8 . 9 …

v = 15 (b = 52, T = 54) (t_{1}, t_{2}, …, t_{7}) = (3, 2, 3, 0, 5, 1, 1), (s_{1}, s_{2}, s_{3}) = (13, 19, 22). (p_{1}, p_{2}, …, p_{12}) = (88, 7, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0).

1 . . . . . . . . . . . . 3 4 5 6 . . . . . . . 2 cont’d
2 …. 8 9 10 11 12 13 14 15 . . . . . . . . . . . . below
3 4 5 6 7 . . . . . . . . . . . . 8 9 10 11 12 13 14 .
. . . . . . 3 4 5 . . . . . . . . 3 …. 4 8 12 . .
8 9 10 11 12 13 . . . . . . . . 3 4 …. 10 …. 9 .
. . . . . . . . . 8 9 10 11 12 . . 6 . 8 9 . 11 …. 8

Table 7. Standardized row-irregular tsccd(v,3)’s with v = 11, 14, 15, 18, 19

construction used for these examples. Amongst the similarities between the examples, we find that the quantities t_{1}, t_{2}, ..., t_{6} are the same for the designs with v = 14 and 15, and that the quantities t_{1}, t_{2}, ..., t_{8} are the same for the designs with v = 18 and 19.

v = 18 (b = 76, T = 78) (t_{1}, t_{2}, …, t_{8}) = (3, 2, 3, 1, 2, 2, 4, 1),

(s_{1}, s_{2}, s_{3}) = (20, 28, 30).
(p_{1}, p_{2}, …, p_{15}) = (132, 7, 3, 2, 1, 2, 3, 1, 1, 1, 0, 0, 0, 0, 0).
1 . . . . . . . . . . . . . . . 3 4 5 6 7 8 cont’d
2 . . . . . . 10 11 12 13 14 15 16 17 18 . . . . . . below
3 4 5 6 7 8 9 . . . . . . . . . . . . . . .
. . . . . . . . 2 . . . . . . . 3 4 5 6 7 . cont’d
. . . . . . . . . 10 11 12 13 14 15 16 . . . . . . below
10 11 12 13 14 15 16 17 . . . . . . . . . . . . . .
. . . . . . . . . . . 3 4 5 . . . . . . .  cont’d
. . . . . . 3 4 5 6 . . . . . . . . . 3 4  below
10 11 12 13 14 15 …. 8 … 10 11 12 13 14 . .
12 13 . . . . . 10 11 …
… 10 11 12 … 14 . 4
. . 3 … 15 … 10 .

v = 19 (b = 85, T = 87) (t_{1}, t_{2}, …, t_{9}) = (3, 2, 3, 1, 2, 2, 4, 1, 1),

(s_{1}, s_{2}, s_{3}) = (22, 32, 33).
(p_{1}, p_{2}, …, p_{16}) = (150, 6, 2, 3, 2, 1, 3, 1, 1, 1, 1, 0, 0, 0, 0, 0).
1 . . . . . . . . . . . . . . . . 3 4 5 6 7 8 cont’d
2 . . . . . . 10 11 12 13 14 15 16 17 18 19 . . . . . . below
3 4 5 6 7 8 9 . . . . . . . . . . . . . . . .
. . . . . . . . . 2 . . . . . . . . 3 4 5 6 7 cont’d
. . . . . . . . . . 10 11 12 13 14 15 16 17 . . . . . below
10 11 12 13 14 15 16 17 18 . . . . . . . . . . . . . .
. . . . . . . . . . . . 3 4 5 . . . . . . . . cont’d
. . . . . . . 3 4 5 6 . . . . . . . . . . 3 4 below
10 11 12 13 14 15 16 …. 8 … 10 11 12 13 14 15 . .
12 13 14 . . . . . . 12 11 10 ….
…. 10 11 12 13 …. 15 . 4 12
… 3 …. 16 …. 11 . .

Table 7. (continued)

(v, k) = (12, 4), (15, 4) and (18, 4)

From (3.3), there is no tsccd(v, 4) for v = 6, 7, 9, 10. However, tsccd(12, 4)’s have been found and partially enumerated. Five of these, in standardised form, are given as designs A, B, C, D and E in Table 8. The values taken by (t_{1}, t_{2}, t_{3}) for A, B, C, D, E constitute all 5 sets of solutions to equations (4.2) for (v, k) = (12, 4). Each of designs D and E has a single persistent pair of elements.

Further standardised tsccd(12, 4)’s can be obtained as the reverses and as minor variants of the tsccd’s A, B, C, D and E. Two simple such variants are obtained by swapping the last two blocks of A and the last two blocks of E. Two other variants of E are obtained by taking the blocks 7, 8, 9 in the order 8, 7, 9 and in the order 8, 9, 7. Yet another variant of E is obtained by replacing the element 10 in blocks 15 and 19 by the element 11, and the element 11 in block 16 by the element 10. And so on.

The tsccd(12, 4)’s A to E in Table 8 have some special properties that can be used, as described in Section 8 below, to construct tsccd(v, 4)’s with v = 12 + 9i (i = 1, 2, ...) or 13 + 9i (i = 0, 1, 2, ...). To recognise these properties we must, for a particular tsccd(v, k), consider first the ‘unchanged subsets’ of S, each of these being the (k − 1)-subset of elements that survives from one block to the next. In A, the subset {1, 2, 3} survives from block 1 to block 2, the subset {1, 2, 5} survives from block 2 to block 3, and so on. We shall say that an unchanged subset is ‘at location i’ of a tsccd if it is the (k − 1)-subset that survives from block i to block i + 1. Thus the unchanged subsets for A are

{1, 2, 3} at location 1,

{1, 2, 5} at locations 2, 3 and 4, {1, 8, 5} at location 5, etc.

In particular, these unchanged subsets, with corresponding locations, include

{1, 2, 3} (location 1),  {9, 8, 5}  (location 6),

{4, 7, 6} (location 11), {10, 11, 12} (location 19).

These 4 unchanged subsets yield a partition {1, 2, 3; 9, 8, 5; 4, 7, 6; 10, 11, 12} of S; the locations are indicated in Table 8 by arrowheads ˆ . Another

A:  (t_{1}, t_{2}, t_{3}) = (0, 12, 0)

(s_{1}, s_{2}, s_{3}, s_{4}) = (6, 6, 6, 6), (p_{1}, p_{2}, …, p_{8}) = (35, 14, 9, 4, 4, 0, 0, 0),

1 . . . . . 4 . . . . . 3 …. 2 . 5  1
2 …. 9 . . 10 11 . 12 … 10 ….  .
3 . 6 7 8 . . . . . 7 . . . . . 11 …  .
4 5 . . . . . 6 . . . . . 8 9 … 12 .  .
∧ ∧ ∧ ∧
B:  (t_{1}, t_{2}, t_{3}) = (1, 10, 1)

(s_{1}, s_{2}, s_{3}, s_{4}) = (6, 6, 6, 6), (p_{1}, p_{2}, …, p_{8}) = (39, 12, 4, 4, 7, 0, 0, 0),

1 . . . . . 4 . . . . . 3 …. 5 1 2  .
2 …. 9 . . 10 11 . 12 . . . . . . . .  9
3 . 6 7 8 . . . . . 7 . . . . . 11 …  .
4 5 . . . . . 6 . . . . . 8 9 10 ….  .
∧ ∧ ∧ ∧
C:  (t_{1}, t_{2}, t_{3}) = (2, 8, 2)

(s_{1}, s_{2}, s_{3}, s_{4}) = (6, 6, 6, 6), (p_{1}, p_{2}, …, p_{8}) = (39, 11, 7, 2, 6, 1, 0, 0),

1 . . . . . 3 5 . . . . . 8 9 10 ….  .
2 …. 9 . . 10 11 . 12 . . . . . . . .  9
3 . . 7 . . . . . . . . 6 …. 1 3 2  .
4 5 6 . 8 . . . . . 4 . . . . . 11 …  .
∧ ∧ ∧ ∧
D:  (t_{1}, t_{2}, t_{3}) = (3, 6, 3)

(s_{1}, s_{2}, s_{3}, s_{4}) = (5, 6, 7, 6), (p_{1}, p_{2}, …, p_{8}) = (37, 15, 4, 6, 3, 0, 0, 1),

*  *
1 . . . . . . . . 4 . 2 8 . . . . . 6 .  .
2 . . 7 8 9 . . . . . . . . 10 . . . . .  3
3 . 6 … 10 11 12 …. 3 . 11 ….  .
4 5 . . . . . . . . 7 . . . . . 2 4 . 12  .
∧ ∧ ∧ ∧
E:  (t_{1}, t_{2}, t_{3}) = (4, 4, 4)

(s_{1}, s_{2}, s_{3}, s_{4}) = (5, 7, 4, 8), (p_{1}, p_{2}, …, p_{8}) = (39, 10, 11, 1, 2, 2, 0, 1),

*  *
1 … 8 9 . . . . . . . . 10 11 ….  .
2 . . 7 . . 4 10 11 12 . . . . . . . . 10 .  .
3 . 6 . . . . . . . . 8 . . . . . 7 . .  .
4 5 . . . . . . . . 3 . 2 1 . . 4 . . 3  2
∧  ∧  ∧  ∧

Table 8. Standardized tsccd(12,4)’s for each of the 5 solutions of equations (4.2) (b = 21, T = 24). In each tsccd, the arrowheads indicate an expansion set of locations; the start and end of each long run are indicated by asterisks. such partition is {1, 2, 5; 4, 8, 6; 3, 12, 7; 10, 11, 9}, whose subsets occur as unchanged subsets of A at locations 2, 8, 13 and 17 respectively.

We also need the concept of an ‘end-subset’ of a tsccd(v, k), this being any (k−1)-subset of elements in the first or last block of a tsccd(v, k), i.e. ‘at location 0’ or ‘at location b’ respectively. In design A from Table 8, {1, 2, 3} and {10, 11, 12} are end-subsets (at locations 0 and 21 respectively) as well as unchanged subsets (at locations 1 and 20 respectively).

Design A from Table 8 is thus remarkable in (a) being both elementregular and row-regular and (b) having each of the following properties:

U1 The set S can be partitioned into v/(k − 1) unchanged subsets;

U2 The set S can be partitioned into an end subset and [v/(k − 1)]-1 unchanged subsets;

U3 The set S can be partitioned into 2 end subsets and [v/(k − 1)]-2 unchanged subsets.

Also, each of designs B to E has at least one of the properties U1, U2, U3; for each of these designs, Table 8 again uses arrowheads to indicate a corresponding set of locations of S-partitioning subsets of S.

In general, if a tsccd(v, k) has a set L of v/(k −1) locations, not including locations 0 and b, whose unchanged subsets partition S, then L will be called an ‘inner expansion set of locations’. If a tsccd(v, k) has a set L^{∗} of v/(k − 1) locations, including at least one of 0 and b, with end/unchanged subsets that partition S, then L^{∗} will be called an ‘outer expansion set of locations’. Each of designs A to E from Table 8 has an outer expansion set of locations, and so can be used for any of the constructions in Section 8 below; these constructions enable us to obtain tsccd’s with k = 4 and v = 13, 16, 19, ....

A tsccd(12, 4) that is neither element-regular nor row-regular nor satisfies any of the properties U1, U2, U3 is design X from Table 10.

Designs A, D and E of Table 8 were discovered with paper and pencil, but the row-regular designs B and C and the row-irregular design X of Table 10 were generated by computer. A program was written to try to grow standardised tsccd(12, 4)’s from a ‘seed’, i.e. from a sequence of blocks that legally could be the first c blocks of a tsccd(12, 4). The program seeks to grow the c blocks up to 21 blocks. Blocks were progressively removed from the end of design A and the program was run with the curtailed tsccd to see if any new tsccd(12, 4)’s were produced. Using the first 15 columns of design A, the new program found design B. However, using fewer columns, the amount of computation proved impractical despite efficient backtracking. The program was therefore modified to search only part of the search space. Using the first 12 columns of A, the new program found design C. (The program also generated over 1000 standardised tsccd(12, 4)’s from the seed

1 1 2 2 3 3 4 5

but it did not thereby grow any tsccd(12, 4)’s with (t_{1}, t_{2}, t_{3}) = (0, 12, 0) or (1, 10, 1).)

The tsccd(12, 4)’s A, B, C, D, E and X all have p_{8} = 0 or 1 , i.e. they have no persistent pair or just one persistent pair. Two tsccd(12,4)’s with p_{8} = 2, i.e. with 2 persistent pairs, are given in Table 9.

————————————————————————————

a:  (t_{1}, t_{2}, t_{3}) = (4, 4, 4),
(s_{1}, s_{2}, s_{3}, s_{4}) = (6, 8, 5, 5),
(p_{1}, p_{2}, …, p_{8}) = (35, 17, 8, 3, 1, 0, 0, 2).
* * *
1 . . . . . . . . 4 . . 2 3 6 …. 7 .
2 . . 7 . 9 10 . 12 . . . . . . . . 4 3 . .
3 . 6 . 8 . . 11 . . . . . . . . 10 … 2
4 5 . . . . . . . . 7 8 … 9 . . . . .
∧ ∧ ∧ ∧
b:  (t_{1}, t_{2}, t_{3}) = (4, 4, 4),
(s_{1}, s_{2}, s_{3}, s_{4}) = (7, 7, 5, 5),
(p_{1}, p_{2}, …, p_{8}) = (33, 20, 8, 2, 1, 0, 0, 2).
* * * *
1 . . . . . . . . 4 . . 3 6 2 … 3 . 4
2 . . 7 . 9 10 . 12 . . . . . . . . 7 . 6 .
3 . 6 . 8 . . 11 . . . . . . . . 10 ….
4 5 . . . . . . . . 7 8 … 9 . . . . .
∧  ∧  ∧  ∧

Table 9. Two standardized row-irregular tsccd(12,4)’s having p_{8} = 2. In each tsccd, the arrowheads indicate an outer expansion set of locations; the start and end of the long run are indicated by asterisks.

—————————————————————————————-

X:  (t_{1}, t_{2}, t_{3}) = (2, 8, 2),
(s_{1}, s_{2}, s_{3}, s_{4}) = (5, 4, 9, 6),
(p_{1}, p_{2}, …, p_{8}) = (41, 9, 7, 2, 4, 3, 0, 0).
1 . . . . . 4 . . 10 3 …. 11 . . . . .
2 …. 9 . . . . . 11 12 . . . . . . . .
3 . 6 7 8 . . . . . . . . 6 . . 1 4 5 2 .
4 5 . . . . . 6 7 . . . . . 10 . . . . . 9
Y:  (t_{1}, t_{2}, t_{3}) = (4, 4, 4),
(s_{1}, s_{2}, s_{3}, s_{4}) = (5, 5, 6, 8),
(p_{1}, p_{2}, …, p_{8}) = (37, 12, 11, 3, 1, 0, 1, 1).
*  *
1 . . . . . 3 10 . 11 . . . . . . . . 4 . .
2 … 8 . . . . . . . . 9 10 …. 5 .
3 . . 7 . . . . . . . . 2 . . 1 3 6 …
4 5 6 . . 9 . . 5 . 4 12 . . . . . . . . 9
∧  ∧  ∧  ∧

Table 10. Two contrasting standardized row-irregular tsccd(12,4)’s. The first has no inner or outer expansion set of locations, and no long run. The second has many expansion sets of locations (one of these sets being indicated by arrowheads) and also a long run (the start and end of which are indicated by asterisks).

The same program was used to find a tsccd(15, 4) and a tsccd(18, 4). Some initial blocks of the tsccd(12, 4) given as design Y in Table 10 proved to be a fertile seed for finding a tsccd(15, 4). Design Y has features suggesting that this approach might succeed, namely:

(i) It has unusually many ways in which 4 unchanged subsets that partition S can be selected.

(ii) It has a persistent pair of elements, namely (7, 8), and the long run for this pair occurs in 8 early blocks (though not as early as the long runs in designs D and E of Table 8).

(iii) As in designs A, B and C of Table 8, the final element to appear, namely 12, first occurs late in the design.

These gave hope that the program might grow the first c blocks (c ≥ 11) to the 34 blocks of a tsccd(15, 4) and that the persistent pair might occur in an unchanged subset of the result, perhaps even in one of 5 unchanged or end subsets partitioning S. The hope was fulfilled. With c = 12, the program succeeded in finding a large number of tsccd(15, 4)’s, many of which are trivial variants of each other obtained by permuting the order of the blocks. The first tsccd(15, 4) that it constructed is reproduced in Table 11. The table shows that this tsccd(15, 4) satisfies properties U2 and U3 and has unchanged/end subsets that partition S as {1, 2, 3; 7, 8, 11; 6, 10, 15; 12, 13, 14; 4, 5, 9}; a corresponding outer expansion set of locations is indicated in Table 11 by arrowheads.

———————————————————————————

(t_{1}, t_{2}, t_{3}, t_{4}) = (4, 3, 5, 3),

(s_{1}, s_{2}, s_{3}, s_{4}) = (7, 7, 8, 15),
(p_{1}, p_{2}, …, p_{11}) = (66, 16, 11, 4, 1, 2, 3, 1, 0, 0, 1).
*  *
1 . . . . . 3 10 . 11 . . . . . . . cont’d
2 … 8 . . . . . . . . . . . 9 below
3 . . 7 . . . . . . . . . . . 2 .
4 5 6 . . 9 . . 5 . 4 12 13 14 15 . .
∧  ∧
…. 4 . . 5 14 . . . . . . . .
10 …. 12 . . . . . . . . 6 . 4
. 1 3 6 . . 13 . . . . . . . . 5 .
. . . . . . . . . 1 2 3 10 9 …
∧  ∧  ∧

Table 11. A standardized tsccd(15,4) (b = 34, T = 37). The arrowheads indicate an outer expansion set of locations; the start and end of the long run are indicated by asterisks.

——————————————————————————————

The seed that grew to a tsccd(15, 4) did not work for (v, k) = (18, 4), nor did various seeds constructed from tsccd(15, 4)’s and tsccd(16, 4)’s. However, a pattern can almost be detected in the first 17 or so blocks of the last tsccd(13, 4) in Table 13; the outline of this pattern was copied to produce a seed with 28 blocks that eventually grew to the 50 blocks of a tsccd(18, 4). The growth was achieved in stages, using versions of the program that differed in the amount of search space that they tried. Without this staged approach, the amount of computation needed would not have been feasible. Table 12 gives the tsccd(18, 4) that was found. The table shows that this tsccd(18, 4) satisfies properties U1 and U2 and has unchanged/end subsets that partition S as {1, 2, 5; 4, 17, 18; 13, 14, 15; 7, 9, 16; 3, 6, 10; 8, 11, 12}; a corresponding outer expansion subset of locations in the tsccd(18, 4) is indicated in Table 12 by arrowheads.

(t_{1}, t_{2}, t_{3}, t_{4}, t_{5}) = (4, 3, 2, 8, 1), (s_{1}, s_{2}, s_{3}, s_{4}) = (11, 7, 19, 16), (p_{1}, p_{2}, …, p_{14}) = (102, 21, 14, 5, 2, 4, 0, 0, 1, 0, 1, 1, 0, 2).

*  *
1 . . . . . . . . . . . . . . 4 . . . . . 2 10 11 12
2 . . . . . . . . . . . 16 17 . . . . . . . . . . . cont’d
3 . 6 7 8 9 10 11 12 13 14 15 . . 18 . . . . . . . . . . below
4 5 . . . . . . . . . . . . . . 6 7 8 9 16 ….
∧  ∧

*

13 . . . . . . . . . . . 3 . 16 … 10 . . . . . 14
… 15 . . . . . . . . . 7 . . 6 … 12 ….
…. 4 … 6 . . 9 . . . . . 3 … 7 9 8 .
. 3 14 . . 10 11 12 . 7 8 …. 14 … 11 . . . . .
∧  ∧  ∧  ∧

Table 12. A standardized tsccd(18,4) (b = 50, T = 53). The arrowheads indicate an outer expansion set of locations; the start and end of the long run are indicated by asterisks.

8 Constructing tight single-change covering designs with v − 1 = n(k − 1)

A tsccd(v, k) for which v is a multiple of k − 1, say v′ = n(k − 1), may or may not have an inner expansion set of locations, and may or may not have an outer expansion set of locations. If it does indeed have an expansion set L, whether inner or outer, associated with a partition P of S, the tsccd(v′, k) can very simply be expanded into a tsccd(v′+1, k) by inserting an extra block at each location from L. Each such block contains the k − 1 elements of the end/unchanged subset associated with its location, each of these elements being in the same position as in the adjoining block(s), plus element v′ + 1 in the remaining position; if an end-subset is used, it must of course be a subset belonging to P. Thus, for example, the tsccd(12, 4) given as design C in Table 8 can be expanded into a tsccd(13, 4) by inserting the blocks

1 5 13 and 10
2 13 12  9
3 7 6  13
13 8 4  11

in locations 1, 9, 14 and 21 respectively. Similarly, the tsccd(6, 3) given as (1.1) can be expanded into a tsccd(7, 3) by inserting the blocks

7 1 and 7
2 7  6
3 4  5

in locations 0, 2 and 6 respectively.

Theorem 8.1. For any tsccd(v′′, k) with v′′ = n(k − 1) + 1 for some integer n that is greater than 2, we must have t_{i} = 0 for i > n, and t_{n} = 0 or 1, the value 1 being possible if and only if there exists a tsccd(v′′ − 1, k) that has an expansion set of locations.

Proof: If D is a tsccd(v′′, k) with v′′ = n(k − 1) + 1, then, from (4.1), it must have t_{i} = 0 for i > n. If D has t_{n} = m where m > 0, then D must contain an element x that is transferred n times; if the blocks containing x are removed from D, we are left with a tsccd(v′′ − 1, k) that has t_{n} = m − 1; but, from (4.1), any tsccd(v′′ − 1, k) must have t_{n} = 0. The rest of the proof is obvious.

For (v, k) = (13, 4), the equations (4.2) have 10 sets of solutions with t_{4} = 0 or 1, namely

(t_{1}, t_{2}, t_{3}, t_{4}) = (0, 11, 2, 0), (1, 9, 3, 0), (2, 7, 4, 0), (3, 5, 5, 0), (4, 3, 6, 0),

(0, 12, 0, 1), (1, 10, 1, 1), (2, 8, 2, 1), (3, 6, 3, 1), (4, 4, 4, 1).

It follows from Theorem 8.1 that, for each of the 5 sets of solutions with t_{4} = 1, a tsccd(13, 4) can be obtained by expanding a tsccd(12, 4) that has an expansion set of locations and that has the same values of (t_{1}, t_{2}, t_{3}); designs A through E of Table 8 are available for this purpose. Specimen standardised row-irregular tsccd(13, 4)’s for each of the 5 sets of solutions with t_{4} = 0 are in Table 13. A standardised row-regular tsccd(13, 4) with t_{4} = 0 is in Table 14.

The tsccd(15, 4) in Table 11 and the tsccd(18, 4) in Table 12 can be expanded, as described above, to give, respectively, a tsccd(16, 4) and a tsccd(19, 4). Furthermore, we show in the next Section that a tsccd(12+3i, k) with an expansion set of locations exists for any i = 0, 1, 2, ...; from this result and Theorem 8.1 it follows that there exists a tsccd(13 + 3i, 4) for any i = 0, 1, 2, ....

(t_{1}, t_{2}, t_{3}, t_{4}) = (0, 11, 2, 0), (s_{1}, s_{2}, s_{3}, s_{4}) = (6, 8, 8, 6), (p_{1}, p_{2}, …, p_{9}) = (43, 14, 11, 6, 2, 2, 0, 0, 0).

1 . . . . . . 4 . . . . . . 3 . . . . . 2 . . 1 5
2 …. 9 10 . . 11 12 . 7 . . . . . . 9 . . 12 . .
3 . 6 7 8 . . . . . . 9 . 13 … 12 11 . . . . . .
4 5 . . . . . . 6 . . . . . . 8 10 …. 13 …

(t_{1}, t_{2}, t_{3}, t_{4}) = (1, 9, 3, 0), (s_{1}, s_{2}, s_{3}, s_{4}) = (6, 7, 9, 6), (p_{1}, p_{2}, …, p_{9}) = (47, 12, 7, 5, 4, 3, 0, 0, 0).

1 . . . . . . 4 . . . . . . 3 . . . . . 1 5 2 . .
2 …. 9 10 . . 11 12 . . . . . . . . . . . . 10 .
3 . 6 7 8 . . . . . . 9 . 13 . 6 8 10 11 . . . . . .
4 5 . . . . . . 6 … 7 . . . . . . 12 …. 9

(t_{1}, t_{2}, t_{3}, t_{4}) = (2, 7, 4, 0), (s_{1}, s_{2}, s_{3}, s_{4}) = (5, 7, 11, 5), (p_{1}, p_{2}, …, p_{9}) = (47, 14, 6, 4, 2, 4, 1, 0, 0).

1 . . . . . . 4 . . . . . . 3 . . 10 11 . . . . . .
2 . . . . . 10 . . 6 11 12 . 13 . . . . . . . . . 10 .
3 . 6 7 8 9 . . . . . . . . . 7 6 … 1 5 2 . 3
4 5 . . . . . . 7 … 8 . . . . . . 12 . . . . .

(t_{1}, t_{2}, t_{3}, t_{4}) = (3, 5, 5, 0), (s_{1}, s_{2}, s_{3}, s_{4}) = (5, 4, 11, 8), (p_{1}, p_{2}, …, p_{9}) = (45, 19, 5, 2, 2, 3, 1, 0, 1).

*  *
1 . . . . . . 4 … 11 . 12 . . . . . . . . . 3 .
2 . . . . . 10 . . . . . . . . . 11 . . . . . 8 . .
3 . 6 7 8 9 . . . . . . . . . 2 . 1 4 5 6 … 13
4 5 . . . . . . 6 7 8 . 3 . 13 . . . . . . 7 …

(t_{1}, t_{2}, t_{3}, t_{4}) = (4, 3, 6, 0), (s_{1}, s_{2}, s_{3}, s_{4}) = (5, 5, 10, 8), (p_{1}, p_{2}, …, p_{9}) = (49, 10, 10, 5, 0, 1, 1, 0, 2).

* * *
1 . . . . . . . . . 4 … 2 8 . . . . . . 3 . .
2 . . . . . . 11 12 . . . . . . . . . 10 …. 11 .
3 . 6 7 8 9 10 . . 13 . . . . . . . . . 4 7 … 9
4 5 . . . . . . . . . 6 7 11 . . 3 9 … 6 …

Table 13. Specimen standardized row-irregular tsccd(13,4)’s with t_{4} = 0 (b = 25, T = 28). The start and end of each long run are indicated by asterisks.

(t_{1}, t_{2}, t_{3}, t_{4}) = (1, 9, 3, 0),
(p_{1}, p_{2}, …, p_{9}) = (47, 13, 8, 3, 2, 4, 1, 0, 0).
1 . . . . . . 4 . . . . . . 3 . . 5 1 2 . 7 …
2 . . . . . 10 . . 11 7 8 . 13 . . . . . . 10 ….
3 . 6 7 8 9 . . . . . . 12 . . . . . . . . . 8 . .
4 5 . . . . . . 6 . . . . . . 9 11 . . . . . . 13 3

Table 14. A standardized row-regular tsccd(13,4) with t_{4} = 0 (b = 25, T = 28, T/k = 7).

9 A recursive construction for tight singlechange covering designs

For a fixed value of k, let D be a standardised tsccd(v, k) and D′ be a standardised tsccd(n(k − 1), k) that has an outer expansion set of locations {L_{1} = 0, L_{2}, ..., L_{n}}. Relabel the elements {1, 2, ..., n(k−1)} of D′ so that the elements of the relevant end-subset for location 0 become, in any order, k −1 of the elements from the last block of D, and so that the other (n − 1)(k − 1) elements of D′, in their order of first appearance, become {v +1, v +2, ..., v + (n − 1)(k − 1)} respectively. Now, if necessary, re-order the rows of the relabelled D′ so that its first column is obtainable by a single element-change from the last column of D. Denote the elements of D, other than the k − 1 chosen elements from the last block, by e_{1}, e_{2}, ..., e_{v−k+1}. Now, in each of the locations L_{1}, L_{2}, ..., L_{n} of the rewritten D′, insert v − k + 1 extra blocks such that (i) the v − k + 3 successive blocks comprising the extra, preceding and successive blocks have the same unchanged subset throughout, and (ii) each of the elements e_{1}, e_{2}, ..., e_{v−k+1} is the transferred element in just one of the extra blocks, the ordering of these extra blocks being immaterial. Now append the augmented rewritten D′ to D, to obtain Dˆ , a standardised tsccd(v + (n − 1)(k − 1), k).

If D has an expansion set L of locations, then Dˆ has an expansion set Lˆ of locations, whose members include those of L; the remaining members of Lˆ can be taken to be the locations at the start of each set of v − k + 1 extra blocks.

To illustrate this construction, let v = 6, k = 3, n = 3. Let D and D′ be the following standardised tsccd(6, 3), which has an outer expansion set of locations {L_{1} = 0, L_{2} = 2, L_{3} = 6}:

∗  ∗
1 … 3 . 2
2 . 5 6 …
3 4 … 5 .
∧ ∧ ∧

The relevant end-subset for location 0 in D′ is {2,3}, and 2 elements from the last block of D are {2,5}. For illustration, we choose to relabel the elements 2 and 3 of D′ as 5 and 2 respectively. We therefore relabel the elements 1, 4, 5, 6 of D′ as 7, 8, 9, 10 respectively. Re-ordering the rows of D′ so that its first block is obtainable by a single change from the last block of D we have

2 8 … 9 .
7 … 2 . 5
5 . 9 10 …
∧  ∧  ∧

Inserting the extra blocks in locations 2 and 6 of this rewritten D′, and appending the augmented design to D, we obtain Dˆ as the standardised tsccd(10, 3) given in Table 15. This tsccd(10,3) has an outer expansion set of locations {0, 2, 6, 9, 17}, and is unlike any tsccd(10, 3) from Table 5 in having p_{6} = 1.

——————————————————————————-

(t_{1}, t_{2}, t_{3}, t_{4}) = (3, 1, 5, 1),
(p_{1}, p_{2}, …, p_{7}) = (34, 8, 1, 0, 0, 1, 1).
*  *
1 … 3 . 2 . 8 . . . . . . . 9 . . . . .
2 . 5 6 … 7 . . . . . . . 2 . 1 3 4 6 5
3 4 … 5 … 1 3 4 6 9 10 . . . . . . .
∧  ∧  ∧  ∧

Table 15. A standardized row-irregular tsccd(10,3) obtained by the recursive construction. The arrowheads indicate an outer expansion set of locations; the start and end of the long run are indicated by asterisks.

————————————————————————————

We have already seen (Tables 8, 9, 11 and 12) that, for each of the values v = 12, 15, 18, we have a tsccd(v, 4) that has an outer expansion set of locations. The recursive construction can therefore be used to obtain a tsccd(12 + 3i, 4) for any i = 1, 2, ....

k > 4

None is known. The smallest would be a tsccd(20, 5), and a search for such a design would be impractical using the methodology described above.

11 The complement of a tight single-change covering design

The ‘complement’ of a tsccd(v, k) P with b blocks can be defined as the block sequence P^{∗}, also comprising b blocks, such that each block of P^{∗} contains the elements of {1, 2, ..., v} that are absent from the corresponding block of P. For convenience, we again (i) write blocks as columns, (ii) take the sequence as running from left to right, and (iii) leave a block’s unchanged elements in the same positions as they had in the previous block. Thus, if element i displaces element j when block x + 1 of P is formed from block x of P, then element j displaces element i when block x + 1 of P^{∗} is formed from block x of P^{∗}.

In general, the complement of a tsccd(v, k) will not itself be a tsccd, even if v = 2k. For v = 2k, this contradicts an erroneous more general statement on pages 86-87 of Gower and Preece [2]. The point can be illustrated by the complement of tsccd(6, 3) (1.1), namely

\begin{matrix}∗4 & ∗3 & 3 & 3 & ∗1 & 1 & 1 \\ ∗5 & 5 & ∗2 & 2 & 2 & 2 & ∗3 \\ ∗6 & 6 & 6 & ∗5 & 5 & ∗4 & 4 \end{matrix}

Here, when element 5 is transferred into block 4, it is paired with element 3, as it was in block 2, so the sequence is not a tsccd; indeed, the elements 1 and 6 are not paired in any block of this sequence.

Only for (v, k) = (4, 2) must the complement of a tsccd be itself a tsccd, but the complement of a standardised tsccd(4, 2) is, of course, not itself standardised. Examination of the standardised tsccd’s (5.2) through (5.6) shows that none of the ten standardised tsccd(4, 2)’s is identical to its standardised complement.

References

[1] M. J. Colbourn and J. K. Johnstone, Twofold tiple systems with a minimal change property, Ars Combinatoria 18 (1983) 151-160.

[2] J. C. Gower and D. A. Preece, Generating successive incomplete blocks with each pair of elements in at least one block, J. Combin. Theory 12 (1972) 81-97.

[3] M. J. Garside, The best sub-set in multiple regression analysis, Applied Statistics 14 (1965) 196-200.

[4] D. H. Lawrence, Art and Morality, in “Phoenix - The posthumous Papers of D. H. Lawrence” (ed. E. D. McDonald), pp. 521-526, London, Heinemann (1936).

[5] J. A. Nelder, The efficient formation of a triangular array with restricted storage for data, Applied Statistics 18 (1969) 203-206.

[6] W. D. Wallis, J. L. Yucas and G.-H. Zhang, Single-change covering designs, Designs, Codes and Cryptography 3 (1993) 9-19.

[7] G.-H. Zhang, Some new bounds on single-change covering designs, SIAM J. Discrete Mathematics 7 (1994) 166-171.