login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A309345 a(n) is the minimum number of transversals in Latin squares of order n that have at least 1 transversal. 0
3, 8, 3, 8, 3, 8 (list; graph; refs; listen; history; text; internal format)
OFFSET

3,1

COMMENTS

We find all the transversals of the main class representatives of order n Latin squares then find the one with the fewest transversals.

LINKS

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

Brendan McKay, Latin squares

EXAMPLE

For n = 5,they are 2 main classes of Latin squares. One of them has representative M = [[1,2,3,4,5],[2,4,1,5,3],[3,5,4,2,1],[4,1,5,3,2],[5,3,2,1,4]], and it has 3 transversals; {M(1,1), M(5,2), M(3,3), M(2,4), M(4,5)}, {M(2,1), M(5,2), M(4,3), M(1,4), M(3,5)}, and {M(4,1), M(5,2), M(2,3), M(3,4), M(1,5)}. The other main class representative [[1,2,3,4,5],[2,3,4,5,1],[3,4,5,1,2],[4,5,1,2,3],[5,1,2,3,4]] has 15 transversals. Therefore, the minimum number of transversals in order 5 Latin squares is 3, i.e., a(5) = 3.

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

Sequence in context: A333287 A117240 A151857 * A010706 A125025 A204998

Adjacent sequences:  A309342 A309343 A309344 * A309346 A309347 A309348

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 29 08:07 EDT 2020. Contains 334697 sequences. (Running on oeis4.)