% Plain TeX; 4 pages
% Latin squares of order ten
% B. D. McKay and E. Rogoyski
% Draft of Aug 26.

\magnification=1095

\hsize=159truemm
\vsize=230truemm
\baselineskip=5.5truemm
\parindent=8truemm
\headline={\ifnum\pageno>1{\smcp the electronic journal of combinatorics
   2 (1995) \#N3\hfill\folio}\fi}

\font\bi=cmmib10
\font\smallrm=cmr9
\font\smallit=cmti9
\font\sevenit=cmti7
\font\smcp=cmcsc8
\scriptfont\itfam=\sevenit
\newfam\srmfam
\textfont\srmfam=\smallrm
\def\srm{\fam\srmfam\smallrm}

\def\strut{\vrule height 4.4truemm depth 1.4truemm width 0pt}
\def\blackslug{\hbox{\kern1pt\vrule height6pt width4pt depth1pt\kern1pt}}
\long\outer\def\proclaim#1. #2\par{\medbreak
    \noindent{\bf#1.\enspace}{\it #2}\par
    \ifdim\lastskip<\medskipamount\removelastskip\penalty55\medskip\fi}
\def\proof{\par\noindent{\bf Proof.\enspace}\rm}
\def\eop{\penalty 500\hbox{\quad\blackslug}\ifmmode\else\par
    \vskip4.5pt plus3pt minus2pt\fi}

\def\abs#1{{\mathopen|#1\mathclose|}}
\def\Aut{{\rm Aut}}
\def\({\bigl(}
\def\){\bigr)}

\outer\def\beginsection#1\par{\goodbreak\bigskip\vskip\parskip
 \message{#1}\leftline{\bf#1}\nobreak\smallskip\indent}

\mathchardef\Gammait"0100
\mathchardef\Deltait"0101
\mathchardef\Thetait"0102
\mathchardef\Lambdait"0103
\mathchardef\Xiit"0104
\mathchardef\Piit"0105
\mathchardef\Sigmait"0106
\mathchardef\Upsilonit"0107
\mathchardef\Phiit"0108
\mathchardef\Psiit"0109
\mathchardef\Omegait"010A
\let\e=\epsilon
\let\t=\theta
\fontdimen16\tensy=1\fontdimen17\tensy  % make subscripts level

\newbox\rmzero\setbox\rmzero=\hbox{\tenrm0}
\def\0{\kern1\wd\rmzero}

\centerline{\bf LATIN SQUARES OF ORDER 10}
\smallskip
\centerline{\rm Submitted: August 20, 1995; 
                Accepted: August 25, 1995 (revised)}
{\medskip
\baselineskip=0.82\baselineskip
\smallit\tabskip=10pt plus 50pt
$$\halign to 0.9\hsize{\hfil#\hfil&\hfil#\hfil\cr
\rm Brendan D. McKay&\rm Eric Rogoyski\cr
\noalign{\vskip 2pt}
Department of Computer Science&Cadence Design Systems, Inc.\cr
Australian National University&555 River Oaks Parkway\cr
Canberra, ACT 0200, Australia&San Jose, CA 95134, USA\cr
bdm@cs.anu.edu.au&rogoyski@cadence.com\cr}$$
}

%------------------------------------------------------------

\beginsection Abstract.

We describe two independent computations of the number 
of Latin squares of order 10.
We also give counts of Latin rectangles with up to 10 columns, and
estimates of the number of Latin squares of orders up to~15.
\smallskip
\noindent Mathematics Reviews Subject Classifications: 05B15, 05-04

\medskip

%----------------------------------------------------------------------

\beginsection 1. Introduction.

A $k\times n$ {\it Latin rectangle\/} is a $k\times n$ matrix with entries
from $\{1,2,\ldots,n\}$ such that the entries in each row and the
entries in each column are distinct.
A {\it Latin square\/} of order $n$ is an $n\times n$ Latin rectangle.

A Latin rectangle is said to be {\it normalized\/} if the first row
and first column read $[1,2,\ldots n]$ and $[1,2,\ldots,k]$, respectively.
For example, 
$$\left[\;\vcenter{\hbox{1 2 3 4 5 6}\hbox{2 3 1 5 6 4}\hbox{3 5 4 6 2 1}}
  \;\right]$$
is a normalized $3\times 6$ Latin rectangle.
It is not hard to see that the total number of $k\times n$ Latin
rectangles is $n!\,(n-1)!\,L(k,n)/(n-k)!\,$, where $L(k,n)$ is the number of 
normalized $k\times n$ Latin rectangles.

The values of $L(n,n)$ for $n=7,8,9$ were found by 
Sade~[9], Wells~[11], and Bammel and Rothstein~[2], respectively.
A recurrence for $L(3,n)$ was found by Kerewala~[5], and a complicated
summation for $L(4,n)$ by Athreya, Pranesachar and Singhi~[1].
General formulae for $L(n,n)$ appear in~[3], [8] and~[10], but
do not appear useful for either exact or asymptotic computation.
The asymptotic value of $L(k,n)$ for $k=o(n^{6/7})$ was found
by Godsil and McKay~[4].

The numbers of distinct Latin squares under various symmetry operations
are given to $n=8$ in~[6].

The value of $L(10,10)$ was computed independently by the two authors
in 1991 and 1990, respectively, using similar but not identical methods.
In chronological order, we will refer to these as the ``first'' 
and ``second'' computations throughout this paper.
They have much in common with each other, and also with the method 
of~[2], so we will describe them together.
We wish to thank Neil Sloane for introducing~us.

%------------------------------------------------------------------------

\beginsection 2.  Description of the computations.

Let $R$ be a $k\times n$ Latin rectangle.
We can define an associated $k$-regular bipartite graph $G=G(R)$ thus: 
$V(G) = C\cup S$, where $C=\{c_1,c_2,\ldots,c_n\}$ and 
$S=\{s_1,s_2,\ldots,s_n\}$ and
$E(G) = \{c_is_j\mid \hbox{ column $i$ contains symbol $j$}\}$.
We will call this graph the {\it template\/} of $R$.
Clearly, many Latin rectangles may have the same template; for example,
every Latin square of order $n$ has the complete bipartite graph
$K_{n,n}$ as its template.

A {\it one-factor\/} of a graph $G$ is a spanning regular subgraph of 
degree one.
A {\it one-factorization\/} of $G$ is a partition of $E(G)$ into
one-factors.
Clearly, the rows of a Latin rectangle $R$ correspond to the one-factors
in a one-factorization of $G(R)$.
For any template $G$, define $N(G)$ to be the number of one-factorizations
of $G$, or equivalently the number of normalised Latin squares with
template~$G$.
In forming this count, one-factorizations which differ only in the order
of the one-factors are not counted separately.
The value of $N(G)$ can be found from the following recursion:
$$N(G) = \sum_F N(G-F),\eqno{(1)}$$
where the sum is over one-factors $F$ of $G$ which contain some
fixed edge of~$G$.
The feasibility of this computation for $n=10$ is due to the fact
that $N(G)$ is an invariant of the isomorphism class of $G$.
Thus, we need only apply (1) to one member of each isomorphism class.
The challenge with efficiency is that the templates on the right need 
to be identified according to which isomorphism class they belong. 

The two computations differed in the types of isomorphism recognised
between two templates.  
In the first computation, isomorphisms fixing the sets $C$ and $S$
were used, while in the second the exchange of $C$ and $S$ was
also permitted.
In order to apply recursion (1), it is necessary to be able to
identify $G-F$ from amongst the templates for which the value of
$N(\,)$ is already known.
In the first computation, this was achieved by defining a canonical
labelling for templates.
Templates were stored in canonical form, and templates $G-F$ were
identified by converting them to canonical form.
In the second computation, a combinatorial invariant was devised such 
that no two templates had the same invariant.  
The invariant had two components.
The first component was a quickly-computed number depending on the
distribution of the cycles of length~4 in $G-F$.  
This proved sufficient to identify the great majority of templates
uniquely.
For those not uniquely identified, there was a second component formed
from a canonical labelling of the template, using the first author's
graph isomorphism program {\tt nauty}~[7].
The set of nonisomorphic templates was determined in advance using
{\tt nauty}.

The number of distinct templates under the two definitions of
equivalence for $n=10$ and
$k=1,\ldots,5$ were  1, 12, 1165, 121790, 601055 for the first
computation, and 1, 12, 725, 62616, 304496 for the second computation.

\topinsert
$$\vbox{\offinterlineskip\def\,{\kern1.5pt}
\tabskip=0pt\halign to 0.98\hsize
  {\vrule height3.9mm depth 1.4mm#\tabskip=0pt plus 10pt\relax
  &\hfil#&\hfil#&\hfil#&#\vrule
  &\hfil#&\hfil#&\hfil#&#\vrule
  &\hfil#&\hfil#&\hfil#&#\vrule
  \tabskip=0pt\cr
  \noalign{\hrule}
  &$n$&$k$&$L(k,n)\kern-5pt$&&$n$&$k$&$L(k,n)$\quad
      &&$n$&$k$&$L(k,n)$\qquad\quad&\cr
  \noalign{\hrule}
&1&1&1&&7&1&1&&9&1&1&\cr
&2&1&1&&&2&309&&&2&16687&\cr
&&2&1&&&3&35792&&&3&1034\,43808&\cr
&3&1&1&&&4&1293216&&&4&20\,76245\,60256&\cr
&&2&1&&&5&11270400&&&5&11268\,16430\,83776&\cr
&&3&1&&&6&16942080&&&6&12\,95260\,54043\,81184&\cr
&4&1&1&&&7&16942080&&&7&224\,38296\,79166\,91456&\cr
&&2&3&&8&1&1&&&8&377\,59757\,09642\,58816&\cr
&&3&4&&&2&2119&&&9&377\,59757\,09642\,58816&\cr
&&4&4&&&3&1673792&&10&1&1&\cr
&5&1&1&&&4&4209\,09504&&&2&1\,48329&\cr
&&2&11&&&5&27206\,658048&&&3&81549\,99232&\cr
&&3&46&&&6&33\,53901\,89568&&&4&14717\,45210\,59584&\cr
&&4&56&&&7&53\,52814\,01856&&&5&746\,98838\,30762\,86464&\cr
&&5&56&&&8&53\,52814\,01856&&&6&8\,70735\,40559\,10037\,09440&\cr
&6&1&1&&&&&&&7&1771\,44296\,98305\,41859\,22560&\cr
&&2&53&&&&&&&8&42920\,39421\,59185\,42730\,03520&\cr
&&3&1064&&&&&&&9&75807\,21483\,16013\,28114\,89280&\cr
&&4&6552&&&&&&&10&75807\,21483\,16013\,28114\,89280&\cr
&&5&9408&&&&&&&&&\cr
&&6&9408&&&&&&&&&\cr
\noalign{\hrule}}}$$
\smallskip
\centerline{\bf Table 1. \rm Numbers of normalized Latin rectangles.}
\bigskip
\endinsert

When $N(G)$ is known for each template $G$, the number of
normalized Latin rectangles can be determined.
In terms of the second computation, we have
$$L(k,n) = 2nk!\,(n-k)!\sum_G {N(G)\over\abs{\Aut(G)}},\eqno{(2)}$$
where the sum is over all templates of degree $k$, and
$\Aut(G)$ is the automorphism group of $G$.
The reason for (2) is that $2n!\,k!\,(n-k)!/\abs{\Aut(G)}$ is
the number of labellings of $G$ in which the neighbours of $c_1$
are $\{s_1,\ldots,s_k\}$, and $(n-1)!$ is removed to allow for
normalization of the first row.
In the case of $k=n$, equation (2) simplifies to 
$L(n,n)=N(K_{n,n})/(n-1)!\,$.

Each method requires a few days on a fast workstation.
The results are listed in Table~1.
To obtain the total number of Latin rectangles, not necessarily
normalized, multiply $L(k,n)$ by $n!\,(n-1)!/(n-k)!\,$.

%------------------------------------------------------------------------

\beginsection 3. Estimates.

For $n=11$ and $k=1,\ldots,5$, the numbers of distinct templates under the
weaker of our two definitions of isomorphism are 1, 14, 7454, 5582612, 
156473848.
Allowing interchange of $C$ and $S$ gains almost a factor of two, but
still the numbers are too large for $L(11,11)$ to be computable by our
method in a reasonable time.
However, we can find approximate values for higher order
using a probabilistic method.

Suppose we form a ``random'' normalized Latin square with rows 
$R_1,\ldots,R_n$ by this process: $R_1$ is the usual first row for a 
normalized square.
For $i=2,\ldots,n$, $R_i$ is chosen uniformly at random
from amongst those extensions of $[R_1,\ldots,R_{i-1}]$ which have
$i$ in the first position.
For $i=1,\ldots,n-1$, let $e_i$ be the total number of such extensions
of $[R_1,\ldots,R_{i-1}]$.
Then it is easy to show that $e_1e_2\cdots e_{n-1}$ is an unbiased
estimator of $L(n,n)$.
(This is an example of a method originally due to Knuth.)
For best experimental efficiency, we computed $e_i$ exactly for 
$i>n-8$ and by testing random permutations for smaller~$i$.

In Table~2, we present our estimates and the number of trials used
for each~$n$.
It is not possible to be precise about the accuracy, but we feel that
probably these numbers are correct to within one value of the least 
significant digit.

\midinsert
$$\vbox{\offinterlineskip\def\,{\kern1.5pt}
\tabskip=0pt\halign to 0.4\hsize
  {\vrule height3.9mm depth 1.4mm#\tabskip=0pt plus 10pt\relax
  &\hfil#\hfil&#\vrule&\hfil#\hfil&#\vrule&\hfil#\hfil&#\vrule
  \tabskip=0pt\cr
  \noalign{\hrule}
  &$n$&&{\it trials}&&$L(n,n)$&\cr
  \noalign{\hrule}
&11&&1000000&&$5.36\times10^{33}$&\cr
&12&&1100000&&$1.62\times10^{44}$&\cr
&13&&400000&&$2.51\times10^{56}$&\cr
&14&&200000&&$2.33\times10^{70}$&\cr
&15&&20000&&$1.5\times10^{86}$&\cr
\noalign{\hrule}}}$$
\smallskip
\centerline{\bf Table 2. \rm Estimates of $L(n,n)$ for larger $n$.}
%\bigskip
\endinsert

%------------------------------------------------------------------

\beginsection References.

\vskip-3mm
\frenchspacing

\item{[1]} K. B. Athreya, C. R. Pranesachar and N. M. Singhi,
  On the number of Latin rectangles and chromatic polynomial of
  $L(K_{r,s})$, {\it European J. Combinatorics}, {\bf 1} (1980) 9--17.

\item{[2]} S. E. Bammel and J. Rothstein, The number of $9\times9$
  Latin squares, {\it Discrete Math.}, {\bf 11} (1975) 93--95.

\item{[3]} I. Gessel, Counting Latin rectangles, {\it Bull. Amer.
  Math. Soc.}, {\bf 16} (1987) 79--83.

\item{[4]} C. D. Godsil and B. D. McKay, Asymptotic enumeration
  of Latin rectangles, {\it J. Combinatorial Theory, Ser. B},
  {\bf 48} (1990) 19--44.

\item{[5]} S. M. Kerewala, The enumeration of Latin rectangle of
  depth three by means of difference equation, {\it Bull. Calcutta
  Math. Soc.}, {\bf 33} (1941) 119--127.

\item{[6]} G. Kolesova, C. W. H. Lam and L. Thiel, On the number
  of $8\times8$ Latin squares, {\it J. Combinatorial Theory, Ser. A},
  {\bf 54} (1990) 143--148.

\item{[7]} B. D. McKay, nauty users' guide (version 1.5), Technical
  Report TR-CS-90-02, Computer Science Dept., Australian National 
  University, 1990.

\item{[8]} J. R. Nechvatal, Asymptotic enumeration of generalised
  Latin rectangles, {\it Utilitas Math.}, {\bf 20} (1981) 273--292.

\item{[9]} A. Sade, Enumeration des carr\'es latins. Application au
  $7^{\rm e}$ ordre. Conjecture pour les ordres sup\'erieurs,
  Marseille, 1948, 8pp.

\item{[10]} Jia-yu Shao and Wan-di Wei, A formula for the number
  of Latin squares, {\it Discrete Math.}, {\bf 110} (1992) 293--296.

\item{[11]} M. B. Wells, The number of Latin squares of order eight,
  {\it J. Combinatorial Theory}, {\bf 3} (1967) 98--99.

\bye




.
