Counting $3$ by $n$ Latin rectangles

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$.