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
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 119161129
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Context-free grammars for permutations and increasing trees.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Chen%2C+William+Y%2EC%2E%22">Chen, William Y.C.</searchLink><relatesTo>1</relatesTo><i> chenyc@tju.edu.cn</i><br /><searchLink fieldCode="AR" term="%22Fu%2C+Amy+M%2E%22">Fu, Amy M.</searchLink><relatesTo>2</relatesTo><i> fu@nankai.edu.cn</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Advances+in+Applied+Mathematics%22">Advances in Applied Mathematics</searchLink>. Jan2017, Vol. 82, p58-82. 25p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Permutations%22">Permutations</searchLink><br /><searchLink fieldCode="DE" term="%22Combinatorics%22">Combinatorics</searchLink><br /><searchLink fieldCode="DE" term="%22Tree+graphs%22">Tree graphs</searchLink><br /><searchLink fieldCode="DE" term="%22Numerical+analysis%22">Numerical analysis</searchLink><br /><searchLink fieldCode="DE" term="%22Euler's+numbers%22">Euler's numbers</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>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.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=119161129
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.aam.2016.07.003
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 25
        StartPage: 58
    Subjects:
      – SubjectFull: Permutations
        Type: general
      – SubjectFull: Combinatorics
        Type: general
      – SubjectFull: Tree graphs
        Type: general
      – SubjectFull: Numerical analysis
        Type: general
      – SubjectFull: Euler's numbers
        Type: general
    Titles:
      – TitleFull: Context-free grammars for permutations and increasing trees.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Chen, William Y.C.
      – PersonEntity:
          Name:
            NameFull: Fu, Amy M.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 01
              Text: Jan2017
              Type: published
              Y: 2017
          Identifiers:
            – Type: issn-print
              Value: 01968858
          Numbering:
            – Type: volume
              Value: 82
          Titles:
            – TitleFull: Advances in Applied Mathematics
              Type: main
ResultId 1