Heaps and two exponential structures
Heaps and two exponential structures
复制标题
堆和两个指数结构
DOI：
10.1016/j.ejc.2015.12.007
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Emma Yu Jin
中科院分区：
文献类型：
--
作者：
Emma Yu Jin
摘要取Q=(Q1，Q2，…)是指数结构，M(N)是Qn的极小元素的个数，其中M(0)=1。然后，数列{rn(Qn)}n≥1由方程∑n≥1rn(Qn)zn n！M(N)=−(∑n≥0(−1)n z n n！M(N))。设Q̄n表示带有0ˆ的偏序集Qn，1ˆ表示偏序集Qn中唯一的极大元.进一步，设μQn是偏序集Q̄n上的Möbius函数.Stanley证明了Rn(Qn)=(−1)nμQn(0ˆ，1ˆ).这意味着数字rn(Qn)是整数。本文研究了Qn=Πn(R)和Qn=Qn(R)的情形，其中Πn(R)和Qn(R)分别是块大小可被r整除的[rn]的集合划分和[n]的r-划分的偏序集.在这两种情况下，我们利用Cartier-Foata么半群恒等式证明了rn(Πn(R))和rn(qn(R))计数金字塔，并进一步证明了rn(Πn(R))是广义欧拉数E r n−1，rn(Qn(2))是大小为2 n−1的完全非二义树的个数.这给出了WELKER定理rn(Πn(R))=Ern−1的一个新的证明，并暗示了r维完全非二义树的构造。作为应用堆理论的一个好处，我们在完全无歧义森林的集合和没有公升的排列对的集合之间建立了双射。这回答了Aval等人提出的一个公开问题。
Abstract Take Q=(Q 1, Q 2,…) to be an exponential structure and M (n) to be the number of minimal elements of Q n where M (0)= 1. Then a sequence of numbers {r n (Q n)} n≥ 1 is defined by the equation∑ n≥ 1 r n (Q n) z n n! M (n)=− log (∑ n≥ 0 (− 1) n z n n! M (n)). Let Q ̄ n denote the poset Q n with a 0 ˆ adjoined and let 1 ˆ denote the unique maximal element in the poset Q n. Furthermore, let μ Q n be the Möbius function on the poset Q ̄ n. Stanley proved that r n (Q n)=(− 1) n μ Q n (0 ˆ, 1 ˆ). This implies that the numbers r n (Q n) are integers. In this paper, we study the cases Q n= Π n (r) and Q n= Q n (r) where Π n (r) and 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 (Π n (r)) and r n (Q n (r)) enumerate the pyramids by applying the Cartier–Foata monoid identity and further prove that r n (Π n (r)) is the generalized Euler number E r n− 1 and that r n (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 (Π 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 et al.
登录
查看更多内容
影响因子：
1.3
作者：
L. Carlitz;R. Scoville;T. Vaughan
通讯作者：
T. Vaughan
DOI：
10.1016/j.ejc.2007.11.028
发表时间：
2010
期刊：
Eur. J. Comb.
影响因子：
--
作者：
R. Ehrenborg;Margaret A. Readdy
通讯作者：
Margaret A. Readdy
DOI：
10.1006/jctb.1995.1017
发表时间：
1995
期刊：
J. Comb. Theory B
影响因子：
--
作者：
V. Welker
通讯作者：
V. Welker
非歧义树的组合学
DOI：
10.1016/j.aam.2013.11.004
发表时间：
2013
期刊：
Adv. Appl. Math.
影响因子：
--
作者：
J. Aval;A. Boussicault;M. Bouvel;M. Silimbani
通讯作者：
M. Silimbani