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

DOI10.1016/J.AAM.2018.06.004MaRDI QIDQ1661490zbMATH OpenOpenAlexWikidataFDO

Authors Amy M. Fu

Publication date 16 August 2018

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.04397

zbMATH Keywords

context-free grammarsgrammatical labelingexterior peaksproper double descents

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19)

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,ldots,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 independently deduced the generating function of the number of permutations on $[n]$ with no proper double descents. We find a context-free grammar which 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 given 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 descent derived by Carlitz and Scoville.

Recommendations

• Joint distributions of permutation statistics and the parabolic cylinder functions
• A grammatical calculus for peaks and runs of permutations
• Context-free grammars for permutations and increasing trees
• Counting permutations by peaks, descents, and cycle type
• scientific article; zbMATH DE number 1792574

Cites work

• scientific article; zbMATH DE number 3425611 (Why is no real title available?)
• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 3433888 (Why is no real title available?)
• Consecutive patterns in permutations
• Constructing exponential Riordan arrays from their \(A\) and \(Z\) sequences
• Context-free grammars for permutations and increasing trees
• Context-free grammars for several polynomials associated with Eulerian polynomials
• Context-free grammars, differential operators and formal power series
• Counting and Generating Permutations Using Timed Languages
• Derivative polynomials and enumeration of permutations by number of interior and left peaks
• Minimax trees and André polynomials
• Ramanujan grammar and Cayley trees
• The On-Line Encyclopedia of Integer Sequences
• The peak algebra and the descent algebras of types B and D
• William Chen grammars and derivations in trees and arborescences

Cited in

(9)

• Joint distributions of permutation statistics and the parabolic cylinder functions
• \(\gamma\)-positivity and partial \(\gamma\)-positivity of descent-type polynomials
• Counting and signed counting permutations by descent-based statistics
• Context-free grammars, generating functions and combinatorial arrays
• Hankel continued fractions and Hankel determinants of the Euler numbers
• Context-free grammars for permutations and increasing trees
• A grammatical calculus for peaks and runs of permutations
• A \(q\)-analog of the Stirling-Eulerian polynomials
• A \(q\)-analogue of generalized Eulerian polynomials with applications

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: A context-free grammar for peaks and double descents of permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1661490)