Counting $3$ by $n$ Latin rectangles
HTML articles powered by AMS MathViewer
- by K. P. Bogart and J. Q. Longyear PDF
- Proc. Amer. Math. Soc. 54 (1976), 463-467 Request permission
Abstract:
A $k$ by $n$ rectangular array $A$ is called a Latin rectangle if all the integers $1,2, \ldots ,n$ appear in each row of $A$ and if $k$ distinct integers occur in each column of $A$. The number of $k$ by $n$ Latin rectangles is unknown for $k \geqslant 4$; Riordan has given a formula for the number of $3$ by $n$ rectangles in terms of the solutions of the derangement (or displacement) problem and the menage problem. In this paper we derive an elementary formula for the number of $3$ by $n$ Latin rectangles by using Möbius inversion. We include a table giving the approximate number of $3$ by $n$ Latin rectangles for $n \leqslant 20$. The table has exact values for $n \leqslant 11$.References
-
K. P. Bogart, Closure relations and Möbius functions (submitted).
- Henry H. Crapo, Möbius inversion in lattices, Arch. Math. (Basel) 19 (1968), 595–607 (1969). MR 245483, DOI 10.1007/BF01899388 C. Greene, Combinatorial geometry, Notes from the course given at N.S.F. Seminar in Combinatorics at Bowdoin College in 1971.
- John Riordan, An introduction to combinatorial analysis, Wiley Publications in Mathematical Statistics, John Wiley & Sons, Inc., New York; Chapman & Hall, Ltd., London, 1958. MR 0096594
- Gian-Carlo Rota, On the foundations of combinatorial theory. I. Theory of Möbius functions, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1964), 340–368 (1964). MR 174487, DOI 10.1007/BF00531932
Additional Information
- © Copyright 1976 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 54 (1976), 463-467
- DOI: https://doi.org/10.1090/S0002-9939-1976-0389618-9
- MathSciNet review: 0389618