\(q\)-enumeration of convex polyominoes (Q1318368)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | \(q\)-enumeration of convex polyominoes |
scientific article |
Statements
\(q\)-enumeration of convex polyominoes (English)
0 references
7 June 1994
0 references
The theory of heaps of pieces has been developed by Viennot. It is a geometrical version of the theory of partially commutative monoids, introduced by Cartier and Foata. Nice inversion formulas are known to enumerate families of heaps. For example, Viennot gave a formula for the generating function of heaps whose maximal pieces lie in a given set \({\mathcal M}_ 1\). The first part of this paper is an extension of this result: a new inversion theorem is proved, giving the generating function of heaps whose maximal pieces lie in a given set \({\mathcal M}_ 1\) and whose minimal pieces lie in another set \({\mathcal M}_ 2\). In the second part, using a one-to-one correspondence between parallelogram polyominoes and some heaps of segments [the author and \textit{X. G. Viennot}, J. Comb. Theory, Ser. A 60, No. 2, 196-224 (1992; Zbl 0753.05023)], the new inversion theorem is applied to derive an expression for the width, height and area generating function of convex polyominoes. This expression was at that time the simplest one. Another one, much more complicated, had been given in [\textit{Lin}, J. Phys. A, Math. Gen. 24, 2411-2417 (1991)]. However, a simpler expression for this generating function has been obtained later, using two different methods [the author and \textit{J. M. Fédou}, to appear in Discrete Math.] and [the author, preprint].
0 references
heaps of pieces
0 references
inversion formulas
0 references
generating function
0 references
polyominoes
0 references
convex polyominoes
0 references