The many formulae for the number of Latin rectangles (Q986688): Difference between revisions

Summary: A \(k\times n\) Latin rectangle \(L\) is a \(k\times n\) 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 \(L_{k,n}\) be the number of \(k\times n\) Latin rectangles. We survey (a) the many combinatorial objects equivalent to Latin squares, (b) the known bounds on \(L_{k,n}\) and approximations for \(L_n\), (c) congruences satisfied by \(L_{k,n}\) and (d) the many published formulae for \(L_{k,n}\) and related numbers. We also describe in detail the method of Sade in finding \(L_{7,7}\), an important milestone in the enumeration of Latin squares, but which was privately published in French. Doyle's formula for \(L_{k,n}\) is given in a closed form and is used to compute previously unpublished values of \(L_{4,n}\), \(L_{5,n}\) and \(L_{6,n}\). We reproduce the three formulae for Lk,n by Fu that were published in Chinese. We give a formula for \(L_{k,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 \(L_{k,n}\) whose complexity lies in computing subgraphs of the rook's graph.