Heaps and two exponential structures

DOI10.1016/J.EJC.2015.12.007MaRDI QIDQ5964258zbMATH OpenOpenAlexFDO

Authors Emma Yu Jin

Publication date 29 February 2016

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.0242

zbMATH Keywords

Cartier-Foata monoid identity complete non-ambiguous trees

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Partitions of sets (05A18) Trees (05C05)

Abstract: Take

s f Q = ({s f Q}_{1}, {s f Q}_{2}, l d o t s)

to be an exponential structure and

M (n)

to be the number of minimal elements of

{s f Q}_{n}

where

M (0) = 1

. Then a sequence of numbers

{r_{n} ({s f Q}_{n})}_{n g e 1}

is defined by the equation �egin{eqnarray*} sum_{nge 1}r_n({sf Q}_n)frac{z^n}{n!,M(n)}=-log(sum_{nge 0}(-1)^nfrac{z^n}{n!,M(n)}). end{eqnarray*} Let

denote the poset

{s f Q}_{n}

with a

h a t 0

adjoined and let

h a t 1

denote the unique maximal element in the poset

{s f Q}_{n}

. Furthermore, let

m u_{{s f Q}_{n}}

be the M"{o}bius function on the poset

. Stanley proved that

r_{n} ({s f Q}_{n}) = (- 1)^{n} m u_{{s f Q}_{n}} (h a t 0, h a t 1)

. This implies that the numbers

r_{n} ({s f Q}_{n})

are integers. In this paper, we study the cases

{s f Q}_{n} = P i_{n}^{(r)}

and

{s f Q}_{n} = {s f Q}_{n}^{(r)}

where

P i_{n}^{(r)}

and

{s f Q}_{n}^{(r)}

are posets, respectively, of set partitions of

[r n]

whose block sizes are divisible by

r

and of

r

-partitions of

[n]

. In both cases we prove that

r_{n} (P i_{n}^{(r)})

and

r_{n} ({s f Q}_{n}^{(r)})

enumerate the pyramids by applying the Cartier-Foata monoid identity and further prove that

r_{n} (P i_{n}^{(r)})

is the generalized Euler number

E_{r n - 1}

and that

r_{n} ({s f Q}_{n}^{(2)})

is the number of complete non-ambiguous trees of size

2 n - 1

by bijections. This gives a new proof of Welker's theorem that

r_{n} (P i_{n}^{(r)}) = E_{r n - 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.}.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Heaps and two exponential structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5964258)