\documentclass[12pt]{article} \usepackage{amsmath} \usepackage{amssymb} \usepackage{amsthm} % \textwidth= 6.25in \textheight= 9.0in \topmargin = -10pt \evensidemargin=10pt \oddsidemargin=10pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 %\hbadness=10000 %\tolerance=10000 %\allowdisplaybreaks % \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \def\clktheorem#1{\bigskip\noindent{\bf Theorem #1.}\quad} \def\clktheoremlab#1#2{\bigskip\noindent{\bf Theorem #1}#2.\quad} \def\endclktheorem{\medskip} \def\clklemma#1{\bigskip\noindent{\bf Lemma #1.}\quad} \def\clklemmalab#1#2{\bigskip\noindent{\bf Lemma #1}#2.\quad} \def\endclklemma{\medskip} \def\clkremark{\bigskip\noindent{\bf Remark.}\quad} \def\endclkremark{\medskip} %------------------------------------------- % DEFINITIONS - %------------------------------------------- % % general definitions % \def\qed {$\,\,\,\, \blacksquare$} \def\eee{\hbox{e}\,} \def\lldots{\ldots\kern -0.8truept} \def\clkbinom#1#2{\bigl( \kern 1truept \raise 7truept \hbox{$ #1 $} \kern -6truept \lower 5truept \hbox{$ #2 $} \kern 1truept \bigr)} % % local definitions to this paper % \def\Q{\mathbb Q} \def\R{\mathbb R} \def\S{S} \def\N{\mathbb N} \def\P{\mathbb P} \def\dt{\,dt} \def\dz{\,dz} \def\du{\,du} \def\bnk{b(n,k)} \def\Var{\hbox{Var}} \def\Pr{\hbox{Pr}\,} \def\Des{\hbox{Des}} \def\E{\hbox{E}} \def\maj{\hbox{maj}} \def\limn{\lim_{n\to\infty}} \def\lbxn{\lfloor (x)_n \rfloor} \def\Xnj{X_{n,j}} \def\Pnj{P_{n,j}} \def\Qln{Q_{\lambda,n}} \def\Xln{X_{\lambda,n}} \def\All{A_{\lambda_i-1}} \def\sip{\sum_{i=1}^p} \def\pip{\prod_{i=1}^p} % \def\G{{\frak S}} \def\D{{\frak D}} % %------------------------------------------- % HYPHENATIONS - %------------------------------------------- \hyphenation{derangement decompensation conjugatory precisely formalize combinatorica answering polynomials interested enumerating Monterey distribution cycle permutations conjugacy derangements} %------------------------------------------- % DOCUMENT TITLE - %------------------------------------------- \begin{document} \pagestyle{plain} %\pagestyle{myheadings} %\markright{\sc the electronic journal of combinatorial %number theorey \textbf{2} % (2002), \#A03\hfill} \thispagestyle{empty} %\title{Central and Local Limit Theorems for Excedances by Conjugacy % Class and by Derangement} % %\author{Lane Clark \\ % {Department of Mathematics} \\ % {Southern Illinois University Carbondale} \\ % {Carbondale, IL 62901} \\ % \small\texttt{lclark@math.siu.edu} % } % %\date{Submitted: December 17, 1998;\ \ Accepted: August 8, 2000} % %\maketitle %\vbox to 1.0truein{\ } % was 1.0 \begin{center} {\bf CENTRAL AND LOCAL LIMIT THEOREMS FOR EXCEDANCES BY CONJUGACY CLASS AND BY DERANGEMENT} \vskip 20pt {\bf Lane Clark}\\ {\smallit Department of Mathematics, Southern Illinois University Carbondale,\\ Carbondale, IL 62901}\\ {\tt lclark@math.siu.edu}\\ \end{center} \vskip 30pt \centerline{\smallit Received: 11/15/00, Revised: 9/14/01 Accepted: 1/31/02, Published: 2/8/02 } \vskip 30pt \centerline{\bf Abstract} \noindent We give central and local limit theorems for the number of excedances of a uniformly distributed random permutation belonging to certain sequences of conjugacy classes and belonging to the sequence of derangements. %which is of a certain cycle type or is a derangement. %\end{abstract} %\leavevmode\hbox to 0.12truein{\ } %\hbox{\small{AMS Subject Classification: 05A16, 05A15, 05A10}} \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 2 (2002), \#A03\hfill} %------------------------------------------- % DOCUMENT BODY - %------------------------------------------- \thispagestyle{empty} \baselineskip=15pt \vskip 30pt \section*{\normalsize 1. Introduction} For $n\in \P$ and $0\le k \le D_n \in \N$, let $\bnk \in [0,\infty)$ and $B_n := b(n,0) + \cdots + b(n,D_n) > 0$. We say the array $\{ \bnk : n\ge 1, \,\,\, 0\le k \le D_n\}$ satisfies a {\it central limit theorem with mean $\mu_n$ and variance $\sigma_n^2$} provided % \begin{equation} \limn \, \sup_{x\in \R} \bigg| \sum_{k\le \lbxn} \frac{\bnk}{B_n} - \Phi(x) \bigg| = 0, % \tag 1 \end{equation} % where $(x)_n := x\sigma_n + \mu_n$. Equivalently, we say $\{ \bnk \}$ is {\it asymptotically normal}. Further, the array $\{ \bnk : n\ge 1, \,\,\, 0\le k \le D_n\}$ satisfies a {\it local limit theorem on}~$\S \subseteq \R$ if and only if % \begin{equation} \limn \, \sup_{x\in \S} \left| \sigma_n \frac{b(n,\lbxn)}{B_n} - \phi(x) \right| = 0. % \tag 2 \end{equation} % %In general we have (1) and (2) in terms of the distribution and density %functions of a sequence of random variables (see Theorems 1, 3, and 4). In general, a central limit theorem for a sequence of random variables gives (1) from which (2) follows under certain conditions (see Theorems 1, 3 and 4 and Lemma 2). We note that (1) is equivalent to pointwise convergence in view of the uniform continuity of $\eee^{-t^2/2}$ and [11; Theorem 1 of Section 9] (see Bender [1]). A permutation of $[n]$ is a bijection $\sigma : [n] \to [n]$ which we write as $\sigma = \big(\sigma(1),\lldots,\sigma(n)\big)$. We denote the set of permutations of $[n]$ by $\G[n]$. A permutation $\sigma \in \G[n]$ is a {\it derangement\/} of $[n]$ provided $\sigma(i) \ne i$ for all $i \in [n]$. Let $\D[n]$ denote the set of derangements of $[n]$. Given a partition $\lambda = (\lambda_1 \ge \cdots \ge \lambda_p \ge 1)$ of $n$ ($= \lambda_1 + \cdots + \lambda_p$) $\in \P$, let $m_i = m_i(\lambda) := \big| \{ j\in [p] : \lambda_j=i\} \big|$ for $i \in [n]$. Here we write $\lambda = 1^{m_1} 2^{m_2} \cdots n^{m_n}$. We say $\sigma \in \G[n]$ is of {\it cycle type} $\lambda$ if and only if the decomposition of $\sigma$ into a product of disjoint cycles has precisely $m_i(\lambda)$ cycles of length $i$ for $i\in [n]$. We denote the set of all permutations of $[n]$ of cycle type $\lambda$ by $\G_\lambda[n]$. The $\G_\lambda[n]$, where $\lambda$ is a partition of $n$, are the conjugacy classes of $\G[n]$. It is readily seen (see [7]; p.\ 233]) that $|\G_\lambda[n]| = n! / (1^{m_1} 2^{m_2} \cdots n^{m_n}) (m_1!\, m_2! \cdots m_n!)$. We say $i\in [n]$ is an {\it excedance} (respectively, a {\it descent}) of $\sigma \in \G[n]$ provided $\sigma(i) > i$ (respectively, $i\ne n$ and $\sigma(i) > \sigma(i+1)$). Let $\E(\sigma)$ (respectively, $\Des(\sigma)$) denote the {\it set of excedances} (respectively, {\it descents\/}) of $\sigma$ and $e(\sigma) := |\E(\sigma)|$ (respectively, $d(\sigma) := |\Des(\sigma)|+1$ and $\maj(\sigma) := \sum \{ i: i\in \Des(\sigma)\}$). Given a partition $\lambda = 1^{m_1} 2^{m_2} \cdots n^{m_n}$ of $n\ge 2$, let $a_\lambda(n,k) := |\{\sigma \in \G_\lambda[n] : |\Des(\sigma)| = k\}|$ and $b_\lambda(n,k) := |\{ \sigma \in \G_\lambda[n] : e(\sigma) = k\}|$ for $k\in \N$. From [8; Theorem B], $a_\lambda(n,1) = \prod_{i=1}^n \binom{f_{i2} + m_i - 1}{m_i}$ where $f_{i2} = \sum_{d|i} \mu(d) 2^{i/d} /i$ for $i\in P$ when $m_1 \ne n$ and $n\ge 2$. Here, $a_\lambda(n,1) \in \P$ since $f_{i2} \in \P$ upon appealing to its definition, while, $a_\lambda(n,1) = (n-b+1) f_{b2}$ when $\lambda = 1^{n-b}b$ with $2\le b \le n$. From [4; Theorem 3.1], $b_\lambda(n,1)$ is the coefficient of $x$ in $Q_{\lambda,n}(x)$ (see Section 3). Properties of the Eulerian polynomials imply that $b_\lambda(n,1)=0$ when $m_2+\cdots +m_n \ge 2$ and $b_\lambda(n,1) = \binom{n}{b}$ when $\lambda = 1^{n-b} b$ with $2\le b\le n$. Hence, $a_\lambda(n,1) \ne b_\lambda(n,1)$ when $m_2 + \cdots + m_n \ge 2$ and $a_\lambda(n,1) \ne b_\lambda(n,1)$ for all but at most $b-1$ integers $n$ when $\lambda = 1^{n-b}b$ with $2 \le b \le n$. Consequently, descents and excedances are {\bf not} equidistributed over conjugacy classes in general. As is well known (see [14; p.~23]), they {\bf are} equidistributed over $\G[n]$. %Stanley [15] was interested in the symmetry and unimodality of some %polynomials obtained by enumerating a set of permutations according %to the number of excedances. %Brenti [3], [4] %showed these polynomials are symmetric and unimodal when %the set is a conjugacy class or is the set of derangements. %We are interested in probabilistic properties of these polynomials %over both of these sets. %Probabilistic properties of polynomials %obtained by enumerating permutations in a conjugacy class %according to the number of descents were given in [10]. In connection with the Betti numbers of certain varieties, Stanley [15] was interested in the symmetry and unimodality of the coefficients of some polynomials obtained by enumerating a set of permutations according to the number of excedances. Brenti [3], [4] showed these excedance polynomials are symmetric and unimodal when the set is a conjugacy class or is the set of derangements thus generalizing a conjecture and answering a question of [15]. Fulman [10] gave a central limit theorem for the coefficients of polynomials obtained by enumerating permutations belonging to certain sequences of conjugacy classes according to the number of descents. Our discussion in the previous paragraph shows that descents and excedances are not equidistributed over the conjugacy classes considered in [10] (see the remark after Theorem 3). We give both central and local limit theorems for the coefficients of excedance polynomials over certain sequences of conjugacy classes, including those of [10], and over the sequence of derangements (see Theorems 3 and 4). A more precise statement of the results and techniques is given in the next paragraph. %\looseness=1 Using the method of moments, Fulman [10] recently gave a central limit theorem for $d(\sigma)$ with $\mu_n = (n-1)/2$, $\sigma_n^2 = (n-1)/12$ and for $\maj(\sigma)$ with $\mu_n =\binom{n}{2} /2$, $\sigma_n^2 = n(n-1)(2n+5)/72$ when $\sigma$ is a uniformly distributed random permutation in $\G_{\lambda(n)}[n]$ for certain % cycle types $\lambda$. sequences $\lambda(n)$ of cycle types. In this paper, we give central and local limit theorems for $e(\sigma)$ with various $\mu_n$, $\sigma_n^2$ when $\sigma$ is a uniformly distributed random permutation in $\G_{\lambda(n)}[n]$ for certain % cycle types $\lambda$ sequences $\lambda(n)$ of cycle types, including those of [10], and for $e(\sigma)$ with $\mu_n = (n-1)/2 + o(1)$, $\sigma_n^2 = 25n/12 + o(1)$ when $\sigma$ is a uniformly distributed random permutation in $\D[n]$ (see Theorems 3 and 4). Of course our results immediately give asymptotic formulas for the number of such permutations with a certain number of excedances. We use the method of Harper [12]. % which we formalize in the next section. A slight extension of this method requiring only a nice factorization of the polynomials over $\R[x]$ is given in the next section (see Theorem 1). We refer the reader to the excellent survey of P\'olya frequency sequences by Pitman [13]. \looseness=1 Let $\N$ denote the nonnegative integers; $\P$ the positive integers; $\R_0$ the nonnegative real numbers and $\R$ the real numbers. The collection of all polynomials in an indeterminate $x$ whose coefficients are in the {\it set} $A$ is denoted by $A[x]$. For $n\in \P$, $[n] := \{1,\lldots,n\}$. The cardinality of a set $A$ is denoted by $|A|$. We denote the largest integer at most $x$ by $\lfloor x \rfloor$. The expectation of a random variable (r.v.) $X$ is denoted by $\E(X)$ and its variance by $\Var(X)$. We write $X_n \overset{d}{\to} X$ when the sequence $X_n$ of r.v.s converges in distribution to the r.v.\ $X$. For $x\in \R$, let % $$ \phi(x) := \frac{1}{\sqrt{2\pi}} \eee^{-x^2/2} \quad \hbox{and} \quad \Phi(x) := \int_{-\infty}^x \phi(t) \dt \, . $$ % We write $N(0,1)$ for a normally distributed r.v.\ with mean $0$ and variance $1$. We refer the reader to Comtet [7] for combinatorics and Durrett [9] for probability. \vskip 30pt \section*{\normalsize 2. General Results} For completeness, we first formalize a slight extension of the method of Harper [12] requiring only a nice factorization of the polynomials over $\R[x]$, which we will use in the next section. For $n\in \P$, let $Q_n(x) := P_{n,1}(x) \cdots P_{n,N(n)}(x)$ where $P_{n,j}(x) := \sum_{k=0}^{d_{n,j}} a(n,j,k) x^k \in \R_0[x] - \{0\}$ for $1\le j \le N(n) \in \P$. Let $X_{n,1}, \lldots, X_{n,N(n)}$ be row-independent r.v.s with % $$ \Pr(\Xnj = k) = \frac{a(n,j,k)}{P_{n,j}(1)} \quad (1\le j \le N(n), \,\, 0 \le k \le d_{n,j}) $$ % (which, of course, exist), hence, % $$ \E(\Xnj) = \frac{\Pnj'(1)}{\Pnj(1)} \quad\hbox{and}\quad \E(\Xnj^2) = \frac{\Pnj'(1) + \Pnj''(1)}{\Pnj(1)} \quad (1\le j\le N(n)). $$ % Let % $$ X_n := X_{n,1} + \cdots + X_{n,N(n)} $$ % hence, % \begin{equation} \mu_n := \E(X_n) = \frac{Q_n'(1)}{Q_n(1)} \quad \hbox{and} \quad \sigma_n^2 := \Var(X_n) = \frac{Q_n'(1)}{Q_n(1)} + \frac{Q_n''(1)}{Q_n(1)} - \left( \frac{Q_n'(1)}{Q_n(1)} \right)^2 \, . % \tag 3 \end{equation} % If $Q_n(x) := \sum_{k=0}^{D_n} \bnk x^k$ where $D_n := d_{n,1} + \cdots + d_{n,N(n)}$, then by row-independence % $$ \Pr(X_n = k) = \frac{\bnk}{Q_n(1)} \quad (0\le k \le D_n) \, . $$ % Let % $$ Y_{n,j} := \frac{\Xnj - \E(\Xnj)}{\sigma_n} \quad \hbox{and} \quad Y_n := Y_{n,1} + \cdots + Y_{n,N(m)} = \frac{X_n-\mu_n}{\sigma_n}\,. $$ % Then $Y_{n,j}$ assumes the values $\big(k-\E(\Xnj)\big) / \sigma_n$ with probabilities $a(n,j,k)/P_{n,j}(1)$ for $0\le k \le d_{n,j}$. Let $M_n := \max_{1\le j \le N(n)} \big\{ \E(\Xnj),\,\, |d_{n,j} - \E(\Xnj)| \big\}$ and $G_{n,j}(x) := \Pr (Y_{n,j} \le x)$ be the distribution function of $Y_{n,j}$ for $1\le j \le N(n)$. For all $\epsilon > 0$, % $$ \limn \, \sum_{j=1}^{N(n)} \int_{|y|>\epsilon} y^2 d G_{n,j} (y) = 0 \, , $$ % provided $\limn M_n/\sigma_n = 0$. By the Lindeberg-Feller Theorem (see [9; pp.\ 98--101]), $Y_n \overset{d}{\to} N(0,1)$. We have proved the following central limit theorem which can be expressed in terms of the $\bnk$, $X_n$ or $Y_n$ since % $$ \Pr(Y_n \le x) = \Pr(X_n \le \lbxn ) = \sum_{k\le \lbxn} \frac{\bnk}{Q_n(1)} $$ % for all $x\in \R$ where $(x)_n := x\sigma_n + \mu_n$. \clktheorem{1} Suppose $\limn M_n/\sigma_n = 0$. For each $x\in \R$, % $$ \limn \, \sum_{k\le \lbxn} \frac{\bnk}{Q_n(1)} = \Phi(x) $$ % where $(x)_n = x\sigma_n + \mu_n$. (As mentioned in the introduction, this is equivalent to (1).) \endclktheorem \clkremark If $d_{n,j} \le 1$ for all $1\le j \le N(n)$, then $M_n \le 1$ and $\sigma_n \to \infty$ as $n\to\infty$ suffices (Harper's method). \endclkremark A sequence $a(0),\lldots,a(D)$ of real numbers is {\it log-concave} provided $a^2(j) \ge a(j-1)a(j+1)$ for all $1\le j \le D-1$. It has {\it no internal zeros} if and only if there exist no indices $0 \le i < j < k \le D$ with $a_i,a_k \ne 0$ but $a_j=0$. The array $\{ \bnk : n\ge 1, \,\,\, 0\le k \le D_n\}$ of real numbers {\it has property $P$} provided the sequence $b(n,0), \lldots, b(n,D_n)$ has property $P$ for all $n\in \P$. We require the following result of Canfield [5; Theorem II]. %LEMMA 2 %\clklemmalab{2}{\ \ (Bender [1])} %Suppose the array %$\{\bnk : n\ge 1, \,\,\, 0\le k \le D_n\}$ satisfies (1) and %is eventually unimodal where $\sigma_n \to \infty$ as $n\to \infty$. %Then, for every $\epsilon > 0$, the array %$\{\bnk : n\ge 1, \,\,\, 0\le k \le D_n\}$ satisfies (1) on %$S = \{x\in \R : |x| \ge \epsilon\}$. %\endclklemma % %\noindent %and %LEMMA 3 \clklemmalab{2}{\ \ (Canfield [5])} %(Canfield [5]). Suppose the array $\{\bnk : n\ge 1, \,\,\, 0\le k \le D_n\}$ satisfies (1) and is log-concave with no internal zeros where $\sigma_n \to \infty$ as $n\to \infty$. Then the array $\{\bnk : n\ge 1, \,\,\, 0\le k \le D_n\}$ satisfies (2) on $S = \R$. \endclklemma \vskip 30pt \section*{\normalsize 3. Applications to Excedances} % 3 Applications to Excedances For $n\in \P$, the polynomial % $$ A_n(x) := \sum_{\sigma \in \G[n]} x^{d(\sigma)} := \sum_{k=1}^n A(n,k) x^k \in \N[x] $$ % is called the {\it $n$th Eulerian polynomial} where $A_0(x) := 1$. The {\it Eulerian numbers} $A(n,k)$ satisfy the recurrence relation % \begin{equation} A(n,k) = (n-k+1) A(n-1,k-1) + kA(n-1,k) \qquad (n,k \ge 2) % \tag{4} \end{equation} % with the boundary conditions $A(n,1)=1$ ($n\ge 1$) and $A(n,k)=0$ ($1\le n