A generating tree for 321,hexagon-avoiding permutations

The 321,hexagon-avoiding permutations are introduced by Sara Billey and Gregory Warrington in a recent preprint. In the language of permutations with forbidden subsequences, they are the permutations avoiding all of the patterns 46718235, 46781235, 56718234, 56781234, and 321.

Standard `generating tree' techniques lead to a recursive construction of the 321,hexagon-avoiding permutations. The nodes on level n of the generating tree correspond to the 321,hexagon-avoiding permutations on n symbols. Each node is further labelled with four parameters which summarize the important features of the permutation; the subtree below a node can be reconstructed from these four parameters alone.