Combinatorics of diagonally convex directed polyominoes Original Research Article

A new bijection between the diagonally convex directed (dcd-) polyominoes and ternary trees makes it possible to enumerate the dcd-polyominoes according to several parameters (sources, diagonals, horizontal and vertical edges, target cells). For a part of these results we also give another proof, which is based on Raneyʹs generalized lemma. Thanks to the fact that the diagonals of a dcd-polyomino can grow at most by one, the problem of q-enumeration of this object can be solved by an application of Gesselʹs q-analog of the Lagrange inversion formula. Résumé Une nouvelle bijection entre les polyominos dirigés diagonalement convexes (polyominos d.d.c.) et les arbres ternaires permet lʹénumération des polyominos d.d.c. suivant plusieur paramètres (sources, diagonales, arêtes horizontales et verticales, cellules cibles). Pour une partie de ces résultats nous donnons une preuve supplémentaire, qui est basée sur le lemme généralisée de Raney. Grâce au fait que les diagonales dʹun polyomino d.d.c. croissent au plus dʹune unité, leur q-énumération peut être résolue en utilisant le q-analogue de la formule dʹinversion de Lagrange dû à Gessel.