<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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 &amp;=&amp; | \{i \in [n-1]\ |\ a_i &gt; a_{i+1} \}| \\
	\inv \sigma &amp;=&amp; | \{(i,j) \in [n]^2\ |\ i &lt; j \text{ and } a_i &gt; a_j \}| \\
	\maj \sigma &amp;=&amp; \sum_{i \in \Des \sigma} i \\
	\exc \sigma &amp;=&amp; |\{ i \in [n]\ |\ a_i &gt; i\}|,
\end{eqnarray*}
where $\Des \sigma = \{i \in [n-1]\ |\ a_i &gt; 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_{&gt;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 &gt; 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 &gt; 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 &gt; a_j$ and $j - i = mk$ for some positive integer $m$.
Let
\[
	\Inv_k(\sigma) = \{ (i,j) \in [n]^2 \mid a_i &gt; 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 &lt; 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 &lt; 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}, &amp; \text{ if $i \leq r$};\\
						a_ia_{i+k}a_{i+2k}\cdots a_{i + (d-1)k}, &amp; \text{ if $r &lt; i &lt; 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) &amp;=&amp; (\std \beta_{9,4}^1(\sigma), \std \beta_{9,4}^2(\sigma), \std \beta_{9,4}^3(\sigma),\std \beta_{9,4}^4(\sigma)) \\
						&amp;=&amp; (\std 815, \std 27, \std 96, \std 34) \\
						&amp;=&amp; (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 &lt; 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) &amp;=&amp; M_{n,k}A_{d+1}^r(q)A_d^{k-r}(q)\\
		F_n^{\inv_k}(q) &amp;=&amp;  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)&amp;=&amp;\sum_{\sigma\in\symm_n} q^{\des_k\sigma} \\
					&amp;=&amp; 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)\\
					&amp;=&amp; 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 &lt; 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 &amp; G_{6,k}(q) &amp; G_{8,k}(q) &amp; G_{9,k}(q) \\ \hline
		1 &amp; 6A_5(q) &amp; 8A_7(q) &amp; 9A_9(q) \\
		2 &amp; 180A_2(q)^2 &amp; 1120A_3(q)^2 &amp; 9q^{-1}A_9(q) \\
		3 &amp; 6! &amp; 8q^{-2}A_7(q) &amp; 45360A_2(q)^3 \\
		4 &amp; 180q^{-2}A_2(q)^2 &amp; 8! &amp; 9q^{-3}A_9(q) \\
		5 &amp; 6q^{-4}A_5(q) &amp; 8q^{-4}A_7(q) &amp; 9q^{-4}A_9(q) \\
		6 &amp; &amp; 1120q^{-4}A_3(q)^2 &amp; 45360q^{-3}A_2(q)^3 \\
		7 &amp; &amp; 8q^{-6}A_7(q) &amp; 9q^{-6}A_9(q) \\
		8 &amp; &amp; &amp; 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}) &amp;=&amp; \sum_{\sigma \in \Av_n(\pi^c)} \prod_{k = 1}^{n-1}t_k^{\des_k(\sigma)} \\
							  &amp;=&amp; \sum_{\sigma \in \Av_n(\pi)} \prod_{k = 1}^{n-1}t_k^{\des_k(\sigma^c)} \\
							  &amp;=&amp; \sum_{\sigma \in \Av_n(\pi)} \prod_{k = 1}^{n-1}t_k^{n-k-\des_k(\sigma)} \\
							  &amp;=&amp; 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}\} &lt; \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 &gt; 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 &gt; a_j$ for all $j &lt; 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) &amp;=&amp; \sum_{i=1}^k q^{\min(i,n-k)}F_{n-i}^{\des_k}(123,132;q) \\
							&amp;&amp; + \sum_{i=k+1}^{n-k} q^{\min(i-1,n-k-1)}F_{n-i}^{\des_k}(123,132;q) \\
							&amp;&amp; + 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 &gt; 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 &gt; 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 &gt; 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 &lt; 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 &lt; n$,
	\begin{eqnarray*}
		F_n^{\des_k}(123,312;q) &amp;=&amp; \sum_{i=1}^k q^{\max(0,n-k-i)} + \sum_{i=k+1}^{n-1} q^{\max(n-2k,i-k)} \\
							&amp;&amp; + 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 &lt; i &lt; 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) &lt; 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 &lt; n$,
	\begin{eqnarray*}
		F_n^{\des_k}(132,213;q) &amp;=&amp; \sum_{i=1}^k q^{\min(i,n-k)}F_{n-i}^{\des_k}(132,213;q) \\
						&amp;&amp; + \sum_{i = k+1}^{n-k} q^{\min(k,n-i)}F_{n-i}^{\des_k}(132,213;q) \\
						&amp;&amp; + \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 &lt; 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}

                                                                                

</pre></body></html>