View in EDS

Context-free grammars for permutations and increasing trees.

Saved in:
Bibliographic Details
Title: Context-free grammars for permutations and increasing trees.
Authors: Chen, William Y.C.1 chenyc@tju.edu.cn, Fu, Amy M.2 fu@nankai.edu.cn
Source: Advances in Applied Mathematics. Jan2017, Vol. 82, p58-82. 25p.
Subjects: Permutations, Combinatorics, Tree graphs, Numerical analysis, Euler's numbers
Abstract: 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. [ABSTRACT FROM AUTHOR]
Copyright of Advances in Applied Mathematics is the property of Academic Press Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract: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. [ABSTRACT FROM AUTHOR]
ISSN:01968858
DOI:10.1016/j.aam.2016.07.003