A Congruence Connecting Latin Rectangles and Partial Orthomorphisms

A partial orthomorphism of ℤ _n is an injective map σ: S →ℤ _n such that S ⊆ ℤ _n and σ(i)-i ≢ σ(j)- j (mod n) for distinct i, j ∈ S. We say σ has deficit d if{Pipe}S{Pipe} = n-d. Let ω(n, d) be the number of partial orthomorphisms of ℤ _n of deficit d. Let χ(n, d) be the number of partial orthomorphisms σ of ℤ _n of deficit d such that σ(i) ∉ {0, i} for all i ∈ S. Then ω(n, d) = χ(n, d)n ²/d ² when 1 ≤ d < n. Let R _k,n be the number of reduced k × n Latin rectangles. We show that, when p is a prime and n≥k≥ p+1. In particular, this enables us to calculate some previously unknown congruences for R _n,n. We also develop techniques for computing ω(n, d) exactly. We show that for each a there exists μ _a such that, on each congruence class modulo μ _a, ω(n, n-a) is determined by a polynomial of degree 2a in n. We give these polynomials for 1 ≤ a ≤ 6, and find an asymptotic formula for ω(n, n-a) as n → ∞, for arbitrary fixed a.