Context-free grammars for permutations and increasing trees

详细信息    查看全文

• 作者：William Y.C. Chen^a ; ^{chenyc@tju.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Amy M. Fu^b ; ^{fu@nankai.edu.cn" class="auth_mail" title="E-mail the corresponding author}
• 关键词：05A15 ; 05A19
• 刊名：Advances in Applied Mathematics
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：82
• 期：Complete
• 页码：58-82
• 全文大小：409 K

文摘

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 formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0196885816300598&_mathId=si1.gif&_user=111111111&_pii=S0196885816300598&_rdoc=1&_issn=01968858&md5=5b3c1f7cfa5ce9f741e434873236112f" title="Click to view the MathML source">T(n,k)flow="scroll">Tfalse">(n,kfalse">) of permutations on formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0196885816300598&_mathId=si2.gif&_user=111111111&_pii=S0196885816300598&_rdoc=1&_issn=01968858&md5=e3e3dac9cdb9f7cdc92b0f4874896a54" title="Click to view the MathML source">[n]={1,2,…,n}flow="scroll">false">[nfalse">]=false">{1,2,…,nfalse">} with k   exterior peaks. We demonstrate that Gessel's formula for the generating function of formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0196885816300598&_mathId=si1.gif&_user=111111111&_pii=S0196885816300598&_rdoc=1&_issn=01968858&md5=5b3c1f7cfa5ce9f741e434873236112f" title="Click to view the MathML source">T(n,k)flow="scroll">Tfalse">(n,kfalse">) can be deduced from this grammar. From a grammatical point of view, it is easily seen that the number of the permutations on formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0196885816300598&_mathId=si112.gif&_user=111111111&_pii=S0196885816300598&_rdoc=1&_issn=01968858&md5=564642ea6f537e45b69be8071dd611c1" title="Click to view the MathML source">[n]flow="scroll">false">[nfalse">] with k   exterior peaks equals the number of increasing trees on formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0196885816300598&_mathId=si121.gif&_user=111111111&_pii=S0196885816300598&_rdoc=1&_issn=01968858&md5=d2247cbcc3ed19bbcb2643638a90ec78" title="Click to view the MathML source">{0,1,2,…,n}flow="scroll">false">{0,1,2,…,nfalse">} with formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0196885816300598&_mathId=si5.gif&_user=111111111&_pii=S0196885816300598&_rdoc=1&_issn=01968858&md5=8f35df94f1030b80a24b289a91dd1ef2" title="Click to view the MathML source">2k+1flow="scroll">2k+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.