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.2794Combinatorial aspects of pyramids of one-dimensional pieces of fixed integer lengthConference paper
Authors: Bergfinnur Durhuus 1; Søren Eilers 1
NULL##NULL
Bergfinnur Durhuus;Søren Eilers
- 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: [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], [en] heaps, pyramids, polyominoes, lattice animals, enumeration, trees, Dyck paths, LEGOs