tailieunhanh - Báo cáo toán học: "The many formulae for the number of Latin rectangles"

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: The many formulae for the number of Latin rectangles. | The many formulae for the number of Latin rectangles Douglas S. Stones School of Mathematical Sciences Monash University VIC 3800 Australia the_empty_element@yahoo. com Submitted Apr 29 2010 Accepted Jun 1 2010 Published Jun 14 2010 Mathematics Subject Classifications 05B15 00-02 05A05 01A05 Abstract A k X n Latin rectangle L is a kxn array with symbols from a set of cardinality n such that each row and each column contains only distinct symbols. If k n then L is a Latin square. Let Lkn be the number of k xn Latin rectangles. We survey a the many combinatorial objects equivalent to Latin squares b the known bounds on Lk n and approximations for Ln c congruences satisfied by Lk n and d the many published formulae for Lk n and related numbers. We also describe in detail the method of Sade in finding L77 an important milestone in the enumeration of Latin squares but which was privately published in French. Doyle s formula for Lk n is given in a closed form and is used to compute previously unpublished values of L4 n L5 n and L6 n. We reproduce the three formulae for Lk n by Fu that were published in Chinese. We give a formula for Lk n that contains as special cases formulae of a Fu b Shao and Wei and c McKay and Wanless. We also introduce a new equation for Lk n whose complexity lies in computing subgraphs of the rook s graph. 1 Introduction A k X n Latin rectangle is a k X n array L with symbols from Zn such that each row and each column contains only distinct symbols. If k n then L is a Latin square of order n. Let Lk n be the number of k X n Latin rectangles. As we will see the exact value of Lk n can be computed only for small values of k or n. The main aim of this paper is to provide a survey of the many formulae involving Lk n. The structure of this paper is as follows. In the remainder of this section we summarise the enumeration of Ln n for small n. In Section 2 we identify several combinatorial objects that Supported by the Monash Faculty of Science .

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN