View in EDS

A context-free grammar for peaks and double descents of permutations.

Saved in:
Bibliographic Details
Title: A context-free grammar for peaks and double descents of permutations.
Authors: Fu, Amy M.1 fu.mei@mail.shufe.edu.cn
Source: Advances in Applied Mathematics. Sep2018, Vol. 100, p179-196. 18p.
Subjects: Permutations, Number theory, Smoothness of functions, Differential equations, Mathematical formulas, Linear systems
Abstract: This paper is concerned with the joint distribution of the number of exterior peaks and the number of proper double descents over permutations on [ n ] = { 1 , 2 , … , n } . The notion of exterior peaks of a permutation was introduced by Aguiar, Bergeron and Nyman in their study of the peak algebra. Gessel obtained the generating function of the number of permutations on [ n ] with a given number of exterior peaks. On the other hand, by establishing differential equations, Elizalde and Noy derived the generating function for the number of permutations on [ n ] with a given number of proper double descents. Barry and Basset deduced the generating function of the number of permutations on [ n ] with no proper double descents. We find a context-free grammar that can be used to compute the number of permutations on [ n ] with a given number of exterior peaks and a given number of proper double descents. Based on the grammar, the recurrence relation of the number of permutations on [ n ] with a give number of exterior peaks can be easily obtained. Moreover, we use the grammatical calculus to derive the generating function without solving differential equations. Our formula reduces to the formulas of Gessel, Elizalde-Noy, Barry, and Basset. Finally, from the grammar we establish a relationship between our generating function and the generating function of the joint distribution of the number of peaks and the number of double descents derived by Carlitz and Scoville. [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: 131031669
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: A context-free grammar for peaks and double descents of permutations.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Fu%2C+Amy+M%2E%22">Fu, Amy M.</searchLink><relatesTo>1</relatesTo><i> fu.mei@mail.shufe.edu.cn</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Advances+in+Applied+Mathematics%22">Advances in Applied Mathematics</searchLink>. Sep2018, Vol. 100, p179-196. 18p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Permutations%22">Permutations</searchLink><br /><searchLink fieldCode="DE" term="%22Number+theory%22">Number theory</searchLink><br /><searchLink fieldCode="DE" term="%22Smoothness+of+functions%22">Smoothness of functions</searchLink><br /><searchLink fieldCode="DE" term="%22Differential+equations%22">Differential equations</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+formulas%22">Mathematical formulas</searchLink><br /><searchLink fieldCode="DE" term="%22Linear+systems%22">Linear systems</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: This paper is concerned with the joint distribution of the number of exterior peaks and the number of proper double descents over permutations on [ n ] = { 1 , 2 , … , n } . The notion of exterior peaks of a permutation was introduced by Aguiar, Bergeron and Nyman in their study of the peak algebra. Gessel obtained the generating function of the number of permutations on [ n ] with a given number of exterior peaks. On the other hand, by establishing differential equations, Elizalde and Noy derived the generating function for the number of permutations on [ n ] with a given number of proper double descents. Barry and Basset deduced the generating function of the number of permutations on [ n ] with no proper double descents. We find a context-free grammar that can be used to compute the number of permutations on [ n ] with a given number of exterior peaks and a given number of proper double descents. Based on the grammar, the recurrence relation of the number of permutations on [ n ] with a give number of exterior peaks can be easily obtained. Moreover, we use the grammatical calculus to derive the generating function without solving differential equations. Our formula reduces to the formulas of Gessel, Elizalde-Noy, Barry, and Basset. Finally, from the grammar we establish a relationship between our generating function and the generating function of the joint distribution of the number of peaks and the number of double descents derived by Carlitz and Scoville. [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=131031669
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.aam.2018.06.004
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 18
        StartPage: 179
    Subjects:
      – SubjectFull: Permutations
        Type: general
      – SubjectFull: Number theory
        Type: general
      – SubjectFull: Smoothness of functions
        Type: general
      – SubjectFull: Differential equations
        Type: general
      – SubjectFull: Mathematical formulas
        Type: general
      – SubjectFull: Linear systems
        Type: general
    Titles:
      – TitleFull: A context-free grammar for peaks and double descents of permutations.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Fu, Amy M.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 09
              Text: Sep2018
              Type: published
              Y: 2018
          Identifiers:
            – Type: issn-print
              Value: 01968858
          Numbering:
            – Type: volume
              Value: 100
          Titles:
            – TitleFull: Advances in Applied Mathematics
              Type: main
ResultId 1