% LaTeX Article Template
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P27}{19(4)}{2012}

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\usepackage{amsmath, amssymb, amsthm}

\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\theoremstyle{plain}
\newtheorem{Theorem}{Theorem}
\newtheorem{Corollary}{Corollary}
\newtheorem{Example}{Example}
\newtheorem{Lemma}{Lemma}
\newtheorem{Conjecture}{Conjecture}

\DeclareMathOperator{\ch}{ch}
\DeclareMathOperator{\Av}{Av}
\DeclareMathOperator{\st}{st}
\DeclareMathOperator{\maj}{maj}
\DeclareMathOperator{\inv}{inv}
\DeclareMathOperator{\chv}{chv}

% Set the beginning of a LaTeX document


\title{\bf\boldmath On the parity of certain coefficients\\ for a $q$-analogue of the Catalan Numbers }        
\author{Kendra Killpatrick \\
\small Natural Science Division\\[-0.8ex]
\small Pepperdine University\\[-0.8ex]
\small Malibu, California, U.S.A.\\
\small\tt Kendra.Killpatrick@pepperdine.edu
}        

\date{\dateline{May 5, 2012}{Nov 10, 2012}{Nov 22, 2012}\\  
\small Mathematics Subject Classifications:  05A05}    

\begin{document}
   
\maketitle

\begin{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$.
\end{abstract}







\section{Introduction}      





Suppose $\pi = a_1 a_2 \cdots a_n$ and $\sigma = b_1 b_2 \cdots b_n$ are two sequences of distinct positive integers of the same length $n$.  We say that $\pi$ is {\it {order isomorphic}} to $\sigma$ if $a_i < a_j$ if and only if $b_i < b_j$.  Let $S_n$ be the symmetric group of all permutations of the set $[n] = \{ 1, 2, \dots, n\}$.  For any $\pi \in S_n$ and $\sigma \in S_k$ for $k \leq n$, we say that $\pi$ {\it {contains a copy of $\sigma$}} if $\pi$ has a subsequence that is order isomorphic to $\sigma$.  If $\pi$ contains no subsequence order isomorphic to $\sigma$ then we say that $\pi$ {\it {avoids}} $\sigma$.  

Now let $\Pi$ be a subset of permutations in $S_n$ and define $\Av_n(\Pi)$ as the set of permutations in $S_n$ which avoid every permutation in $\Pi$.  Two sets of permutations $\Pi$ and $\Pi'$ are said to be {\it {Wilf equivalent}} if $\vert \Av_n(\Pi)\vert = \vert \Av_n(\Pi')\vert$.  If $\Pi$ and $\Pi'$ are Wilf equivalent, we write $\Pi \equiv \Pi'$.  

Sagan and Savage \cite{SSa} defined a $q$-analogue of Wilf equivalence by considering any permutation statistic $\st$ from $\uplus_{n \geq 0} S_n \rightarrow \mathbb{N}$, where $\mathbb{N}$ is the set of nonnegative integers, and letting 
\[
F_n^{\st}(\Pi;q) = \sum_{\sigma \in \Av_n(\Pi)} q^{\st(\sigma)}.
\]
They defined $\Pi$ and $\Pi'$ to be {\it {$\st$-Wilf equivalent}} if $F_n^{\st}(\Pi;q) = F_n^{\st}(\Pi';q)$ for all $n \geq 0$.  In this case, we write $\Pi \stackrel{\st}{\equiv} \Pi'$. We will use $[\Pi]_{\st}$ to denote the $\st$-Wilf equivalence class of $\Pi$.  If we set $q=1$ in the generating function above we have $F_n^{\st}(\Pi;1) = \vert \Av_n(\Pi) \vert$, thus $\st$-Wilf equivalence implies Wilf equivalence.  

In \cite{DDJ}, Dokos, Dwyer, Johnson, Sagan and Selsor give a thorough investigation of $\st$-Wilf equivalence for both the major index, {\it {$\maj$}}, and the inversion statistic, {\it {$\inv$}}.  Through a relatively straightforward map on permutations that takes the major index to another well known Mahonian statistic, the charge statistic, one can give a similarly thorough investigation for the charge statistic and we indicate how to do this in Section 3.  


