Bergfinnur Durhuus ; Søren Eilers - Combinatorial aspects of pyramids of one-dimensional pieces of fixed integer length

dmtcs:2794 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) - https://doi.org/10.46298/dmtcs.2794
Combinatorial aspects of pyramids of one-dimensional pieces of fixed integer lengthArticle

Authors: Bergfinnur Durhuus 1; Søren Eilers 1

  • 1 Department of Mathematical Sciences [Copenhagen]

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 $\binom{am-1}{m-1}$ for each $a \geq 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{\frac{\pi}{2} a(a-1)m}$.


Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: LEGOs,Dyck paths,heaps,pyramids,polyominoes,lattice animals,enumeration,trees,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

1 Document citing this article

Consultation statistics

This page has been seen 148 times.
This article's PDF has been downloaded 144 times.