Counting Latin rectangles

Abstract

A fc x n Latin rectangle is a fc x n array of numbers such that each row is a permutation of {1,2,..., n} and each column has distinct entries. The problem of counting Latin rectangles is of considerable interest. Explicit formulas for fc = 3 are fairly well known [1-3, 4, pp. 284-286 and 506-507, 5, 6, 9-11, 12, pp. 204-210]. Formulas for fc = 4 were found by Pranesachar et al. [1, 9] and a complicated formula for all fc was found by Nechvatal [8]. We give here a simple derivation of a formula similar to Nechvatal's. The formula implies that for fixed fc, the number of fc x n Latin rectangles satisfies a linear recurrence with polynomial coefficients. We use properties of the Möbius functions of partition lattices, as did Bogart and Longyear [2], Pranesachar et al. [1, 9], and Nechvatal [8], but in a somewhat different way. In order to state the formula, we first make some definitions. Let P be the set of partitions of k = {1,2,..., fc} and let S be the set of nonempty subsets of k. If ƒ is a function from P to the nonnegative integers N, and A is in S, then we set (ƒ, A) = Y1*BA f M ' wnere the sum ' ls °ver all partitions 7T of which.A is a block. We shall say that two functions f,g: P —> N are compatible if (f,A) = (g,A) for each A in S. THEOREM. The number of kxn Latin rectangles is where the sum is over all compatible pairs ƒ, g of functions from P to N satisfying J2„eP ƒ00 = J2*eP 000 = n ' PROOF. We first restate the problem in terms of bipartite graphs. Given a, kxn "rectangle " satisfying the row conditions, but with column entries not necessarily distinct, we may associate to it a bipartite graph with vertex sets P = {pi,P2î---,Pn} and Q = {91,^2,- • •><?n}, and with edges colored in fc colors. (We identify the set of colors with k.) If the rectangle has the entry /