Abstract:  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) of permutations of [n] = {1, 2,..., n} with k exterior peaks. We demonstrate that Gessel's formula for the generating function of 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] with k exterior peaks equals the number of increasing trees on [n] with 2k+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.

  AMS Classification:  05A15, 05A19

  Keywords:  context-free grammar, Eulerian grammar, grammatical labeling, increasing tree, exterior peak of a permutation, Stirling permutation

  Download:   PDF