Re: Combinatorial design?

From: KRamsay (kramsay_at_aol.com)
Date: 12/21/04 

Date: 21 Dec 2004 17:38:46 GMT

In article <1103643122.667962.250660@c13g2000cwb.googlegroups.com>, "Randy Poe"
<poespam-trap@yahoo.com> writes:
|I need to construct N x N blocks such that each number
|from 1 to N occurs exactly once in each row and each
|column. I have this vague memory that such constructions
|fall under the keyword mentioned in the subject line,
|but I don't have a combinatorics book at hand.

These are known as "latin squares". You should be able
to find quite a bit about them knowing what they're called.

|Are there well-known algorithms for constructing such
|arrangements?

I assume so.

|How many are there?

The number is Sloan's sequence A002860. One of the
citations there is to a 2004 paper couting how many of
order 11 there are. I'm assuming that there's no known
nice formula for how many there are.

Let X=Y=Z={1,...,N}. A latin square can be thought of as a
function f:XxY->Z, but a function can be thought
of as a special kind of relation, r on X, Y, and Z, which
brings out a symmetry in the definition: a relation r on
three sets of order N is a latin square if each pair in
XxY, XxZ, and YxZ occurs once, i.e., it's a function from
XxY to Z, from XxZ to Y, and YxZ to X. The sets X, Y, and
Z are called the constraints.

|One thought I had
|was to make the trivial one:
|
|1 2 3 ... N
|2 3 ...N 1
|3 ..N 1 2
|.
|.
|.
|N 1 2 ...N-1
|
|and them permute the rows and columns. Will that generate
|all possible legitimate arrangements?

No. Two are considered "isomorphic" if one can obtain one
from the other by permuting rows, columns, and symbols.
Thinking of it as a relation, two are isomorphic if one can
be obtained from the other by applying permutations to
the constraints. (The six permutations of the constraints
with each other are also sometimes relevant....)

Here's a latin square not isomorphic to the trivial one:

1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1.

The permutations needed to obtain one row from another in
your "trivial" one are the elements of a cyclic group of order
n. For this one, they form a group isomorphic to a Klein
4-group; each has order 2.

In general, the multiplication table of a group is a Latin square.
Not all latin squares are isomorphic to group tables, though.
For example,

 12345
 21453
 35124
 43512
 54231.

Keith Ramsay

Relevant Pages