DMTCS Proceedings, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)

Font Size:  Small  Medium  Large

Combinatorial aspects of pyramids of one-dimensional pieces of fixed integer length

Bergfinnur Durhuus, Søren Eilers

Abstract


We consider pyramids made of one-dimensional pieces of fixed integer length a and which may have pairwise overlaps of integer length from 1 to a. We give a combinatorial proof that the number of pyramids of size m, i.e., consisting of m pieces, equals am-1&choose; m-1 for each a≥2. This generalises a well known result for a=2. A bijective correspondence between so-called right (or left) pyramids and a-ary trees is pointed out, and it is shown that asymptotically the average width of pyramids equals &sqrt; / 2a(a-1)m.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional