\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \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{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \usepackage{epsfig} \usepackage{latexsym} \usepackage{amsfonts} \newtheorem{thm}{Theorem}[section] \newtheorem{lem}[thm]{Lemma} \newtheorem{cor}[thm]{Corollary} \newtheorem{prop}[thm]{Proposition} \newtheorem{rem}[thm]{Remark} \newtheorem{deff}[thm]{Definition} \newtheorem{conj}[thm]{Conjecture} \newtheorem{key}[thm]{Keywords} \newtheorem{prob}[thm]{Problem} \newenvironment{probb}{ \begin{prob} \rm}{ \end{prob} } \newcommand{\bprobb}{\begin{probb}} \newcommand{\eprobb}{\end{probb}} \newcommand{\bth}{\begin{thm}} \newcommand{\eth}{\end{thm}} \newcommand{\bconj}{\begin{conj}} \newcommand{\econj}{\end{conj}} \newcommand{\bkey}{\begin{key}} \newcommand{\ekey}{\end{key}} \newcommand{\bl}{\begin{lem}} \newcommand{\el}{\end{lem}} \newcommand{\bdeff}{\begin{deff}} \newcommand{\edeff}{\end{deff}} \newcommand{\bcor}{\begin{cor}} \newcommand{\ecor}{\end{cor}} \newcommand{\bprop}{\begin{prop}} \newcommand{\eprop}{\end{prop}} \newcommand{\brem}{\begin{rem}} \newcommand{\erem}{\end{rem}} \newcommand{\beq}{\begin{equation}} \newcommand{\eeq}{\end{equation}} \newcommand{\beqn}{\begin{eqnarray}} \newcommand{\eeqn}{\end{eqnarray}} \newcommand{\beqns}{\begin{eqnarray*}} \newcommand{\eeqns}{\end{eqnarray*}} %\newcommand{\bpr}{\begin{proof}} %\newcommand{\epr}{\end{proof}} \newcommand{\bpr}{\noindent{\bf Proof.\hspace{1em}}} \newcommand{\epr}{\hfill\rule{3mm}{3mm}\vspace{\baselineskip}\\} \newcommand{\BO}{\mathcal{O}} \newcommand{\BN}{\mathcal{N}} \newcommand{\BF}{\mathcal{F}} \newcommand{\BMC}{\mathcal{M}} \newcommand{\non}{\nonumber} \newcommand{\babs}{\begin{abstract}} \newcommand{\eabs}{\end{abstract}} \newcommand{\da}{\downarrow} \newcommand{\ra}{\rightarrow} \newcommand{\Lra}{\Leftrightarrow} \newcommand{\implies}{\Longrightarrow} \newcommand{\B}{\quad} \newcommand{\BB}{\qquad} \newcommand{\kl}{[\hspace{-0.5 mm}[} \newcommand{\kr}{]\hspace{-0.5 mm}]} \newcommand{\BU}{\mathbf{1}} \newcommand{\BR}{\mathbf{R}} \newcommand{\Bh}{\mathbf{h}} \newcommand{\BD}{\mathbf{D}} \newcommand{\BI}{\mathbf{I}} \newcommand{\BM}{\mathbf{M}} \newcommand{\BZ}{\mathbf{Z}} \newcommand{\BS}{\mathbf{S}} \newcommand{\BDd}{\mathbf{D^{(2)} }} \newcommand{\Bmu}{\mbox{\boldmath$\mu$}} \newcommand{\Bpi}{\mbox{\boldmath$\pi$}} \newcommand{\BPi}{\mbox{\boldmath$\Pi$}} \newcommand{\Bal}{\mbox{\boldmath$\al$}} \newcommand{\Bde}{\mbox{\boldmath$\de$}} \newcommand{\BFi}{\mbox{\boldmath$\Fi$}} \newcommand{\Bpsi}{\mbox{\boldmath$\psi$}} \newcommand{\Bchi}{\mbox{\boldmath$\chi$}} \newcommand{\Bpsid}{\mbox{\boldmath$\psi^{(2)}$}} \newcommand{\Bchid}{\mbox{\boldmath$\chi^{(2)}$}} \newcommand{\Bded}{\mbox{\boldmath$\de^{(2)}$}} \newcommand{\SSl}{\sum_{l=1}^\II} \newcommand{\SSi}{\sum_{i=1}^\II} \newcommand{\SSk}{\sum_{k=1}^\II} \newcommand{\SSj}{\sum_{j=1}^\II} \newcommand{\SSu}{\sum_{u=1}^\II} \newcommand{\etasi}{\eta^{*i}} \newcommand{\etas}{\eta^*} \newcommand{\las}{\la^*} \newcommand{\pis}{\pi^*} \newcommand{\xis}{\xi^*} \newcommand{\Pis}{\Pi^*} \newcommand{\xs}{x^{*}} \newcommand{\zs}{z^{*}} \newcommand{\zsi}{z^{*i}} \newcommand{\zsj}{z^{*j}} \newcommand{\zsl}{z^{*l}} \newcommand{\zsk}{z^{*k}} \newcommand{\zt}{\tilde{z}} \newcommand{\ft}{\tilde{f}} \newcommand{\FIt}{\tilde{\FI}} \newcommand{\Lt}{\tilde{L}} \newcommand{\pt}{\tilde{p}} \newcommand{\Lb}{\bar{L}} \newcommand{\hid}{h_i^{(2)}} \newcommand{\Dd}{D^{(2)}} \newcommand{\chid}{\chi^{(2)}} \newcommand{\psid}{\psi^{(2)}} \newcommand{\ded}{\de^{(2)}} \newcommand{\Tet}{\Theta} \newcommand{\de}{\delta} \newcommand{\De}{\Delta} \newcommand{\K}{\kappa} \newcommand{\la}{\lambda} \newcommand{\La}{\Lambda} \newcommand{\al}{\alpha} \newcommand{\be}{\beta} \newcommand{\srt}{\sqrt{2}} \newcommand{\srn}{\sqrt{n}} \newcommand{\srpi}{\sqrt{\pi}} \newcommand{\Fi}{\varphi} \newcommand{\FI}{\phi} \newcommand{\eps}{\varepsilon} \newcommand{\II}{\infty} \newcommand{\tet}{\theta} \newcommand{\sig}{\sigma} \newcommand{\Sig}{\Sigma} \newcommand{\gam}{\gamma} \newcommand{\Gam}{\Gamma} \newcommand{\om}{\omega} \newcommand{\Om}{\Omega} \newcommand{\ta}{\tau} \def\1{{\ifmmode 1\mskip-1.5\thinmuskip\mathrm{l}% \else\textrm{1\hskip -.23em l}\fi}} \newcommand{\conv}{\stackrel{\mathcal{D}}{\sim}} \newcommand{\equ}{\stackrel{\mathcal{D}}{\equiv}} \newcommand{\Z}{\mbox{$\mathbb Z$}} \newcommand{\E}{\mbox{$\mathbb E$}} \newcommand{\V}{\mbox{$\mathbb V$}} \newcommand{\bib}{\bibliographystyle{plain} \bibliography{biblio}} \newcommand{\dilog}{\mathrm{dilog}} \newcommand{\biindice}[3] {\renewcommand{\arraystretch}{0.6} \begin{array}[t]{c} #1\\ {\scriptstyle #2}\\ {\scriptstyle #3} \end{array} \renewcommand{\arraystretch}{1} } \newcommand{\bin}[2] { {#1\choose #2} } \newcommand{\binom}[2] { {#1\choose #2} } %BProdinger \def\j{\bold{j}} \def\fl#1{\left\lfloor#1\right\rfloor} \def\a{\alpha} \def\qf#1#2{(#1;q)_{#2}} \def\la{\lambda} \def\bu{\mathbf{u}} %EProdinger \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm {\LARGE\bf The Number of Inversions in Permutations:} \vskip .15in {\LARGE\bf A Saddle Point Approach} \vskip 1cm \large Guy Louchard\\ D\'epartement d'Informatique\\ CP 212, Boulevard du Triomphe \\ B-1050 Bruxelles \\ Belgium\\ \href{mailto:louchard@ulb.ac.be}{louchard@ulb.ac.be}\\ \ \\ Helmut Prodinger\\ University of the Witwatersrand\\ The John Knopfmacher Centre for Applicable Analysis and Number Theory\\ School of Mathematics \\ P. O. Wits \\ 2050 Johannesburg \\ South Africa \\ \href{mailto:helmut@maths.wits.ac.za}{helmut@maths.wits.ac.za} \\ \end{center} \babs Using the saddle point method, we obtain from the generating function of the inversion numbers of permutations and Cauchy's integral formula asymptotic results in central and noncentral regions. \eabs %\thanks % % \section{Introduction}\label{S1} % Let $a_1\cdots a_n$ be a permutation of the set $\{1,\dots,n\}$. If $a_i>a_k$ and $i0$. Section 5 is devoted to the moderate large deviation, and Section 6 to the large deviation. Section 7 concludes the paper. } % \section{The Gaussian limit, $ j=m+x \sig,m=n(n-1)/4 $ }\label{S2} % The Gaussian limit of $I_n(j)$ is easily derived from the generating function $\Phi_n(z)$ (using the Lindeberg-L\'evy conditions, see for instance, Feller \cite{FE68}); this is also reviewed in Margolius' paper, following Sachkov's book \cite{SA}. Another analysis is given in Bender \cite{BE73}. Indeed, this generating function corresponds to a sum for $i=1,\ldots,n$ of independent, uniform $[0..i-1]$ random variables. As an exercise, let us recover this result with the \emph{saddle point method,} with an additional correction of order $1/n$. We have, with $J_n:=I_n/n!$, \beqns m:=\E(J_n)=n(n-1)/4,\\ \sig^2:=\V(J_n)=n(2n+5)(n-1)/72. \eeqns We know that \[ I_n(j)=\frac{1}{2\pi i}\int_\Om \frac{e^{S(z)}}{z^{j+1}}dz \] where $\Om$ is inside the analyticity domain of the integrand and encircles the origin. Since $\Phi_n(z)$ is just a polynomial, the analyticity restriction can be ignored. We split the exponent of the integrand $S=\ln(\Phi_n(z))-(j+1)\ln z$ as follows: \beqn S &:=& S_1+S_2, \label{E0}\\ S_1 &:=& \sum_{i=1}^n \ln(1-z^i),\non \\ S_2 &:=& -n \ln(1-z) -(j+1) \ln z. \non \eeqn Set \[ S^{(i)} :=\frac{d^i S}{dz^i}.\] To use the saddle point method, we must find the solution of \beq S^{(1)}(\zt)=0. \label{E2} \eeq Set $\zt:=\zs-\eps$, where, here, $\zs=1$. (This notation always means that $\zs$ is the approximate saddle point and $\zt$ is the exact saddle point; they differ by a quantity that has to be computed to some degree of accuracy.) This leads, to first order, to the equation \beq [(n+1)^2/4-3n/4-5/4-j]+[-(n+1)^3/36+7(n+1)^2/24-49n/72-91/72-j]\eps=0. \label{E1} \eeq Set $ j=m+x \sig $ in (\ref{E1}). This shows that, asymptotically, $\eps$ is given by a \emph{Puiseux series\/} of powers of $n^{-1/2}$, starting with $-6x/n^{3/2} $. To obtain the next terms, we compute the next terms in the expansion of (\ref{E2}), i.e., we first obtain \beqn & & [(n+1)^2/4-3n/4-5/4-j]+[-(n+1)^3/36+7(n+1)^2/24-49n/72-91/72-j]\eps \non\\ & & {}+[-j-61/48-(n+1)^3/24+5(n+1)^2/16-31n/48]\eps^2=0. \label{E5} \eeqn More generally, even powers $\eps^{2k}$ lead to a $\BO(n^{2k+1})\cdot\eps^{2k}$ term and odd powers $\eps^{2k+1}$ lead to a $\BO(n^{2k+3})\cdot\eps^{2k+1}$ term. Now we set $j=m+x \sig $, expand into powers of $n^{-1/2}$ and equate each coefficient with $0$. This leads successively to a full expansion of $\eps$. Note that to obtain a given precision of $\eps$, it is enough to compute a given finite number of terms in the generalization of (\ref{E5}). We obtain \beqn &&\eps=-6x/n^{3/2}+(9x/2-54/25x^3)/n^{5/2}-(18 x^2+36)/n^3 \non\\ &&\qquad\qquad{}+ x[-30942/30625x^4+27/10x^2-201/16]/n^{7/2}+\BO(1/n^4). \eeqn % We have, with $\zt:=\zs-\eps$, \[J_n(j) =\frac{1}{n! 2\pi i}\int_\Om \exp\Big[S(\zt)+ S^{(2)}(\zt)(z-\zt)^2/2! +\sum_{l=3}^\II S^{(l)}(\zt)(z-\zt)^l/l! \Big]dz \] (note carefully that the linear term vanishes). Set $z=\zt +i \ta$. This gives \beq J_n(j) = \frac{1}{n! 2\pi }\exp[S(\zt)] \int_{-\II}^{\II} \exp\Big[ S^{(2)}(\zt)(i \ta)^2/2! +\sum_{l=3}^\II S^{(l)}(\zt)(i \ta)^l/l! \Big]d\ta. \label{E4} \eeq Let us first analyze $S(\zt)$. We obtain \beqns S_1(\zt) &=& \sum_{i=1}^n\ln(i)+[-3/2 \ln (n)+\ln( 6)+\ln(-x)]n+3/2x\sqrt n+43/50x^2-3/4\\ &&{}+[3x/8+6/x+ 27/50x^3 ]/\sqrt n+[ 5679/12250x^4-9/50x^2+173/16 ]/n+\BO(n^{-3/2}),\\ S_2(\zt) &=& [3/2 \ln (n)-\ln (6)-\ln(-x)]n-3/2x\sqrt n-34/25x^2+3/4\\ &&{}-[3x/8+6/x+27/50x^3 ]/\sqrt n -[5679/12250x^4-9/50x^2+173/16 ]/n+\BO(n^{-3/2}), \eeqns and so \[S(\zt)=-x^2/2+\ln(n!)+ \BO(n^{-3/2}). \] Also, \beqns S^{(2)}(\zt)&=&n^3/36+(1/24-3/100x^2) n^2 + \BO(n^{3/2}),\\ S^{(3)}(\zt) &=&\BO(n^{7/2}),\\ S^{(4)}(\zt)&=&-n^5/600+\BO(n^4),\\ S^{(l)}(\zt)&=&\BO(n^{l+1}),\quad l\geq 5. \eeqns We can now compute (\ref{E4}), for instance by using the classical trick of setting \[S^{(2)}(\zt)(i \ta)^2/2! +\sum_{l=3}^\II S^{(l)}(\zt)(i \ta)^l/l!=-u^2/2, \] computing $\ta$ as a truncated series in $u$, setting $d\ta=\frac{d\ta}{du}du$, expanding with respect to $n$ and integrating on $[u=-\II..\II]$. (This amounts to the \emph{reversion\/} of a series.) Finally, (\ref{E4}) leads to \beq J_n \sim e^{-x^2/2}\cdot \exp[(-51/50+27/50x^2)/n+\BO(n^{-3/2}) ] /(2\pi n^3/36)^{1/2}. \label {E51} \eeq Note that $S^{(3)}(\zt) $ does not contribute to the $1/n$ correction. To check the effect of the correction, we first give in Figure \ref{F4}, for $n=60$, the comparison between $J_n(j)$ and the asymptotics (\ref{E51}), without the $1/n$ term. Figure \ref{F5} gives the same comparison, with the constant term $-51/(50n)$ in the correction. Figure \ref{F6} shows the quotient of $J_n(j)$ and the asymptotics (\ref{E51}), with the constant term $-51/(50n)$. The ``hat" behaviour, already noticed by Margolius, is apparent. Finally, Figure~\ref{F62} shows the quotient of $J_n(j)$ and the asymptotics (\ref{E51}), with the full correction.\\ % \begin{figure} \begin{center} \epsfig{file=pinv3.ps,height=11cm,width=8cm,angle=270} \end{center} \caption{ $J_n(j)$ (circle) and the asymptotics (\ref{E51}) (line), without the $1/n$ term, $n=60$} \label{F4} \end{figure} % % \begin{figure} \begin{center} \epsfig{file=pinv4.ps,height=11cm,width=8cm,angle=270} \end{center} \caption{$J_n(j)$ (circle) and the asymptotics (\ref{E51}) (line), with the constant in the $1/n$ term, $n=60$} \label{F5} \end{figure} % % \begin{figure} \begin{center} \epsfig{file=pinv5.ps,height=11cm,width=8cm,angle=270} \end{center} \caption{ Quotient of $J_n(j)$ and the asymptotics (\ref{E51}), with the constant in the $1/n$ term, $n=60$} \label{F6} \end{figure} % % \begin{figure} \begin{center} \epsfig{file=pinv17.ps,height=11cm,width=8cm,angle=270} \end{center} \caption{ Quotient of $J_n(j)$ and the asymptotics (\ref{E51}), with the full $1/n$ term, $n=60$} \label{F62} \end{figure} % % \section{The case $j=n-k$} \label{S3} % Figure %\ref{F1} and \ref{F2} shows the real part of $S(z)$ as given by (\ref{E0}), together with a path $\Om$ through the saddle point. % %\begin{figure} %\begin{center} %\epsfig{file=pinv1.ps,height=11cm,width=8cm,angle=270} %\end{center} %\caption{Real part of $S(z)$. Saddle-point and path, $n=10$, $k=0$, Colour} \label{F1} %\end{figure} % % % \begin{figure} \begin{center} \epsfig{file=pinv2.ps,height=11cm,width=8cm,angle=270} \end{center} \caption{Real part of $S(z)$. Saddle-point and path, $n=10$, $k=0$ } \label{F2} \end{figure} % % It is easy to see that here, we have $\zs=1/2$. We obtain, to first order, \[[ C_{1,n} -2j-2+2n]+[C_{2,n}-4j-4-4n]\eps=0\] with \beqns C_{1,n} &=& C_1+\BO(2^{-n}),\\ C_1 &=& \sum_{i=1}^\II \frac{-2i}{ 2^i-1 } =-5.48806777751\ldots,\\ C_{2,n} &=& C_2+\BO(2^{-n}),\\ C_2 &=& \sum_{i=1}^\II 4\frac{i(i2^i-2^i+1)}{(2^i-1)^2} =24.3761367267\ldots\,. \eeqns Set $j=n-k$. This shows that, asymptotically, $\eps$ is given by a Laurent series of powers of $n^{-1}$, starting with $ (k-1+C_1/2)/(4n) $. Next, we obtain \[[ C_{1} -2j-2+2n]+[C_{2}-4j-4-4n]\eps+[C_3+8n-8j-8]\eps^2=0\] for some constant $C_3$. More generally, powers $\eps^{2k}$ lead to a $\BO(1)\cdot\eps^{2k}$ term, powers $\eps^{2k+1}$ lead to a $\BO(n)\cdot\eps^{2k+1}$ term. This gives the estimate \[\eps= (k-1+C_1/2)/(4n) +(2k-2+C_1)(4k-4+C_2)/(64n^2)+ \BO(1/n^3). \] Now we derive \[ S_1(\zt) =\ln (Q)-C_1(k-1+C_1/2)/(4n)+\BO(1/n^2) \] with $Q :=\prod_{i=1}^\II (1-1/2^i)=.288788095086\ldots $. Similarly, \[S_2(\zt)= 2 \ln(2)n+(1-k)\ln(2) +(-k^2/2+k-1/2+C_1^2/8)/(2n) + \BO(1/n^2) \] and so \[S(\zt)=\ln(Q)+ 2 \ln(2)n+(1-k)\ln(2) +(A_0+A_1 k-k^2/4)/n+\BO(1/n^2) \] with \beqns A_0 &:=& -(C_1-2)^2/16,\\ A_1 &:=& (-C_1/2+1)/2. \eeqns Now we turn to the derivatives of $S$. We will analyze, with some precision, $ S^{(2)}$, $S^{(3)}$, $S^{(4)}$ (the exact number of needed terms is defined by the precision we want in the final result). Note that, from $S^{(3)}$ on, only $S_2^{(l)}$ must be computed, as $ S_1^{(l)}(\zt) =\BO(1)$. This leads to \beqns S^{(2)}(\zt) &=& 8n +(-C_2-4k+4)+ \BO(1/n), \\ S_2^{(3)}(\zt) &=& \BO(1), \\ S_2^{(4)}(\zt) &=& 192 n +\BO(1), \\ S_2^{(l)}(\zt) &=& \BO(n),\quad l\geq 5. \eeqns We denote by $ S^{(2,1)} $ the dominant term of $ S^{(2)}(\zt)$, i.e., $S^{(2,1)} :=8n$. We now compute ($S_2^{(3)}(\zt) $ is not necessary here) \[ \frac{1}{ 2\pi }\exp[S(\zt)] \int_{-\II}^{\II} \exp[ S^{2}(\zt)(i \ta)^2/2! ] \exp[ S^{4}(\zt)(i \ta)^4/4!+\BO(n \ta^5) ]d\ta \] which gives \begin{eqnarray} I_n(n-k) & \sim & e^{ 2 \ln(2)n+(1-k)\ln(2) }\frac{Q}{( 2\pi S^{(2,1)})^{1/2}} \cdot \nonumber \\ && \exp\left\{\left[(A_0+1/8+C_2/16)+(A_1+1/4)k-k^2/4\right]/n +\BO(1/n^2)\right \}.\label{E52} \end{eqnarray} To compare our result with Margolius', we replace $n$ by $n+k$ and find $$ I_{n+k}(n)=\frac{2^{2n+k-1}}{\sqrt{\pi n}}\Big( q_0-\frac{q_0+q_2-2q_1}{8n}+\frac{(q_0-q_1)k}{4n}-\frac{q_0k^2}{n}+\BO(n^{-2})\Big). $$ We have $$ q_0=Q=\prod_{i=1}^\infty(1-2^{-i}), $$ and $$ q_1=-2q_0\sum_{i=1}^\infty\frac{i}{2^i-1}, $$ and $$ \frac{q_2}{2q_0}=-\sum_{i=1}^\infty\frac{i(i-1)}{2^i-1}+ \bigg(\sum_{i=1}^\infty\frac{i}{2^i-1}\bigg)^2 -\sum_{i=1}^\infty\frac{i^2}{{(2^i-1)}^2}. $$ Margolius' form of the constants follows from Euler's pentagonal theorem, \cite{And76} $$ Q(z)=\prod_{i=1}^{\II}(1-z^i)=\sum_{i\in\mathbb{Z}}(-1)^iz^{\frac{i(3i-1)}{2}} $$ and differentiations: $$ q_1=\sum_{i\in\mathbb{Z}}(-1)^ii(3i-1)2^{-\frac{i(3i-1)}{2}}, $$ respectively, $$ q_2= \sum_{i\in\mathbb{Z}}(-1)^i{i(3i-1)}\Big(\frac{i(3i-1)}{2}-1\Big) 2^{-\frac{i(3i-1)}{2}}. $$ In our formula, $k$ can be negative as well (which was excluded in Margolius' analysis). Figure \ref{F7} gives, for $n=300$, $I_n(n-k)$ normalized by the first two terms of (\ref{E52}) together with the $1/n$ correction in (\ref{E52}); the result is a bell shaped curve, which is perhaps not too unexpected. Figure~\ref{F8} shows the quotient of $I_n(n-k)$ and the asymptotics (\ref{E52}).\\ % \begin{figure} \begin{center} \epsfig{file=pinv6.ps,height=11cm,width=8cm,angle=270} \end{center} \caption{ normalized $I_n(n-k)$ (circle) and the $1/n$ term in the asymptotics (\ref{E52}) (line), $n=300$ } \label{F7} \end{figure} % % \begin{figure} \begin{center} \epsfig{file=pinv7.ps,height=11cm,width=8cm,angle=270} \end{center} \caption{ Quotient of $I_n(n-k)$ and the asymptotics (\ref{E52}), $n=300$ } \label{F8} \end{figure} % % \section{The case $j= \al n-x$, $\al>0$ }\label{S4} % Of course, we must have that $\al n-x $ is an integer. For instance, we can choose $\al$, $x $ integers. But this also covers more general cases, for instance $I_{\al n +\be}(\gam n+\de)$, with $\al$, $\be$, $\gam$, $\de$ integers. We have here $\zs=\al/(1+\al)$. We derive, to first order, \[[ C_{1,n}(\al) -(j+1)(1+\al)/\al+(1+\al)n]+[C_{2,n}(\al)-(j+1)(1+\al)^2/\al^2-(1+\al)^2 n]\eps =0\] with, setting $\Fi (i,\al) :=[\al/(1+\al)]^i $, \beqns C_{1,n}(\al) &=& C_1(\al)+ \BO( [\al/(1+\al)] ^{-n}), \\ C_1(\al) &=& \sum_{i=1}^\II \frac{i(1+\al) \Fi(i,\al) }{ \al[ \Fi(i,\al) -1]}, \\ C_{2,n}(\al) &=& C_2(\al)+ \BO( [\al/(1+\al)] ^{-n}), \\ C_2(\al) &=& \sum_{i=1}^\II \Fi(i,\al) i(1+\al)^2(i-1+\Fi(i,\al) )/ [(\Fi(i,\al) -1)^2\al^2]. \eeqns Set $j=\al n-x$. This leads to \[\eps= [x+\al x-1-\al+C_1\al]/[ (1+\al)^3n]+\BO(1/n^2). \] Next, we obtain \beqns &&[ C_{1,n}(\al) -(j+1)(1+\al)/\al+(1+\al)n]+[C_{2,n}(\al)-(j+1)(1+\al)^2/\al^2-(1+\al)^2 n]\eps\\ &&\quad{}+[C_{3,n}(\al)+(1+\al)^3n-(j+1)(1+\al)^3/\al^3]\eps^2=0 \eeqns for some function $C_{3,n}(\al)$. More generally, powers $\eps^{k}$ lead to a $\BO(n)\cdot\eps^{k}$ term. This gives \beqns \eps&=& [x+\al x-1-\al+C_1\al]/[ (1+\al)^3n]+ (x+x\al-1-\al+C_1 \al)\times\\ &&\quad{}\times(x+2x\al+x\al^2-\al^2+C_1\al^2-2\al+C_2\al-1-C_1)/[(1+\al)^6n^2] +\BO(1/n^3). \eeqns Next we derive \[S_1(\zt)= \ln(\hat Q(\al)) -C_1[x+\al x-1-\al+C_1\al]/[ (1+\al)^3n] +\BO(1/n^2) \] with \[\hat Q(\al):=\prod_{i=1}^\II (1-\Fi(i,\al) ) =\prod_{i=1}^\II \bigg(1-\Big(\frac{\al}{1+\al}\Big)^i \bigg)=Q\Big(\frac{\al}{1+\al}\Big). \] Similarly \beqns S_2(\zt) &=& [-\ln(1/(1+\al)) -\al \ln(\al/(1+\al)) ]n+(x-1) \ln(\al/(1+\al)) \\ &&{}+ \{(C_1\al+\al+1) (C_1\al-\al-1) /[2\al(1+\al)^3]+x/[\al(1+\al)] \\ && \ -x^2/[2\al(1+\al)]\}/n +\BO(1/n^2). \eeqns So \beqns S(\zt) &=& [-\ln(1/(1+\al)) -\al \ln(\al/(1+\al)) ]n+\ln(\hat Q(\al)) +(x-1) \ln(\al/(1+\al)) \\ &&{}+ \{-(C_1\al-\al-1)^2/[2\al(1+\al)^3]-x(C_1\al-\al-1) /[\al(1+\al)^2]-x^2/[2\al(1+\al)]\}/n \\ && +\ \BO(1/n^2). \eeqns The derivatives of $S$ are computed as follows: \beqns S^{(2)}(\zt) &=& (1+\al)^3/\al n -(2x\al^3+2C_1\al^3-2\al^3+C_2\al^2+3x\al^2-3\al^2-2C_1\al-x+1)/\al^2+\BO(1/n), \\ S_2^{(3)}(\zt) &=& 2(1+\al^3)(\al^2-1)/\al^2 n+ \BO(1), \\ S_2^{(4)}(\zt) &=& 6(1+\al)^4(\al^3+1)/\al^3 n+\BO(1), \\ S_2^{(l)}(\zt) &=& \BO(n),\quad l\geq 5. \eeqns We denote by $ S^{(2,1)} $ the dominant term of $ S^{(2)}(\zt)$, e.g., $ S^{(2,1)} :=n(1+\al)^3/\al$. Note that, now, $ S_2^{(3)}(\zt) =\BO(n)$, so we cannot ignore its contribution. Of course, $\mu_3=0$ (third moment of the Gaussian), but $\mu_6\neq 0$, so $ S_2^{(3)}(\zt) $ contributes to the $1/n$ term. Finally, Maple gives us \beqn I_n(\al n-x ) &\sim& e^{ [-\ln(1/(1+\al)) -\al \ln(\al/(1+\al)) ]n +(x-1) \ln(\al/(1+\al)) } \frac{\hat Q(\al)}{( 2\pi S^{(2,1)})^{1/2} }\times\non \\ &&{}\times \exp[\{-(1+3\al+4\al^2-12\al^2C_1+6C_1^2\al^2+\al^4+3\al^3-6C_2\al^2 \\ && -12C_1^3\al)/[12\al(1+\al)^3]\} ] \non\\ &&{}\left. \left. + x(2\al^2-2C_1\al+3\al+1)/[2\al(1+\al)^2]-x^2/[2\al(1+\al)]\right\}/n+ \BO(1/n^2) \right] \non. \label{E53} \eeqn Figure \ref{F9} gives, for $\al=1/2$, $n=300$, $I_n(\al n-x)$ normalized by the first two terms of (\ref{E53}) together with the $1/n$ correction in (\ref{E53}). Figure \ref{F10} shows the quotient of $I_n(\al n-x)$ and the asymptotics (\ref{E53}).\\ % \begin{figure} \begin{center} \epsfig{file=pinv8.ps,height=11cm,width=8cm,angle=270} \end{center} \caption{normalized $I_n(\al n-x)$ (circle) and the $1/n$ term in the asymptotics (\ref{E53}) (line), $\al=1/2$, $n=300$ } \label{F9} \end{figure} % % \begin{figure} \begin{center} \epsfig{file=pinv9.ps,height=11cm,width=8cm,angle=270} \end{center} \caption{ Quotient of $I_n(\al n-x)$ and the asymptotics (\ref{E53}), $\al=1/2$, $n=300$} \label{F10} \end{figure} % % \section{ The moderate Large deviation, $ j=m+x n^{7/4}$ }\label{S21} % Now we consider the case $ j=m+x n^{7/4}$. We have here $\zs=1$. We observe the same behaviour as in Section \ref{S2} for the coefficients of $\eps$ in the generalization of (\ref{E5}). Proceeding as before, we see that asymptotically, $\eps$ is now given by a Puiseux series of powers of $n^{-1/4}$, starting with $-36x/n^{5/4} $. This leads to \[\eps=-36x/n^{5/4}-1164/25x^3/n^{7/4}+(-240604992/30625x^5+54x)/n^{9/4}+F_1(x)/n^{5/2} +\BO(n^{-11/4}), \] where $F_1$ is an (unimportant) polynomial of $x$. This leads to \beqns S(\zt)&=&\ln(n!) -18x^2 \sqrt n -2916/25x^4 -27/625x^2(69984x^4-625)/\sqrt n\\ &&{}-1458/15625x^4(-4375+1259712x^4)/n + \BO(n^{-5/4}). \eeqns Also, \beqns S^{(2)}(\zt)&=&n^3/36+(1/24+357696/30625x^4)n^2-27/25x^2n^{5/2}+ \BO(n^{7/4}),\\ S^{(3)}(\zt) &=&-1/12 n^3+\BO(n^{15/4}),\\ S^{(4)}(\zt)&=&-n^5/600+\BO(n^{9/2}),\\ S^{(l)}(\zt)&=&\BO(n^{l+1}),\quad l\geq 5, \eeqns and finally we obtain \beqn J_n &\sim& e^{-18x^2 \sqrt n -2916/25x^4 }\times \non\\ &&{}\times \exp\Big[x^2(-1889568/625x^4+1161/25)/\sqrt n\non\\ &&{} +(-51/50 -1836660096/15625x^8+17637426/30625x^4)/n \non\\ &&{}+\BO(n^{-5/4}) \Big]/(2\pi n^3/36)^{1/2}. \label {E511} \eeqn Note that $S^{(3)}(\zt) $ does not contribute to the correction and that this correction is equivalent to the Gaussian case when $x=0$. Of course, the dominant term is null for $x=0$. To check the effect of the correction, we first give in Figure \ref{F41}, for $n=60$ and $x \in[-1/4..1/4]$, the comparison between $J_n(j)$ and the asymptotics (\ref{E511}), without the $1/\sqrt n$ and $1/n$ term. Figure \ref{F51} gives the same comparison, with the correction. Figure \ref{F61} shows the quotient of $J_n(j)$ and the asymptotics (\ref{E511}), with the $1/\sqrt n$ and $1/n$ term. \\ % \begin{figure} \begin{center} \epsfig{file=pinv12.ps,height=11cm,width=8cm,angle=270} \end{center} \caption{ $J_n(j)$ (circle) and the asymptotics (\ref{E511}) (line), without the $1/\sqrt n$ and $1/n$ term, $n=60$} \label{F41} \end{figure} % % \begin{figure} \begin{center} \epsfig{file=pinv13.ps,height=11cm,width=8cm,angle=270} \end{center} \caption{$J_n(j)$ (circle) and the asymptotics (\ref{E511}) (line), with the $1/\sqrt n$ and $1/n$ term, $n=60$} \label{F51} \end{figure} % % \begin{figure} \begin{center} \epsfig{file=pinv14.ps,height=11cm,width=8cm,angle=270} \end{center} \caption{ Quotient of $J_n(j)$ and the asymptotics (\ref{E511}), with the $1/\sqrt n$ and $1/n$ term, $n=60$} \label{F61} \end{figure} % The exponent $7/4$ that we have chosen is of course not sacred; any fixed number below $2$ could also have been considered. % \section{Large deviations, $ j= \al n(n-1)$, $0<\al <1/2$}\label{S5} % Here, again, $\zs=1$. Asymptotically, $\eps$ is given by a Laurent series of powers of $n^{-1}$, but here the behaviour is quite different: \textit{all} terms of the series generalizing (\ref{E5}) contribute to the computation of the coefficients. It is convenient to analyze separately $S_1^{(1)}$ and $S_2^{(1)}$. This gives, by substituting \[\zt:=1-\eps,\ j= \al n(n-1) ,\ \eps= a_1/n+a_2/n^2 +a_3/n^3+\BO(1/n^4) ,\] and expanding with respect to $n$, \beqns S_2^{(1)}(\zt) &\sim& (1/a_1-\al) n^2+ (\al-\al a_1-a_2/a_1^2) n+\BO(1),\\ S_1^{(1)}(\zt) &\sim& \sum_{k=0}^{n-1} f(k), \eeqns where \beqns f(k) &:=& -(k+1)(1-\eps)^k/[1-(1-\eps)^{k+1}]\\ &=& -(k+1) (1-[a_1/n+a_2/n^2 +a_3/n^3+\BO(1/n^4) ])^k\\&&\quad{}/ \{1-(1-[a_1/n+a_2/n^2 +a_3/n^3+\BO(1/n^4) ])^{k+1}\} . \eeqns This immediately suggests to apply the Euler-Mac Laurin summation formula, which gives, to first order, \[ S_1^{(1)}(\zt) \sim \int_0^n f(k) dk -\frac12(f(n)-f(0)) ,\] so we set $k=-un/a_1$ and expand $-f(k)n/a_1$. This leads to \beqns \int_0^n f(k) dk &\sim& \int_0^{-a_1} \left[-\frac{u e^u}{a_1^2(1-e^u)}n^2 +\frac{e^u[2a_1^2-2e^u a_1^2-2u^2a_2-u^2a_1^2+2e^u ua_1^2]}{2a_1^3(1-e^u)^2}n \right] du+\BO(1) \\ &&\qquad\qquad -\frac12(f(n)-f(0))\\ &\sim& \left(\frac{ e^{-a_1} }{2(1-e^{-a_1} )} -\frac{1}{2a_1}\right) n+\BO(1). \eeqns This readily gives \beqns \int_0^n f(k) dk &\sim& - \dilog( e^{-a_1}) /a_1^2 n^2\\ &+& [2a_1^3 e^{-a_1}+a_1^4 e^{-a_1} -4 a_2\dilog( e^{-a_1}) +4a_2\dilog( e^{-a_1}) e^{-a_1} \\ &+&2a_2a_1^2e^{-a_1}-2a_1^2+2a_1^2e^{-a_1}]/[2a_1^3(e^{-a_1}-1)] n +\BO(1). \eeqns Combining $S_1^{(1)}(\zt) +S_2^{(1)}(\zt)=0$, we see that $a_1= a_1(\al) $ is the solution of \[ -\dilog( e^{-a_1}) /a_1^2 +1/a_1-\al=0. \] We check that $ \lim_{\al\to0}a_1(\al) =\II$, $\lim_{\al\to1/2}a_1(\al) =-\II $. Similarly, $a_2(\al)$ is the solution of the linear equation \beqns &&\al-\al a_1-a_2/a_1^2+ e^{-a_1} /[2(1-e^{-a_1} )]-1/(2a_1) \\ &+&[2a_1^3 e^{-a_1}+a_1^4 e^{-a_1} +4 a_2 \dilog( e^{-a_1}) (e^{-a_1} -1) +2a_2a_1^2e^{-a_1}-2a_1^2+2a_1^2 e^{-a_1} ]/[2a_1^3(e^{-a_1} -1)]\\ &=&0 \eeqns and $ \lim_{\al\to0}a_2(\al) =-\II$, $\lim_{\al\to1/2}a_2(\al) =\II$. We could proceed in the same manner to derive $a_3(\al)$ but the computation becomes quite heavy. So we have computed an approximate solution $\tilde{a}_3(\al)$ as follows: we have expanded $S^{(1)}(\zt)$ into powers of $\eps$ up to $\eps^{19}$. Then an asymptotic expansion into $n$ leads to a $n^0$ coefficient which is a polynomial of $a_1$ of degree $19$ (of degree $2$ in $a_2$ and linear in $a_3$). Substituting $a_1(\al)$, $a_2(\al)$ immediately gives $\tilde{a}_3(\al)$. This approximation is satisfactory for $\al \in[0.15..0.35]$. Note that $a_1(1/4)=0$, $a_2(1/4)=0$ as expected, and $a_3(1/4)=-36$. We obtain \beqns S(\zt)& =&\ln(n!)+[1/72a_1(a_1-18+72\al)]n\\ &+&[1/72a_1^3-1/4a_2+1/4a_1-a_1\al-5/48a_1^2+1/36a_1a_2+a_2\al+1/2a_1^2\al]\\ &+&[1/72a_2^2+1/36a_1a_3-1/4a_3+1/4a_2+a_1+a_3\al+a_1a_2\al+1/3a_1^3\al\\ &-&a_2\al-1/2a_1^2\al-5/24a_1a_2+1/24a_1^2a_2+13/144a_1^2-1/16a_1^3]/n+\BO(1/n^2). \eeqns Note that the three terms of $S(\zt)$ are null for $\al=1/4$, as expected. This leads to \beqns S^{(2)}(\zt) &=& n^3/36+(-5/24+1/12a_1+\al)n^2+\BO(n), \\ S^{(3)}(\zt) &=& 1/600a_1 n^4+\BO(n^3), \\ S^{(4)}(\zt) &=& -n^5/600+\BO(n^4), \\ S_2^{(l)}(\zt) &=& \BO(n^{l+1}),\quad l\geq 5. \eeqns Finally, \beqn &&J_n(\al n(n-1)) \non \\ &\sim& e^{ [1/72a_1(a_1-18+72\al)]n +[1/72a_1^3-1/4a_2+1/4a_1-a_1\al-5/48a_1^2+1/36a_1a_2+a_2\al+1/2a_1^2\al]} \frac{1}{( 2\pi n^3/36)^{1/2}}\times\non\\ & &{}\times \exp[ (1/72a_2^2+1/36a_1a_3-1/4a_3+1/4a_2-1/2a_1 +a_3\al+a_1a_2\al+1/3a_1^3\al-a_2\al \non \\ & -&1/2a_1^2\al-5/24a_1a_2+1/24a_1^2a_2+1139/18000a_1^2-1/16a_1^3+87/25-18\al)/n \non \\ && +\ \BO(1/n^2) ] . \label{E54} \eeqn Note that, for $\al=1/4$, the $1/n$ term gives $-51/50$, again as expected. Figure \ref{F11} gives, for $n=80$ and $\al \in[0.15..0.35]$, $J_n(\al n(n-1))$ normalized by the first two terms of (\ref{E54}) together with the $1/n$ correction in (\ref{E54}). Figure \ref{F12} shows the quotient of $J_n(\al n(n-1))$ and the asymptotics (\ref{E54}).\\ % \begin{figure} \begin{center} \epsfig{file=pinv15.ps,height=11cm,width=8cm,angle=270} \end{center} \caption{normalized $J_n(\al n(n-1))$ (circle) and the $1/n$ term in the asymptotics (\ref{E54}) (line), $n=80$ } \label{F11} \end{figure} % % \begin{figure} \begin{center} \epsfig{file=pinv16.ps,height=11cm,width=8cm,angle=270} \end{center} \caption{Quotient of $J_n(\al n(n-1))$ and the asymptotics (\ref{E54}), $n=80$} \label{F12} \end{figure} % % \section{Conclusion}\label{S6} % Once more the \emph{saddle point method\/} revealed itself as a powerful tool for asymptotic analysis. With careful human guidance, the computational operations are almost automatic, and can be performed to any degree of accuracy with the help of some computer algebra, at least in principle. This allowed us to include correction terms in our asymptotic formul{\ae}, where we have covered all ranges of interest and one can see their effect in the figures displayed. An interesting open problem would be to extend our results to $q-$analogues (see, for instance, \cite{P01}). \section{Acknowledgments} The pertinent comments of the referee led to improvements in the presentation. \bibliographystyle{plain} %\bibliography{C:/texfiles2002/biblio} \begin{thebibliography}{1} \bibitem{And76} G.E. Andrews. \newblock {\em The Theory of Partitions}, volume~2 of {\em Encyclopedia of Mathematics and its Applications}. \newblock Addison--Wesley, 1976. \bibitem{BE73} E.A. Bender. \newblock Central and local limit theorems applied to asymptotics enumeration. \newblock {\em Journal of Combinatorial Theory, {\rm {S}eries {A}}}, {\bf 15} (1973), 91--111. \bibitem{FE68} W.~Feller. \newblock {\em Introduction to Probability Theory and its Applications. Vol I}. \newblock Wiley, 1968. \bibitem{FS94} P.~Flajolet and R.~Sedgewick. \newblock Analytic combinatorics---symbolic combinatorics: Saddle point asymptotics. \newblock Technical Report 2376, INRIA, 1994. \bibitem{HW98} H.K. Hwang. \newblock Large deviations of combinatorial distributions II: Local limit theorems. \newblock {\em Annals of Applied Probability} {\bf 8} (1998), 163--181. \bibitem{P01} H. Prodinger \newblock Combinatorics of geometrically distributed random variables: Inversions and a parameter of Knuth. \newblock {\em Annals of Combinatorics} {\bf 5} (2001), 241--250. \bibitem{MA01} B.H. Margolius. \newblock Permutations with inversions. \newblock {\em Journal of Integer Sequences}, {\bf 4} (2001), 1--13. \bibitem{OD95} A.~Odlyzko. \newblock Asymptotic enumeration methods. \newblock In R. Graham, M. G{\"o}tschel, and L. Lov\'{a}sz, eds., {\it Handbook of Combinatorics}, Elsevier Science, 1995, pp.\ 1063--1229. \bibitem{SA} V.N. Sachkov. \newblock {\em Probabilistic Methods in Combinatorial Analysis}. \newblock Cambridge University Press, 1997. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 05A16; Secondary 05A10. \noindent \emph{Keywords: } Inversions, permutations, saddle point method . \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received November 15, 2002; revised version received July 3, 2003. Published in {\it Journal of Integer Sequences}, July 22, 2003. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwate rloo.ca/JIS/}. \vskip .1in \end{document}