Context-free Grammars for Permutations and Increasing Trees
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 -- increasing trees given by Dumont, we obtain a grammatical derivation of the generating function of the André polynomials obtained by Foata and Schützenberger, without solving a differential equation. We also find a grammar for the number of permutations of with exterior peaks, which was independently discovered by Ma. We demonstrate that Gessel's formula for the generating function of can be deduced from this grammar. Moreover, by using grammars we show that the number of the permutations of with exterior peaks equals the number of increasing trees on with vertices of even degree. A combinatorial proof of this fact is also presented.