\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \usepackage{mathtools} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \DeclareMathOperator{\Av}{Av} \DeclareMathOperator{\Des}{Des} \DeclareMathOperator{\des}{des} \DeclareMathOperator{\inv}{inv} \DeclareMathOperator{\maj}{maj} \DeclareMathOperator{\Exc}{Exc} \DeclareMathOperator{\exc}{exc} \DeclareMathOperator{\Inv}{Inv} \DeclareMathOperator{\lcm}{lcm} \DeclareMathOperator{\st}{st} \DeclareMathOperator{\std}{std} \DeclarePairedDelimiter{\multiset}{\{\!\{}{\}\!\}} \newcommand{\NN}{\mathbb{N}} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\symm}{\mathfrak{S}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Width-$k$ Generalizations of Classical \\ \vskip .1in Permutation Statistics } \vskip 1cm \large Robert Davis\\ Department of Mathematics\\ Michigan State University\\ East Lansing, MI 48824-1027\\ USA\\ \href{mailto:davisr@math.msu.edu}{\tt davisr@math.msu.edu}\\ \end{center} \vskip .2 in \begin{abstract} We introduce new natural generalizations of the classical descent and inversion statistics for permutations, called \emph{width-$k$ descents} and \emph{width-$k$ inversions}. These variations induce generalizations of the excedance and major statistics, providing a framework in which well-known equidistributivity results for classical statistics are paralleled. We explore additional relationships among the statistics providing specific formulas in certain special cases. Moreover, we explore the behavior of these width-$k$ statistics in the context of pattern avoidance. \end{abstract} \section{Introduction} Let $\symm_n$ denote the set of permutations $\sigma = a_1\cdots a_n$ of $[n] = \{1,\ldots,n\}$, and let $\symm = \symm_1 \cup \symm_2 \cup \cdots$. A function $\st: \symm_n \to \NN$ is called a \emph{statistic}, and the systematic study of permutation statistics is generally accepted to have begun with MacMahon \cite{MacMahonCA}. In particular, four of the most well-known statistics are the \emph{descent}, \emph{inversion}, \emph{major}, and \emph{excedance} statistics, defined respectively by \begin{eqnarray*} \des \sigma &=& | \{i \in [n-1]\ |\ a_i > a_{i+1} \}| \\ \inv \sigma &=& | \{(i,j) \in [n]^2\ |\ i < j \text{ and } a_i > a_j \}| \\ \maj \sigma &=& \sum_{i \in \Des \sigma} i \\ \exc \sigma &=& |\{ i \in [n]\ |\ a_i > i\}|, \end{eqnarray*} where $\Des \sigma = \{i \in [n-1]\ |\ a_i > a_{i+1}\}$. Given any statistic $\st$, one may form the generating function \[ F_n^{\st}(q) = \sum_{\sigma \in \symm_n} q^{\st \sigma}. \] A famous result due to MacMahon \cite{MacMahonCA} states that $F_n^{\des}(q) = F_n^{\exc}(q)$, and that both are equal to the \emph{Eulerian polynomial} $A_n(q)$. The Eulerian polynomials themselves may be defined via the identity \[ \sum_{j \geq 0} (1+j)^nq^j = \frac{A_n(q)}{(1-q)^{n+1}}. \] Another well-known result, due to MacMahon \cite{MacMahonMaj} and Rodrigues \cite{RodriguesInv}, states that $F_n^{\inv}(q) = F_n^{\maj}(q) = [n]_q!$. Foata famously provided combinatorial proofs of the equidistributivity of each; Lothaire \cite{Rearrangements} gives a treatment of these. Thus any statistic $\st$ for which $F_n^{\st}(q) = A_n(q)$ is called \emph{Eulerian}, and if $F_n^{\st}(q) = [n]_q!$ then $\st$ is called \emph{Mahonian}. These four statistics have many generalizations; in this article, we discuss new variations, induced from a simple generalization of $\des$. For each of the following definitions, we assume $n \in \ZZ_{>0}$, $k \in [n-1]$, $\emptyset \neq K \subseteq [n-1]$, and $\sigma = a_1a_2\cdots a_n \in \symm_n$. We define a \emph{width-$k$ descent} of $\sigma$ to be an index $i \subseteq [n-k]$ for which $a_i > a_{i+k}$. Thus the width-$1$ descents are the usual descents of a permutation. Let \[ \Des_k(\sigma) = \{i \in [n-k] \mid a_i > a_{i+k}\} \] denote the set of all width-$k$ descents of $\sigma$, and set \[ \des_k(\sigma) = |\Des_k(\sigma)|. \] If one is interested in descents of $\sigma$ of various widths, first let $K \subseteq [n-1]$ denote the set of widths under consideration. Then, define $\Des_K(\sigma)$ to be the multiset $\bigcup_{k\in K} \Des_k(\sigma)$, and $\des_K(\sigma) = |\Des_K(\sigma)|$. Now, define a \emph{width-$k$ inversion} of $\sigma$ to be a pair $(i,j)$ for which $a_i > a_j$ and $j - i = mk$ for some positive integer $m$. Let \[ \Inv_k(\sigma) = \{ (i,j) \in [n]^2 \mid a_i > a_j \text{ and } j - k = mk, k \in \ZZ\} \] denote the set of width-$k$ inversions of $\sigma$, and set \[ \inv_k(\sigma) = |\Inv_k(\sigma)|. \] Again, one may be interested in width-$k$ inversions for multiple values of $k$, so for $K \subseteq [n-1]$ define $\Inv_K(\sigma) = \bigcup_{k \in K} \Inv_k(\sigma)$. Additionally, let $\inv_K(\sigma) = |\Inv_K(\sigma)|$. \begin{example}\label{ex:first example} If $\sigma = 4136572$, then \[ \Des_{\{2,3\}}(\sigma) = \{1,4,5\} \text{ and } \Inv_{\{2,3\}}(\sigma) = \{(1,3),(1,7),(3,7),(4,7),(5,7)\}. \] Thus, $\des_{\{2,3\}}(\sigma) = 3$, $\inv_{\{2,3\}}(\sigma) = 5$. \end{example} As we will see in the next section, the above definitions motivate us to generalize $\exc$ and $\maj$ in such a way that well-known known relationships among $\des,\inv,\maj,\exc$ are paralleled. However, it is not very convenient to work with $\exc_K$ and $\maj_K$ directly. So, this paper will focus much more on $\des_K$ and $\inv_K$. The main focus of this paper is to explore these new statistics and their relationships among each other. While they are well-behaved for special cases of $K \subseteq [n-1]$, formulas for more general cases have been more elusive. Section~\ref{sec:avoidance} continues this exploration by considering the same statistics for classes of permutations avoiding a variety of patterns. \section{Main results} We begin with simple expressions for $\des_K(\sigma)$ and $\inv_K(\sigma)$ for a fixed $\sigma \in \symm_n$. First, we point out that if $K \subseteq [n-1]$, $j \in K$ and $ij \in K$ for some positive integer $i$, then for any $\sigma \in \symm_n$, $\inv_K(\sigma) = \inv_{K \setminus \{ij\}}(\sigma)$. This occurs because for any $k \in [n-1]$, $\inv_k(\sigma)$ counts all descents whose widths are multiples of $k$. Thus $ij$ is already accounted for in $\inv_{K \setminus \{ij\}}(\sigma)$. This follows quickly from the definitions of $\inv_k$ and $\des_k$. \begin{proposition} For any nonempty $K \subseteq [n-1]$, \[ \inv_K(\sigma) = \sum_{\emptyset \subsetneq K' \subseteq K} (-1)^{|K'| + 1}\inv_{\lcm(K')}(\sigma), \] where we set $\inv_{\lcm(K')}(\sigma) = 0$ if $\lcm(K') \geq n$. \end{proposition} \begin{proof} We first consider the case where $K = \{k\}$. The elements of $\Inv_k(\sigma)$ are pairs of the form $(i,i+jk)$ for some positive integer $j$. Such an element exists if and only if there is a width-$(jk)$ descent of $\sigma$ at $i$. Thus, $\inv_k(\sigma)$ simply counts the number of width-$jk$ descents of $\sigma$ for all possible $j$. This leads to the equality \[ \inv_k(\sigma) = \sum_{j \geq 1} \des_{jk}(\sigma). \] The formula for general $K$ then follows from inclusion-exclusion: by adding the number of all width-$k$ inversions for all $k \in K$, we are twice counting any instances of a width-$\lcm(k_1,k_2)$ inversion since such an inversion is also of widths $k_1$ and $k_2$. If $K$ contains three distinct elements $k_1,k_2,k_3$, then $\lcm(k_1,k_2,k_3)$ would have been added three times (once for each $\inv_{k_i}(\sigma)$) and subtracted three times (once for each $\inv_{\{k_i,k_j\}}(\sigma)$, $i < j$), so it must be added again for the sum. Extending this argument to range over larger subsets of $K$ results in the claimed formula. \end{proof} \begin{example} Let us return to $\sigma = 4136572$. We saw from Example~\ref{ex:first example} that $\inv_{\{2,3\}}(\sigma) = 5$, where four inversions have width $2$ and two have width $3$. But since the inversion $(1,7)$ has width both $2$ and $3$, it must also have width $\lcm(2,3) = 6$. So, it contributes two summands of $1$ and one summand of $-1$. \end{example} We come now to a function which helps demonstrate the interactions among the width-$k$ statistics. Let $n$ and $k$ be positive integers for which $n = dk + r$ for some $d,r \in \ZZ$ with $0 \leq r < k$. To each $\sigma = a_1\cdots a_n \in \symm_n$ we may then associate the set of disjoint substrings $\beta_{n,k}(\sigma) = \{\beta_{n,k}^1(\sigma),\ldots, \beta_{n,k}^k(\sigma)\}$ where \[ \beta_{n,k}^i(\sigma) = \begin{cases} a_ia_{i+k}a_{i+2k}\cdots a_{i + dk}, & \text{ if $i \leq r$};\\ a_ia_{i+k}a_{i+2k}\cdots a_{i + (d-1)k}, & \text{ if $r < i < k$.} \end{cases} \] Now, define \[ \phi: \symm_n \to \symm_{d+1}^r \times \symm_d^{k-r} \] by setting $\phi(\sigma) = (\std \beta_{n,k}^1(\sigma), \ldots, \std \beta_{n,k}^k(\sigma))$, where $\std$ is the \emph{standardization} map, that is, the permutation obtained by replacing the smallest element of $\sigma$ with $1$, the second-smallest element with $2$, etc. Note in particular that each $\std \beta_{n,k}^i(\sigma)$ is a permutation of $[d+1]$ or $[d]$. \begin{example} Suppose that $\sigma = 829317645$, suppose $k = 4$. We then have \begin{eqnarray*} \beta_{9,4}(\sigma) &=& (\std \beta_{9,4}^1(\sigma), \std \beta_{9,4}^2(\sigma), \std \beta_{9,4}^3(\sigma),\std \beta_{9,4}^4(\sigma)) \\ &=& (\std 815, \std 27, \std 96, \std 34) \\ &=& (312, 12, 21, 12). \end{eqnarray*} \end{example} The first of the identities in the following proposition was originally established by Sack and \'Ulfarsson \cite{SackUlfarsson}, though with slightly different notation. We provide an alternate proof and extend their result to width-$k$ inversions. \begin{theorem}\label{thm:main bijection} Let $n$ and $k$ be positive integers such that $n = dk + r$, where $0 \leq r < k$, and let $A_i(q)$ denote the $i^{th}$ Eulerian polynomial. Also let $M_{n,k}$ denote the multinomial coefficient \[ M_{n,k} = \binom{n}{(d+1)^{*r},d^{*(k-r)}} \] where $i^{*j}$ indicates $i$ repeated $j$ times. We then have the identities \begin{eqnarray*} F_n^{\des_k}(q) &=& M_{n,k}A_{d+1}^r(q)A_d^{k-r}(q)\\ F_n^{\inv_k}(q) &=& M_{n,k}[d+1]_q^r![d]_q^{k-r}! \end{eqnarray*} \end{theorem} \begin{proof} Let $k \in [n-1]$ and consider $\phi$ defined above. Note that $\phi$ is an $M_{n,k}$-to-one function since, given $(\sigma_1,\ldots,\sigma_k) \in \symm_{d+1}^r \times \symm_d^{k-r}$, there are $M_{n,k}$ ways to partition $[n]$ into the subsequences $\beta_{n,k}^i(\sigma)$ such that $\std \beta^i_{n,k}(\sigma) = \sigma_i$ for all $i$. Also note that \[ \des_k(\sigma) = \sum_{i=1}^k \des(\std \beta^i_{n,k}(\sigma)). \] Thus, \begin{eqnarray*} F_n^{\des_k}(q)&=&\sum_{\sigma\in\symm_n} q^{\des_k\sigma} \\ &=& M_{n,k}\left(\sum_{(\sigma_1,\ldots,\sigma_k)\in\symm_{d+1}^r \times \symm_d^{k-r}} q^{\des\sigma_1}\cdots q^{\des\sigma_k}\right)\\ &=& M_{n,k}A_{d+1}^r(q)A_d^{k-r}(q). \end{eqnarray*} This proves the first identity. The second identity follows completely analogously, with the main modification being that an element of $\Inv_k(\sigma)$ corresponds to a usual inversion in some unique $\std \beta_{n,k}^j(\sigma)$. \end{proof} We note that the sequences of coefficients of $F_n^{\des_2}(q)$ appear as OEIS sequence \seqnum{A180887}. No other nontrivial choice of $k$ appears to have been studied before, for either $\des_k$ for $\inv_k$. Given $\des_K$ and $\inv_K$, one must wonder what the corresponding generalizations of $\exc$ and $\maj$ are whose relationships with $\des_K$ and $\inv_K$ parallel that of the classical statistics. To do this, we define the multiset \[ \Exc_K(\sigma) = \bigcup_{k \in K} \biguplus_{i = 1}^k \multiset{\lceil j/k \rceil \in [n-1] \mid \lceil j/k \rceil \in \Exc(\std \beta_{n,k}^i(\sigma))} \] and set $\exc_K(\sigma) = | \Exc_K(\sigma)|$, and also set \[ \maj_K(\sigma) = \sum_{k \in K} \sum_{i \in \Des_k(\sigma)} \left\lceil \frac{i}{k} \right\rceil. \] We could equivalently state that \[ \maj_K(\sigma) = \sum_{k \in K} \sum_{i=1}^k \maj(\std \beta^i_{n,k}(\sigma)) \text{ and } \exc_K(\sigma) = \sum_{k \in K} \sum_{i=1}^k \exc(\std \beta^i_{n,k}(\sigma)). \] These are exactly the definitions needed in order to obtain identities that parallel $F_n^{\des}(q) = F_n^{\exc}(q)$ and $F_n^{\inv}(q) = F_n^{\maj}(q)$, as we will soon see. One important distinction to make between $\exc$ and $\exc_K$ is the following. If $\sigma = a_1a_2\cdots a_n$ and $\tau = b_1b_2\cdots b_n$, then even if $a_i = b_i$ for some $i$, one cannot say $i \in \Exc_K(\sigma)$ if and only if $i \in \Exc_K(\tau)$. For example, if $\sigma = 4136572$, then $1 \in \Exc_2(\sigma)$, but if $\tau = 4153627$ then $1 \notin \Exc_2(\tau)$. \begin{example} Again let $\sigma = 4136572$. We then have \[ \exc_{\{2,3\}}(\sigma) = |\multiset{1,3,1,2}| = 4 \] and \[ \maj_{\{2,3\}}(\sigma) = \left\lceil \frac{1}{2} \right\rceil + \left\lceil \frac{5}{2} \right\rceil + \left\lceil \frac{4}{3} \right\rceil = 6. \] \end{example} By constructing a nearly identical argument as in the proof Theorem~\ref{thm:main bijection}, and using the facts that $F_n^{\des}(q) = F_n^{\exc}(q)$ and $F_n^{\inv}(q) = F_n^{\maj}(q)$, we have the following corollary. \begin{corollary} The identities $F_n^{\des_k}(q) = F_n^{\exc_k}(q)$ and $F_n^{\inv_k}(q) = F_n^{\maj_k}(q)$ hold. \end{corollary} Now that we have established the analogous parallels between the four classical statistics and their width-$k$ counterparts, we wish to explore what other structure is present. A simple proposition relates $\des_k$ and $\inv_k$ when $k$ is large. \begin{corollary} For all $k \geq n/2$, $F_n^{\des_k}(q) = F_n^{\inv_k}(q)$. \end{corollary} \begin{proof} Since $k \geq n/2$, the sets $\beta_{n,k}^i(\sigma)$ contain at most two elements. So, width-$k$ descents and width-$k$ inversions of $\sigma$ are identical. \end{proof} We now show that interesting behavior occurs when considering the function \[ G_{n,k}(q) = \sum_{\sigma \in \symm_n} q^{\des_k(\sigma) - \des_{n-k}(\sigma)}. \] According to computational data, the following conjecture holds for all $n \leq 9$ and $1 \leq k < n$ for which $\gcd(k,n) = 1$. \begin{conjecture} If $\gcd(k,n) = 1$, then $G_{n,k}(q) = nq^{1-k}A_{n-1}(q)$. \end{conjecture} Several illustrative polynomials are given in Table~\ref{tab:difference data}. This does not hold more generally, and it would be interesting to determine if a general formula exists. \begin{table}\label{tab:difference data} {\renewcommand{\arraystretch}{1.2} \[ \begin{array}{c|ccc} k & G_{6,k}(q) & G_{8,k}(q) & G_{9,k}(q) \\ \hline 1 & 6A_5(q) & 8A_7(q) & 9A_9(q) \\ 2 & 180A_2(q)^2 & 1120A_3(q)^2 & 9q^{-1}A_9(q) \\ 3 & 6! & 8q^{-2}A_7(q) & 45360A_2(q)^3 \\ 4 & 180q^{-2}A_2(q)^2 & 8! & 9q^{-3}A_9(q) \\ 5 & 6q^{-4}A_5(q) & 8q^{-4}A_7(q) & 9q^{-4}A_9(q) \\ 6 & & 1120q^{-4}A_3(q)^2 & 45360q^{-3}A_2(q)^3 \\ 7 & & 8q^{-6}A_7(q) & 9q^{-6}A_9(q) \\ 8 & & & 9q^{-7}A_9(q) \\ \end{array} \] } \caption{The polynomials $G_{n,k}(q)$ for $n=6,8,9$ and $1 \leq k \leq n$.} \end{table} \begin{question} For which values of $n,k$ does there exist a closed formula for $G_{n,k}(q)$, and what is the formula? \end{question} \section{Pattern avoidance} \label{sec:avoidance} We say that a permutation $\sigma \in \symm_n$ \emph{contains the pattern} $\pi \in \symm_m$ if there exists a subsequence $\sigma'$ of $\sigma$ such that $\std(\sigma') = \pi$. If no such subsequence exists, then we say that $\sigma$ \emph{avoids the pattern} $\pi$. If $\Pi \subseteq \symm$, then we say $\sigma$ \emph{avoids} $\Pi$ if $\sigma$ avoids every element of $\Pi$. Let $\Av_n(\Pi)$ denote the set of all permutations of $\symm_n$ avoiding $\Pi$. In a mild abuse of notation, if $\Pi = \{\pi\}$, we will write $\Av_n(\pi)$. In this section, we consider the functions \[ F_n^{\st}(\Pi;q) = \sum_{\sigma \in \Av_n(\Pi)} q^{\st \sigma}, \] which specializes to $F_n^{\st}(q)$ if $\Pi = \emptyset$. In most instances, $F_n^{\des_k}$ will be the main focus, but $F_n^{\des_K}$ and $F_n^{\inv_k}$ will also make appearances. An important concept within pattern avoidance is that of Wilf equivalence. Two sets $\Pi,\Pi' \subset \symm$ are said to be \emph{Wilf equivalent} if $|\Av_n(\Pi)| = |\Av_n(\Pi')|$ for all $n$. In this case, we write $\Pi \equiv \Pi'$ to denote this Wilf equivalence, which is indeed an equivalence relation. For example, independent work of MacMahon and Knuth \cite{KnuthVol1,MacMahonCA} show that that whenever $\pi, \pi' \in \symm_3$, then $|\Av_n(\pi)| = |\Av_n(\pi')| = C_n$, where \[ C_n = \frac{1}{n+1}\binom{2n}{n} \] is the $n^{th}$ Catalan number. Proving whether $\Pi \equiv \Pi'$ is often quite difficult, and their Wilf equivalence does not imply that $F_n^{\st}(\Pi;q) = F_n^{\st}(\Pi';q)$. However, in some instances, the problems of establishing these identities have straightforward solutions by applying basic transformations on the elements of the avoidance classes. Given $\pi = a_1\cdots a_n \in \symm_m$, let $\pi^r$ denote its \emph{reversal} and $\pi^c$ denote its \emph{complement}, respectively defined by \[ \pi^r = a_ma_{m-1}\cdots a_1 \text{ and } \pi^c = (m+1-a_1)(m+1-a_2)\cdots (m+1-a_m). \] Similarly, given $\Pi \subseteq \symm$, we let \[ \Pi^r = \{\pi^c \mid \pi \in \Pi\} \text{ and } \Pi^c = \{\pi^r \mid \pi \in \Pi\} \] be the \emph{reversal} and \emph{complement} of $\Pi$, respectively. Our results of this section begin with a multivariate generalization of $F_n^{\st}(\Pi;q)$, and with showing how its specializations describe relationships among $\Pi,\Pi^r$, and $\Pi^c$. \begin{definition} Fix $\Pi \subseteq \symm$. Define \[ T_n(\Pi; t_1,\ldots,t_{n-1}) = \sum_{\sigma \in \Av_n(\Pi)} \prod_{k = 1}^{n-1}t_k^{\des_k(\sigma)}. \] \end{definition} The function $T_n$ specializes to $F_n^{\des_K}(\Pi;q)$ by setting $t_i = q$ for $i \in K$ and $t_i = 1$ for all $i \notin K$. We can also recover $F_n^{\inv_K}(\Pi;q)$ from $T_n$ by setting $t_i = q$ whenever $i \in [n-1] \cap k\ZZ$ for some $k \in K$, and setting $t_i = 1$ otherwise. Additionally, when $\Pi = \{\pi\}$, a nice duality appears, providing a mild generalization of \cite[Lemma 2.1]{DokosEtAl}. \begin{proposition}\label{prop:comp reverse rotate} For any $\Pi \subseteq \symm$, let $\Pi'$ denote either $\Pi^r$ or $\Pi^c$. We then have \[ T_n(\Pi';t_1,\ldots,t_{n-1}) = t_1^{n-1}t_2^{n-2}\cdots t_{n-1}T_n(\Pi;t_1^{-1},\ldots,t_{n-1}^{-1}). \] Consequently, \[ T_n((\Pi^r)^c;t_1,\ldots,t_{n-1}) = T_n(\Pi;t_1,\ldots,t_{n-1}). \] \end{proposition} \begin{proof} It is enough to prove the claim when the set of patterns being avoided is $\{\pi\}$ for some $\pi \in \symm_m$, since the full result follows by applying the argument to all elements of $\Pi$ simultaneously. First consider when $\pi' = \pi^c$ and $\sigma \in \Av_n(\pi)$. Because $\sigma \in \Av_n(\pi)$ if and only if $\sigma^c \in \Av_n(\pi^c)$, we have that for each $k$, $i \in \Des_k(\sigma)$ if and only if $i \notin \Des_k(\sigma^c)$. This implies $\Des_k(\sigma^c) = [n-k] \setminus \Des_k(\sigma)$, hence $\des_k(\sigma^c) = n-k-\des_k(\sigma)$. So, \begin{eqnarray*} T_n(\pi^c;t_1,\ldots,t_{n-1}) &=& \sum_{\sigma \in \Av_n(\pi^c)} \prod_{k = 1}^{n-1}t_k^{\des_k(\sigma)} \\ &=& \sum_{\sigma \in \Av_n(\pi)} \prod_{k = 1}^{n-1}t_k^{\des_k(\sigma^c)} \\ &=& \sum_{\sigma \in \Av_n(\pi)} \prod_{k = 1}^{n-1}t_k^{n-k-\des_k(\sigma)} \\ &=& t_1^{n-1}t_2^{n-2}\cdots t_{n-1}T_n(\pi;t_1^{-1},\ldots,t_{n-1}^{-1}). \end{eqnarray*} Proving that the result holds for $\pi' = \pi^r$ follows similarly. The second identity in the proposition statement holds by applying the first identity twice: first for $\Pi^r$ and then for $\Pi^c$. \end{proof} The above identities significantly reduce the amount of work needed to study $F_n^{\des_K}(\Pi;q)$ for all $\Pi \subseteq \symm_n$. For the remainder of this paper, we systematically approach $\Pi$ for $|\Pi| \leq 2$. \subsection{Avoiding singletons} By Proposition~\ref{prop:comp reverse rotate}, we immediately get \[ F_n^{\des_k}(123;q) = q^{n-k}F_n^{\des_k}(321;q^{-1}) \] and \[ F_n^{\des_k}(132;q) = F_n^{\des_k}(213;q) = q^{n-k}F_n^{\des_k}(231;q^{-1}) = q^{n-k}F_n^{\des_k}(312;q^{-1}). \] So, studying $F_n^{\des_k}(\pi;q)$ for $\pi \in \symm_3$ reduces to studying the function for a choice of one pattern from $\{123,321\}$ and one from the remaining patterns. For some choices of $\Pi$, the permutations in $\Av_n(\Pi)$ are especially highly structured, which leads to similar arguments throughout the rest of this paper. We begin with $\pi = 312$. Notice that if $a_1\cdots a_n \in \Av_n(312)$ and $a_i = 1$, then we know $\std(a_1\cdots a_{i-1}) \in \Av_{i-1}(312)$, $\std(a_{i+1}\cdots a_n) \in \Av_{n-i}(312)$, and \[ \max\{a_1,\ldots,a_{i-1}\} < \min\{a_{i+1},\ldots,a_n\}. \] \begin{proposition} For all $n$, \[ F_n^{\des_k}(312;q) = \sum_{i=1}^k C_{i-1}F_{n-i}^{\des_k}(312;q) + \sum_{i=k+1}^n qF_{i-1}^{\des_k}(312;q)F_{n-i}^{\des_k}(312;q) \] where $C_i$ is the $i^{th}$ Catalan number. \end{proposition} \begin{proof} First consider when $\sigma = a_1\cdots a_n \in \Av_n(312)$ and $a_i = 1$ for some $i \leq k$. By the discussion preceding this proposition, $j \notin \Des_k(\sigma)$ for any $j \leq i$. So, none of the $C_{i-1}$ possible permutations that make up $\std(a_1\cdots a_{i-1})$ contribute to $\des_k(\sigma)$. The only contributions to $\des_k(\sigma)$ come from $\std(a_{i+1}\cdots a_n) \in \Av_{n-i}(312;q)$. The overall contribution to $F_n^{\des_k}(312;q)$ is the second summand of the identity. Now suppose $a_i = 1$ for some $i > k$. Each choice of $a_1\cdots a_i$, contributes to $\des_k(\sigma)$ as usual, but there will be an additional width-$k$ descent produced at $i-k$. The elements $a_{i+1}\cdots a_n$ contribute to $\des_k(\sigma)$ as before. The overall contribution to $F_n^{\des_k}(312;q)$ is the first summand of the identity. Since we have considered all possible indices $i$ for which we could have $a_i = 1$, we add the two cases together and are done. \end{proof} Note that when we set $q=1$, the above recursion specializes to the well-known recursion for Catalan numbers $C_{n+1} = \sum_{i=0}^n C_iC_{n-i}$. For more about the Catalan numbers see \seqnum{A000108}. Also, when $k=1$, the coefficients of $F_n^{\des_k}(312;q)$ are the Narayana numbers, appearing in the OEIS as sequence \seqnum{A001263}. The sequence of coefficients of the polynomials $F_n^{\des_{n-1}}(312;q)$ appear as \seqnum{A026008}, where the coefficients are listed with the degree-$1$ summand first and then the constant term second. We can use the previous proposition in conjunction with Proposition~\ref{prop:comp reverse rotate} to produce formulae for $F_n^{\des_k}(\Pi;q)$ and $F_n^{\inv_k}(\Pi;q)$ whenever $\Pi$ is a single element of $\symm_3$ other than $123$ or $321$. The only nontrivial work required, then, is to compute the degrees of the two polynomials. \begin{corollary} For all $n$, \[ \deg F_n^{\des_k}(312;q) = n-k \text{ and } \deg F_n^{\inv_k}(312;q) = \sum_{i=1}^{n-k} \left\lfloor \frac{n-i}{k} \right\rfloor. \] \end{corollary} \begin{proof} The degrees of the above polynomials are given by identifying a permutation in $\Av_n(312)$ with the most possible descents. This is satisfied by $n(n-1)\cdots 21 \in \Av_n(312)$ which has $n-k$ descents of width $k$. Determining the number of width-$k$ inversions in this permutation is done similarly. \end{proof} Although $321$ is Wilf equivalent to $312$, it is not so obvious how to construct a recurrence relation for $F_n^{\des_k}(321;q)$ in general. In the special case of $k=1$, the coefficients are given by sequence \seqnum{A166073}, but the coefficients for other $k$ are not easily identifiable. To help describe the elements of $\Av_n(321)$, first let $\sigma = a_1\cdots a_n \in \symm$ and call $a_i$ a \emph{left-right maximum} if $a_i > a_j$ for all $j < i$. Thus $\sigma \in \Av_n(321)$ if and only if its set of non-left-right maxima form an increasing subsequence of $\sigma$. Indeed, if the non-left-right maxima did contain a descent, then there would be some left-right maximum preceding both elements, which violates the condition that $\sigma$ avoid $321$. Despite such a description, using it to reveal $F_n^{\des_k}(321;q)$ has thus far been unsuccessful. So, we leave the following as an open question. \begin{question} Is there a closed formula or simple recursion for $F_n^{\des_k}(321;q)$ (equivalently, for $F_n^{\des_k}(123;q)$)? \end{question} \subsection{Avoiding doubletons} At this point, we begin studying the functions $F_n^{\des_k}(\Pi;q)$ when avoiding doubletons from $\symm_3$. Recall that, by the Erd\H{o}s-Szekeres theorem \cite{ErdosSzekeres}, there are no permutations in $\symm_n$ for $n \geq 5$ that avoid both $123$ and $321$. Thus, we will not consider this pair. Additionally, the functions $F_n^{\inv_k}(\Pi;q)$ are quite unwieldy, so we will not consider these either. For our first nontrivial example, we begin with $\{123,132\}$. Permutations $a_1\cdots a_n \in \Av_n(123,132)$ have the following structure: for any $i = 1,\ldots, n$, if $a_i = n$, then the substring $a_1a_2\cdots a_{i-1}$ is decreasing and consists of the elements from the interval $[n-i+1,n-1]$. Additionally, the substring $a_{i+1}\cdots a_n$ is an element of $\Av_{n-i}(123,132)$. This structure makes it easy to show that there are $2^{n-1}$ elements of $\Av_n(123,132)$ \cite{SimionSchmidt}. \begin{proposition}\label{prop: 123 132} For all $n$ and $1 \leq k \leq n-1$, \begin{eqnarray*} F_n^{\des_k}(123,132;q) &=& \sum_{i=1}^k q^{\min(i,n-k)}F_{n-i}^{\des_k}(123,132;q) \\ && + \sum_{i=k+1}^{n-k} q^{\min(i-1,n-k-1)}F_{n-i}^{\des_k}(123,132;q) \\ && + 2^{n-\max(k+1,n-k+1)}q^{n-k-1}. \end{eqnarray*} \end{proposition} \begin{proof} Let $\sigma = a_1\cdots a_n \in \Av_n(123,132;q)$. If $a_i = n$ for $i \leq k$, then it is clear from the preceding description of the elements in $\Av_n(123,132)$ that all of $1,\ldots,\min(i,n-k)$ are elements of $\Des_k(\sigma)$. If $j > n-k$ for some $j$, then $j \notin \Des_k(\sigma)$ since $a_{j+k}$ does not exist. The remaining elements of $\Des_k(\sigma)$ arise as a width-$k$ descent of $a_{i+1}\cdots a_n$, which accounts for the factor of $F_{n-i}^{\des_k}(123,132;q)$ in the first summand. Now, if $k+1 \leq n-k$ and $a_i = n$ for $i = k+1,\ldots,n-k$, then every element of $1,\ldots,i$ except $i-k$ is an element of $\Des_k(\sigma)$. If $k+1 > n-k$, then the second summand is empty and nothing is lost by continuing to the case of $a_i = n$ for $i \geq \max(k+1,n-k+1)$. Again, the remaining elements of $\Des_k(\sigma)$ are the width-$k$ descents of $a_{i+1}\cdots a_n$, hence the additional factor of $F_{n-i}^{\des_k}(123,132;q)$. This accounts for the second summand. Finally, let $m = \max(k+1,n-k+1)$. If $a_i = n$ for $i \geq m$, then all of $1,\ldots,n-k$ are descents except $i-k$, and these are the only possible width-$k$ descents. In particular, none of $i+1,i+2,\ldots ,n$ can be the index for a width-$k$ descent. This leads to the sum \[ \sum_{i = m}^n q^{n-k-1}|\Av_{n-i}(123,132)| = \left(1 + \sum_{i = m}^{n-1} 2^{n-i-1}\right)q^{n-k-1} = 2^{n-m}q^{n-k-1}, \] which accounts for the third summand. \end{proof} Again, the sequence of coefficients for $k=1$ has appeared already, this time as sequence \seqnum{A109446}, but the sequences for nontrivial $k > 1$ appear to be entirely unstudied. Next, we consider $\{123,312\}$. We proceed similarly as before but with some minor differences, reflecting the new structure we encounter. If $\sigma = a_1\cdots a_n \in \Av_n(123,312)$ and $a_i = 1$ for some $i < n$, then $\sigma$ is of the form \[ \sigma = i(i-1)\cdots 21n(n-1)\cdots (i+2)(i+1), \] since neither subsequence $a_1\cdots a_{i-1}$ and $a_{i+1}\cdots a_n$ may contain an ascent. If $a_n = 1$, though, then $\std(a_1\cdots a_{n-1}) \in \Av_{n-1}(123,312)$. \begin{proposition} For all $n$ and $1 \leq k < n$, \begin{eqnarray*} F_n^{\des_k}(123,312;q) &=& \sum_{i=1}^k q^{\max(0,n-k-i)} + \sum_{i=k+1}^{n-1} q^{\max(n-2k,i-k)} \\ && + qF_{n-1}^{\des_k}(123,312;q) \end{eqnarray*} \end{proposition} \begin{proof} Suppose $a_i = 1$ for some $i \leq k$. Using the description of elements in $\Av_n(123,312)$, we know there are $n-k-i$ width-$k$ descents. Since there is only one such permutation for each $i$, we simply add all of the $q^{n-k-i}$, so long as $n-k-i \geq 0$. If this inequality does not hold, then there are no width-$k$ descents in this range. This accounts for the first summand. The second summand is computed very similarly to that of the second summand in Proposition~\ref{prop: 123 132}. The final summand is a direct result of noting that when $a_n = 1$, then $(a_1-1)\cdots (a_{n-1}-1)$ may be any element of $\Av_{n-1}(123,312;q)$, which accounts for the factor $F_{n-1}^{\des_k}(123,312;q)$. For each of these choices, we know $n-k \in \Des_k(\sigma)$, hence the factor of $q$. Adding the sums results in the identity claimed. \end{proof} Now we consider $\{132,231\}$. Note that if $a_1\cdots a_n \in \Av_n(132,231)$, then $a_i \neq n$ for any $1 < i < n$. If $a_1 = n$, then $\std(a_2\cdots a_n) \in \Av_{n-1}(132,231)$, and similarly if $a_n = n$. Once again, this allows us to quickly compute that $|\Av_n(132,231)| = 2^{n-1}$. \begin{proposition}\label{prop: 132 231} Let $K = \{k_1,\ldots,k_l\}$ be a nonempty subset of $[n-1]$ whose elements are listed in increasing order. We then have \[ F_n^{\des_K}(132,231;q) = \prod_{i=1}^{l+1} (1+q^{i-1})^{k_i - k_{i-1}} \] where $k_0 = 1$ and $k_{l+1} = n$. \end{proposition} \begin{proof} It follows from the description of elements in $\Av_n(132,231)$ that there are two summands in a recurrence for $F_n^{\des_K}(132,231;q)$: one corresponding to $a_1 = n$ and one corresponding to $a_n = n$. When $a_1 = n$, then there are $|K| = l$ copies of $1 \in \Des_K(\sigma)$; if $a_n = n$, then $a_n$ makes no contribution to $\Des_K(\sigma)$. Thus, by deleting $n$ from $\sigma$, we get the recurrence \[ F_n^{\des_K}(132,231;q) = (1+q^l)F_{n-1}^{\des_K}(132,231;q). \] Repeating this, a factor of $1+q^l$ appears until we get to \[ F_n^{\des_K}(132,231;q) = (1+q^l)^{n-k_l}F_{k_l}^{\des_K}(132,231;q). \] At this point, note that \[ F_{k_l}^{\des_K}(132,231;q) = F_{k_l}^{\des_{K \setminus \{k_l\}}}(132,231;q). \] Repeating the previous argument ends up with the identity claimed. \end{proof} Next, consider $\{132,213\}$. If $\sigma = a_1\cdots a_n \in \Av_n(132,213)$, then if $a_i = n$ for any $i$, then $a_1\cdots a_{i-1}$ must be increasing in order to avoid $213$. Moreover, \[ \max(a_{i+1},\cdots,a_n) < a_1 \] in order to avoid $132$, and $\std(a_{i+1}\cdots a_n) \in \Av_{n-i}(132,213)$. \begin{proposition} For all $n$ and $1 \leq k < n$, \begin{eqnarray*} F_n^{\des_k}(132,213;q) &=& \sum_{i=1}^k q^{\min(i,n-k)}F_{n-i}^{\des_k}(132,213;q) \\ && + \sum_{i = k+1}^{n-k} q^{\min(k,n-i)}F_{n-i}^{\des_k}(132,213;q) \\ && + \sum_{i = \max(k+1,n-k+1)}^n q^{n-i}F_{n-i}^{\des_k}(132,213;q). \end{eqnarray*} \end{proposition} \begin{proof} The proof of this is entirely analogous to the proof of Proposition~\ref{prop: 123 132}. \end{proof} In this case, when $k = 2$, the sequence of coefficients as $n$ grows is the sequence \seqnum{A208343}. No other nontrivial choice of $k$ appears to have been previously studied. Additionally, for all remaining choices of $\Pi$ we consider, the instances of previously-studied sequences appear to be only when $k=1$. Next, we consider $\{132,312\}$. For each $i = 1,\ldots, n-1$, either $a_{i+1} = \max\{a_1,\ldots,a_i\} + 1$ or $a_{i+1} = \min\{a_1,\ldots,a_i\} - 1$. This doubleton often results in especially pleasant formulas, and our results are no exception. \begin{proposition}\label{prop: 132 312} Let $K = \{k_1,\ldots,k_l\}$ be a nonempty subset of $[n-1]$ whose elements are listed in increasing order. We then have \[ F_n^{\des_K}(132,312;q) = \prod_{i=1}^{l+1} (1+q^{i-1})^{k_i - k_{i-1}} \] where $k_0 = 1$ and $k_{l+1} = n$. \end{proposition} \begin{proof} From the description of elements $\sigma = a_1\cdots a_n \in \Av_n(132,312)$, we know that either $a_n = 1$ or $a_n = n$. In the former case, $n-k \in \Des_K(\sigma)$ for each $k \in K$, and in the latter case, $n-k \notin \Des_K(\sigma)$ for each $k \in K$. This leads to the recurrence \[ F_n^{\des_K}(132,312;q) = (1+q^l)F_{n-1}^{\des_K}(132,312;q). \] Following an analogous argument as in the proof of Proposition~\ref{prop: 132 231} obtains the result. \end{proof} From the general formula given above, we are able to quickly determine $F_n^{\inv_k}(132,312;q)$. \begin{corollary} For fixed $n,k$, write $n = dk + r$ for unique nonnegative integers $d,r$ such that $0 \leq r < k$. We then have \[ F_n^{\inv_k}(132,312;q) = F_n^{\inv_k}(132,231;q) = 2^{k-1}(1+q^d)^r\prod_{i = 1}^{d-1} (1+q^i)^k. \] \end{corollary} \begin{proof} This is a direct consequence of the general formulas from Propositions~\ref{prop: 132 231} and \ref{prop: 132 312}, and recalling that \[ F_n^{\inv_k}(\Pi;q) = F_n^{\des_{[n-1] \cap k\ZZ}}(\Pi;q). \] \end{proof} \section{Acknowledgments} The author thanks Bruce Sagan and the anonymous referee for their many helpful comments. \begin{thebibliography}{9} \bibitem{DokosEtAl} Theodore Dokos, Tim Dwyer, Bryan~P. Johnson, Bruce~E. Sagan, and Kimberly Selsor, Permutation patterns and statistics, {\em Discrete Math.} {\bf 312} (2012), 2760--2775. \bibitem{ErdosSzekeres} Paul Erd{\H{o}}s and George Szekeres, A combinatorial problem in geometry, {\em Compositio Math.} {\bf 2} (1935), 463--470. \bibitem{KnuthVol1} Donald~E. Knuth, {\em The {A}rt of {C}omputer {P}rogramming, {V}ol. 1: {F}undamental {A}lgorithms}, 2nd printing, Addison-Wesley, 1969. \bibitem{Rearrangements} M.~Lothaire, {\em Combinatorics on Words}, Vol.~17 of {\em Encyclopedia of Mathematics and its Applications}, Addison-Wesley, 1983. \bibitem{MacMahonMaj} Percy~A. MacMahon, The indices of permutations and the derivation therefrom of functions of a single variable associated with the permutations of any assemblage of objects, {\em Amer. J. Math.} {\bf 35} (1913), 281--322. \bibitem{MacMahonCA} Percy~A. MacMahon, {\em Combinatory {A}nalysis}, Chelsea Publishing Co., 1960. \bibitem{RodriguesInv} Olinde Rodrigues, Note sur les inversions, ou derangements produits dans les permutations, {\em Journal de Math{\'e}matiques} {\bf 4} (1839), 236--240. \bibitem{SackUlfarsson} Joshua Sack and Henning {\'U}lfarsson, Refined inversion statistics on permutations, {\em Electron. J. Combin.} {\bf 19} (1) (2012), Paper \#P29. \bibitem{SimionSchmidt} Rodica Simion and Frank~W. Schmidt, Restricted permutations, {\em European J. Combin.} {\bf 6} (1985), 383--406. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 05A05; Secondary 05A15. \noindent \emph{Keywords:} permutation statistics, pattern avoidance, generating function. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000108}, \seqnum{A001263}, \seqnum{A026008}, \seqnum{A109446}, \seqnum{A166073}, \seqnum{A180887}, and \seqnum{A208343}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received January 19 2017; revised version received May 31 2017. Published in {\it Journal of Integer Sequences}, June 25 2017. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}