ASYMPTOTIC ENUMERATION OF LATIN RECTANGLES

被引：36

作者：

GODSIL, CD

MCKAY, BD

机构：

[1] SIMON FRASER UNIV,BURNABY V5A 1S6,BC,CANADA

[2] AUSTRALIAN NATL UNIV,DEPT COMP SCI,CANBERRA,ACT 2601,AUSTRALIA

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 1990年 / 48卷 / 01期

基金：

加拿大自然科学与工程研究理事会;

关键词：

D O I：

10.1016/0095-8956(90)90128-M

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A k × n Latin rectangle is a k × n matrix with entries from {1,2, ..., n} such that no entry occurs more than once in any row or column. Equivalently, it is an ordered set of k disjoint perfect matchings of Kn,n. We prove that the number of k × n Latin rectangles is asymptotically (n!)( n(n-1)⋯(n-k+1) nkn(1- k n)- n 2e- k 2 as n → ∞ with k = o(n 6 7). This improves substantially on previous work by Erdo{combining double acute accent}s and Kaplansky, Yamamoto, and Stein. We also derive an asymptotic approximation to the generalised ménage numbers, and establish a number of results on entries in random Latin rectangles. © 1990.

引用

页码：19 / 44

页数：26