On the Parity of Certain Coefficients for a $q$-Analogue of the Catalan Numbers

Kendra Killpatrick

Abstract


The 2-adic valuation (highest power of 2) dividing the well-known Catalan numbers, $C_n$, has been completely determined by Alter and Kubota and further studied combinatorially by Deutsch and Sagan.  In particular, it is well known that $C_n$ is odd if and only if $n = 2^k-1$ for some $k \geq 0$.  The polynomial $F_n^{ch}(321;q) = \sum_{\sigma \in Av_n(321)} q^{ch(\sigma)}$, where $Av_n(321)$ is the set of permutations in $S_n$ that avoid 321 and $ch$ is the charge statistic, is a $q$-analogue of the Catalan numbers since specializing $q=1$ gives $C_n$.  We prove that the coefficient of $q^i$ in $F_{2^k-1}^{ch}(321;q)$ is even if $i \geq 1$, giving a refinement of the "if" direction of the $C_n$ parity result.  Furthermore, we use a bijection between the charge statistic and the major index to prove a conjecture of Dokos, Dwyer, Johnson, Sagan and Selsor regarding powers of 2 and the major index. 
 
In addition, Sagan and Savage have recently defined a notion of $st$-Wilf equivalence for any permutation statistic $st$ and any two sets of permutations $\Pi$ and $\Pi'$.  We say $\Pi$ and $\Pi'$ are $st$-Wilf equivalent if $\sum_{\sigma \in Av_n(\Pi)} q^{st(\sigma)} = \sum_{\sigma \in Av_n(\Pi')} q^{st(\sigma)}$.  In this paper we show how one can characterize the charge-Wilf equivalence classes for subsets of $S_3$.

Keywords


Wilf equivalence, charge statistic, Young tableaux, permutation statistics, major index, pattern avoiding sets, Catalan numbers

Full Text: PDF