A congruence connecting Latin rectangles and partial orthomorphisms

Douglas Stuart Stones, Ian Murray Wanless

Research output: Contribution to journalArticleResearchpeer-review

6 Citations (Scopus)

Abstract

A partial orthomorphism of Z(n) is an injective map sigma : S -> Z(n) such that S subset of Z(n) and sigma(i) - i not equivalent to sigma(j) - j (mod n) for distinct i, j is an element of S. We say s has deficit d if vertical bar S vertical bar = n - d. Let omega(n, d) be the number of partial orthomorphisms of Z(n) of deficit d. Let chi(n, d) be the number of partial orthomorphisms sigma of Z(n) of deficit d such that sigma(i) is not an element of 0, i for all i is an element of S. Then omega(n, d) = chi(n, d)n(2)/d(2) when 1 = k >= p + 1. In particular, this enables us to calculate some previously unknown congruences for R-n,R-n. We also develop techniques for computing omega(n, d) exactly. We show that for each a there exists mu(a) such that, on each congruence class modulo mu(a), omega(n, n - a) is determined by a polynomial of degree 2a in n. We give these polynomials for 1 infinity, for arbitrary fixed a.
Original languageEnglish
Pages (from-to)349 - 365
Number of pages17
JournalAnnals of Combinatorics
Volume16
Issue number2
DOIs
Publication statusPublished - 2012

Cite this