...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Enumerating (2 + 2) -free posets by the number of minimal elements and other statistics
【24h】

Enumerating (2 + 2) -free posets by the number of minimal elements and other statistics

机译：通过最小元素数和其他统计信息来枚举（2 + 2）个自由态

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

An unlabeled poset is said to be (2+2)-free if it does not contain an induced subposet that is isomorphic to 2+2, the union of two disjoint 2-element chains. Let pn denote the number of (2+2)-free posets of size n. In a recent paper, Bousquet-Mélou et al. [1] found, using the so called ascent sequences, the generating function for the number of (2+2)-free posets of size n: P(t)=∑_(n<0)~(pntn)= ∑_(n<0)∏i=1n(1-~((1-t)i)). We extend this result in two ways. First, we find the generating function for (2+2)-free posets when four statistics are taken into account, one of which is the number of minimal elements in a poset. Second, we show that if pn,k equals the number of (2+2)-free posets of size n with k minimal elements, then P(t,z)=∑_(n,k<0pn,k)~(tnzk)= 1+∑_(n<0)zt~((1-zt))~(n+1)∏i=1n(1-~((1-t)i)). The second result cannot be derived from the first one by a substitution. Our enumeration results are extended to certain restricted permutations and to regular linearized chord diagrams through bijections in [1,2]. Finally, we define a subset of ascent sequences counted by the Catalan numbers and we discuss its relations with (2+2)- and (3+1)-free posets.
机译：如果未标记的位姿不包含与2 + 2同构的诱导子位，即两个不相交的2个元素链的并集，则称其无（2 + 2）。令pn表示大小为n的（2 + 2）个自由球的数量。在最近的一篇论文中，Bousquet-Mélou等人。 [1]使用所谓的上升序列，发现了大小为n的（2 + 2）个无姿势球的数量的生成函数：P（t）= ∑_（n <0）〜（pntn）= ∑_ （n <0）∏i = 1n（1-〜（（1-t）i））。我们以两种方式扩展此结果。首先，当考虑到四个统计数据时，我们找到了无（2 + 2）个姿势的姿势的生成函数，其中之一是姿势中的最小元素数量。其次，我们证明如果pn，k等于大小为n的（2 + 2）个无姿势球的数量，其中k个最小元素，则P（t，z）= ∑_（n，k <0pn，k）〜（ tnzk）= 1 + ∑_（n <0）zt〜（（1-zt））〜（n + 1）∏i = 1n（1-〜（（1-t）i））。无法通过替换从第一个结果中得出第二个结果。我们的枚举结果通过[1,2]中的双射被扩展到某些受限置换和正则线性化弦图。最后，我们定义由加泰罗尼亚语数字计数的上升序列的子集，并讨论其与（2 + 2）-和（3 + 1）-无姿态的关系。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号