TY - JOUR
T1 - A Congruence Connecting Latin Rectangles and Partial Orthomorphisms
AU - Stones, Douglas S.
AU - Wanless, Ian M.
PY - 2012/6
Y1 - 2012/6
N2 - 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 2/d 2 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.
AB - 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 2/d 2 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.
KW - Latin rectangle
KW - Latin square
KW - PORC function
KW - orthomorphism
KW - partial orthomorphism
UR - http://www.scopus.com/inward/record.url?scp=84862151164&partnerID=8YFLogxK
U2 - 10.1007/s00026-012-0137-6
DO - 10.1007/s00026-012-0137-6
M3 - Article
SN - 0218-0006
VL - 16
SP - 349
EP - 365
JO - Annals of Combinatorics
JF - Annals of Combinatorics
IS - 2
ER -