Context-free grammars for permutations and increasing trees

We introduce the notion of a grammatical labeling to describe a recursive process of generating combinatorial objects based on a context-free grammar. By labeling the ascents and descents of Stirling permutations, we obtain a grammar for the second-order Eulerian polynomials. Using the grammar for 0-1-2 increasing trees given by Dumont, we obtain a grammatical derivation of the generating function of the André polynomials obtained by Foata and Schützenberger. We also find a grammar for the number T(n,k)T(n,k) of permutations on [n]={1,2,…,n}[n]={1,2,…,n} with k   exterior peaks. We demonstrate that Gessel's formula for the generating function of T(n,k)T(n,k) can be deduced from this grammar. From a grammatical point of view, it is easily seen that the number of the permutations on [n][n] with k   exterior peaks equals the number of increasing trees on {0,1,2,…,n}{0,1,2,…,n} with 2k+12k+1 vertices of even degree. We present a combinatorial proof of this fact, which is in the spirit of the recursive construction of the correspondence between even increasing trees and up-down permutations, due to Kuznetsov, Pak and Postnikov.