A309344 a(n) is the number of distinct numbers of transversals of order n Latin squares.

1, 1, 1, 2, 2, 4, 36, 74

Offset

1,4

Comments

We found all transversals in the main class Latin square representatives of order n.

These results are based upon work supported by the National Science Foundation under the grants numbered DMS-1852378 and DMS-1560019.

For all spectra of even orders all known values included in them are divisible by 2. For all spectra of orders n=4k+2 all known values included in the corresponding spectra are divisible by 4. - Eduard I. Vatutin, Mar 01 2025

a(9)>=407, a(10)>=463, a(11)>=6437, a(12)>=23715. - Eduard I. Vatutin, added Mar 01 2025, updated Aug 14 2025

Links

Table of n, a(n) for n=1..8.

Brendan McKay, Combinatorial Data.

Eduard I. Vatutin, Graphical representation of the spectra.

Eduard I. Vatutin, Proving lists (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12).

E. I. Vatutin, N. N. Nikitina, M. O. Manzuk, I. I. Kurochkin, A. M. Albertyan, On the number of transversals in diagonal Latin squares of even orders (in Russian), Cloud and distributed computing systems, within the National supercomputing forum (NSCF - 2023). Pereslavl-Zalessky, 2023. pp. 101-105.

Eduard Vatutin, Jia Wei-Ting, Jun Chi Ma, Qiang Miao, Maxim Manzyuk, Natalia Kukushkina, Ilya Kurochkin, and Alexander Albertian, Construction of Intercalate Number Spectra in Latin Squares of Orders 18-28 Using Distributed Parallel Software Implementations, Supercomputing (RuSCDays 2025) 462-474. See references.

Index entries for sequences related to Latin squares and rectangles.

Example

For n=7, the number of transversals that an order 7 Latin square may have is 3, 7, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 36, 37, 41, 43, 45, 47, 55, 63, or 133. Hence there are 36 distinct numbers of transversals of order 7 Latin squares, so a(7)=36.

Prog

(MATLAB)
%This extracts entries from each column.  For an example, if
%A=[1 2 3 4; 5 6 7 8; 9 10 11 12; 13 14 15 16], and if list = (2, 1, 4),
%this code extracts the second element in the first column, the first
%element in the second column, and the fourth element in the third column.
function [output] = extract(matrix, list)
for i=1:length(list)
    output(i) = matrix(list(i), i);
end
end
%Searches matrix to find transversal and outputs the transversal.
function [output] = findtransversal(matrix)
n=length(matrix);
for i=1:n
    partialtransversal(i, 1)=i;
end
for i=2:n
    newpartialtransversal=[];
    for j=1:length(partialtransversal)
        for k=1:n
            if (~ismember(k, partialtransversal(j, :)))&(~ismember(matrix(k, i), extract(matrix, partialtransversal(j, :))))
                newpartialtransversal=[newpartialtransversal; [partialtransversal(j, :), k]];
            end
        end
    end
    partialtransversal=newpartialtransversal;
end
output=partialtransversal;
end
%Takes input of n^2 numbers with no spaces between them and converts it
%into an n by n matrix.
function [A] = tomatrix(input)
n=sqrt(floor(log10(input))+2);
for i=1:n^2
    temp(i)=mod(floor(input/(10^(i-1))), 10);
end
for i=1:n
    for j=1:n
        A(i, j)=temp(n^2+1-(n*(i-1)+j));
    end
end
A=A+ones(n);
end

Crossrefs

Cf. A003090, A090741 (maximum number), A091323 (minimum number), A301371, A308853, A309088, A344105 (version for diagonal Latin squares).

Sequence in context: A327011 A300361 A257617 * A257618 A088895 A257619

Adjacent sequences: A309341 A309342 A309343 * A309345 A309346 A309347

Keyword

nonn,hard,more

Author

Alvaro R. Belmonte, Eugene Fiorini, Peterson Lenard, Froylan Maldonado, Sabrina Traver, Wing Hong Tony Wong, Jul 24 2019

Status

approved