A Congruence Connecting Latin Rectangles and Partial Orthomorphisms

Douglas S. Stones, Ian M. Wanless

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)349-365
Number of pages17
JournalAnnals of Combinatorics
Volume16
Issue number2
DOIs
Publication statusPublished - Jun 2012
Externally publishedYes

Fingerprint

Dive into the research topics of 'A Congruence Connecting Latin Rectangles and Partial Orthomorphisms'. Together they form a unique fingerprint.

Cite this