Combinatorics of diagonally convex directed polyominoes (Q1924364)

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.