Divisors of the number of Latin rectangles

A k by n Latin rectangle on the symbols {1, 2,...,n} is called reduced if the first row is (1,2,...,n) and the first column is (1,2,...,k)T. Let Rk,n be the number of k by n reduced Latin rectangles and m = floor(n/2). We prove several results giving divisors of Rk,n. For example, (k-1)! divides Rk,n when k ≤ m and m! divides Rk,n when m < k ≤ n. We establish a recurrence which determines the congruence of Rk,n mod t for a range of different t. We use this to show that Rk,n = ((-1)k-1(k-1)!)n-1 mod n. In particular, this means that if n is prime, then Rk,n = 1 mod n for 1 ≤ k ≤ n and if n is composite then Rk,n = 0 mod n if and only if k is greater than the largest prime divisor of n.

Click here to download the whole paper.