The well known Catalan numbers are defined explicitly by the formula
\[
C_n = \frac{1}{n+1} \binom{2n}{n}.
\]
In 1973, Alter and Kubota \cite{AlK} used arithmetic techniques to characterize the divisibility of the Catalan numbers by primes and prime powers.  Since then, a number of combinatorial proofs have been given (\cite{Deu}, \cite{Ege}, \cite{SiU} and most recently \cite{DSa}) for the more specific result that $C_n$ is odd precisely when $n=2^k-1$ for some $k \in \mathbb{N}$.  Deutsch and Sagan \cite{DSa} go on to use group actions to prove a theorem about the $2$-adic valuation (largest power of 2) dividing $C_n$.  

For $\Pi$ equaling a single element of $S_3$, the polynomial $F_n^{\st}(\Pi;q)$ can be thought of as a $q$-analogue of the Catalan numbers since specializing $q=1$ gives $C_n$.  In Section 4 we prove that the coefficient of $q^i$ in $F_{2^k-1}^{\ch}(321;q)$ is even if $i \geq 1$ using some basic facts about standard Young tableaux and the Robinson-Schensted correspondence.  This further refines the ``if'' direction of the $C_n$ parity result.  We can then translate this result into a similar statement for the major index to answer a conjecture of Dokos et al.\ about the coefficients of $F_{2^k-1}^{\maj}(321;q)$.  We close the paper in Section 5 with some directions for further research.

 \section{Definitions}

Throughout this paper we will utilize some basic operations on permutations, namely the {\it{inverse}} and the {\it {reverse}}.  For a permutation $\pi = \pi_1 \ \pi_2 \ \cdots \ \pi_n$, the inverse is the standard group-theoretic inverse operation on permutations and the reverse is
\[
\begin{array}{cccccc}
\pi^r &=& \pi_n& \cdots &\pi_2 &\pi_1.
\end{array}
\]

  

  
For a permutation $\pi  = \pi_1 \ \pi_2 \ \cdots \ \pi_n \in S_n$, define the {\it {descent set of $\pi$}} to be $Des(\pi) = \{ i \ \vert \ \pi_i > \pi_{i+1} \}$.  The {\it {major index}} of a permutation, first defined by MacMahon \cite{Mac}, is then defined as 
\[
\maj(\pi) = \sum_{i \in Des(\pi)} i.
\]

For example, for $\pi = \begin{array}{ccccccccc} 3&2&8&5&7&4&6&1&9 \end{array}$, $Des(\pi) = \{1, 3, 5, 7\}$ and $\maj(\pi) = 1 + 3 + 5 + 7 = 16$.  

Let $\pi$ be a permutation in $S_n$.  For any $i$ in the permutation, define the {\it {charge value of $i$}}, $\chv(i)$, recursively with $\chv(1)=0$ and for $i>1$

\[
\chv(i) = \begin{cases} 
0 & {\text { if $i$ is to the right of $i-1$ in $\pi$,}} \\
n+1-i & {\text { if $i$ is to the left of $i-1$ in $\pi$.}}
\end{cases}
\]

Now for $\pi \in S_n$, define the {\it{charge of $\pi$}}, $\ch(\pi)$, to be
\[
\ch(\pi) = \sum_{i=1}^n \chv(i).
\]

In the following example for $\pi = \begin{array}{ccccccccc} 3&2&8&5&7&4&6&1&9 \end{array}$, the charge values of each element are given below the permutation:
\[
\begin{array}{ccccccccccc}
\pi&=&3&2&8&5&7&4&6&1&9\\
 & &\textnormal{\scriptsize7}&\textnormal{\scriptsize8}&\textnormal{\scriptsize2}&\textnormal{\scriptsize5}&\textnormal{\scriptsize3}&\textnormal{\scriptsize0}&\textnormal{\scriptsize0}&\textnormal{\scriptsize0}&\textnormal{\scriptsize0}
\end{array}
\]
and $\ch(\pi) = 7+8+2+5+3=25$.  The definition of the charge statistic was first given by Lascoux and Sch\"utzenberger \cite{LSc}.







