Heaps and Two Exponential Structures

Abstract

Take $\mathsf{Q}=({\mathsf{Q}}_1,{\mathsf{Q}}_2,\dots )$ to be an exponential structure and $M(n)$ to be the number of minimal elements of ${\mathsf{Q}}_n$ where $M(0)=1$. Then a sequence of numbers $\{r_n({\mathsf{Q}}_n){\}}_{n\ge 1}$ is defined by the equation \begin{eqnarray*} \sum_{n\ge 1}r_n({\sf Q}_n)\frac{z^n}{n!\,M(n)}=-\log(\sum_{n\ge 0}(-1)^n\frac{z^n}{n!\,M(n)}). \end{eqnarray*} Let ${\bar{\mathsf{Q}}}_n$ denote the poset ${\mathsf{Q}}_n$ with a $\hat{0}$ adjoined and let $\hat{1}$ denote the unique maximal element in the poset ${\mathsf{Q}}_n$. Furthermore, let ${\mu }_{{\mathsf{Q}}_n}$ be the Möbius function on the poset ${\bar{\mathsf{Q}}}_n$. Stanley proved that $r_n({\mathsf{Q}}_n)=(-1{)}^n{\mu }_{{\mathsf{Q}}_n}(\hat{0},\hat{1})$. This implies that the numbers $r_n({\mathsf{Q}}_n)$ are integers. In this paper, we study the cases ${\mathsf{Q}}_n={\Pi }_n^{(r)}$ and ${\mathsf{Q}}_n={\mathsf{Q}}_n^{(r)}$ where ${\Pi }_n^{(r)}$ and ${\mathsf{Q}}_n^{(r)}$ are posets, respectively, of set partitions of $[rn]$ whose block sizes are divisible by $r$ and of $r$-partitions of $[n]$. In both cases we prove that $r_n({\Pi }_n^{(r)})$ and $r_n({\mathsf{Q}}_n^{(r)})$ enumerate the pyramids by applying the Cartier-Foata monoid identity and further prove that $r_n({\Pi }_n^{(r)})$ is the generalized Euler number $E_{rn-1}$ and that $r_n({\mathsf{Q}}_n^{(2)})$ is the number of complete non-ambiguous trees of size $2n-1$ by bijections. This gives a new proof of Welker's theorem that $r_n({\Pi }_n^{(r)})=E_{rn-1}$ and implies the construction of $r$-dimensional complete non-ambiguous trees. As a bonus of applying the theory of heaps, we establish a bijection between the set of complete non-ambiguous forests and the set of pairs of permutations with no common rise. This answers an open question raised by Aval {\it et al.}.

16 pages