Treffer: Pyramids of segments: nice new formulas with bijective proofs

In this paper, a segment is a finite row of unit cells. A pyramid of segments is a set of several segments, where one segment is called the base. In every segment other than the base, at least one cell is supported from below by another segment. Pyramids of segments appear in the enumeration of other combinatorial objects (such as directed animals, parallelogram polyominoes and 321-avoiding affine permutations), but are also of independent interest. We shall prove that there are (n choose r)^2 pyramids of segments with n+1 cells and r+1 segments. So there is a total of 2n choose n pyramids of segments with n+1 cells. After obtaining these simple formulas by a generating functions approach, we also give bijective proofs.