4
$\begingroup$

Counting the number of latin squares is a difficult problem. I understand that the common used formula is $n!(n-1)!$ (the number or reduced latin squares). As seen here and in many other pages you can google.

But I was wondering if anyone can explain how this works? Is there a formula or method for calculating the number of reduced latin squares? Also how do the numbers $n!(n-1)!$ come about? It is because there are that many different combinations of numbers we can have in the first row and column?

$\endgroup$
  • 1
    $\begingroup$ $n!(n-1)!$ is easy: you permute columns to bring the top row into reduced form $1,2,\dots,n$. Then you permute rows $2,\dots,n$ to bring the first column into reduced form. There is no formula for the number of reduced squares. $\endgroup$ – almagest May 9 '16 at 12:38
  • 2
    $\begingroup$ Number of reduced Latin squares is tabulated, with lots of links, at oeis.org/A000315 $\endgroup$ – Gerry Myerson May 9 '16 at 13:01
  • $\begingroup$ There is an upper bound for $L_n$ attributed to H.J.Ryser: $(n!)^{2n}/n^{(n^2)}$. For $n=12...15$ there are reasonable estimates by McKay and Rogoyski. $\endgroup$ – Marcel Van de Vel May 4 '17 at 9:18
2
$\begingroup$

If $L_n$ is the number of Latin squares of order $n$, and $R_n$ is the number of reduced Latin squares of order $n$, then $$L_n = n!(n-1)! R_n.$$ The factor $n! (n-1)!$ comes about by counting:

  • Given any Latin square of order $n$, there is a unique permutation of the columns so that the first row is in order ($1,2,\ldots,n$), after which there is a unique permutation of the rows which fixes the first row so that the first column is in order.

  • In the other direction, given a reduced Latin square of order $n$, if we permute the rows except the first and permute the columns, we generate $n! (n-1)!$ distinct Latin squares of order $n$.

So, every reduced Latin square corresponds to $n! (n-1)!$ (not necessarily reduced) Latin squares, and every (not necessarily reduced) Latin square gives exactly one reduced Latin square.

As such, computing $L_n$ is effectively the same as computing $R_n$. While there are many formulae for the number of Latin squares, computationally they're only effective up to $n=11$. With the current best counting technique (Sade's method), as hardware improves, we might see $L_{12}$ in our lifetimes.

  • As far as I know, Sade's method is the only method which has been used for $n \geq 10$.

  • For orders $n \leq 9$, it is possible to generate main class representatives for each main class, computing their main class size using nauty, the sum of which equals $L_n$ (not an easy task for $n=9$ [I'm not sure if anyone has actually done it this way]; representatives can be downloaded on Brendan McKay's website for $n \leq 8$).

  • It possible to use Doyle's formula to compute the number of $6$-line Latin rectangles, which, for $7$ columns, is equal to $L_7$ (ref.).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.