Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)

Counting $ 3$ by $ n$ Latin rectangles


Authors: K. P. Bogart and J. Q. Longyear
Journal: Proc. Amer. Math. Soc. 54 (1976), 463-467
MathSciNet review: 0389618
Full-text PDF Free Access

Abstract | References | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] K. P. Bogart, Closure relations and Möbius functions (submitted).
  • [2] Henry H. Crapo, Möbius inversion in lattices, Arch. Math. (Basel) 19 (1968), 595–607 (1969). MR 0245483 (39 #6791)
  • [3] C. Greene, Combinatorial geometry, Notes from the course given at N.S.F. Seminar in Combinatorics at Bowdoin College in 1971.
  • [4] John Riordan, An introduction to combinatorial analysis, Wiley Publications in Mathematical Statistics, John Wiley & Sons Inc., New York, 1958. MR 0096594 (20 #3077)
  • [5] 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 0174487 (30 #4688)


Additional Information

DOI: http://dx.doi.org/10.1090/S0002-9939-1976-0389618-9
PII: S 0002-9939(1976)0389618-9
Article copyright: © Copyright 1976 American Mathematical Society