[Zurück]


Zeitschriftenartikel:

E. Jin:
"Heaps and Two Exponential Structures";
European Journal of Combinatorics, 54 (2015), S. 87 - 102.



Kurzfassung englisch:
Let ${\bf Q}=(Q_1,Q_2,\ldots)$ be an exponential structure, let $M(n)$ be the
number of minimal elements of $Q_n$ and set $M(0)=1$. Then a sequence of
numbers $\{r_n(Q_n)\}_{n\ge 1}$ is defined by the equation \begin{eqnarray*}
\sum_{n\ge 1}r_n(Q_n)\frac{z^n}{n!\,M(n)}=-\log\left(\sum_{n\ge
0}(-1)^n\frac{z^n}{n!\,M(n)}\right). \end{eqnarray*} Let $\bar{Q}_n$ denote the
poset $Q_n$ with a $\hat{0}$ adjoined, $\mu_{Q_n}$ be the M"{o}bius function
on the poset $\bar{Q}_n$. Stanley proved
$r_n(Q_n)=(-1)^n\mu_{Q_n}(\hat{0},\hat{1})$. This implies the numbers
$r_n(Q_n)$ are integers. In this paper we study the case $Q_n=\Pi_n^{(r)}$
where $\Pi_n^{(r)}$ is the poset of set partitions of $[rn]$ whose block sizes
are divisible by $r$ and the case $Q_n=Q_n^{(r)}$ where $Q_n^{(r)}$ is the
poset of $r$-partitions of $[n]$. In both cases we give combinatorial
interpretations of $r_n(Q_n)$ in terms of heaps by applying Cartier-Foata
monoid identity, and further prove $r_n(\Pi_n^{(r)})$ are the generalized Euler
numbers $E_{rn-1}$, $r_n(Q_n^{(2)})$ are the numbers of complete non-ambiguous
trees by using 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
give 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.}


"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1016/j.ejc.2015.12.007


Erstellt aus der Publikationsdatenbank der Technischen Universitšt Wien.