The Asymptotic Number of Latin Rectangles
The Asymptotic Number of Latin Rectangles
复制标题
拉丁矩形的渐近数
DOI：
10.2307/2371834
复制
发表时间：
1946
影响因子：
1.7
通讯作者：
I. Kaplansky
中科院分区：
文献类型：
--
作者：
P. Erdös;I. Kaplansky
1. 介绍。列举n × k个拉丁矩形的问题由MacMahon[4]用他的运算方法正式解决。对于k = 3,[1],[2],[3]，[5]给出了更显式的解。虽然进一步的精确枚举似乎很困难，但一个简单的启发式猜想是，n × k个拉丁矩形的数量渐近于（-n!）“cexp(-)、CY)。由于一个错误，导致Jacob[2]否认k = 3时的这个猜想；但Kerawala[3]纠正了这个错误，然后将这个猜想验证为高度近似。k = 3•的第一个证明似乎是由Riordan[5]给出的。在本文中，我们不仅证明k固定（如It- >c）的猜想，而且证明k < (loon)的猜想。如下所示，对于前一种情况，我们可以给出一个相当短的证明。(1)对拉丁平方（k = n）方法的兴趣，(2)渐近级数的进一步项的出现，(4),(3)(log n) 3/ 1似乎是该方法的“自然边界”这一事实可能证明了额外的细节是合理的。（然而，我们认为实际的中断发生在k = n 1 /3。）2. 符号。一个n × k的拉丁矩形L是一个n行k列的数组，整数为1，•。每一行有N，每一列都是不同的整数。设N为将(k + 1)-st行添加到L以使增广数组成为拉丁矩形的方法数。我们使用筛选法（包含和排除的方法）来获得x的表达式。（k + 1）-st行的可能选项的总数，我们去掉在给定列中与L冲突的选项，对该列的所有选项求和，然后恢复在两个给定列中有冲突的选项，以此类推。结果可以写成，其中A，是在L中选择r个不同整数的方法的个数，同一列中没有两个整数。特别是A = 1, a1 = nk。为了估计更高的A r值，我们再次应用筛选法。*接收方式总数1945年11月30日。
1. Introduction. The problem of enumerating n by k Latin rectangles was solved formally by MacMahon [4] using his operational methods. For k = 3, more explicit solutions have been given in [1], [2], [3], and [5]. Wile further exact enumeration seems difficult, it is an easy heuristic conjecture that the number of n by k Latin rectangles is asymptotic to (-n!)'cexp (-),CY,). Because of an error, Jacob [2] was led to deny this conjecture for k = 3 ; but Kerawala [3] rectified the error and then verified the conjecture to a high degree of approximation. The first proof for k = 3 • appears to have been given by Riordan [5]. In this paper we shall prove the conjecture not only for k fixed (as It-> c) but for k < (loon) As indicated below, a considerably shorter proof could be given for the former case. The additional detail is perhaps justified by (1) the interest attached to an approach to Latin squares (k = n), (2) the emergence of further terms of an asymptotic series (4), (3) the fact that (log n) 3/ 1 appears to be a "natural boundary" of the method. (We believe however that the actual break occurs at k = n 1 /3 .) 2. Notation. An n by k Latin rectangle L is an array of n rows and k columns, with the integers 1, •. n in each row and all distinct integers in each column. Let N be the number of ways of adding a (k + 1)-st row to L so as to make the augmented array a Latin rectangle. We use the sieve method (method of inclusion and exclusion) to obtain an expression for X. From n !, the total number of possible choices for the (k + 1)-st row, we take away those having a clash with L in a given column-summed over all choices of that column, then reinstate those having clashes in two given columns, etc. The result can be written where A, is the number of ways of choosing r distinct integers in L, no two in the same column. In particular A, = 1, A 1 = nk. To estimate the higher values of A r we apply the sieve method again. The total number of ways of * Received November 30, 1945 .