Automatic counting of generalized Latin rectangles and trapezoids. (English) Zbl 1512.05051
Summary: In this case study in “fully automated enumeration”, we illustrate how to take full advantage of symbolic computation by developing (what we call) ‘symbolic-dynamical-programming’ algorithms for computing many terms of ‘hard to compute sequences’, namely the number of Latin trapezoids, generalized derangements, and generalized three-rowed Latin rectangles. At the end, we also sketch the proof of a generalization of I. M. Gessel’s 1987 theorem
[Bull. Am. Math. Soc., New Ser. 16, 79–82 (1987; Zbl 0617.05015)] that says that for any number of rows, \(k\), the number of Latin rectangles with \(k\) rows and \(n\) columns is \(P\)-recursive in \(n\). Our algorithms are fully implemented in Maple and generated quite a few terms of such sequences.
MSC:
| 05A19 | Combinatorial identities, bijective combinatorics |
| 33F10 | Symbolic computation of special functions (Gosper and Zeilberger algorithms, etc.) |
Keywords:
inclusion-exclusion; Latin rectangle; Latin square; symbolic dynamic programming; weighted enumeration of tilingsCitations:
Zbl 0617.05015Online Encyclopedia of Integer Sequences:
Number of permutations s of {1,2,...,n} such that |s(i)-i|>3 for each i=1,2,...,n.References:
| [1] | K. P. Bogart and J. Q. Longyear, Counting 3 by n Latin rectangles, Proc. Amer. Math. Soc. 54 (1976), 463-467. · Zbl 0295.05004 |
| [2] | I. M. Gessel, Counting three-line Latin rectangles, Lect. Notes Math. 1234 (1986), Springer, 106-111. · Zbl 0612.05015 |
| [3] | I. M. Gessel, Counting Latin rectangles, Bull. Amer. Math. Soc. (N.S.) 16 (1987), 79-82. · Zbl 0617.05015 |
| [4] | I. Kaplansky, Solution of the problème des ménages, Bull. Amer. Math. Soc. 49 (1943), 784-785. [Reprinted in pp. 122-123, “Classical Papers in Combinatorics”, edited by Ira Gessel and Gian-Carlo Rota, Birkhauser, 1987] · Zbl 0060.02904 |
| [5] | J. Riordan, ’Introduction to Combinatorial Analysis’, Dover, originally published by John Wiley, 1958. · Zbl 0078.00805 |
| [6] | D. Zeilberger, A Holonomic systems approach to special functions identities, J. of Computational and Applied Math. 32 (1990), 321-368. · Zbl 0738.33001 |
| [7] | D. Zeilberger, Automatic CounTilings, The Personal Journal pf Shalosh B. Ekhad and Doron Zeilberger https://sites.math.rutgers.edu/ zeilberg/mamarim/mamarimhtml/tilings.html. |
| [8] | D. Zeilberger, Automatic Enumeration of Generalized Ménage Numbers, Séminaire Lotharingien de Com-binatoire 71 (2014), Article B71a. · Zbl 1297.05021 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
