tailieunhanh - Báo cáo toán học: "LATIN SQUARES OF ORDER"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: LATIN SQUARES OF ORDER. | LATIN SQUARES OF ORDER 10 Submitted August 20 1995 Accepted August 25 1995 revised Brendan D. McKay Department of Computer Science Australian National University Canberra ACT 0200 Australia bdm@. Eric Rogoyski Cadence Design Systems Inc. 555 River Oaks Parkway San Jose CA 95134 USA rogoyski@ Abstract. We describe two independent computations of the number of Latin squares of order 10. We also give counts of Latin rectangles with up to 10 columns and estimates of the number of Latin squares of orders up to 15. Mathematics Reviews Subject ClassiHcations 05B15 05-04 1. Introduction. A k X n Latin rectangle is a k X n matrix with entries from 1 2 . n such that the entries in each row and the entries in each column are distinct. A Latin square of order n is an n X n Latin rectangle. A Latin rectangle is said to be normalized if the Hrst row and Hrst column read 1 2 . n and 1 2 . k respectively. For example 2 1 2 3 4 5 6 3 231564 .3 5 4 6 2 1 . is a normalized 3 X 6 Latin rectangle. It is not hard to see that the total number of k X n Latin rectangles is n n 1 L k n n k where L k n is the number of normalized k X n Latin rectangles. The values of L n n for n 7 8 9 were found by Sade 9 Wells 11 and Bammel and Rothstein 2 respectively. A recurrence for L 3 n was found by Kerewala 5 and a complicated summation for L 4 n by Athreya Pranesachar and Singhi 1 . General formulae for L n n appear in 3 8 and 10 but do not appear useful for either exact or asymptotic computation. The asymptotic value of L k n for k o n6 7 was found by Godsil and McKay 4 . The numbers of distinct Latin squares under various symmetry operations are given to n 8 in 6 . The value of L 10 10 was computed independently by the two authors in 1991 and 1990 respectively using similar but not identical methods. In chronological order we will refer to these as the Hrst and second computations throughout this paper. They have much in common with each other and also with the method of 2