## Abstract

A k × n Latin rectangle on the symbols {1, 2, ..., n} is called reduced if the first row is (1, 2, ..., n) and the first column is (1, 2, ..., k)^{T}. Let R_{k, n} be the number of reduced k × n Latin rectangles and m = ⌊ n / 2 ⌋. We prove several results giving divisors of R_{k, n}. For example, (k - 1) ! divides R_{k, n} when k ≤ m and m! divides R_{k, n} when m < k ≤ n. We establish a recurrence which determines the congruence class of R_{k, n} (mod t) for a range of different t. We use this to show that R_{k, n} ≡ ((- 1)^{k - 1} (k - 1) !)^{n - 1}(mod n) . In particular, this means that if n is prime, then R_{k, n} ≡ 1(mod n) for 1 ≤ k ≤ n and if n is composite then R_{k, n} ≡ 0 (mod n) if and only if k is larger than the greatest prime divisor of n.

Original language | English |
---|---|

Pages (from-to) | 204-215 |

Number of pages | 12 |

Journal | Journal of Combinatorial Theory. Series A |

Volume | 117 |

Issue number | 2 |

DOIs | |

Publication status | Published - Feb 2010 |

Externally published | Yes |