A grammatical calculus for peaks and runs of permutations

Authors：Chen, William Y. C.; Fu, Amy M.^*

Source：JOURNAL OF ALGEBRAIC COMBINATORICS, 2023, 57(4): 1139-1162.

DOI：10.1007/s10801-023-01219-5

• Context-free grammars
• Grammatical calculus
• Peak polynomials
• Up-down runs
• Alternating permutations
• Increasing trees

We develop a nonstandard approach to exploring polynomials associated with peaks and runs of permutations. With the aid of a context-free grammar, or a set of substitution rules, one can perform a symbolic calculus, and the computation often becomes rather simple. From a grammar, it follows at once a system of ordinary differential equations for the generating functions. Utilizing a certain constant property, it is even possible to deduce a single equation for each generating function. To bring the grammar to a combinatorial setting, we find a labeling scheme for up-down runs of a permutation, which can be regarded as a refined property, or the differentiability in a certain sense, in contrast with the usual counting argument for the recurrence relation. The labeling scheme also exhibits how the substitution rules arise in the construction of the combinatorial structures. Consequently, polynomials on peaks and runs can be dealt with in two ways, combinatorially or grammatically. The grammar also serves as a guideline to build a bijection between permutations and increasing trees that maps the number of up-down runs to the number of nonroot vertices of even degree. This correspondence can be adapted to left peaks and exterior peaks, and the key step of the construction is called the reflection principle.

• Institution
  天津大学