<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 9 Issue 3" %>
On the Number of Latin Squares
Brendan D. McKay and Ian M. Wanless
Department of Computer Science, Australian National University, Canberra, ACT 0200, Australia
{bdm, imw}@cs.anu.edu.au
Annals of Combinatorics 9 (3) p.335-344 September, 2005
AMS Subject Classification: 05B15, 05C70, 15A15
Abstract:
We (1) determine the number of Latin rectangles with 11 columns and each possible number of rows, including the Latin squares of order 11, (2) answer some questions of Alter by showing that the number of reduced Latin squares of order n is divisible by f ! where f is a particular integer close to , (3) provide a formula for the number of Latin squares in terms of permanents of
(+1,-1)-matrices, (4) find the extremal values for the number of 1-factorisations of k-regular bipartite graphs on 2n vertices whenever , (5) show that the proportion of Latin squares with a non-trivial symmetry group tends quickly to zero as the order increases.
Keywords: Latin square, enumeration, 1-factorisation, permanent, regular bipartite graph

References:

1.R. Alter, How many Latin squares are there? Amer. Math. Monthly 82 (1975) 632--634.

2.S.E. Bammel and J. Rothstein, The number of 9×9 Latin squares, Discrete Math. 11 (1975) 93--95.

3.J.W. Brown, Enumeration of Latin squares with application to order 8, J. Combin. Theory 5 (1968) 177--184.

4.A. Cayley, On Latin squares, Oxf. Camb. Dublin Messenger Math. 19 (1890) 135--137.

5.L. Euler, Recherches sur une nouvelle espece de quarr¨¦s magiques, Verh. Zeeuwsch Gennot. Weten Vliss 9 (1782) 85--239.

6.M. Frolov, Sur les permutations carrés, J. de Math. spéc. IV (1890) 8--11, 25--30.

7. C.D. Godsil and B.D. McKay, Asymptotic enumeration of Latin rectangles, J. Combin. Theory Ser. B 48 (1990) 19--44.

8. P.A. MacMahon, Combinatory Analysis, Cambridge, 1915.

9. G.L. Mullen, How many i- j reduced Latin squares are there? Amer. Math. Monthly 85 (1978) 751--752.

10. B.D. McKay, Nauty graph isomorphic software, available at: http://cs.anu.edu.au/ ~bdm/nauty.

11. B.D. McKay, A. Meynert, and W. Myrvold, Small Latin squares, quasigroups and loops, submitted.

12. B.D. McKay and E. Rogoyski, Latin squares of order 10, Electron. J. Combin. 2 (1995) #N3 4 pp.

13. B.D. McKay and I.M. Wanless, Maximising the permanent of (0,1)-matrices and the number of extensions of Latin rectangles, Electron. J. Combin. 5 (1998) #R11 20 pp.

14. H.W. Norton, The 7×7 squares, Ann. Eugenics 9 (1939) 269--307.

15. A. Sade, Enumération des carrés latins. Application au 7eme ordre. Conjectures pour les ordres supérieurs, privately published, Marseille, 1948, 8 pp.

16. P.N. Saxena, A simplified method of enumerating Latin squares by MacMahon's differential operators; II. The 7×7 Latin squares, J. Indian Soc. Agricultural Statist. 3 (1951) 22--49.

17. J.Y. Shao and W.D. Wei, A formula for the number of Latin squares, Discrete Math. 110 (1992) 293--296.

18. G. Tarry, Le probleme des 36 officiers, Ass. Franc? Paris 29 (1900) 170--203.

19. J.H. van Lint and R.M. Wilson, A Course in Combinatorics, Cambridge University Press, 1992.

20. M.B.Wells, The number of Latin squares of order eight, J. Combin. Theory 3 (1967) 98--99.

21. M.B. Wells, Elements of Combinatorial Computing, Pergamon Press, Oxford-New York- Toronto, 1971.