Context-free grammars for permutations and increasing trees

DOI10.1016/J.AAM.2016.07.003MaRDI QIDQ335859zbMATH OpenOpenAlexFDO

Authors William Y. C. Chen, Amy M. Fu

Publication date 2 November 2016

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

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

zbMATH Keywords

context-free grammarincreasing treeEulerian grammarexterior peak of a permutationgrammatical labelingStirling permutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19) Grammars and rewriting systems (68Q42) Graph theory (05C99)

Abstract: 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.

Recommendations

• A grammatical calculus for peaks and runs of permutations
• A context-free grammar for peaks and double descents of permutations
• A context-free grammar for the \(e\)-positivity of the trivariate second-order Eulerian polynomials
• Joint distributions of permutation statistics and the parabolic cylinder functions
• Context-free grammars for several polynomials associated with Eulerian polynomials

Cites work

• scientific article; zbMATH DE number 3425611 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 3424221 (Why is no real title available?)
• Alternating permutations and binary increasing trees
• Context-free grammars, differential operators and formal power series
• Derivative polynomials and enumeration of permutations by number of interior and left peaks
• Increasing trees and alternating permutations
• Minimax trees and André polynomials
• Real zeros and normal distribution for statistics on Stirling permutations defined by Gessel and Stanley
• Stable multivariate Eulerian polynomials and generalized Stirling permutations
• Stirling polynomials
• William Chen grammars and derivations in trees and arborescences

Cited in

(37)

• Statistics on multipermutations and partial \(\gamma\)-positivity
• \(\gamma\)-positivity and partial \(\gamma\)-positivity of descent-type polynomials
• The binomial-Stirling-Eulerian polynomials
• A context-free grammar for peaks and double descents of permutations
• Context-free grammars for several polynomials associated with Eulerian polynomials
• A context-free grammar for the \(e\)-positivity of the trivariate second-order Eulerian polynomials
• The ascent-plateau statistics on Stirling permutations
• scientific article; zbMATH DE number 7644296 (Why is no real title available?)
• Several variants of the Dumont differential system and permutation statistics
• A context-free grammar for the Ramanujan-Shor polynomials
• Counting permutations by simsun successions
• A unified approach to multivariate polynomial sequences with real stability
• MacMahon's equidistribution theorem for \(k\)-Stirling permutations
• On the joint distributions of succession and Eulerian statistics
• More bijective combinatorics of weakly increasing trees
• Some statistics on Stirling permutations and Stirling derangements
• Generating all permutations by context-free grammars in Chomsky normal form
• Jacobian elliptic functions and a family of bivariate peak polynomials
• Stirling permutation codes
• Two involutions on binary trees and generalizations
• Context-Free Grammars and Stable Multivariate Polynomials over Stirling Permutations
• Excedance-type polynomials, gamma-positivity and alternatingly increasing property
• Eulerian polynomials and the 𝑔-indices of Young tableaux
• Joint distributions of permutation statistics and the parabolic cylinder functions
• scientific article; zbMATH DE number 7599682 (Why is no real title available?)
• Eulerian polynomials, Stirling permutations of the second kind and perfect matchings
• The Dumont ansatz for the Eulerian polynomials, peak polynomials and derivative polynomials
• A new approach to the \(r\)-Whitney numbers by using combinatorial differential calculus
• Alternating Eulerian polynomials and left peak polynomials
• The \(1/k\)-Eulerian polynomials of type \(B\)
• A grammatical calculus for peaks and runs of permutations
• David-Barton type identities and alternating run polynomials
• The formal derivative operator and multifactorial numbers
• Generating functions for the cd-indices of simplices and cubes
• Normal ordering problem and the extensions of the Stirling grammar
• Context-free grammars, generating functions and combinatorial arrays
• On context-free trees

This page was built for publication: Context-free grammars for permutations and increasing trees

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