Context-free grammars for permutations and increasing trees
Context-free grammars for permutations and increasing trees
复制标题
用于排列和增加树的上下文无关语法
DOI：
10.1016/j.aam.2016.07.003
复制
发表时间：
2014-08
影响因子：
1.1
通讯作者：
Fu Amy M.
中科院分区：
文献类型：
--
作者：
Chen William Y. C.;Fu Amy M.
我们引入了语法标签的概念来描述基于上下文无关语法生成组合对象的递归过程。通过对斯特林置换的上、下标号，得到了二阶欧拉多项式的文法。利用Dumont给出的0-1-2增树文法，得到了Foata和Schützenberger给出的André多项式的母函数的文法推导.我们还找到了[n]={1，2，.，n}上置换个数T（n，k）有k个外峰的文法.我们证明，Gessel公式的生成函数的T（n，k）可以推导出这个语法。从语法的角度来看，很容易看出，[n]上具有k个外峰的置换的数目等于{0，1，2，.，n}上具有2k + 1个偶数度顶点的递增树的数目。我们提出了一个组合证明这一事实，这是在递归建设的精神，甚至增加树和上下排列之间的对应关系，由于库兹涅佐夫，帕克和Postnikov。
We introduce the notion of a grammatical labeling to describe a recursive process of generating combinatorial objects based on a context-free grammar. By labeling the ascents and descents of Stirling permutations, we obtain a grammar for the second-order Eulerian polynomials. Using the grammar for 0-1-2 increasing trees given by Dumont, we obtain a grammatical derivation of the generating function of the André polynomials obtained by Foata and Schützenberger. We also find a grammar for the number T (n, k) of permutations on [n]={1, 2,…, n} with k exterior peaks. We demonstrate that Gessel's formula for the generating function of T (n, k) can be deduced from this grammar. From a grammatical point of view, it is easily seen that the number of the permutations on [n] with k exterior peaks equals the number of increasing trees on {0, 1, 2,…, n} with 2 k+ 1 vertices of even degree. We present a combinatorial proof of this fact, which is in the spirit of the recursive construction of the correspondence between even increasing trees and up-down permutations, due to Kuznetsov, Pak and Postnikov.
登录
查看更多内容
DOI：
10.37236/1194
发表时间：
2003-12
期刊：
Electron. J. Comb.
影响因子：
--
作者：
N. Sloane
通讯作者：
N. Sloane
DOI：
10.1006/aama.2001.0740
发表时间：
2001-08
期刊：
Adv. Appl. Math.
影响因子：
--
作者：
D. Foata;G. Han
通讯作者：
D. Foata;G. Han
DOI：
10.1016/j.disc.2011.10.003
发表时间：
2012
期刊：
Discret. Math.
影响因子：
--
作者：
Shi-Mei Ma
通讯作者：
Shi-Mei Ma
DOI：
10.1016/b978-0-7204-2262-7.50021-1
发表时间：
1973
期刊：
--
影响因子：
--
作者：
D. Foata;M. Schützenberger
通讯作者：
D. Foata;M. Schützenberger
DOI：
10.1016/0097-3165(78)90042-0
发表时间：
1978
期刊：
J. Comb. Theory A
影响因子：
--
作者：
I. Gessel;R. Stanley
通讯作者：
I. Gessel;R. Stanley