<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}

\usepackage[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&gt;a_k$ and $i&lt;k$, the pair $(a_i,a_k)$ is called an {\it inversion};
$I_n(j)$ is the number of permutations of length $n$ with $j$ inversions. 
In a recent paper \cite{MA01}, several facts about these
numbers are nicely reviewed, and---as new results---asymptotic
formul{\ae} for the numbers $I_{n+k}(n)$ for fixed $k$ and $n\to \infty$
are derived. This is done using Euler's pentagonal theorem, which leads to
a handy explicit formula for $I_n(j)$, valid for $j\le n$ only. 

Here, we show how to extend these results using the \emph{saddle point method}.
This leads, e.\,g., to asymptotics for $I_{\al n+\be}(\gamma n+\delta)$, for integer
constants $\al$, $\be$, $\gamma$,
$\delta$ and more general ones as well. 
With this technique, we will also show 
the known result that  $I_n(j)$ is asymptotically normal.

The generating function for the numbers $I_n(j)$ is given
by
$$
\Phi_n(z)=\sum_{j\ge0}I_n(j)z^j=(1-z)^{-n}\prod_{i=1}^n(1-z^i).
$$
By Cauchy's theorem,
$$
I_n(j)=\frac1{2\pi i}\int_{\mathcal{C}}\Phi_n(z)\frac{dz}{z^{j+1}},
$$
where ${\mathcal{C}}$ is, say, a circle around the origin
passing (approximately) through the saddle point. In 
Figure~\ref{sad3}, the saddle point (near $z=\frac12$) is shown for $n=j=10$.

\begin{figure}\label{sad3}
\begin{center}
\epsfig{file=saddle3.ps,height=11cm,width=8cm,angle=270}
\caption{$|\Phi_{10}(z)/z^{11}|$ and the path of integration}
\end{center}
\end{figure}


As general references for the application of the saddle point method
in enumeration we cite \cite{FS94,OD95}.

Actually, we obtain here local limit theorems with some corrections
(=lower order terms).
%\textbf
{For other such theorems in large deviations of
 combinatorial distributions, see, for instance, Hwang \cite{HW98}.}

%\textbf
{The paper is organized as follows: Section 2 deals with the Gaussian limit. 
In Section 3,
 we analyze the case  $j=n-k$, that we generalize in Section 4 to the case 
$j=\al n-x$, $\al&gt;0$.
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 &amp;:=&amp; S_1+S_2, \label{E0}\\
S_1 &amp;:=&amp; \sum_{i=1}^n \ln(1-z^i),\non \\
S_2 &amp;:=&amp; -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
&amp; &amp; [(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\\
&amp; &amp; {}+[-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
&amp;&amp;\eps=-6x/n^{3/2}+(9x/2-54/25x^3)/n^{5/2}-(18 x^2+36)/n^3 \non\\
&amp;&amp;\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) &amp;=&amp; \sum_{i=1}^n\ln(i)+[-3/2 \ln (n)+\ln( 6)+\ln(-x)]n+3/2x\sqrt n+43/50x^2-3/4\\
&amp;&amp;{}+[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) &amp;=&amp; [3/2 \ln (n)-\ln (6)-\ln(-x)]n-3/2x\sqrt n-34/25x^2+3/4\\
&amp;&amp;{}-[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)&amp;=&amp;n^3/36+(1/24-3/100x^2) n^2 + \BO(n^{3/2}),\\
S^{(3)}(\zt) &amp;=&amp;\BO(n^{7/2}),\\
S^{(4)}(\zt)&amp;=&amp;-n^5/600+\BO(n^4),\\
S^{(l)}(\zt)&amp;=&amp;\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} &amp;=&amp; C_1+\BO(2^{-n}),\\
C_1 &amp;=&amp; \sum_{i=1}^\II \frac{-2i}{ 2^i-1 } =-5.48806777751\ldots,\\
 C_{2,n} &amp;=&amp; C_2+\BO(2^{-n}),\\
C_2 &amp;=&amp; \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 &amp;:=&amp; -(C_1-2)^2/16,\\
A_1 &amp;:=&amp; (-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) &amp;=&amp; 8n +(-C_2-4k+4)+ \BO(1/n), \\  
S_2^{(3)}(\zt) &amp;=&amp; \BO(1), \\
S_2^{(4)}(\zt) &amp;=&amp; 192 n +\BO(1), \\
S_2^{(l)}(\zt) &amp;=&amp; \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) &amp; \sim &amp; e^{ 2 \ln(2)n+(1-k)\ln(2) }\frac{Q}{( 2\pi S^{(2,1)})^{1/2}}
\cdot \nonumber \\
&amp;&amp; 
\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&gt;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) &amp;=&amp; C_1(\al)+ \BO( [\al/(1+\al)] ^{-n}), \\
C_1(\al) &amp;=&amp; \sum_{i=1}^\II \frac{i(1+\al) \Fi(i,\al) }{ \al[ \Fi(i,\al) -1]}, \\
 C_{2,n}(\al) &amp;=&amp; C_2(\al)+ \BO( [\al/(1+\al)] ^{-n}), \\
C_2(\al) &amp;=&amp; \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
&amp;&amp;[ 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\\
&amp;&amp;\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&amp;=&amp; [x+\al x-1-\al+C_1\al]/[ (1+\al)^3n]+
 (x+x\al-1-\al+C_1 \al)\times\\
&amp;&amp;\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) &amp;=&amp; [-\ln(1/(1+\al)) -\al \ln(\al/(1+\al)) ]n+(x-1) \ln(\al/(1+\al)) \\
&amp;&amp;{}+ \{(C_1\al+\al+1) (C_1\al-\al-1) /[2\al(1+\al)^3]+x/[\al(1+\al)] \\
&amp;&amp; \ -x^2/[2\al(1+\al)]\}/n +\BO(1/n^2).
\eeqns
So
\beqns
S(\zt) &amp;=&amp; [-\ln(1/(1+\al)) -\al \ln(\al/(1+\al)) ]n+\ln(\hat Q(\al)) +(x-1) \ln(\al/(1+\al)) \\
&amp;&amp;{}+ \{-(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 \\
&amp;&amp; +\ \BO(1/n^2). 
\eeqns
The derivatives of $S$ are computed as follows:
\beqns
S^{(2)}(\zt) &amp;=&amp; (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) &amp;=&amp; 2(1+\al^3)(\al^2-1)/\al^2 n+ \BO(1), \\
S_2^{(4)}(\zt) &amp;=&amp;  6(1+\al)^4(\al^3+1)/\al^3 n+\BO(1), \\
S_2^{(l)}(\zt) &amp;=&amp; \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 ) 
&amp;\sim&amp; 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 \\
&amp;&amp;{}\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 \\
&amp;&amp; -12C_1^3\al)/[12\al(1+\al)^3]\} ] \non\\
&amp;&amp;{}\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)&amp;=&amp;\ln(n!) -18x^2 \sqrt n -2916/25x^4 -27/625x^2(69984x^4-625)/\sqrt n\\
&amp;&amp;{}-1458/15625x^4(-4375+1259712x^4)/n +
 \BO(n^{-5/4}). 
