Context-free grammars for permutations and increasing trees

DOI10.1016/J.AAM.2016.07.003zbMATH Open1348.05007arXiv1408.1859OpenAlexW2964196775MaRDI QIDQ335859FDOQ335859

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

Publication date: 2 November 2016

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

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.

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

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

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)

Cites Work

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

Cited In (37)

• Statistics on multipermutations and partial \(\gamma\)-positivity
• The binomial-Stirling-Eulerian polynomials
• \(\gamma\)-positivity and partial \(\gamma\)-positivity of descent-type 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
• Title not available (Why is that?)
• Several variants of the Dumont differential system and permutation statistics
• A unified approach to multivariate polynomial sequences with real stability
• Counting permutations by simsun successions
• A context-free grammar for the Ramanujan-Shor polynomials
• On the joint distributions of succession and Eulerian statistics
• MacMahon's equidistribution theorem for \(k\)-Stirling permutations
• 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
• Two involutions on binary trees and generalizations
• Stirling permutation codes
• Jacobian elliptic functions and a family of bivariate peak polynomials
• 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
• Title not available (Why is that?)
• The Dumont ansatz for the Eulerian polynomials, peak polynomials and derivative polynomials
• Eulerian polynomials, Stirling permutations of the second kind and perfect matchings
• A new approach to the \(r\)-Whitney numbers by using combinatorial differential calculus
• Alternating Eulerian polynomials and left peak polynomials
• A grammatical calculus for peaks and runs of permutations
• The \(1/k\)-Eulerian polynomials of type \(B\)
• The formal derivative operator and multifactorial numbers
• David-Barton type identities and alternating run polynomials
• 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)