Abstract | ||
---|---|---|
In this paper we consider a restricted class of polyominoes that we call Z-convex polyominoes. Z-convex polyominoes are polyominoes such that any two pairs of cells can be connected by a monotone path making at most two turns (like the letter Z). This class of convex polyominoes appears to resist standard decompositions, so we propose a construction by ''inflation'' that allows to write a system of functional equations for their generating functions. The generating function P(t) of Z-convex polyominoes with respect to the semi-perimeter turns out to be algebraic all the same and surprisingly, like the generating function of convex polyominoes, it can be expressed as a rational function of t and the generating function of Catalan numbers. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1016/j.aam.2006.07.004 | Advances in Applied Mathematics |
Keywords | Field | DocType |
functional equation,catalan number,. enumeration,generating function,monotone path,z-convex polyominoes,recursive decomposition. the authors acknowledge support from the french anr under the sada project.,algebraic generating functions,restricted class,generating function p,rational function,letter z,convex polyominoes,primary,enumeration | Discrete mathematics,Generating function,Combinatorics,Algebraic number,Mathematical analysis,Polyomino,Catalan number,Convex function,Rational function,Functional equation,Monotone polygon,Mathematics | Journal |
Volume | Issue | ISSN |
40 | 1 | 0196-8858 |
Citations | PageRank | References |
12 | 0.90 | 9 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Enrica Duchi | 1 | 49 | 16.21 |
Simone Rinaldi | 2 | 174 | 24.93 |
Gilles Schaeffer | 3 | 423 | 44.82 |