A Congruence Connecting Latin Rectangles and Partial Orthomorphisms

Let χ(n,d) be the number of injective maps σ : S -> Zn \ {0} such that

(a) S is a subset of Zn and has cardinality |S|=n-d,

(b) σ(i) ≠ i for all i in S and

(c) σ(i)-i ≠ σ(j)-j mod n for distinct i,j in S.

Let Rk,n be the number of k × n reduced Latin rectangles. We show that

Rk,n = χ(p,n-p) (n-p)! (n-p-1)!2 Rk-p,n-p/(n-k)! mod p

when p is a prime and n ≥ k ≥ p+1. This allows us to calculate explicit congruences for Rn,n for n ≤ 31. We show that χ(n,d) is divisible by d2/gcd(n,d) when 1 ≤ d < n and establish several formulae for χ(n,n-a). In particular, for each a there exists μa such that, on each congruence class modulo μa, χ(n,n-a) is determined by a polynomial in n.