cp's OEIS Frontend

A309345 a(n) is the minimum number of transversals in Latin squares of order n that have at least 1 transversal.

%I A309345 #9 Feb 08 2020 13:31:11
%S A309345 3,8,3,8,3,8
%N A309345 a(n) is the minimum number of transversals in Latin squares of order n that have at least 1 transversal.
%C A309345 We find all the transversals of the main class representatives of order n Latin squares then find the one with the fewest transversals.
%H A309345 Brendan McKay, <a href="https://users.cecs.anu.edu.au/~bdm/data/latin.html">Latin squares</a>
%e A309345 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.
%o A309345 (MATLAB)
%o A309345 %This extracts entries from each column.  For an example, if
%o A309345 %A=[1 2 3 4; 5 6 7 8; 9 10 11 12; 13 14 15 16], and if list = (2, 1, 4),
%o A309345 %this code extracts the second element in the first column, the first
%o A309345 %element in the second column, and the fourth element in the third column.
%o A309345 function [output] = extract(matrix,list)
%o A309345 for i=1:length(list)
%o A309345     output(i) = matrix(list(i),i);
%o A309345 end
%o A309345 end
%o A309345 %Searches matrix to find transversal and outputs the transversal.
%o A309345 function [output] = findtransversal(matrix)
%o A309345 n=length(matrix);
%o A309345 for i=1:n
%o A309345     partialtransversal(i,1)=i;
%o A309345 end
%o A309345 for i=2:n
%o A309345     newpartialtransversal=[];
%o A309345     for j=1:length(partialtransversal)
%o A309345         for k=1:n
%o A309345             if (~ismember(k,partialtransversal(j,:)))&(~ismember(matrix(k,i),extract(matrix,partialtransversal(j,:))))
%o A309345                 newpartialtransversal=[newpartialtransversal;[partialtransversal(j,:),k]];
%o A309345             end
%o A309345         end
%o A309345     end
%o A309345     partialtransversal=newpartialtransversal;
%o A309345 end
%o A309345 output=partialtransversal;
%o A309345 end
%o A309345 %Takes input of n^2 numbers with no spaces between them and converts it
%o A309345 %into an n by n matrix.
%o A309345 function [A] = tomatrix(input)
%o A309345 n=sqrt(floor(log10(input))+2);
%o A309345 for i=1:n^2
%o A309345     temp(i)=mod(floor(input/(10^(i-1))),10);
%o A309345 end
%o A309345 for i=1:n
%o A309345     for j=1:n
%o A309345         A(i,j)=temp(n^2+1-(n*(i-1)+j));
%o A309345     end
%o A309345 end
%o A309345 A=A+ones(n);
%o A309345 end
%K A309345 nonn,hard,more
%O A309345 3,1
%A A309345 _Alvaro R. Belmonte_, _Eugene Fiorini_, _Peterson Lenard_, _Froylan Maldonado_, _Sabrina Traver_, _Wing Hong Tony Wong_, Jul 24 2019