\documentclass[12pt]{article} \usepackage{e-jc} \specs{P7}{19}{2012} %\usepackage[active]{srcltx} \usepackage{amsmath, latexsym, amssymb} \usepackage{graphicx} % SRC Specials for DVI Searching %% The lines between the two rows of %'s are more or less compulsory. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \makeatother \pagestyle{plain} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % THEOREM Environments --------------------------------------------------- \newtheorem{thm}{Theorem}[section] \newtheorem{conj}{Conjecture}[section] \newtheorem{cor}[thm]{Corollary} \newtheorem{lem}[thm]{Lemma} \newtheorem{prop}[thm]{Proposition} \newtheorem{defn}{Definition}[section] \newtheorem{exa}{Example}[section] \newtheorem{rem}{Remark}[section] \numberwithin{equation}{section} \numberwithin{equation}{section} \newenvironment{proof}{\medskip\noindent{\it Proof.\ }}{\hfill \mbox{$\Box$}\medskip} \newenvironment{ack}{\bigskip\noindent{\textbf{Acknowledgement}\ }} % MATH ------------------------------------------------------------------- \newcommand{\qbinom}[2]{{\genfrac{[}{]}{0pt}{}{#1}{#2}}} %\newcommand{\qbinomq}[2]{{\genfrac{[}{]}{0pt}{}{#1}{#2}}_q} \newcommand{\qtrinom}[4]{{\genfrac{[}{]}{0pt}{}{#1}{#2,#3,#4}}} \newcommand{\btop}[2]{{\genfrac{}{}{0pt}{}{#1}{#2}}} \newcommand{\cF}{\mathcal{F}} \newcommand{\bx}{\mathbf{x}} \newcommand{\ba}{\mathbf{a}} \newcommand{\inv}{\mathrm{inv}} \newcommand{\des}{\mathrm{des}} \newcommand{\Des}{\mathrm{Des}} %%% ---------------------------------------------------------------------- %\title{On the joint distribution of inv and des statistic for permutations with bounded rise} % Enter your title between curly braces \title{Descents of Permutations in a Ferrers Board} \author{Chunwei Song\thanks{Supported in part by NSF China grant \#10726011 and by the Scientific Research Foundation for ROCS, Chinese Ministry of Education.} \\ \small School of Mathematical Sciences, LMAM, Peking University,\\[-0.8ex] \small Beijing 100871, P. R. China\\ \and Catherine Yan\thanks{Supported in part by NSF grant \#DMS-0653846 and NSA grant \#H98230-11-1-0167.} \\ \small Department of Mathematics, Texas A\&M University, \\[-0.8ex] \small College Station, TX 77843-3368 } \date{\dateline{Sep 6, 2011}{Dec 20, 2011}{Jan 6, 2012}\\ \small Mathematics Subject Classification: 05A05, 05A15, 05A30} \begin{document} \maketitle \begin{abstract} The classical Eulerian polynomials are defined by setting $$ A_n(t)= \sum_{\sigma \in \mathfrak{S}_n} t^{1+\mathrm{des}(\sigma)}= \sum_{k=1}^n A_{n,k} t^k $$ where $A_{n,k}$ is the number of permutations of length $n$ with $k-1$ descents. Let $A_n(t, q) = \sum_{\pi \in \mathfrak{S}_n} t^{1+\des(\pi)}q^{\inv(\pi)} $ be the $\inv$ $q$-analogue of the classical Eulerian polynomials whose generating function is well known: \begin{eqnarray}\label{invq2abs} \sum_{n \geq 0} \frac{u^n A_n(t, q)}{[n]_q!} = \frac{1}{\displaystyle 1-t\sum_{k \geq 1} \frac{(1-t)^ku^k}{[k]_q!}}. \label{perm_gf abs} \end{eqnarray} In this paper we consider permutations restricted in a Ferrers board and study their descent polynomials. For a general Ferrers board $F$, we derive a formula in the form of permanent for the restricted $q$-Eulerian polynomial $$ A_F(t,q) := \sum_{\sigma \in F} t^{1+\des(\sigma)} q^{\inv(\sigma)}. $$ If the Ferrers board has the special shape of an $n\times n$ square with a triangular board of size $s$ removed, we prove that $A_F(t,q)$ is a sum of $s+1$ terms, each satisfying an equation that is similar to \eqref{invq2abs}. Then we apply our results to permutations with bounded drop (or excedance) size, for which the descent polynomial was first studied by Chung et al. ({\em European J. Combin.}, 31(7) (2010): 1853-1867). Our method presents an alternative approach. \end{abstract} \section{Introduction} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % notation, background of Eulerian polynomials, lattice path, outline of the paper % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Let $\mathfrak{S}_n$ denote the symmetric group of order $n$. Given a permutation $\sigma \in \mathfrak{S}_n$, let $\Des (\sigma)$ be the \emph{descent set} of $\sigma$, i.e., $\Des (\sigma) = \{ i | \sigma_i > \sigma_{i+1}, 1 \leq i \leq n-1 \}$, and let $\des(\sigma) = |Des(\sigma)|$ denote the number of descents of $\sigma$. For $D \subseteq \{1,2, \dots, n-1\}$, %For $D \subseteq [n-1]:=\{1,2, \dots, n-1\}$, %be a subset of $[n-1]$ with %$1 \leq d_1 < d_2 < \cdots < d_k \leq n-1$. By convention, also let $d_0=0$ and %$d_{k+1}=n$. we denote by $\alpha_n(D)$ the number of permutations $\pi \in \mathfrak{S}_n$ whose descent set is \emph{contained} in $D$, and by $\beta_n (D)$ the number of permutations $\pi \in \mathfrak{S}_n$ whose descent set is \emph{equal} to $D$. In symbols, \[ \alpha_n(D) :=|\{\sigma \in \mathfrak{S}_n: Des(\sigma) \subseteq D\}|, \qquad \beta_n(D) := |\{\sigma \in \mathfrak{S}_n: Des(\sigma) = D\}|. \] Let $D=\{d_1, d_2, \dots, d_k\}$ where $1 \leq d_1 < \cdots < d_k \leq n-1$. For convenience, also let $d_0=0$ and $d_{k+1}=n$. Then the following formulas for $\alpha_n(D)$ and $\beta_n(D)$ are well-known (see, for example, \cite[p.69]{Stan1}): \begin{align} \alpha_n(D)&= \binom{n}{d_1, d_2-d_1, \dots, n-d_k} \label{alpha} \\ \beta_n(D)& =n! \det\left[\frac{1}{(d_{j+1}-d_i)!}\right] = \det \left[ \binom{n-d_i}{d_{j+1}-d_i}\right], \label{beta} \end{align} where $(i, j) \in [0,k] \times [0,k]$ in the matrix of equation \eqref{beta}. A $q$-analogue of the above formulas is given by considering the permutation statistic $\inv (\sigma)$, where $\inv (\sigma)=\sum_{i < j} \chi(\sigma_i > \sigma_j)$. By convention, the symbol $\chi(P)$ is 1 if the statement $P$ is true and 0 if not. See \cite[Example 2.2.5]{Stan1}. Explicitly, let \begin{align*} \alpha_n(D, q)=\sum_{\pi \in \mathfrak{S}_n: \Des(\pi)\subseteq D} q^{\inv(\pi)}, \qquad \beta_n(D, q)=\sum_{\pi \in \mathfrak{S}_n: \Des(\pi)=D} q^{\inv(\pi)}. \end{align*} Then \begin{align} \alpha_n(D,q)&= \qbinom{n}{d_1, d_2-d_1, \dots, n-d_k} =\frac{[n]!}{[d_1]! [d_2-d_1]!\cdots [n-d_k]!} \label{alphaq}\\ \beta_n(D,q)&=[n]! \det\left[\frac{1}{[d_{j+1}-d_i]!} \right]= \det \left[ \qbinom{n-d_i}{d_{j+1}-d_i} \right], \label{betaq} \end{align} where $(i,j) \in [0,k]\times [0,k]$ as before. Here we use the standard notation $$[n] : = (1-q^{n})/(1-q),\qquad [n]! : = [1][2]\cdots[n], \qquad \qbinom{n}{k} : = \frac{[n]_q!}{[k]![n-k]!} $$ for the $q$-analogue of the integer $n$, the $q$-factorial, and the $q$-binomial coefficient, respectively. %Sometimes it is possible to omit the base $q$ and write simply as $[n]$, %$[n]!$, and ${\qbinom{n}{k}}$, etc., but here in this paper we will %keep it for clarity. %in this paper whenever it is clear from the context. %Also let $(a;q)_{n} : = (1-a)(1-q %a)\cdots(1-q^{n-1} a)$ be the $q$-rising factorial, and $(a;q)_\infty=\prod_{i=0}^\infty (1-aq^i)$. Sometimes it is necessary to write the base $q$ explicitly as in $[n]_q, [n]_q!$, and ${\qbinom{n}{k}}_q$, etc., but we omit $q$ in this paper as we do not use the analogues of any other variables. %whenever it is clear from the context. The classical Eulerian polynomials are defined by setting \[ A_n(t)= \sum_{\sigma \in \mathfrak{S}_n} t^{1+\mathrm{des}(\sigma)}= \sum_{k=1}^n A_{n,k} t^k, \] where $A_{n,k}$ is called the Eulerian number that denotes the number of permutations of length $n$ with $k-1$ descents. Let $A_0(t)=1$. The polynomials $A_n(t)$ have the generating function (see e.g. Riordan \cite{Riordan58}) \begin{eqnarray} \sum_{n \geq 0} A_n(t) \frac{u^n}{n!} = \frac{1}{\displaystyle 1-t\sum_{k \geq 1} \frac{(1-t)^{k-1}u^k}{k!}} =\frac{1-t}{1-te^{u(1-t)}}. \end{eqnarray} Let $A_n(t, q) = \sum_{\pi \in \mathfrak{S}_n} t^{1+\des(\pi)}q^{\inv(\pi)} $ be the $\inv$ $q$-analogue of the Eulerian polynomials. Stanley \cite{Sta76} showed that \begin{eqnarray}\label{invq} \sum_{n \geq 0} \frac{u^n A_n(t, q)}{[n]!} = \frac{1-t}{1-t E(u(1-t);q)}, \end{eqnarray} where \[ E(z;q)= \sum_{n \geq 0} \frac{z^n}{[n]!}. \] By simple manipulations we can see that an equivalent form of \eqref{invq} is \begin{eqnarray}\label{invq2} \sum_{n \geq 0} \frac{u^n A_n(t, q)}{[n]!} = \frac{1}{\displaystyle 1-t\sum_{k \geq 1} \frac{(1-t)^{k-1} u^k} {[k]!}}. \label{perm_gf} \end{eqnarray} Alternative proofs of \eqref{invq2} have been given by Gessel \cite{Gessel77} and Garsia \cite{Gar79}. In this paper we consider permutations with restricted positions, and extend the above results to descent polynomials of permutations in a Ferrers board. Traditionally a permutation $\sigma \in \mathfrak{S}_n$ is also represented as a 01-filling of an $n$ by $n$ square board: Reading from left to right and bottom to top, we simply put a $1$ in the $i$th row and the $j$th column whenever $\sigma_{i}=j$ for $i=1, \ldots, n$. Given integers $0 < r_1 \leq r_2 \leq \cdots \leq r_n$, the Ferrers board of shape $(r_1, \dots, r_n)$ is defined by \[ F=\{(i,j): 1 \leq i \leq n, 1 \leq j \leq r_i\}. \] In the following we identify a permutation $\sigma$ with its 01-filling representation, and say that $\sigma$ is in a Ferrers board $F$ if all the cells $(i, \sigma_i)$ are in $F$. In Section 2 we extend the formulas \eqref{alphaq} and \eqref{betaq} to the set of permutations on a fixed Ferrers shape with $n$ rows and $n$ columns, and derive a permanent formula for the restricted $q$-Eulerian polynomial \[ A_F(t,q) := \sum_{\sigma \in F} t^{1+\des(\sigma)} q^{\inv(\sigma)}. \] In Section 3 we focus on the Ferrers board that is obtained from the $n\times n$ square by removing a triangular board of size $s$, and prove that the restricted $q$-Eularian polynomial is a sum of $s+1$ terms, each determined by an equation that generalizes \eqref{invq2}. Finally in Section 4, we apply our results to permutations with bounded drop (or excedance) size, for which the descent polynomial was first studied by Chung, Claesson, Dukes and Graham \cite{CCDG}. Our method presents an alternative approach to the results in \cite{CCDG}. %%%%%%was \cite{CCDK10} \vspace{.4cm} \noindent \textbf{Notation on lattice path} Here we recall some notation and results about the counting of lattice paths with a general right boundary. These results offer the main tool to describe permutations restricted in a Ferrers board. For a reference on lattice path counting, see Mohanty \cite{Mohanty79}. A lattice path $P$ is a path in the plane with two kinds of steps: a unit north step $N$ or a unit east step $E$. If $x$ is a positive integer, a lattice path from the origin $(0,0)$ to the point $(x,n)$ can be coded by a length $n$ non-decreasing sequence $(x_1,x_2,\dots, x_n)$, where $0 \leq x_i \leq x$ and $x_i$ is the $x$-coordinate of the $i$th north step. For example, let $x=5$ and $n=3$. Then the path $EENENNEE$ is coded by $(2,3,3)$. In general, let $\mathbf{s}$ be a non-decreasing sequence with positive integer terms $s_1, s_2, \dots, s_n$. A lattice path from $(0,0)$ to $(x,n)$ is one with the right boundary $\mathbf{s}$ if $x_i < s_i$ for $1 \leq i \leq n$. If $x \geq s_n$, then the number of lattice paths from $(0,0)$ to $(x,n)$ with the right boundary $\mathbf{s}$ does not depend on $x$. Let $Path_n(\mathbf{s})$ be the set of lattice paths from $(0,0)$ to $(s_n, n)$ with the right boundary $\mathbf{s}$, and $LP_n(\mathbf{s})$ be the cardinality of $Path_n(\mathbf{s})$. For a given sequence $\mathbf{s}=(s_1, s_2, \dots, s_n)$, let \[ LP_n(\mathbf{s};q) = \sum_{P \in Path_n (\mathbf{s}) } q^{area(P)}, \] where $area(P)=\sum_{i=1}^n x_i$ is the area enclosed by the path $P$, the $y$-axis, and the line $y=n$. Hence $LP_n(\mathbf{s})=LP_n(\mathbf{s};1)$. In this paper we will also allow the entries $s_i$ to satisfy $s_1 \geq s_2 \geq \cdots \geq s_n$, in which case \[ LP_n(\mathbf{s}; q) = LP_n( (s_n, s_n,\dots, s_n); q) = \qbinom{s_n+n-1}{n}. \] In particular $ LP_n( (n+1, n+1, \ldots, n+1); q) = \qbinom{2n}{n}$. It is also easy to see that \[ LP_n( (1, 2, \ldots, n); q) = C_n (q), \] where $C_n (q)$ is Carlitz-Riordan's $q$-Catalan number \cite{CR64}. \section{Descents of permutations in Ferrers boards} %Let's use 01-fillings of an $n \times n$ square board to represent permutations in $\mathfrak{S}_n$. %Given $\pi \in \mathfrak{S}_n$, for $i = 1, \ldots, n$, %we put a $1$ in the %$i$th row (from bottom to top) and the $j$th column (from left to right), whenever $\pi_{i}=j$. %This establishes a bijection between the permutations in $\mathfrak{S}_n$ and the 01-fillings of the %$n \times n$ square %board. %For a 01-fillings $F$ of a Ferrers diagram in which every row has exactly one 1, define %$\Des(F) = \{ i: \text{ the two 1's in row $i$ and row $i+1$ form an SE chain}\}$, and %$\des(F)=|Des(F)|$. Let $se_2$ be the number of SE-chains of size 2 in $F$. %Then under the bijection $\inv(\sigma)$ becomes $se_2$, and %$\Des(\sigma)$ becomes the descent set of the filling. %Any relation on the statistics of $\des$ and $\inv$ of permutations can be viewed as special cases for %the statistics $\des$ and $se_2$ of 01-fillings of Ferrers diagrams. %Our objective is to extend the results on permutations to 01-fillings of more general Ferrers diagrams. Let $F$ be a Ferrers board with $n$ rows and $n$ columns, which is aligned on the top and left. Index the rows from bottom to top, and columns from left to right. Let $r_i$ be the size of row $i$. Hence $1 \leq r_1\leq r_2 \leq \cdots \leq r_n=n$. %Denote by $\cF$ the set of all %01-fillings of $A$ with $n$ 1's, such that there is exactly one $1$ in each row and each column. %That is, $F$ is the set of all permutations in the restricted board $A$. For a set $D=\{d_1, d_2, \dots, d_k\}$ with $1 \leq d_1 < \cdots < d_k \leq n-1$, let $\beta_F(D)$ be the number of permutations in $F$ with the descent set $D$, and $\alpha_F(D)$ be the number of permutations in $F$ whose descent set is contained in $D$. %In symbols, %\[ % \alpha_A(D)=\sum_{T \subseteq D} \beta_A(T), % \qquad \beta_A(D)=\sum_{T \subseteq D} (-1)^{|D-T|} \alpha_A(T). %\] The $\inv$ $q$-analogues of $\alpha_F(D)$ and $\beta_F(D)$ are defined by \[ \alpha_F(D,q)= \sum_{\sigma \in F: \Des(\sigma) \subseteq D} q^{\inv(\sigma)}, \qquad \beta_F(D,q) = \sum_{\sigma \in F: \Des(\sigma)=D} q^{\inv(\sigma)}. \] Clearly $\alpha_F(D, 1)=\alpha_F(D)$ and $\beta_F(D,1)=\beta_F(D)$. The Inclusion-Exclusion Principle implies that \[ \alpha_F(D,q)=\sum_{T \subseteq D} \beta_F(T,q), \qquad \beta_F(D,q)=\sum_{T \subseteq D} (-1)^{|D-T|} \alpha_F(T,q). \] We shall show that $\alpha_F(D,q)$ and $\beta_F(D,q)$ can be expressed in terms of $LP_n(\mathbf{s}, q)$, the area enumerator of lattice paths with proper right boundaries and lengths. Let's first compute $\alpha_F(D,q)$. To get a permutation $\sigma$ in $F$ satisfying $\Des(\sigma) \subseteq D$, we first choose $x_1 < x_2 < \cdots < x_{d_1}$ such that $1 \leq x_i \leq r_i$, and put a $1$ in the cell $(x_i, i)$ for $1 \leq i \leq d_1$. Then choose $x_{d_1+1} < x_{d_1+2} < \cdots < x_{d_2}$ such that $1 \leq x_i \leq r_i$, and put a $1$ in the cell $(x_i, i)$ for $d_1 < i \leq d_2$, and so on. We say that the cell $(i,j)$ is a $1$-cell if it is filled with a 1. It is clear that an inversion of $\sigma$ corresponds to a southeast chain of size 2 in the filling, i.e. a pair of 1-cells \{ $(x_{i_1}, i_1), (x_{i_2}, i_2)$ \} such that $i_1 < i_2$ while $x_{i_1} > x_{i_2}$. For $1 \leq i \leq d_1$, the $1$-cell in the $i$th row (i.e. $y=i$) has exactly $x_i-i$ many other 1-cells lying above it and to its left. Hence the 1-cell in the $i$th row contributes $x_i-i$ to the statistic $\inv(\sigma)$, and all the 1-cells in the first $d_1$ rows contributed \[ (x_1-1) + (x_2-2) + \cdots +(x_{d_1}-d_1) \] to the statistic $\inv(\sigma)$. Note that $0 \leq x_1 -1 \leq x_2-2 \leq \cdots \leq x_{d_1}-d_1$, and $x_i-i < r_i-i+1$. Hence the number of choices for the sequence $(x_1, \dots, x_{d_1})$ is exactly the number of lattice paths from $(0,0)$ to $(r_{d_1}-d_1+1,d_1)$ with the right boundary $(r_1, r_2-1, \dots, r_{d_1}-d_1+1)$, and $\sum_{i=1}^{d_1} (x_i-i)$ is the area of the corresponding lattice path. Therefore the first $d_1$ rows of $F$ contribute a factor of $LP_{d_1}((h_1,\dots, h_{d_1}); q)$ to $\alpha_F(D, q)$. Let $\mathbf{h} = (h_1, h_2, \dots, h_n)$ where $h_i=r_i-i+1$. Let the $i$-th block of $F$ consist of rows $d_{i-1}+1$ to $d_i$. Applying the above analysis to the $i$-th block of the Ferrers board $F$ for $i=2, \dots, k+1$, we get that \begin{thm} \label{thm-alpha} \begin{eqnarray} \label{eq-alpha} \alpha_F (D,q) = \sum_{\sigma \in F: \Des(\sigma)\subseteq D} q^{\inv(\sigma)} = \prod_{i=0}^k LP_{d_{i+1}-d_i} ((h_{d_i+1}, \dots, h_{d_{i+1}}); q) % LP_{d_2-d_1} ( (h_{d_1+1}, \dots, h_{d_2}); q) \cdots LP_{n-d_k} ( (h_{d_k+1},\dots, h_n);q) \end{eqnarray} where we use the convention that $d_0=0$ and $d_{k+1}=n$. \end{thm} Accordingly, \begin{eqnarray*} \beta_F(D,q)& =& \sum_{T \subseteq D} (-1)^{|D-T|} \alpha_F(T,q ) \\ &=&\sum_{1 \leq i_1 < i_2 < \dots < i_j \leq k} (-1)^{k-j} f(0, i_1) f(i_1, i_2) \dots f(i_j, k+1) \end{eqnarray*} where \begin{eqnarray} \label{f_ij} f(i,j)=\left\{ \begin{array}{ll} LP_{d_j-d_i}(h_{d_i+1}, \dots, h_{d_j}); q) & \text{ if } i < j \\ 1 & \text{ if } i=j \\ 0 & \text{ if } i > j. \end{array} \right. \end{eqnarray} %Shortly we will see the reason to assign the values $f(i,j)$ for $i \geq j$. Following the discussion of Stanley \cite[p.69]{Stan1}, we obtain that \begin{thm} \label{thm-beta} $\beta_F(D,q)$ is the determinant of a $(k+1)\times (k+1)$ matrix with its $(i,j)$ entry $f(i, j+1)$, $0 \leq i,j \leq k$. That is, \begin{eqnarray} \label{betaboard} \beta_F (D,q) = \det[f_{i,j+1}]_0^k \end{eqnarray} where $f(i,j)$ is given by \eqref{f_ij}. \end{thm} When the Ferrers board $F$ is an $n \times n$ square, $h_i=n-i+1$, and \[ LP_{j-i}((h_{i+1}, \dots, h_j); q) =\qbinom{n-i}{j-i}. \] Theorems \ref{thm-alpha} and \ref{thm-beta} reduce to the classical results \[ \sum_{\btop{\pi \in \mathfrak{S}_n }{Des(\pi)\subseteq D}} q^{\inv (\pi)} = \qbinom{n}{d_1, d_2-d_1, \dots, n-d_k} \] and \[ \sum_{\btop{\pi \in \mathfrak{S}_n}{ Des(\pi)= D}} q^{\inv (\pi)} = \det \left[ \qbinom{n-d_i}{d_{j+1}-d_i} \right]_0^k. \] For a general Ferrers board with $n$ rows and $n$ columns, let's check two extreme cases: $D=\{1,2,\ldots,n-1\}$ and $D=\emptyset$. \begin{itemize} \item Case 1. $D=\{1,2,\ldots,n-1\}$: \ Theorem \ref{thm-alpha} yields the identity \begin{eqnarray} \label{[n-1]} \sum_{\sigma \in F} q^{\inv(\sigma)} = \alpha_F (=\{1,2,\ldots,n-1\},q) = \prod_{i=1}^n LP_1((h_i) ; q) = \prod_{i=1}^n [h_i]. \end{eqnarray} Note that permutation fillings of a Ferrers board with $n$ rows and $n$ columns correspond to complete matchings of $\{1, \ldots, 2n \}$ with fixed sets of left endpoints and right endpoints, and an inversion of the permutation is exactly a nesting of the matching; See de Mier \cite{deMier06} and Kasraoui \cite{Kas10}. To see this, for a given Ferrers board $F$ with $n$ rows and $n$ columns, one traverses the path from the lower-left corner to the top-right corner, and records the path by its steps $a_1,a_2,\ldots, a_{2n}$ where $a_i=E$ if the $i$th step is East, and $a_i=N$ if the $i$th step is North. Let $L=\{i: a_i = E\}$ and $R=\{i: a_i=N\}$. Then 01-fillings of $F$ considered here are in one-to-one correspondence with the matchings of $\{1, \ldots, 2n \}$ for which the set of left endpoints is $L$ and the set of right endpoints is $R$. For example, in the following Ferrers board $F$, traversing from the lower-left corner to the top-right corner, we get the sequence $EENENENN$. Thus $L={1,2,4,6}$ and $R={3,5,7,8}$. The filling given in the figure corresponds to the matching $\{ (1,7), (2,3), (4,5), (6, 8)\}$. \begin{center} \setlength{\unitlength}{0.4mm} \begin{picture}(100,90) \put(0,0){\line(1,0){40}} \put(0,20){\line(1,0){60}} \put(0,40){\line(1,0){80}} \put(0,60){\line(1,0){80}} \put(0,80){\line(1,0){80}} \put(0,0){\line(0,1){80}} \put(20,0){\line(0,1){80}} \put(40, 0){\line(0,1){80}} \put(60, 20){\line(0,1){60}} \put(80, 40){\line(0,1){40}} \put(8,47){\large{1}} \put(28,7){\large{1}} \put(48,27){\large{1}} \put(68,67){\large{1}} \end{picture} \end{center} It follows that equation \eqref{[n-1]} is exactly the generating function of the statistic $ne_2(M)$, which is the number of nestings in a matching $M$, counted over all the matchings with given sets of left and right endpoints. That is, \[ \sum_{M} q^{ne_2(M)} = \prod_{i=1}^n [h_i], \] which matches the known results in \cite{Sainte93,Kas10}. \item Case 2, $D=\emptyset$: \ We have \[ \alpha_F(\emptyset, q) = \beta_F(\emptyset, q) = LP_n((h_1, \dots, h_n),q) \] Note that $h_n=1$, hence $LP_n((h_1, \dots, h_n),q)=1$ iff $r_i \geq i$ for all $i$, where the only permutation in the Ferrers board $F$ with no descents is the identity permutation; otherwise $Path_n(h_1, \dots, h_n)=\emptyset$ and $LP_n((h_1, \dots, h_n),q)=0$. \end{itemize} Theorems 2.1 and 2.2 can be used to get a formula for the joint distribution of $\des(\sigma)$ and $\inv(\sigma)$ over permutations in $F$. Let \begin{eqnarray} \label{F-qEularian} A_F(t,q) =\sum_{\sigma \in F} t^{1+\des(\sigma)} q^{\inv(\sigma)}. \end{eqnarray} \begin{thm} \label{A_f(t,q)} \begin{eqnarray} A_F(t,q) = (1-t)^n per(M), \end{eqnarray} where $M$ is an $n \times n$ matrix whose $(i,j)$-entry is given by \begin{eqnarray*} M_{ij} = \left\{ \begin{array}{ll} \frac{t}{1-t} LP_{j-i+1} ((h_i, \ldots, h_j);q) & \text{ if } i \leq j \\ 1 & \text{ if } i=j+1 \\ 0 & \text{ if } i > j+1, \end{array} \right. \end{eqnarray*} and $per(M)$ is the permanent of the matrix $M$. \end{thm} \begin{proof} We have \begin{eqnarray*} \sum_{\sigma \in F} t^{1+\des(\sigma)} q^{\inv(\sigma)} &=& \sum_{D \subseteq \{1,2,\ldots,n-1\}} t^{1+|D|} \beta_F (D, q) \\ & = & \sum_{D \subseteq \{1,2,\ldots,n-1\}} t^{1+|D|} \sum_{T: T \subseteq D} (-1)^{|D-T|} \alpha_F (T, q) \\ & = & \sum_{T \subseteq \{1,2,\ldots,n-1\}} \alpha_F (T, q) \sum_{D: T \subseteq D} (-1)^{|D-T|} t^{1+|T|+|D-T|} \\ & = & (1-t)^n \sum_{T=\{t_1, \dots, t_k\}_<} \left(\frac{t}{1-t}\right)^{1+k} \Delta_T(LP_n(\mathbf{h})) \\ & = & (1-t)^n per(M), \end{eqnarray*} where $M$ is an $n \times n$ matrix as described in Theorem \label{A_F(t,q)}, and $\Delta_D(LP_n(\mathbf{h}))$ denotes the right-hand side of \eqref{eq-alpha}. \end{proof} \begin{rem} \emph{We remark that descents of permutations in a Ferrers board provide an example of one-dependent determinantal point processes, as studied by Borodin, Diaconis and Fulman \cite{Borodin10}. % Borodin, Diaconis and Fulman showed that many examples from combinatorics, algebra and group theory %can be characterized as determinantal one-dependent point processes. Let $U$ be a finite set. A point process on $U$ is a probability measure $P$ on the $2^{|U|}$ subsets of $U$. One simple way to specify $P$ is via its correlation functions $\rho(A)$, where for $A \subseteq U$, \[ \rho(A)=P\{ S : S \supseteq A\}. \] A point process is \emph{determinantal} with kernel $K(x,y)$ if \[ \rho(A)=\det [K(x,y) ]_{x,y \in A}. \] It is \emph{one-dependent} if $\rho(X \cup Y) = \rho(X) \rho(Y)$ whenever dist($X, Y$)$\geq 2$.} \emph{Borodin et al. showed that many examples from combinatorics, algebra and group theory are determinantal one-dependent point processes, for example, the carries process, the descent set of uniformly random permutations, and the descent set in Mallows model \cite{Borodin10}. For these three cases, the point processes are stationary, while the descent set of permutations in a Ferrers board corresponds to a determinantal one-dependent point process that is not stationary. Explicitly, for any set $D=\{d_1, \dots, d_k\}$ with $1 \leq d_1 < \cdots < d_k \leq n-1$, let $P_F(D) = \beta_F(D)/(\prod_{i=1}^n h_i)$. Using \cite[Theorem 7.5]{Borodin10} we obtain that $P_F$ is a determinantal, one-dependent process with correlation functions \[ \rho(D)=\alpha_F(D) =\det [ K(d_i, d_j) ]_{i,j=1}^k \] and with correlation kernel \[ K(x,y) = \delta_{x,y} + (E^{-1})_{x, y+1}, \] where $E$ is the upper triangular matrix $E=[e(i-1,j)]_{i,j=1}^n$ whose entries are given by} \begin{eqnarray*} e(i,j) = \left\{ \begin{array}{ll} LP_{j-i}(h_{i+1}, \dots, h_{j}) & \text{ if } i < j \\ 1 & \text{ if } i=j \\ 0 & \text{ if } i > j. \end{array} \right. \end{eqnarray*} \end{rem} \section{Permutations in the truncated board $n\times n -\Delta_s$} For a general non-decreasing sequence of positive integers $\mathbf{s}$, $LP_n(\mathbf{s},q)$ can be computed by a determinant formula (see, for example, \cite{Mohanty79}). But there is no simple closed formula. In the special cases that the Ferrers board $F$ is obtained from truncating the $n \times n$ square board by a triangular board in the corner, %such that the permutations on $A$ are those with a bounded maxrise, we can describe the joint distribution of the statistics $\des(\sigma)$ and $\inv(\sigma)$ by identities of their bi-variate generating functions. Let $\Delta_s$ be the triangular board with row size $(s, s-1, \dots, 1)$. For $ n \geq s$, let $\Lambda_{n,s}$ be the truncated board $n \times n -\Delta_s$ consisting of cells that are lying in $0 \leq x,y \leq n$ and above the line $y=x-(n-s)$. In other words, $\Lambda_{n,s}$ is the Ferrers board whose row lengths are $(n-s, n-s+1, \dots, n, \dots, n)$. See the following figure for $\Lambda_{n,s}$ with with $n=7$ and $s=4$. \begin{center} \setlength{\unitlength}{0.3mm} \begin{picture}(140,140) \put(0,0){\line(1,0){60}} \put(0,20){\line(1,0){80}} \put(0,40){\line(1,0){100}} \put(0,60){\line(1,0){120}} \put(0,80){\line(1,0){140}} \put(0,100){\line(1,0){140}} \put(0,120){\line(1,0){140}} \put(0,140){\line(1,0){140}} \put(0,0){\line(0,1){140}} \put(20,0){\line(0,1){140}} \put(40, 0){\line(0,1){140}} \put(60, 0){\line(0,1){140}} \put(80,20){\line(0,1){120}} \put(100,40){\line(0,1){100}} \put(120,60){\line(0,1){80}} \put(140,80){\line(0,1){60}} \end{picture} \end{center} %It's easy to check that 01-fillings of $\Lambda_{n,s}$ correspond exactly to permutations in $L_{n, n-s-1}$. Now let $D=\{ d_1, \ldots, d_k \}$ with $1 \leq d_1 < \cdots < d_k \leq n-1$. We shall compute the joint distribution of $1+\des$ and $\inv$ over all permutations in $\Lambda_{n,s}$ using the formulas obtained in Section 2. Again let $d_0=0$ and $d_{k+1}=n$. Let $\delta_i=d_i-d_{i-1}$ for $i=1,\dots, k+1$, and assume that $j$ is the particular index to make $d_j \leq s < d_{j+1}$ occur. %Fix $n$ and $s$, and abbreviated $\Lambda_{n,s}$ as $\Lambda$. First we compute $\alpha_{\Lambda_{n,s}}(D,q)$. Let $r_i$ be the size of row $i$ in $\Lambda_{n, s}$. Then \begin{eqnarray*} r_i = \left\{ \begin{array}{ll} n-s-1+i & \text{ if } i \leq s \\ n & \text{ if } s < i \leq n. \end{array} \right. \end{eqnarray*} Let $h_i = r_i-i+1$. Then \begin{enumerate} \item For $0 \leq i < j$, \[ LP_{d_{i+1}-d_{i}}((h_{d_{i}+1} , \dots, h_{d_{i+1}}),q) = LP_{\delta_{i+1}} ((n-s,\dots, n-s),q) = \qbinom{n-s-1+\delta_{i+1}}{\delta_{i+1}}. \] \item For $i=j$, \begin{align*} LP_{d_{j+1}-d_j}((h_{d_j+1} , \dots, h_{d_{i+1}}),q) &= LP_{\delta_{j+1}} (((n-s)^{s-d_j},n-s-1,\dots, n-d_{j+1}+1),q) \\ &= \qbinom{n-d_{j+1}+\delta_{j+1}}{\delta_{j+1}}\\ &= \qbinom{n-d_j}{\delta_{j+1}}. \end{align*} \item For $i > j$, \begin{eqnarray*} LP_{d_{i+1}-d_i}((h_{d_i+1} , \dots, h_{d_{i+1}}),q)&=& LP_{\delta_{i+1}} (((n-d_i,n-d_i-1,\dots, n-d_{i+1}+1),q) \\ &= &\qbinom{n-d_{i+1}+\delta_{i+1}}{\delta_{i+1}} \\ & = & \qbinom{n-d_{i}}{\delta_{i+1}}. \end{eqnarray*} \end{enumerate} Summing over all permutations $\sigma$ with $\Des(\sigma) \subseteq D$ in the Ferrers board $\Lambda_{n,s}$, we obtain \begin{align} \alpha_{\Lambda_{n,s}}(D, q) = \sum_{\btop{\sigma \in \Lambda_{n,s}}{Des(\sigma) \subseteq D}} q^{\inv (\sigma)} &= \prod_{i=1}^{j} \qbinom{n-s-1+\delta_i} {\delta_i } \cdot \prod_{i=j}^k \qbinom{n-d_{i}}{\delta_{i+1}} \notag \\ & = \prod_{i=1}^{j} \qbinom{n-s-1+\delta_i} {\delta_i} \cdot \qbinom{n-d_{j}}{\Delta(D_j)}, \notag \end{align} where ${\Delta(D_j)}$ represents the sequence $\delta_{j+1}, \ldots, \delta_{k+1} $. Hence the Principle of Inclusion-Exclusion leads to \begin{eqnarray} \beta_{\Lambda_{n,s}}(I, q) = \sum_{\btop{\sigma \in \Lambda_{n,s}} {Des(\sigma)=I}} q^{\inv (\sigma)} = \sum_{D \subseteq I} (-1)^{|I|-|D|} \qbinom{n-d_{j}}{\Delta(D_j)} \prod_{i=1}^{j} \qbinom{n-s-1+\delta_i} {\delta_i}. \label{beta_ns} \end{eqnarray} Let $F_{n,s}(q,t)$ be the bi-variate generating function of the statistics $\inv$ and $\des$ over all permutations in the board $\Lambda_{n,s}$. That is, \begin{align} F_{n,s} (q, t) &= \sum_{\sigma \in \Lambda_s} t^{1+ des(\sigma)} q^{\inv(\sigma)} \notag \\ &=\sum_{I \subseteq \{1,2,\ldots,n-1\}} t^{1+|I|} \sum_{\btop{\sigma \in \Lambda_{n,s}} {Des(\sigma)=I}} q^{\inv(\sigma)}. \notag \end{align} Let $(a; q)_n= (1-a)(1-aq)\cdots (1-aq^{n-1})$ and $(a,q)_\infty = \prod_{i=0}^\infty (1-aq^i)$. Our main result here is an analog of the formula \eqref{perm_gf}. Explicitly, we show that $F_{n,s}(q,t)$ can be expressed as a linear combination of $s+1$ terms, each of which satisfies a $q$-identity similar to \eqref{perm_gf}. \begin{thm} \label{Board-inv-des} For $n \leq s$, $F_{n,s}(q,t)=0$. For $n > s$, we have \begin{eqnarray} F_{n,s} (q,t) = \theta_0 F_{n,s}^{(0)}(q,t) + \theta_1 F_{n,s}^{(1)}(q,t) + \cdots + \theta_s F_{n,s}^{(s)}(q,t), \end{eqnarray} where the $\theta_k$'s are defined by the formal power series \begin{eqnarray} \sum_{k=0}^\infty \theta_k z^k = \left( 1- \frac{t}{1-t} \left(\frac{1}{(z;q)_{n-s}} -1 \right) \right)^{-1}, \label{a_i} \end{eqnarray} and for each $i=0,1, \dots, s$, the term $F_{n,s}^{(i)}(q,t)$ is given by the identity \begin{eqnarray} \sum_{n \geq s+1} \frac{z^n}{[n-i]!} \frac{ F_{n,s}^{(i)}(q,t)}{(1-t)^n} = \frac{\displaystyle \frac{t}{1-t} \sum_{ k \geq s+1-i} \frac{z^k}{[k]!} } {\displaystyle 1-\frac{t}{1-t} \sum_{k \geq 1} \frac{z^k}{[k]!} } . \label{f_nsi} \end{eqnarray} \end{thm} \begin{proof} As before assume $D=\{d_1, d_2,\dots, d_k\}$ with $d_0=0 $ and $d_{k+1}=n$. Let $j$ be the index uniquely decided by $d_j \leq s < d_{j+1}$. For $n \geq s+1$, by the equation \eqref{beta_ns} we have \begin{align} F_{n, s} (q, t) &= \sum_{I \subseteq \{1,2,\ldots,n-1\}} t^{1+|I|} \sum_{D \subseteq I} (-1)^{|I|-|D|} \qbinom{n-d_{j}}{\Delta(D_j)} \prod_{i=1}^{j} \qbinom{n-s-1+\delta_i} {\delta_i} \notag \\ &=\sum_{D \subseteq \{1,2,\ldots,n-1\}} \qbinom{n-d_{j}} {\Delta(D_j)} \prod_{i=1}^{j} \qbinom{n-s-1+\delta_i} {\delta_i } \sum_{I: D \subseteq I} (-1)^{|I|-|D|} t^{1+|I|} \notag \\ &=\sum_{D \subseteq \{1,2,\ldots,n-1\}} \qbinom{n-d_{j}} {\Delta(D_j)} \prod_{i=1}^{j} \qbinom{n-s-1+\delta_i} {\delta_i} (1-t)^{n-1-|D|} t^{1+|D|} \notag \\ &= \sum_{k=0}^{n-1} t^{1+k} (1-t)^{n-1-k} \sum_{\btop{\delta_1+ \delta_2 +\ldots + \delta_{k+1} =n} {\delta_1 + \ldots + \delta_{j} \leq s < \delta_1 + \ldots +\delta_{j+1}} } \frac{[n-d_{j}]! \prod_{i=1}^{j} [n-s-1 + \delta_i]! }{ [\delta_1]! \cdots [\delta_{k+1}]! ([n-s-1]!)^j } . \notag \end{align} Let $d_i=l$ and $\gamma=\frac{t}{1-t}$. Then, \begin{align} & \frac{F_{n, s} (q, t)}{(1-t)^n} \notag \\ =& \sum_{l=0}^s \sum_{k \geq 0} \gamma^{1+k} \sum_{\btop{\delta_1 + \delta_2 + \ldots + \delta_{k+1} =n} {l= \delta_1 + \ldots + \delta_{j} \leq s < \delta_1 + \ldots + \delta_{j+1} }} \frac{[n-l]! {\prod_{i=1}^{j} [n-s-1 + \delta_i]! }} {[\delta_1]! \cdots [\delta_{k+1}]! ([n-s-1]!)^j }. \notag \\ =& \sum_{l=0}^s \left(\sum_{\btop{j}{\delta_1 + \ldots + \delta_{j} = l}} \gamma^j \prod_{i=1}^j \qbinom{n-s-1+\delta_i}{\delta_i} \right) \left(\sum_{\btop{ k; \delta_{j+1}\geq s+1-l} {\delta_{j+1}+ \delta_{j+2}+ \ldots + \delta_{k+1}=n-l}} \frac{\gamma^{k+1-j}[n-l]!}{[\delta_{j+1}]! \cdots [\delta_{k+1}]!} \right) \label{AC} \end{align} Let $\theta_0=1$ and for $l=1, \dots, s$, \[ \theta_l := \sum_{\btop{j}{\delta_1 + \ldots + \delta_{j} = l}} \gamma^j \prod_{i=1}^j \qbinom{n-s-1+\delta_i}{\delta_i}, \] and \begin{eqnarray} F_{n,s}^{(l)} := (1-t)^n \sum_{\btop{k; \tau_{0}\geq s+1-l}{ \tau_{0}+ \tau_{1}+ \ldots + \tau_{k}=n-l}} \frac{\gamma^{k+1}[n-l]!}{[\tau_0]! \cdots [\tau_k]!}. \label{f_nsi2} \end{eqnarray} Then \begin{eqnarray*} F_{n,s} (q,t) = \theta_0 F_{n,s}^{(0)}(q,t) +\theta_1 F_{n,s}^{(1)}(q,t) +\cdots + \theta_s F_{n,s}^{(s)}(q,t). \end{eqnarray*} We show that $\theta_l$ and $F_{n,s}^{(l)}(q,t)$ satisfy \eqref{a_i} and \eqref{f_nsi}. First, observe that for $l > 0$, $\theta_l$ is the coefficient of $z^l$ in the formal power series \begin{align} \sum_{j=0}^\infty \left(\gamma \sum_{k=1}^\infty \qbinom{n-s-1+k}{k} z^k \right) ^j. \end{align} Using the $q$-analog of the binomial theorem \[ \sum_{k=0}^\infty \frac{(a;q)_k}{(q;q)_k} z^k=\frac{(az;q)_\infty}{(z;q)_\infty}, \] %where $(a; q)_n= (1-a)(1-aq)\cdots (1-aq^{n-1})$ and $(a,q)_\infty = \prod_{i=0}^\infty (1-aq^i)$, we have \begin{align} \sum_{l=0}^\infty \theta_l z^l &= \sum_{j=0}^\infty \left(\gamma \sum_{k=1}^\infty \frac{[n-s+k-1][n-s+k-2] \cdots [n-s]} {[k]!} z^k\right)^j \notag \\ & = \sum_{j=0}^\infty \left(\gamma \cdot (\frac{(q^{n-s}z;q)_\infty}{(z;q)_\infty} -1) \right)^j \notag \\ & = \left(1 - \gamma (\frac{1}{(z;q)_{n-s}} -1) \right)^{-1}. \notag \end{align} This proves the formula \eqref{a_i}. To get the formula \eqref{f_nsi}, observe that \eqref{f_nsi2} can be written as \[ \frac{1}{[n-l]!} \frac{F_{n,s}^{(l)}}{(1-t)^n} =[z^{n-l}] \left(\gamma \sum_{\tau_0 \geq s+1-l} \frac{z^{\tau_0} }{[\tau_0]!} \cdot \sum_{k=0}^\infty \gamma^k (\sum_{\tau=1}^\infty \frac{z^\tau }{[\tau]!} )^k \right). \] This leads to the identity \[ \sum_{n \geq s+1} \frac{z^{n-l}}{[n-l]!} \frac{ F_{n,s}^{(l)}(q,t)}{(1-t)^n} = \frac{\displaystyle \frac{t}{1-t} \sum_{ k \geq s+1-l} \frac{z^k}{[k]!} }{\displaystyle 1-\frac{t}{1-t} \sum_{k \geq 1} \frac{z^k}{[k]!}}. \] %Furthermore, \begin{align} & \sum_{\btop{u_1 + u_2 + \ldots + %u_{k+1} =n} { u_1 + \ldots + u_{j} \leq s < u_1 + \ldots + %u_{j+1} }} \frac{[n-d_{j}]! {\prod_{i=1}^{j} [n-s-1 + %u_i]! }} {[u_1]! \cdots [u_{k+1}]! ([n-s-1]!)^j } % \notag \\ %& = \sum_{l \geq 0} \frac{1}{\qbinom{2n-s-1}{n-l}} \sum_{j \geq 1} %\sum_{a_1 + \ldots + a_j =l} \frac{1}{[a_1]! \cdots [a_{j}]!} %\sum_{l \geq s+1} \frac{1}{[l-l]!} \sum_{b_1 + \ldots + b_{k-j} = %n-l} \frac{1}{[b_1]! \cdots [b_{k-j}]!} %\notag \\ %& = \sum_{l \geq 0} \frac{1}{\qbinom{2n-s-1}{n-l}} \sum_{j \geq 0} ( %(\sum_{a \geq 0} \frac{y^a}{[a]!})^{j} |_{y^l} (\sum_{c \geq %s+1-l} \frac{y^c}{[c]!} (\sum_{b \geq 0} \frac{y^b}{[b]!})^{k-j}) %|_{y^{n-l}} ) \notag \\ %& = \sum_{l \geq 0} \frac{1}{\qbinom{2n-s-1}{n-l}} ( (\sum_{a \geq %0} \frac{y^a}{[a]!})^{k} \sum_{c \geq s+1-l} \frac{y^c}{[c]!}) %|_{y^{n}}. \notag %& = \sum_{l \geq 0} \frac{1}{\qbinom{2n-s-1}{n-l}} \sum_{j \geq 0} ( %(\sum_{a \geq 0} \frac{y^a}{[a]!})^{j} |_{y^l} ( (\sum_{b \geq 0} %\frac{y^b}{[b]!})^{k-j+1} - \sum_{r=0}^{s-l} \frac{y^r}{[r]!} %(\sum_{b \geq 0} \frac{y^b}{[b]!})^{k-j} ) %|_{y^{n-l}} ) \notag \\ %&=\sum_{l \geq 0} \frac{1}{\qbinom{2n-s-1}{n-l}} ( (\sum_{a \geq 0} %\frac{y^a}{[a]!})^{k+1} |_{y^n} - \sum_{r=0}^{s-l} \frac{1}{[r]!} %(\sum_{b \geq 0} \frac{y^b}{[b]!})^{k} |_{y^{n-r}} ) \notag %\end{align} %So that we have \begin{align} \sum_{n \geq 0} \frac{F_{n, s} (q, t) %[n-s-1]!} {t (1-t)^{n-1} [2n-s-1]!} y^n &= % \sum_{l \geq 0} \frac{1}{\qbinom{2n-s-1}{n-l}} ( \sum_{k \geq 0} (\frac{t} {1-t} \sum_{a \geq %0} \frac{y^a}{[a]!})^{k} \sum_{c \geq s+1-l} \frac{y^c}{[c]!} ) %\notag \\ %&=\sum_{l \geq 0} \frac{1}{\qbinom{2n-s-1}{n-l}} \sum_{c \geq %s+1-l} \frac {y^c} {[c]! (1- \frac{t} {1-t} \sum_{a \geq 0} %\frac{y^a}{[a]!})} . \notag %\end{align} In the case that $s=0$, $F_{n,s}(q,t) = F_{n,s}^{(0)}(q,t) = A_n (t, q)$, and equation \eqref{f_nsi} reduces to the well-known identity \eqref{perm_gf} by letting $u=\frac{z}{1-t}$. \end{proof} %%%%%%%%%%%% add new materials \section{Permutations with bounded drop or excedance size} Permutations with bounded drop size is related to the bubble sort and sequences that can be translated into juggling patterns \cite{Chung08}, whose enumeration was first studied by Chung, Claesson, Dukes, and Graham \cite{CCDG}. For a permutation $\sigma$, we say that $i$ is a \emph{drop} of $\sigma$ if $\sigma_i < i$ and the \emph{drop size} is $i-\sigma_i$. Similarly, we say that $i$ is an \emph{excedance} of $\sigma$ if $\sigma_i > i$, and the \emph{excedance size} is $\sigma_i-i$. It is well-known that the number of excedances is an Eulerian statistic, i.e., has the same distribution as $\des$ over the set of permutations. Following \cite{CCDG}, we use $\text{maxdrop} (\sigma)$ to denote the maximum drop of $\sigma$, $$ \text{maxdrop} (\sigma) := \max \{ i- \sigma_{i} | 1 \leq i \leq n \}, $$ and similarly, $\text{maxexc} (\sigma)$ to denote the maximum excedance size of $\sigma$, $$ \text{maxexc} (\sigma) := \max \{ \sigma_{i} - i | 1 \leq i \leq n \}. $$ Let $\mathcal{B}_{n,k}=\{ \sigma \in \mathfrak{S}_n | \text{maxdrop} (\sigma) \leq k \}$. It is easy to see that $|\mathcal{B}_{n,k}| = k! (k+1)^{n-k}$: Just note that there are $(k+1)^{n-k}$ ways to determine $\sigma_n, \cdots, \sigma_{k+1}$ in the correct order, one after another, and the remaining is clear (e.g., see \cite[Thm.1]{Chung08}). In \cite{CCDG}, Chung et al. defined the $k$-maxdrop descent polynomials \begin{align} B_{n,k} (t) := \sum_{\sigma \in \mathcal{B}_{n, k}} t^{des(\sigma)} \notag \end{align} and obtained recurrences as well as a formula for the generating function ${B}_k(t,z) := \sum_{n \geq 0} B_{n,k}(t) z^n$. In this section, we will use the analysis in the previous section to derive a variant generating function for $B_k(t,z)$. Explicitly, we get an exact formula for \begin{eqnarray} \label{E_k(t,z)} E_k(t, z) := \sum_{n \geq k} B_{n,k}(t)z^n= \sum_{n \geq k} \left(\sum_{\sigma \in \mathcal{B}_{n,k}} t^{des(\sigma)} \right)z^n. \end{eqnarray} First, let $\mathcal{B}'_{n,k}=\{ \sigma \in \mathfrak{S}_n | \text{maxexc} (\sigma) \leq k \}$. It is clear that the map $a_1a_2 \dots a_n \mapsto (n+1-a_n)(n+1-a_{n-1}) \dots (n+1-a_1)$ is a bijection from $\mathcal{B}_{n,k}$ to $\mathcal{B}'_{n,k}$ that preserves the statistic $\des(\sigma)$ and $\inv(\sigma)$. It follows that \[ B_{n,k}(t) =\sum_{\sigma \in \mathcal{B}'_{n,s}} t^{des(\sigma)} \qquad \text{ and hence} \qquad E_k(t, z) = \sum_{n \geq k} \left(\sum_{\sigma \in \mathcal{B}'_{n,k}} t^{des(\sigma)} \right)z^n. \] Note that $\mathcal{B}'_{n,k}$ is the set of permutations $\sigma \in \mathfrak{S}_n$ satisfying $\sigma_i \leq i+k$. It is easy to check that it is exactly the set of permutations on the truncated board $\Lambda_{n, n-k-1}$. Hence for $n \geq k+1$, we have \[ \sum_{\sigma \in \mathcal{B}_{n,k}} t^{1+des(\sigma)} q^{\inv(\sigma)}=F_{n,n-k-1}(q,t) \] and Theorem \ref{Board-inv-des} with $s=n-k-1$ gives a description of $F_{n,n-k-1} (q,t)$. To obtain the ordinary generating function for $B_{n,k}(t)$, set $q=1$. As before, let $\gamma=t/(1-t)$. Then formula \eqref{AC} becomes the following equation for $n \geq k+1$: \begin{eqnarray*} \frac{tB_{n, k} (t)}{(1-t)^n} =\sum_{l=0}^{n-k} \left(\sum_{\btop{j}{\delta_1 + \ldots + \delta_{j} = l}} \gamma^j \prod_{i=1}^j \binom{k+\delta_i}{\delta_i} \right) \left(\sum_{\btop{ p; \delta_{j+1} > n-k-l} {\delta_{j+1}+ \delta_{j+2}+ \ldots + \delta_{p+1}=n-l}} \frac{\gamma^{p+1-j}(n-l)!}{\delta_{j+1}! \cdots \delta_{k+1}!} \right). \end{eqnarray*} (Note that from the analysis, the upper limit of $l$ can include $n-k$. ) Let $\theta^{(k)}_0=1$ and for $l\geq 1$, \[ \theta^{(k)}_l : = \sum_{\btop{j; \delta_1 + \ldots + \delta_{j} = l}{\delta_i > 0} } \gamma^j \prod_{i=1}^j \binom{k+\delta_i}{\delta_i}, \] and \[ c^{(k)}_{n-l} := \sum_{\tau_0 > n-k-l} \gamma \binom{n-l}{\tau_0} \cdot \sum_{\btop{\tau_1+\cdots+\tau_p=n-l-\tau_0}{\tau_i \geq 1}} \gamma^p \binom{n-l-\tau_0}{\tau_1, \dots, \tau_p}, \qquad \text{for } k >0. \] For $k=0$, let $c^{(0)}_n=\delta_{n,0}$. Then for any fixed $k \geq 0$ and $n \geq k+1$, we have \begin{eqnarray} \label{B_nk} \frac{tB_{n, k} (t)}{(1-t)^n} = \sum_{l=0}^{n-k} \theta^{(k)}_l c^{(k)}_{n-l}, \end{eqnarray} Letting $q=1$ and $k=n-s-1$ in equation \eqref{a_i}, we obtain \begin{eqnarray} \label{Theta_k} \Theta_k(z)= \sum_{n\geq 0} \theta^{(k)}_n z^n = \left( 1- \frac{t}{1-t} \left( \frac{1}{(1-z)^{k+1}} -1 \right) \right)^{-1}. \end{eqnarray} For the coefficient $c^{(k)}_i$, using formula \eqref{AC} with $s=0$, we get that \[ \sum_{\btop{\tau_1+\cdots+\tau_p=n}{\tau_i \geq 1}} \gamma^p \binom{n}{\tau_1, \dots, \tau_p} = \frac{A_n(t)}{(1-t)^n}, \] where $A_n(t)$ is the classical Eulerian polynomial defined by $$ A_n(t) = \sum_{\sigma \in \mathfrak{S}_n} t^{1+des(\sigma)}, \qquad n >0. $$ By convention, we set $A_0(t)=1$. It follows that for $k >0$, \begin{eqnarray} \label{c_nk} c^{(k)}_n = \gamma \sum_{p > n-k} \binom{n}{p} \frac{A_{n-p}(t)}{(1-t)^{n-p}} = \gamma \sum_{p=0}^{k-1} \binom{n}{p} \frac{A_{p}(t)}{(1-t)^{p}}. \end{eqnarray} Writing as a generating function, we obtain that for $k >0$, \begin{eqnarray*} C_k(z) = \sum_{n \geq k} c^{(k)}_n z^n = \gamma \sum_{p=0}^{k-1} \frac{A_p(t)}{(1-t)^p} \sum_{n \geq k} \binom{n}{p} z^n \end{eqnarray*} which leads to \begin{eqnarray} C_k(z) = \frac{t}{1-t} \sum_{p=0}^{k-1} \frac{A_p(t)}{(1-t)^p} \left( \frac{z^p}{(1-z)^{p+1}} -\sum_{n=p}^{k-1} \binom{n}{p} z^n \right). \label{C_k} \end{eqnarray} For $k=0$, $C_0(z)=1$. Observe that equation \eqref{B_nk} is true for $n=k$ as well. In fact it is equivalent to the identity \[ A_k(t) = t \sum_{p=0}^{k-1} \binom{k}{p} (1-t)^{k-p-1} A_p(t), \] which can be readily checked by using the following expression of the Eulerian polynomial, see, for example \cite[Lemma 14.1, p.517]{Cha02}, \[ A_n(t) =(1-t)^{n+1} \sum_{j=0}^\infty j^n t^j, \qquad n\geq 0. \] Therefore for all $n \geq k$, \[ B_{n, k} (t) = \frac{(1-t)^n}{t} \sum_{l=0}^{n-k} \theta^{(k)}_l c^{(k)}_{n-l}, \] Multiplying both sides by $z^n$ and summing over $n \geq k$, we have obtained the generating function $E_k(t,z)$. \begin{thm} \label{E_k} Let \[ E_k(t,z) = \sum_{ n \geq k} B_{n,k}(t)z^n = \sum_{ n \geq k} \left(\sum_{ \sigma \in \mathcal{B}_{n,k}} t^{des(\sigma)} \right)z^n. \] Then $E_0(t,z)= 1/(1-z)$ and for $k \geq 1$, \begin{eqnarray} E_k(t, z) = \frac{1}{t} \Theta_k ((1-t)z) C_k ((1-t)z), \end{eqnarray} where $\Theta_k(z)$ and $C_k(z)$ are given in formulas \eqref{Theta_k} and \eqref{C_k}. Explicitly, \begin{eqnarray} E_k(t, z) = \frac{\displaystyle \sum_{p=0}^{k-1} A_p(t)\left( \frac{z^p}{(1-(1-t)z)^{p+1}} -\sum_{n=p}^{k-1} \binom{n}{p} (1-t)^{n-p} z^{n} \right)}{1-\frac{t}{ (1-(1-t)z)^{k+1}}}. \label{product2} \end{eqnarray} \end{thm} \begin{exa} For the case $k=1$, formula \eqref{product2} gives \[ E_1(t, z) = \frac{\frac{1}{1-(1-t)z}-1}{ 1-\frac{t}{(1-(1-t)z)^2} } =\frac{z(1-(1-t)z)}{1-z(2-(1-t)z)}. \] Comparing with equation (5) in \cite{CCDG}, and noting that the summation of $B_k(z,y)$ in \cite{CCDG} starts from $n=0$, one checks easily that the two formulas agree with each other. \end{exa} \begin{ack} The authors wish to thank an anonymous referee for the very careful reading and many helpful suggestions. \end{ack} % ------------------------------------------------------------------------ %GATHER{songXbib.bib} % For Gather Purpose Only %GATHER{songPaper.bbl} % For Gather Purpose Only %\bibliographystyle{plain} %\bibliography{SY} \begin{thebibliography}{10} \bibitem{Borodin10} Alexei Borodin, Persi Diaconis, and Jason Fulman. \newblock On adding a list of numbers (and other one-dependent determinantal processes). \newblock {\em Bull. Amer. Math. Soc. (N.S.)}, 47(4):639--670, 2010. \bibitem{CR64} Leonard Carlitz and John Riordan. \newblock Two element lattice permutation numbers and their {$q$}-generalization. \newblock {\em Duke Math. J.}, 31:371--388, 1964. \bibitem{Cha02} Charalambos~A. Charalambides. \newblock {\em Enumerative combinatorics}. \newblock CRC Press Series on Discrete Mathematics and its Applications. Chapman \& Hall/CRC, Boca Raton, FL, 2002. \bibitem{CCDG} Fan Chung, Anders Claesson, Mark Dukes, and Ronald Graham. \newblock Descent polynomials for permutations with bounded drop size. \newblock {\em European J. Combin.}, 31(7):1853--1867, 2010. \bibitem{Chung08} Fan Chung and Ron Graham. \newblock Primitive juggling sequences. \newblock {\em Amer. Math. Monthly}, 115(3):185--194, 2008. \bibitem{deMier06} Anna de~Mier. \newblock On the symmetry of the distribution of {$k$}-crossings and {$k$}-nestings in graphs. \newblock {\em Electron. J. Combin.}, 13(1):Note 21, 6 pp. (electronic), 2006. \bibitem{Sainte93} M.~de~Sainte-Catherine. \newblock Couplages et pfaffiens en combinatoire, physique et informatique. \newblock Master's thesis, University of Bordeaux I. \bibitem{Gar79} Adriano~M. Garsia. \newblock On the ``maj'' and ``inv'' {$q$}-analogues of {E}ulerian polynomials. \newblock {\em Linear and Multilinear Algebra}, 8(1):21--34, 1979/80. \bibitem{Gessel77} Ira~M. Gessel. \newblock {\em Generating functions and enumeration of sequences}. \newblock PhD thesis, M.I.T., 1977. \bibitem{Kas10} Anisse Kasraoui. \newblock Ascents and descents in 01-fillings of moon polyominoes. \newblock {\em European J. Combin.}, 31(1):87--105, 2010. \bibitem{Mohanty79} Sri~Gopal Mohanty. \newblock {\em Lattice path counting and applications}. \newblock Academic Press [Harcourt Brace Jovanovich Publishers], New York, 1979. \newblock Probability and Mathematical Statistics. \bibitem{Riordan58} John Riordan. \newblock {\em An introduction to combinatorial analysis}. \newblock Wiley Publications in Mathematical Statistics. John Wiley \& Sons Inc., New York, 1958. \bibitem{Sta76} Richard~P. Stanley. \newblock Binomial posets, {M}\"obius inversion, and permutation enumeration. \newblock {\em J. Combinatorial Theory Ser. A}, 20(3):336--356, 1976. \bibitem{Stan1} Richard~P. Stanley. \newblock {\em Enumerative combinatorics. {V}ol. 1}, volume~49 of {\em Cambridge Studies in Advanced Mathematics}. \newblock Cambridge University Press, Cambridge, 1997. \newblock With a foreword by Gian-Carlo Rota, Corrected reprint of the 1986 original. \end{thebibliography} \end{document} % ------------------------------------------------------------------------