Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 060.02808
Autor: Erdös, Paul; Kaplansky, Irving
Title: The asymptotic number of Latin rectangles. (In English)
Source: Amer. J. Math. 68, 230-236 (1946).
Review: (1): Die Verff. finden für die Anzahl 3Kn der lat. Rechtecke mit 3 Zeilen und n Spalten eine lineare Differenzengleichung 5. Ordnung und geben die numerischen Werte bis n = 15. Ein früheres Ergebnis von Jacob wird als irrig nachgewiesen. Dagegen bestätigt sich die Jacobsche Vermutung 3Kn ~ e-3 (n!)2 insofern, als der Limes 3Kn/(n!)2 existiert und in den ersten 5 Dezimalen mit e-3 übereinstimmt.
(2): Aufstellung einer expliziten Formel für 3 Kn, nämlich sumi {n \choose i} Di Dn-1 un-2i. Dabei bedeuten Di die Anzahl der Permutationen, die an keiner Stelle mit (1,...,n) übereinstimmen, und un die Anzahl derjenigen, die außerdem überall von (2,...,n,1) abweichen. Ferner Beweis für die Jacobsche Vermutung in vollem Umfange.
(3): Verallgemeinerung der Abschätzung 3Kn ~ e-3 (n!)2 mit der Bezeichnung f(n,k) = n!k Kn zu f(n,k) ~ (n!)k e-k(k-1)/2, gültig nicht nur für jedes feste k, sondern sogar für k < (log n)3/2-\epsilon. Dieselben Autoren geben auch die Anfangsglieder einer asymptotischen Entwicklung, die im Falle k = 3 die Form hat f(n,3) = (n!)3e-3 [1-n-1-(2n2)-1+···]. Die ersten 3 Glieder liefern bei n > 20 vier richtige Stellen mit erheblich geringerem Aufwand an Rechnung, als die genaue Bestimmung nach der Formel von Riordan erfordern würde.
Reviewer: R.Sprague
Classif.: * 05B15 Orthogonal arrays, etc.
05A18 Partitions of sets
Index Words: combinatorics
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag