The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. 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 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 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.

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