Plateau-Descent joint Symmetry On Quasi-Stirling Permutations

Stirling permutations, $ST_n$, are permutations of the multiset $[0,0,1,1,\dots,n,n]$ which avoid the pattern $212$. Elizalde showed, extending a result from Bona, that the bivariate generating function for the plateau and descent statistics, P and D, respectively, is jointly symmetric over $ST_n$. This dissertation considers an extension of the Stirling permutations introduced by Archer et al. called the Quasi-Stirling permutations, $Q_n$. Quasi-Stirling permutations generalize Stirling permutations by requiring only that patterns $1212$ and $2121$ are avoided. While the P and D statistics extend naturally onto $Q_n$ the corresponding bivariate generating function is no longer symmetric. We propose a new statistic, $P_d$, which reduces to $P$ over the Stirling permutations, and we conjecture produces a jointly symmetric generating function with $D$ over $Q_n$. We prove this symmetry for a subset of $Q_n$ in two ways using both a finer partition of the descent statistic as well as a recursion on intransitive trees. This work features heavily the combinatorial analysis of rooted edge labeled plane trees, rooted vertex labeled binary plane trees and intransitive bipartite trees. We generalize the connection to bipartite trees by introducing a new notation which generates tripartite graphs and conjecture the existence of a map on these objects which demonstrates the $P_d-D$ joint symmetry on all of $Q_n$.