We say $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_r)$ is a
{\it partition of n} if $\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_r
\ge 0$ and $\sum_i \lambda_i = n$.  A partition $\lambda$ may be described pictorially by its Ferrers diagram, an array of $n$ cells into $k$ left-justified rows with row $i$ containing $\lambda_i$ cells for $1 \leq i \leq k$.  If $(i,j)$ is the cell in the $i$th row and the $j$th column in the diagram of $\lambda$, then the {\it hook} of that cell is
\[
H_{i,j} = \{ (i,j') \ \vert \ j' \geq j \} \cup \{ (i',j) \ \vert \ i' \geq i \}
\]
and the corresponding {\it {hooklength}} of $(i,j)$ is $h_{i,j} = \vert H_{i,j} \vert$.

A {\it standard Young tableau of shape $\lambda$} is a filling of the cells in the Ferrers diagram for $\lambda$ with the integers $1$, $2$, $\dots$, $n$ such that the rows are increasing from left to right and the columns are increasing from top to bottom.  The number of standard Young tableaux of shape $\lambda$, $f^{\lambda}$, can be computed using the well-known Hook Formula of Frame, Robinson and Thrall \cite{FRT}. 

\begin{Theorem} 
If $\lambda$ is a partition of $n$, then
\[
f^{\lambda} = \frac{n!}{\Pi_{(i,j) \in \lambda} h_{i,j} }.
\]
\end{Theorem}
 

The Robinson-Schensted correspondence is a bijection $\pi\stackrel{R-S}{\longleftrightarrow}(P,Q)$
where $\pi\in S_n$, and $P$, $Q$ are standard Young tableaux of the same shape $\lambda$, as $\lambda$ varies over all partitions of $n$ \cite{Rob} \cite{Sch}.   The tableaux $P$ and $Q$ are called the {\it {P-tableau}} and {\it {Q-tableau}} of $\pi$, respectively.  The Robinson-Schensted correspondence and its applications and extensions have proved extremely useful in giving a combinatorial context to many fundamental representation theory and symmetric function results.  


Schensted \cite{Sch} proved the following theorem:
\begin{Theorem}
Given $\pi \in S_n$.  The length of the longest increasing subsequence of $\pi$ is the length of the first row of its $P$-tableau.  The length of the longest decreasing subsequence of $\pi$ is the length of the first column of its $P$-tableau.  
\end{Theorem}

The interested reader can consult Chapter 3 of Sagan's excellent book \cite{Sag} for a proof of this result and a thorough exposition of the Robinson-Schensted correspondence and the many interesting results that follow from this important algorithm.










\section{Equivalence for permutations in $S_3$}

In this section, we will consider the polynomials $F_n^{\ch}(\Pi;q)$ where $\Pi \subseteq S_3$.  To begin, fix $n \geq 0$ and let $\pi \in S_n$.  Define $f(\pi) = ((\pi^r)^{-1})^r$.  It is a well-known result that $f$ is a bijection from $S_n$ to $S_n$ that takes the major index to the charge statistic, i.e. $\maj(\pi) = \ch(f(\pi))$ (see \cite{GKi} for further exposition).   




\begin{Lemma} Fix $n \geq 0$.  Then for any permutation $\pi \in S_3$, 
\[
f: \Av_n(\pi) \rightarrow \Av_n(f(\pi)).\]
\end{Lemma}

\begin{proof}
We have that $\sigma$ contains $\pi$ if and only if $f(\sigma)$ contains $f(\pi)$ as this is obvious for reversal and inverse.  Thus $\sigma$ avoids $\pi$ if and only if $f(\sigma)$ avoids $f(\pi)$, which is equivalent to the statement of the Lemma.  
\end{proof}

We now prove the following result:

\begin{Theorem}
We have
\begin{align*}
[123]_{\ch} &= \{ 123 \}\\
[321]_{\ch} &= \{ 321 \} \\
[132]_{\ch} &= \{ 132, 312 \} = [312]_{\ch}\\
[213]_{\ch} &= \{213, 231 \} = [231]_{\ch}.
\end{align*}
\end{Theorem}



\begin{proof} 
  

Dokos et al.\ \cite{DDJ} proved 
\begin{align*}
[123]_{\maj} &= \{ 123 \}\\
[321]_{\maj} &= \{ 321 \} \\
[213]_{\maj} &= \{213, 312 \} = [312]_{\maj}\\
[132]_{\maj} &= \{ 132, 231 \} = [231]_{\maj}
.
\end{align*}

By Lemma 1, the fact that $f$ is bijective and the fact that $\maj(\sigma) = \ch(f(\sigma))$ for $\sigma \in S_n$, it follows immediately that $\pi$ is $\maj$-Wilf equivalent to $\pi'$ if and only if $f(\pi)$ is $\ch$-Wilf equivalent to $f(\pi')$.  Thus utilizing the result of Dokos et al.\ gives the theorem.
\end{proof}

Dokos et al.\ go on to classify the $\maj$-Wilf equivalence classes for all subsets of $S_3$ and one can translate these results into equivalent statements for the charge statistic if desired by utilizing the function $f$. 



\section{A Conjecture of Dokos, Dwyer, Johnson, Sagan and Selsor}

Motivated by the literature on the 2-adic valuation of the Catalan numbers and the fact that $C_n$ is odd if and only if $n=2^k-1$ for some $k \geq 0$,  Dokos et al.\ \cite{DDJ} prove a refinement of the ``if'' direction.

\begin{Theorem}(Theorem 3.5 in \cite{DDJ})
For all $k \geq 0$ we have
\[
<q^i>F_{2^k-1}^{\inv}(321;q) = \begin{cases}
1 & {\text {if }} i=0,\cr
{\text {an even number}} & {\text {if }} i \geq 1.
\end{cases} 
\]
where $\inv$ is the well known inversion statistic for permutations and $<q^i>$ denotes the coefficient of $q^i$ in the polynomial.  
\end{Theorem}



They go on to state the following conjecture (Conjecture 3.6):

{\bf {Conjecture:}}
{\it {For all $k \geq 0$ we have
\[
<q^i> F_{2^k-1}^{\maj} (321;q) = \begin{cases}
1 & {\text {if }} i = 0,\cr
{\text {an even number}} & {\text {if }} i \geq 1.
\end{cases}
\]}} 

We will prove the analogous statement for the charge statistic in this section.  



In Lascoux and Sch\"utzenberger's original paper \cite{LSc} defining the charge statistic, they give an alternate definition from which it is clear that if two permutations have the same $P$-tableau then the charge statistic on those two permutations is the same.  






\begin{Lemma}
Let $k \geq 1$.   There are an even number of 2-row standard Young tableaux of size $2^k-1$ and shape $\lambda = (2^k - i - 1, i)$ for $1 \leq i \leq 2^{k-1} - 1$.  
\end{Lemma}

\begin{proof}
By the Hook Formula, it is clear that for $k \geq 1$ and $1 \leq i \leq 2^{k-1} - 1$,
\[
f^{(2^k-i-1,i)} = \frac{2^k - 2i}{2^k-i} \binom{2^k-1}{i}.
\]

Since the binomial coefficient in the above term is an integer, it suffices to show that the fraction is even, meaning the highest power of 2 in the numerator is larger than the highest power of 2 in the denominator.  Let $2^l$ be the largest power of 2 dividing $i$, for $0 \leq l \leq k-2$.  Then $2^l$ is the largest power dividing the denominator.  In addition, $2^{l+1}$ is the largest power of 2 dividing $2i$ and thus also dividing the numerator.  Thus the fraction is even.  
\end{proof}

\begin{Theorem}
For all $k \geq 0$ we have
\[
<q^i> F_{2^k-1}^{\ch}(321;q) = \begin{cases}
1 & {\text {if }} i = 0,\cr
{\text {an even number}} & {\text {if }} i \geq 1.
\end{cases}
\]
\end{Theorem} 




\begin{proof}  
Since any inversion in a permutation $\pi$ introduces a charge value, the only permutation in $S_{2^k-1}$ with a charge value of zero is $\pi = \begin{array}{ccccc}1&2&3&\cdots&n, \end{array}$ which corresponds to the only 1-row tableau of size $2^k-1$.  Thus, by Theorem 2, all other permutations in $\Av_{2^k-1}(321)$ correspond to pairs of 2-row standard Young tableaux under the Robinson-Schensted correspondence.  It suffices to find a partition of this remaining set of permutations into subsets of even size where each subset has constant charge.  

Let $\lambda$ be a partition of $2^k-1$ into two parts.  Let $l$ be the number of standard Young tableaux of shape $\lambda$.  By Lemma 2, $l$ is even.  Let $A_1$, $A_2$, $\dots$, $A_l$ be the $l$ standard Young tableaux of shape $\lambda$.  Then since the pairs $(A_i, A_1)$, $(A_i, A_2)$, $\dots$, $(A_i, A_l)$ for $1 \leq i \leq l$ all have the same $P$-tableau, the permutations corresponding to these $l$ pairs all have the same charge.  Thus the set of permutations corresponding to 2-row standard Young tableaux of size $2^k-1$ can be partitioned into sets of permutations of even size which all have the same charge value.  This gives our result.
\end{proof}




We now obtain the conjecture of Dokos et al.\ \cite{DDJ} as a corollary.

\begin{Corollary}
For all $k \geq 0$ we have
\[
<q^i> F_{2^k-1}^{\maj}(321;q) = \begin{cases}
1 & {\text {if }} i = 0,\cr
{\text {an even number}} & {\text {if }} i \geq 1.
\end{cases}
\]
\end{Corollary} 

\begin{proof}
By Lemma 1, the function $f$ defined in Section 3 is a bijection from $\Av_n(321)$ to $\Av_n(321)$ that takes the major index to the charge statistic.  Thus applying $f$ to this set gives the result.
\end{proof}







\section{Further Research}

\vskip-2pt

There are several interesting directions for further research.  One could investigate the notion of charge Wilf equivalence for subsets $\Pi \in S_4$ as it is well-known that certain pattern avoiding sets of permutations give rise to the Schr\"oder numbers for patterns of length four.  The author is currently investigating what can be said about the coefficients of $F_n^{\ch}(\Pi; q)$ for values of $n$ other than $2^k-1$ and for sets of permutations $\Pi$ other than $\{321\}$.  In particular, the question of the 2-adic valuation of the coefficients (the highest power of 2 dividing the coefficients) remains an open and interesting question.  The author would like to thank Bruce Sagan for his helpful comments in leading to these questions and to the anonymous referee for many insightful comments on ways to improve the paper.


\vskip-5pt
\vskip-5pt

\SquashBibFurther

\begin{thebibliography}{10}

\vskip-5pt
\vskip-5pt

\bibitem{AlK}  R.~Alter and K.~Kubota.  \newblock Prime and prime power divisibility of Catalan numbers.  \newblock {\em J. Combin. Theory Ser. A.},  15:243-256, 1973.

\bibitem{Deu}  E.~Deutsch. \newblock An involution on Dyck paths and its consequences. \newblock {\em Discrete Math.}, 204:163-166, 1999. 

\bibitem{DSa}  E.~Deutsch and B.~Sagan.  \newblock Congruences for Catalan and Motzkin numbers and related sequences.  \newblock {\em Journal of Number Theory}, 117:191-215, 2006.  

\bibitem{DDJ}  T.~Dokos, T.~Dwyer, B.~Johnson, B.~Sagan and K.~Selsor.  \newblock Permutation patterns and statistics. \arxiv {1109.4976}.

\bibitem{Ege}  \"O.~E\u gecio\u glu. \newblock The parity of the Catalan numbers via lattice paths. \newblock {\em Fibonacci Quart.}, 21:65-66, 1983. 

\bibitem{FRT}  J.S.~Frame, G.~de~B.~Robinson and R.~M.~Thrall. \newblock The hook graphs of the symmetric group. \newblock {\em Canad. J. Math},  6:316-325, 1954. 

\bibitem{GKi}  K.~Garrett and K.~Killpatrick. \newblock A sign-reversing involution on bimahonian generating functions. \newblock {\em Ars Combinatoria}, 100:225-237, 2011. 

\bibitem{Knu}  D.E.~Knuth.  \newblock Permutations, matrices and generalized Young tableaux. \newblock {\em Pacific Journal of Mathematics}, 34:709-727, 1970.

\bibitem{LSc}  A.~Lascoux and M.P.~Schutzenberger. \newblock Sur une conjecture do H.O. Foulkes. \newblock {\em C.R. Acad. Sc. Paris}, 286A:323-324, 1978. 

\bibitem{Mac}  P.A.~MacMahon. \newblock Combinatory Analysis, Vol. 1, Cambridge University Press, 1915.  (Reprinted by Chelsea, NY, 1955).

\bibitem{Rob}  G.~de~B.~Robinson. \newblock On representations of the symmetric group. \newblock {\em Amer. J. Math}, 60:745-760, 1938. 

\bibitem{Sag}  B.~Sagan. \newblock The Symmetric Group, second edition, Springer, New York, NY, 2001.

\bibitem{SSa}  B.~Sagan and C.~Savage. \newblock  Mahonian pairs.  \arxiv {1101.4332}.

\bibitem{Sch}  C.~Schensted. \newblock Longest increasing and decreasing subsequences. \newblock {\em Canad. J. Math} 13:179-191, 1961. 

\bibitem{SiU}  R.~Simion and D.~Ullman. \newblock On the structure of the lattice of noncrossing partitions. \newblock {\em Discrete Math.}  98:193-206, 1991. 

\end{thebibliography}

\end{document}