A309344 - OEIS

%I #31 Sep 29 2024 06:24:26

%S 1,1,1,2,2,4,36,74

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

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

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

%H Brendan McKay, <a href="https://users.cecs.anu.edu.au/~bdm/data/latin.html">Combinatorial Data</a>.

%H Eduard I. Vatutin, <a href="https://evatutin.narod.ru/spectra/spectra_ls_transversals_all.png">Graphical representation of the spectra</a>.

%H Eduard I. Vatutin, Proving lists (<a href="http://evatutin.narod.ru/spectra/spectrum_ls_transversals_n1_1_item.txt">1</a>, <a href="http://evatutin.narod.ru/spectra/spectrum_ls_transversals_n2_1_item.txt">2</a>, <a href="http://evatutin.narod.ru/spectra/spectrum_ls_transversals_n3_1_item.txt">3</a>, <a href="http://evatutin.narod.ru/spectra/spectrum_ls_transversals_n4_2_items.txt">4</a>, <a href="http://evatutin.narod.ru/spectra/spectrum_ls_transversals_n5_2_items.txt">5</a>, <a href="http://evatutin.narod.ru/spectra/spectrum_ls_transversals_n6_4_items.txt">6</a>, <a href="http://evatutin.narod.ru/spectra/spectrum_ls_transversals_n7_36_items.txt">7</a>, <a href="http://evatutin.narod.ru/spectra/spectrum_ls_transversals_n8_74_items.txt">8</a>).

%H <a href="/index/La#Latin">Index entries for sequences related to Latin squares and rectangles</a>.

%e 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.

%o (MATLAB)

%o %This extracts entries from each column.  For an example, if

%o %A=[1 2 3 4; 5 6 7 8; 9 10 11 12; 13 14 15 16], and if list = (2, 1, 4),

%o %this code extracts the second element in the first column, the first

%o %element in the second column, and the fourth element in the third column.

%o function [output] = extract(matrix,list)

%o for i=1:length(list)

%o     output(i) = matrix(list(i),i);

%o end

%o end

%o %Searches matrix to find transversal and outputs the transversal.

%o function [output] = findtransversal(matrix)

%o n=length(matrix);

%o for i=1:n

%o     partialtransversal(i,1)=i;

%o end

%o for i=2:n

%o     newpartialtransversal=[];

%o     for j=1:length(partialtransversal)

%o         for k=1:n

%o             if (~ismember(k,partialtransversal(j,:)))&(~ismember(matrix(k,i),extract(matrix,partialtransversal(j,:))))

%o                 newpartialtransversal=[newpartialtransversal;[partialtransversal(j,:),k]];

%o             end

%o         end

%o     end

%o     partialtransversal=newpartialtransversal;

%o end

%o output=partialtransversal;

%o end

%o %Takes input of n^2 numbers with no spaces between them and converts it

%o %into an n by n matrix.

%o function [A] = tomatrix(input)

%o n=sqrt(floor(log10(input))+2);

%o for i=1:n^2

%o     temp(i)=mod(floor(input/(10^(i-1))),10);

%o end

%o for i=1:n

%o     for j=1:n

%o         A(i,j)=temp(n^2+1-(n*(i-1)+j));

%o     end

%o end

%o A=A+ones(n);

%o end

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

%K nonn,hard,more

%O 1,4

%A _Alvaro R. Belmonte_, _Eugene Fiorini_, _Peterson Lenard_, _Froylan Maldonado_, _Sabrina Traver_, _Wing Hong Tony Wong_, Jul 24 2019