\eeqns

Also, 
\beqns
S^{(2)}(\zt)&amp;=&amp;n^3/36+(1/24+357696/30625x^4)n^2-27/25x^2n^{5/2}+ \BO(n^{7/4}),\\
S^{(3)}(\zt) &amp;=&amp;-1/12 n^3+\BO(n^{15/4}),\\
S^{(4)}(\zt)&amp;=&amp;-n^5/600+\BO(n^{9/2}),\\
S^{(l)}(\zt)&amp;=&amp;\BO(n^{l+1}),\quad l\geq 5,
\eeqns
 and finally we obtain 
\beqn
J_n &amp;\sim&amp; e^{-18x^2 \sqrt n -2916/25x^4  }\times \non\\
 &amp;&amp;{}\times \exp\Big[x^2(-1889568/625x^4+1161/25)/\sqrt n\non\\
&amp;&amp;{} +(-51/50 -1836660096/15625x^8+17637426/30625x^4)/n
\non\\
 &amp;&amp;{}+\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&lt;\al &lt;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) &amp;\sim&amp; (1/a_1-\al) n^2+ (\al-\al a_1-a_2/a_1^2) n+\BO(1),\\
S_1^{(1)}(\zt) &amp;\sim&amp;  \sum_{k=0}^{n-1} f(k), 
\eeqns
where
\beqns
f(k) &amp;:=&amp; -(k+1)(1-\eps)^k/[1-(1-\eps)^{k+1}]\\
&amp;=&amp; -(k+1) (1-[a_1/n+a_2/n^2 +a_3/n^3+\BO(1/n^4) ])^k\\&amp;&amp;\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 &amp;\sim&amp; \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) \\
&amp;&amp;\qquad\qquad -\frac12(f(n)-f(0))\\
 &amp;\sim&amp; \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 &amp;\sim&amp; - \dilog( e^{-a_1}) /a_1^2  n^2\\
&amp;+&amp; [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} \\
&amp;+&amp;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
&amp;&amp;\al-\al a_1-a_2/a_1^2+  e^{-a_1} /[2(1-e^{-a_1} )]-1/(2a_1) \\
&amp;+&amp;[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)]\\
&amp;=&amp;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)&amp; =&amp;\ln(n!)+[1/72a_1(a_1-18+72\al)]n\\
 &amp;+&amp;[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]\\
&amp;+&amp;[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\\
&amp;-&amp;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) &amp;=&amp; n^3/36+(-5/24+1/12a_1+\al)n^2+\BO(n), \\  
S^{(3)}(\zt) &amp;=&amp; 1/600a_1 n^4+\BO(n^3), \\  
S^{(4)}(\zt) &amp;=&amp; -n^5/600+\BO(n^4), \\  
S_2^{(l)}(\zt) &amp;=&amp; \BO(n^{l+1}),\quad l\geq 5. 
\eeqns 

 
Finally,
\beqn
&amp;&amp;J_n(\al n(n-1)) \non \\
&amp;\sim&amp; 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\\
 &amp; &amp;{}\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 \\
&amp; -&amp;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 \\
&amp;&amp; +\ \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}







 





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