华东师范大学学报（自然科学版） >

2015 , Vol. 2015 >Issue 3: 31 - 37

DOI: https://doi.org/10.3969/j.issn.1000-5641.2015.03.005

应用数学与基础数学

k-色斜路的计数

  • 卢青林
展开
  • 江苏师范大学 数学与统计学院, 江苏 徐州 221116
卢青林, 男, 教授, 博士, 主要从事组合数学的研究.

收稿日期: 2014-08-16

  网络出版日期: 2015-05-28

基金资助

国家自然科学基金(11171288, 11171150)

收起

Enumeration of k-colored skew Dyck path

  • LU Qing-Lin
Expand

Received date: 2014-08-16

  Online published: 2015-05-28

Fold

摘要

本文研究k-色斜Dyck路的计数问题,给出半长为n的k-色斜Dyck路的数目s_n的计数公式、递推关系以及s_n/s_{n-1}的极限, 并对半长、左步数、峰数、谷数以及双升数等参数给出了k-色斜Dyck路相应的计数公式.

关键词： Dyck路;k-色斜Dyck路; 计数;Lagrange反演定理

本文引用格式

卢青林 . k-色斜路的计数[J]. 华东师范大学学报（自然科学版）, 2015 , 2015(3) : 31 -37 . DOI: 10.3969/j.issn.1000-5641.2015.03.005

Abstract

In this paper we study the enumeration of k-colored skew Dyck paths. We first give a counting formula and a recurrence for s_n and the limit of s_n/s_{n-1}. We then give the countingformulas of the $k$-colored skew Dyck paths with semilength naccording to the number of left steps and the number of peaks,
valleys and double rises

Key words： Dyck path; k-colored skew Dyck path; enumeration; Lagrange inversion theorem

参考文献

[1]ALONSO L. Uniform generation of a Motzkin word [J]. Theoret ComputSci, 1994, 134: 529-536.
[2]DEUTSCH E. Dyck path enumeration [J]. Discrete Math, 1999, 204:167-202.
[3]DONAGHEY R, SHAPIRO L W. Motzkin numbers [J]. J Combin Theory Ser A,1977, 23: 291-301.
[4]MANSOUR T. Counting peaks at height k in a Dyck path [J]. JInteger Seq, 2002, 5: Article 02.1.1.
[5]PEART P, WOAN W J. Dyck paths with no peaks at height k[J]. JInteger Seq, 2001, 4: Article 01.1.3.
[6]PANAYOTOPOULAOS A, SAPOUNAKIS A. On the prime decomposition of Dyckwords [J]. J Combin Math Combin Comput, 2002, 40: 33-39.
[7]PANAYOTOPOULAOS A, SAPOUNAKIS A. On Motzkin words and noncrossingpartitions [J]. Ars Combin, 2003, 69: 109-116.
[8]SULANKE R A. Bijective recurrences for Motzkin paths [J]. Adv InAppl Math, 2001, 27: 627-640.
[9]BARCUCCI E, LUNGO A D, PERGOLA E, et al. A construction forenumerating k-colored Motzkin paths [C]Proc of the First Annual

International Conference on Computing and Combinatorics Springer,1995: 254-263.
[10]SAPOUNAKIS A, TSIKOURAS P. On k-colored Motzkin words [J]. J

Integer Seq, 2004, 7: Article 04.2.5.
[11]SAPOUNAKIS A, TSIKOURAS P. Counting peaks and valleys in $k$-coloredMotzkin paths. The Electron J Combin, 2005, 12: R16.
[12]DEUTSCH E, MUNARINI E, RINALDI S. Skew Dyck paths [J]. J StatistPlann Inference, 2010, 140: 2191-2203.
[13]DEUTSCH E, MUNARINI E, RINALDI S. Skew Dyck paths, area, andsuperdigonal bargraphs [J]. J Statist Plann Inference, 2010, 140:

1550-1562.
[14]LIU L L, WANG Y. On the log-convexity of combinatorial sequences[J]. Adv Appl Math, 2007, 39: 453-476.
Options
文章导航

/

〈 〉