Fw: arXiv submission submit/1040384 发件人： W.Y.C. Chen 时 间： 2014年08月13日 19:58:33 (星期三) 收件人： kevin@nankai.edu.cn -----原始邮件----- 发件人: e-prints@arxiv.org 发送时间: 2014-08-08 22:07:00 (星期五) 收件人: chen@nankai.edu.cn 抄送: 主题: arXiv submission submit/1040384 We have received your submission to arXiv. Your temporary submission identifier is: submit/1040384. You may update your submission at: http://arxiv.org/submit/1040384 Your article is scheduled to be announced at Mon, 11 Aug 2014 00:00:00 GMT. The abstract will appear in the subsequent mailing as displayed below, except that the submission identifier will be replaced by the official arXiv identifier. Updates before Fri, 8 Aug 2014 20:00:00 GMT will not delay announcement. A paper password will be emailed to you when the article is announced. You should share this with co-authors to allow them to claim ownership. If you have a problem that you are not able to resolve through the web interface, contact help@arxiv.org with a description of the issue and reference the submission identifier. arXiv admin ------------------------------------------------------------------------------ \\ arXiv:submit/1040384 From: William Y. C. Chen Date: Fri, 8 Aug 2014 10:06:58 EST (17kb) Title: Context-free Grammars for Permutations and Increasing Trees Authors: William Y.C. Chen and Amy M. Fu Categories: math.CO Comments: 25 pages MSC-class: 05A15, 05A19 License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/ \\ In this paper, we introduce the notion of a grammatical labeling to describe a recursive process of generating combinatorial objects based on a context-free grammar. For example, by labeling the ascents and descents of a Stirling permutation, we obtain a grammar for the second-order Eulerian polynomials. By using the grammar for $0$-$1$-$2$ increasing trees given by Dumont, we obtain a grammatical derivation of the generating function of the Andr\'e polynomials obtained by Foata and Sch\"utzenberger, without solving a differential equation. We also find a grammar for the number $T(n,k)$ of permutations of $[n]=\{1,2,\ldots, n\}$ with $k$ exterior peaks, which was independently discovered by Ma. We demonstrate that Gessel's formula for the generating function of $T(n,k)$ can be deduced from this grammar. Moreover, by using grammars we show that the number of the permutations of $[n]$ with $k$ exterior peaks equals the number of increasing trees on $[n]$ with $2k+1$ vertices of even degree. A combinatorial proof of this fact is also presented. \\