×

Combinatorics of diagonally convex directed polyominoes. (English) Zbl 0857.05020

The authors consider the problem of finding a generating function for diagonally convex directed (dcd) polyominoes. These are first defined and shown to be in correspondence (not (1-1)) with lattice paths wholly below the line \(y={1\over 2} x\) and also with ternary trees, to which “1-source” polyominoes are shown to be in 1-1 correspondence. The main result of the paper is to extend the enumeration by perimeter of dcd polyominoes to the multisource case. The formula is confined by another method, and a start is made on the problem of finding a “\(q\)-enumeration” generating function, enumeration by perimeter and area. This is accomplished for “1-source” polyominoes, but the general case is deferred to a further paper.
Reviewer’s note: This is one of the most skilful uses of generating functions and transformations I have ever seen. It is comparable with MacMahon’s classic work.

MSC:

05B50 Polyominoes
05A15 Exact enumeration problems, generating functions
PDFBibTeX XMLCite
Full Text: DOI

Online Encyclopedia of Integer Sequences:

Revert transform of (-1 + x + x^2)/((x - 1)*(x + 1)).

References:

[1] Bousquet-Mélou, M.; Fédou, J. M., Énumération des polyominos convexes suivant l’aire: exemple de résolution d’un système de \(q\)-équations différentielles, (Barlotti, A.; Delest, M.; Pinzani, R., 5th FPSAC Proc., Firenze (1993)), 97-108
[2] Delest, M. P., Polyominoes and animals: some recent results, J. Math. Chem., 8, 3-18 (1991)
[3] Delest, M. P.; Fédou, J. M., Exact formulas for fully diagonal compact animals, Rapport LaBRI no. 89-06 (1989), Université de Bordeaux I · Zbl 0768.05006
[4] Dershowitz, N.; Zaks, S., Enumerations of ordered trees, Discrete Math., 31, 9-28 (1980) · Zbl 0443.05049
[5] Dershowitz, N.; Zaks, S., The cycle lemma and some applications, European J. Combin., 11, 35-40 (1990) · Zbl 0715.05004
[6] Dhar, D.; Phani, M. K.; Barma, M., Enumeration of directed site animals on two-dimensional lattices, J. Phys. A, 15, L279-L284 (1982)
[7] Dvoretzky, A.; Motzkin, Th., A problem of arrangements, Duke Math. J., 14, 305-313 (1947) · Zbl 0030.16701
[8] Feretić, S., A new coding for column-convex directed animals, Croat. Chem. Acta, 66, 81-90 (1993)
[9] Gessel, I. M., A combinatorial proof of the multivariable Lagrange inversion formula, J. Combin. Theory Ser. A, 45, 178-195 (1987) · Zbl 0651.05009
[10] Gessel, I. M., A noncommutative generalization and \(q\)-analog of the Lagrange inversion formula, Trans. Amer. Math. Soc., 257, 455-482 (1980) · Zbl 0459.05014
[11] Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete Mathematics: A Foundation for Computer Science (1989), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0668.00003
[12] Macdonald, I. G., Symmetric Functions and Hall Polynomials (1979), Oxford Univ. Press: Oxford Univ. Press Oxford · Zbl 0487.20007
[13] Penaud, J. G., Animaux dirigés diagonalement convexes et arbres ternaires, Rapport LaBRI no. 90-62 (1990), Université de Bordeaux I
[14] Privman, V.; Švrakić, N. M., Exact generating function for fully directed compact lattice animals, Phys. Rev. Lett., 60, 1107-1109 (1988)
[15] Privman, V.; Švrakić, N. M., Directed Models of Polymers, Interfaces and Clusters: Scaling and Finite-Size Properties, Lecture Notes in Physics, 338 (1989), Springer: Springer Berlin
[16] Raney, G. N., Functional composition patterns and power series reversion, Trans. Amer. Math. Soc., 94, 441-451 (1960) · Zbl 0131.01402
[17] Temperley, H. N.V., Combinatorial problems suggested by the statistical mechanics of domains and of rubber-like molecules, Phys. Rev., 103, 1-16 (1956) · Zbl 0075.20502
[18] Viennot, X. G., A survey of polyominoes enumeration, (Leroux, P.; Reutenauer, C., 4th FPSAC Proc. Montréal (1992)), 399-420
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.