Mathematical Construction Methods - Automatic Generation of Combinatorial Test Data - page 17

Chapter 2
Mathematical Construction Methods

Abstract This chapter presents some representative mathematical methods that are
commonly used in the construction of orthogonal arrays and covering arrays, as well
as some bounds on the size of such arrays.

As we mentioned in Chap. 1 , combinatorial testing is closely related to combinatorics,
which is a branch of mathematics. For an introduction to combinatorial theory and
combinatorial designs, see [ 3 , 5 ]. Mathematicians have obtained many results in this
field. Some of them can be used to construct combinatorial designs directly. Mathe-
matical methods, in particular product or recursive constructions, can be employed
to build large instances of orthogonal arrays and covering arrays. However, many of
these methods are applicable only in specific cases.

2.1 Mathematical Methods for Constructing
Orthogonal Arrays

As a combinatorial design with beautiful balancing property, the orthogonal array
has long been the interest of mathematicians. There are many mathematical results
about OA, either dealing with construction or proving its nonexistence given some
parameters. For simplicity, here we just review a few ones that are easy to understand.

2.1.1 Juxaposition

N , s 1 · N , s 1 · Theorem 2.1 If an OA ( s 2 ··· s k , t ) and an OA ( s 2 ··· s k , t ) both exist,

N
s 1

N
s 1

N + N ,( s 1 + s 1 ) ·

and = , then an OA ( s 2 ··· s k , t ) exists.

N , s 1 ·

(

s 2 ··· s k ,

)

The proof of this theorem is trivial. Given an OA t and an

N , s 1 · OA , we just need to relabel the elements in the first column of

one array, and put it underneath the other array. Obviously the resulting array is an
OA

( s 2 ··· s k , t )

N + N ,( s 1 + s 1 ) ·

( s 2 ··· s k , t ) .