Enumerating partial Latin rectangles

Raúl M. Falcón¹ ; Rebecca J. Stones²

¹Universidad de Sevilla
²Nankai University

The electronic journal of combinatorics, Tome 27 (2020) no. 2

Résumé

This paper deals with different computational methods to enumerate the set $\mathrm{PLR}(r,s,n;m)$ of $r \times s$ partial Latin rectangles on $n$ symbols with $m$ non-empty cells. For fixed $r$, $s$, and $n$, we prove that the size of this set is given by a symmetric polynomial of degree $3m$, and we determine the leading terms (the monomials of degree $3m$ through $3m-9$) using inclusion-exclusion. For $m \leqslant 13$, exact formulas for these symmetric polynomials are determined using a chromatic polynomial method. Adapting Sade's method for enumerating Latin squares, we compute the exact size of $\mathrm{PLR}(r,s,n;m)$, for all $r \leqslant s \leqslant n \leqslant 7$, and all $r \leqslant s \leqslant 6$ when $n=8$. Using an algebraic geometry method together with Burnside's Lemma, we enumerate isomorphism, isotopism, and main classes when $r \leqslant s \leqslant n \leqslant 6$. Numerical results have been cross-checked where possible.

Détail

DOI : 10.37236/9093

Classification : 05B15, 05A15
Mots-clés : partial Latin rectangle, isomorphism, isotopism, main class, species, inclusion-exclusion, chromatic polynomial, algebraic geometry