TY - JOUR

T1 - A congruence connecting Latin rectangles and partial orthomorphisms

AU - Stones, Douglas Stuart

AU - Wanless, Ian Murray

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

UR - http://www.springerlink.com/content/261115716uqn78g5/

U2 - 10.1007/s00026-012-0137-6

DO - 10.1007/s00026-012-0137-6

M3 - Article

VL - 16

SP - 349

EP - 365

JO - Annals of Combinatorics

JF - Annals of Combinatorics

SN - 0218-0006

IS - 2

ER -