×

Permutations with forbidden patterns and polyominoes on a twisted cylinder of width 3. (English) Zbl 1263.05002

Summary: In a cubical lattice on a “twisted cylinder,” connectivity of cells form a spiral rather than a cylindrical shape. It was recently proven that for any fixed \(w\), the enumerating sequence for the number of polyominoes on the twisted cylinder of perimeter \(w\) satisfies a linear recursion. This recursion is determined by the minimal polynomial of the transfer matrix that models the growth of polyominoes on the cylinder.
In this paper we present a direct construction of the recursion for the case \(w=3\) polyominoes and of permutations: We find bijections between three classes of permutations, each defined in terms of eight forbidden patterns, and the set of polyominoes on a twisted cylinder of width 3.
In particular, it follows that all three classes of permutations belong to the same Wilf class, obeying the same recurrence formula (with respect to size) as that of the considered polyominoes, that is, \(a_{n}=2a_{n - 1}+a_{n - 2}+2a_{n - 3}\), with \(a_{1}=1\), \(a_{2}=2\) and \(a_{3}=6\).

MSC:

05A05 Permutations, words, matrices
05B50 Polyominoes

Software:

WILF; HERB
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aleksandrowicz, G.; Asinowski, A.; Barequet, G., A polyominoes-permutations injection and tree-like convex polyominoes, J. Combin. Theory Ser. A, 119, 503-520 (2012) · Zbl 1242.05052
[3] Barequet, G.; Moffie, M.; Ribó, A.; Rote, G., Counting polyominoes on twisted cylinders, Integers: Electron. J. Combin. Number Theory, 6, 37 (2006), #A22 · Zbl 1106.05026
[4] Bona, M., Combinatorics of Permutations (2012), CRC Press, p. 458 · Zbl 1255.05001
[6] Gaunt, D. S.; Sykes, M. F.; Ruskin, H., Percolation processes in \(d\)-dimensions, J. Phys. A: Math. Gen., 9, 1899-1911 (1976)
[7] Jensen, I., Enumerations of lattice animals and trees, J. Stat. Phys., 102, 865-881 (2001) · Zbl 0999.82037
[8] Jensen, I., Counting polyominoes: a parallel implementation for cluster computing, (Proc. Int. Conf. on Computational Science, Part III, Melbourne, Australia and St. Petersburg, Russia. Proc. Int. Conf. on Computational Science, Part III, Melbourne, Australia and St. Petersburg, Russia, Lecture Notes in Computer Science, vol. 2659 (2003), Springer), 203-212
[9] Kitaev, S., Patterns in Permutations and Words (2011), Springer · Zbl 1257.68007
[10] Klarner, D. A., Cell growth problems, Canad. J. Math., 19, 851-863 (1967) · Zbl 0178.00904
[11] Klarner, D. A.; Rivest, R. L., A procedure for improving the upper bound for the number of \(n\)-ominoes, Canad. J. Math., 25, 585-602 (1973) · Zbl 0261.05113
[12] Knuth, D. E., The Art of Computer Programming, Vol. 1 (1968), Addison-Wesley: Addison-Wesley Boston · Zbl 0191.17903
[13] Madras, N., A pattern theorem for lattice clusters, Ann. Comb., 3, 357-384 (1999) · Zbl 0935.60089
[14] Zeilberger, D., Enumeration schemes, and more importantly, their automatic generation, Ann. Comb., 2, 185-195 (1998) · Zbl 0931.05006
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.