# Counting the number of Latin squares

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?

• $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. – almagest May 9 '16 at 12:38
• Number of reduced Latin squares is tabulated, with lots of links, at oeis.org/A000315 – Gerry Myerson May 9 '16 at 13:01
• 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. – Marcel Van de Vel May 4 '17 at 9:18

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.).