\documentclass[11pt]{article}
\usepackage
[colorlinks=true,
linkcolor=webblue,
filecolor=webbrown,
citecolor=webblue]
{hyperref}

%\usepackage{graphicx}
\usepackage{amssymb,graphics,psfig,epsfig}
\usepackage{amsthm,amssymb}
%\usepackage[dvips]{graphicx,epsfig}


%\usepackage{mathtimy}

% i changed the next line - njas

\setlength{\topmargin}{-.3in}
\setlength{\textwidth}{5.5in}
\setlength{\textheight}{8.6in}
\setlength{\oddsidemargin}{0 in}
\renewcommand{\baselinestretch}{1.2}
\def\ds{\displaystyle}
\pagestyle{myheadings}

\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\N}{\mathbb N}
\newcommand{\Q}{\mathbb Q}
\newcommand{\Z}{\mathbb Z}

\markright{ Margolius }  % Put author surname(s) here
\parskip = 3mm
\begin{document}
\thispagestyle{empty}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo122.eps}
\vskip 1cm
{\LARGE\bf Permutations with Inversions}
\vskip 1cm
\large Barbara H.~Margolius \\
Cleveland State University \\
Cleveland, Ohio 44115 \\
\medskip
Email address:
\href{mailto:b.margolius@csuohio.edu}{b.margolius@csuohio.edu}
\vskip2cm
\bf {Abstract}
\end{center}

\newtheorem{defin}{Definition}
\newtheorem{algo}{Algorithm}
\newtheorem{exer}{Exercise}
\newtheorem{theorem}{Theorem}
\newtheorem{coro}{Corollary}
\newtheorem{remark}{Remark}
\newtheorem{lemma}{Lemma}
\newtheorem{claim}{Claim}

{\em The number of inversions in a random 
permutation is a way to measure the extent to which the permutation is
``out of order". 
Let $I_n (k)$ denote the number of permutations of length $n$ with $k$ inversions.
This paper gives asymptotic formulae for the sequences $\{I_{n+k} (n), n=1,2,\ldots \}$ for fixed $k$.
}


\paragraph*{1. Introduction} 
Let $a_1,a_2,\dots,a_n$ be a permutation of the set $\{1,2,\dots,n\}$.  If $i<j$ and $a_i>a_j$, the pair $(a_i,a_j)$ is called an ``inversion" of the permutation; for example, the permutation 3142 has three inversions: (3,1), (3,2), and (4,2).  Each inversion is a pair of 
elements that is ``out of sort", so the only permutation with no
inversions is the sorted permutation.

\paragraph*{2. Generating Function} 
Let $I_n(k)$ represent the number of permutations of length $n$
with $k$ inversions.  
\begin{theorem}[Muir,1898] \cite{muir} The numbers $I_n(k)$ have as generating
function
\begin{eqnarray*}
\Phi_n(x)&=&\sum_{k=0}^{n\choose 2}I_n(k)x^k\cr
&=&\prod_{j=1}^n\sum_{k=0}^{j-1}x^k\cr
&=&\prod_{j=1}^n\frac{1-x^j}{1-x}.
\end{eqnarray*}
\end{theorem}
Clearly the number of permutations with no inversions, $I_n(0)$, is
1 for all $n$, and in particular $I_1(0)=1=\Phi_1(x)$.  So the 
formula given in the theorem is correct for $n=1$. 
Consider 
a permutation of $n-1$ elements.  We insert the $n$th element 
in the $j$th position, $j=1,2,\dots,n$, choosing the insertion point
randomly.  Since the $n$th element is larger than the $n-1$
elements in the set $\{1,2,\dots,n-1\}$, by inserting the element
in the $j$th position, $n-j$ additional inversions are added.  
The generating function for the number of additional inversions
is $1+x+x^2+\cdots+x^{n-1}$ since each number of additional inversions
is equally likely.  The additional inversions are independent from 
the inversions present in the permutation of length $n-1$, so the 
total number of inversions has as its generating function the 
product of the generating function for $n-1$ inversions and the 
generating function for the additional inversions: 
\begin{eqnarray*}
\Phi_n(x)&=&(1+x+\cdots+x^{n-1})\Phi_{n-1}(x).
\end{eqnarray*}
The required result then follows by induction.


Below is a table of values of the number of inversions (see sequence A008302 in \cite{eis}, also \cite{comtet}, \cite{davidbarton1}, \cite{knuth}, \cite{netto}):

\noindent
\begin{tabular}{|r||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\multicolumn{15}{|c|}{Table 1 $I_n(k)=I_n({n\choose 2}-k)$}
\\* \hline\hline
&\multicolumn{14}{|c|}{$k$, number of inversions}\\* \hline\hline
$n\backslash k$&0&1&2&3&4&5&6&7&8&9&10&11&12&13\\* \hline\hline
1&${\bf 1}$&&&&&&&&&&&&&\\ \hline
2&1&${\bf 1}$&&&&&&&&&&&&\\ \hline
3&1&2&${\bf 2}$&1&&&&&&&&&&\\ \hline
4&1&3&5&${\bf 6}$&5&3&1&&&&&&&\\ \hline
5&1&4&9&15&${\bf 20}$&22&20&15&9&4&1&&&\\ \hline
6&1&5&14&29&49&${\bf 71}$&90&101&101&90&71&49&29&14\\ \hline
7&1&6&20&49&98&169&${\bf 259}$&359&455&531&573&573&531&455\\ \hline
8&1&7&27&76&174&343&602&${\bf 961}$&1415&1940&2493&3017&3450&3736\\ \hline
9&1&8&35&111&285&628&1230&2191&${\bf 3606}$&5545&8031&11021&14395&17957\\ \hline
10&1&9&44&155&440&1068&2298&4489&8095&${\bf 13640}$&21670&32683&47043&64889\\ \hline
\end{tabular}

\noindent
\begin{tabular}{|r||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\multicolumn{11}{|c|}{Table 1 (continued) $I_n(k)=I_n({n\choose 2}-k)$}
\\* \hline\hline
&\multicolumn{10}{|c|}{$k$, number of inversions}\\* \hline\hline
$n\backslash k$&14&15&16&17&18&19&20&21&22&23\\* \hline\hline
6&5&1&&&&&&&&\\ \hline
7&359&259&169&98&49&20&6&1&&\\ \hline
8&3836&3736&3450&3017&2493&1940&1415&961&602&343\\ \hline
9&21450&24584&27073&28675&29228&28675&27073&24584&21450&17957\\ \hline
10&86054&110010&135853&162337&187959&211089&230131&243694&250749&250749\\ \hline
\end{tabular}

\paragraph*{3. Asymptotic Normality} 
The unimodal behavior of the inversion numbers suggests that the number
of inversions in a random permutation may be asymptotically normal.  
We explore this possibility by looking at the generating function for the 
probability distribution of the number of inversions. To get this generating function, 
we divide 
$\Phi_n(x)$ by $n!$ since each of the $n!$ permutations is equally
likely.
\begin{eqnarray*}
\phi_n(x)&=&\Phi_n(x)/n!.
\end{eqnarray*}
Following Vladimir Sachkov, we have the moment generating function \cite{sachkov}
\begin{eqnarray*}
M_n(x)&=&\phi_n(e^x)\cr
&=&\prod_{j=1}^n\frac{1-e^{jx}}{j(1-e^{x})}\cr
&=&\exp\biggl\{\frac{1}{2}\sum_{j=0}^{n-1}jx\biggr\}
\prod_{j=1}^n\frac{e^{-jx/2}-e^{jx/2}}{j(e^{-x/2}-e^{x/2})}\cr
&=&\exp\biggl\{\frac{1}{2}\sum_{j=0}^{n-1}jx\biggr\}\prod_{j=1}^n\frac{e^{jx/2}-e^{-jx/2}}{j (e^{x/2}-e^{-x/2})}\cr
&=&\exp\biggl\{\frac{n(n-1)x}{4}\biggr\}\prod_{j=1}^n\frac{{\rm sinh}(xj/2)}{j{\rm sinh}(x/2)}
\end{eqnarray*}

\noindent
An explicit formula for the generating function of the 
Bernoulli numbers is
\begin{eqnarray*}
\frac{x}{e^x-1}&=&\sum_{k=0}^{\infty}B_k\frac{x^k}{k!}.
\end{eqnarray*}
Hence
\begin{eqnarray*}
\frac{x}{e^x-1}+\frac{x}{1-e^{-x}}
&=&\sum_{k=0}^{\infty}B_k\frac{x^k}{k!}+\sum_{k=0}^{\infty}B_k\frac{(-x)^k}{k!}\cr
\frac{xe^{-x/2}}{e^{x/2}-e^{-x/2}}+\frac{xe^{x/2}}{e^{x/2}-e^{-x/2}}
&=&2\sum_{k=0}^{\infty}B_{2k}\frac{x^{2k}}{(2k)!}\cr
\frac{e^{-x/2}+e^{x/2}}{e^{x/2}-e^{-x/2}}
&=&2\sum_{k=0}^{\infty}B_{2k}\frac{x^{2k-1}}{(2k)!}\cr
\frac{e^{-x/2}+e^{x/2}}{2(e^{x/2}-e^{-x/2})}
&=&\frac{1}{x}+\sum_{k=1}^{\infty}B_{2k}\frac{x^{2k-1}}{(2k)!}\cr
\frac{e^{-x/2}+e^{x/2}}{2(e^{x/2}-e^{-x/2})}-\frac{1}{x}
&=&\sum_{k=1}^{\infty}B_{2k}\frac{x^{2k-1}}{(2k)!}\cr
\ln\biggl(\frac{\sinh(x/2)}{x/2}\biggr)
&=&\sum_{k=1}^{\infty}B_{2k}\frac{x^{2k}}{2k(2k)!},
\end{eqnarray*}
where the final step follows from integrating both sides and noting that
\begin{eqnarray*}
\lim_{x\rightarrow 0}\frac{\sinh(x/2)}{x/2}=1,
\end{eqnarray*}
so the constant of integration is zero.

Using this generating function, we find that the log of the moment generating function is
\begin{eqnarray*}
\ln M_n(x)&=&\frac{n(n-1)x}{4}+\sum_{j=1}^n\biggl(\ln\biggl(\frac{\sinh(xj/2)}{xj/2}\biggr)-\ln\biggl(\frac{\sinh(x/2)}{x/2}\biggr)\biggr)\cr
&=&\frac{n(n-1)x}{4}+\sum_{k=1}^\infty B_{2k}\frac{x^{2k}}{2k(2k)!}\sum_{j=1}^n(j^{2k}-1).
\end{eqnarray*}
Now consider $\ln M_n(t/\sigma)$, where $\sigma$ is the standard deviation of the number of
inversions in a random equiprobable permutation with $n$ elements,
\begin{eqnarray*}
\sigma&=&\sqrt{\frac{2n^3+3n^2-5n}{72}},
\end{eqnarray*}
\begin{eqnarray*}
\ln M_n(t/\sigma)&=&\frac{n(n-1)t}{4\sigma}+\sum_{k=1}^\infty B_{2k}\frac{t^{2k}}{2k(2k)!\sigma^{2k}}\sum_{j=1}^n(j^{2k}-1).
\end{eqnarray*}
The sum
\begin{eqnarray*}
\sigma^{-2k}\sum_{j=1}^n(j^{2k}-1),
\end{eqnarray*}
for $k>1$ is bounded above by the following integral:
\begin{eqnarray*}
\sum_{j=1}^n(j^{2k}-1)<\int_1^{n+1}(t^{2k}-1)dt=\frac{(n+1)^{2k+1}-1}{2k+1}-n,
\end{eqnarray*}
so
\begin{eqnarray*}
\sigma^{-2k}\sum_{j=1}^n(j^{2k}-1)=O(n^{1-k}).
\end{eqnarray*}
Hence 
\begin{eqnarray*}
\sum_{k=2}^\infty B_{2k}\frac{t^{2k}}{2k(2k)!\sigma^{2k}}\sum_{j=1}^n(j^{2k}-1)
\rightarrow 0,\;\;{\rm as}\;\;n\rightarrow\infty~,
\end{eqnarray*}
uniformly for $t$ from any bounded set. Therefore
\begin{eqnarray*}
\lim_{n\rightarrow\infty}M_n(t/\sigma)\exp\biggl\{-\frac{n(n-1)t}{4\sigma}\biggr\}&=&\lim_{n\rightarrow\infty}
\exp\biggl\{\sum_{k=1}^\infty B_{2k}\frac{t^{2k}}{2k(2k)!\sigma^{2k}}\sum_{j=1}^n(j^{2k}-1)
\biggr\}\cr
&=&\lim_{n\rightarrow\infty}
\exp\biggl\{ B_{2}\frac{t^{2}}{2(2)!\sigma^{2}}\sum_{j=1}^n(j^{2}-1)
\biggr\}\cr
&=&e^{t^2/2}.
\end{eqnarray*}
This leads to the following theorem:
\begin{theorem}[Sachkov]\cite{sachkov}
If $\xi_n$ is a random variable representing the number of inversions in a random equiprobable permutation of $n$ elements, then the random variable 
\begin{eqnarray*}
\eta_n&=&(\xi_n-E\xi_n)({\rm Var}\xi_n)^{-1}
\end{eqnarray*}
has as $n\rightarrow\infty$ an asymptotically normal distribution with parameters $(0,1)$.
\end{theorem}

The graph below shows the density for a standard normal random
variable in black.  The red curve gives a continuous approximation
for the discrete probability mass function for the number of 
inversions of a random permutation with $n$ elements.  The graph
shown is for $n=10$.  As $n$ increases,
the red curve moves closer to the standard normal density so that it 
appears that the normal density may serve as a useful tool for 
approximating the inversion numbers.  

\eject
\noindent
{\bf Figure 1.} Comparison of the inversion probability mass 
function to the standard normal density

%\includegraphics*[35mm,10mm][160mm,85mm]
%{/usr/njas/gauss/hisdir/NJAS/MARGOLIUS/norm.eps}
\centerline{\psfig{file=norm.eps,width=4in}}


%\begin{figure}
%\unitlength1cm
%{\includegraphics*[35mm,10mm][160mm,85mm]
%{/usr/njas/gauss/hisdir/NJAS/MARGOLIUS/norm.eps}}
%\caption{The functions $g(n)/n$ and $n^{\epsilon}$}
%\end{figure}


% From the BROUGHAN paper:
%\begin{figure}
%\unitlength1cm
%\center{\includegraphics*[scale=0.8, bb=2cm 20cm 12cm 27cm]
%{/usr/njas/gauss/hisdir/NJAS/MARGOLIUS/norm.eps}}
%\caption{The functions $g(n)/n$ and $n^{\epsilon}$}
%\end{figure}


The figure below shows the ratio of the inversion numbers to the 
estimate provided by the normal density.  The better the
approximation, the closer the curve will be to 1.  The graph is
scaled so that the $x-$axis is the number of standard deviations from 
the mean.

\noindent
{\bf Figure 2.} The ratio of the inversion probability mass function to the standard normal density scaled by the
number of standard deviations from the mean

%\includegraphics*[35mm,10mm][160mm,85mm]{cowboy1.eps}
\centerline{\psfig{file=cowboy1.eps,width=4in}}

The curves have roughly the shape of a cowboy hat.  The top of the hat at about $y=1$ seems to be getting broader as $n$ increases (black is $n=10$, red  is $n=25$, blue is $n=50$, and green is $n=100$), suggesting that the approximation improves with increasing $n$.  Compare the figure above to the one below:

\noindent
{\bf Figure 3.} The ratio of the inversion probability mass function to the standard normal density scaled by the nonzero inversion numbers

%\includegraphics*[35mm,10mm][160mm,85mm]{cowboy2.eps}
\centerline{\psfig{file=cowboy2.eps,width=4in}}

\noindent
The curves are rescaled in this figure so that 0 inversions is mapped to $-0.5$, and ${n\choose 2}$ inversions is mapped to $0.5$ on the $x-$axis.  In this way, we can see whether the estimates
for the  nonzero inversion numbers improve as a percentage of the total
nonzero inversion numbers as $n$ increases.  Note that the colored curves are in the opposite order of the preceding figure.
The figure suggests that the estimates actually get worse as $n$ increases.  The width of the top of the cowboy hat is getting narrower as $n$ increases. What this shows is
that the relative error of the normal density approximation increases as $n$ increases 
as we move further into the tails of the distribution.  We can examine the asymptotic behavior of $I_n(k)$ for $k\le n$ more closely.

\paragraph*{4. An explicit formula for the inversion numbers}
Donald Knuth has made the observation that we may write an explicit formula for the $k$th coefficient of the generating function when $k\le n$ (\cite{knuth}, p.~16).  In that case,
\begin{theorem}[Knuth, Netto]\cite{knuth},\cite{netto}
The inversion numbers $I_n(k)$ satisfy the formula
\begin{eqnarray}
\label{eq:Ink}
I_n(k)&=&{{n+k-1}\choose k}+
\sum_{j=1}^\infty(-1)^j{{n+k-u_j-j-1}\choose{k-u_j-j}}\cr
&&\hskip 1in
+
\sum_{j=1}^\infty(-1)^j{{n+k-u_j-1}\choose k-u_j},
\end{eqnarray}
for $k\le n$.
\end{theorem}
The binomial coefficients are defined to be zero when the lower
index is negative, so there are only finitely many nonzero terms:
$\lfloor-1/6+\sqrt{1/36+2k/3}\rfloor$ in the first sum, and 
$\lfloor 1/6+\sqrt{1/36+2k/3}\rfloor$ in the second.
The $u_j$ are the pentagonal numbers (sequence A001318 in \cite{eis}),
\begin{eqnarray*}
u_j&=&\frac{j(3j-1)}{2}.
\end{eqnarray*}
%A graphical representation of the pentagonal numbers is shown below.

\noindent
{\bf Figure 4.} The pentagonal numbers

%\includegraphics*[35mm,10mm][160mm,100mm]{pent.eps}
\centerline{\psfig{file=pent.eps,width=4in}}

Donald Knuth's formula follows from the generating function and Euler's pentagonal number theorem.  
\begin{theorem}[Euler]\cite{Andrews}\cite{HardyWright}\cite{knuth}
\begin{eqnarray*}
\prod_{j=1}^\infty(1-x^j)=
1+\sum_{k=1}^\infty(-1)^k(x^{k(3k-1)/2}+x^{k(3k+1)/2}).
\end{eqnarray*}
\end{theorem} 

Recall the generating function
\begin{eqnarray*}
\Phi_n(x)&=&\prod_{j=1}^n\frac{1-x^j}{1-x}\cr
&=&\biggl(\prod_{j=1}^n(1-x^j)\biggr)(1-x)^{-n}\cr
&=&\biggl(\prod_{j=1}^n(1-x^j)\biggr)
\sum_{m=0}^\infty{m+n-1\choose m}x^m,\;\;{\rm for}\;\;|x|<1.
\end{eqnarray*}
The coefficients of $\prod_{j=1}^n(1-x^j)$ will match those in 
the power series expansion of the infinite product given by Euler's
pentagonal number theorem up to the coefficient on $x^n$.
We consider the product
\begin{eqnarray*}
&&\biggl(\prod_{j=1}^\infty(1-x^j)\biggr)
\sum_{m=0}^\infty{m+n-1\choose m}x^m=\cr
&&\hskip 1in
\biggl(1+\sum_{i=1}^\infty(-1)^i(x^{i(3i-1)/2}+x^{i(3i+1)/2})\biggr)
\sum_{m=0}^\infty{m+n-1\choose m}x^m.
\end{eqnarray*}
The coefficient on $x^k$ is given by (\ref{eq:Ink}),
for $k\le n$.

\paragraph*{5. An asymptotic formula for the inversion numbers}
We are interested in the sequences $\{ I_{n+k}(n)$, $n=1,2, \ldots \}$.  For $k\ge 0$, the
$n$th term of the sequence is given by
\begin{eqnarray}
\label{eq:in+k}
I_{n+k}(n)&=&
{{2n+k-1}\choose n}+
\sum_{j=1}^{\lfloor-1/6+\sqrt{1/36+2n/3}\rfloor}(-1)^j{{2n+k-u_j-j-1}\choose{n-u_j-j}}\cr
&&\hskip 1in
+
\sum_{j=1}^{\lfloor 1/6+\sqrt{1/36+2n/3}\rfloor}(-1)^j{{2n+k-u_j-1}\choose n-u_j}
\end{eqnarray}
With $a=u_j+j$ or $a=u_j$, all terms are of the form
\begin{eqnarray*}
{{2n+k-a-1}\choose{n-a}}&=&\frac{(2n+k-a-1)!}{(n-a)!(n+k-1)!}.
\end{eqnarray*}
We can approximate this quantity using Stirling's approximation (\cite{feller}, p.54 or \cite{grahamknuthpatashnik}, p.452):
\begin{eqnarray*}
n!=\sqrt{2\pi}n^{n+1/2}e^{-n}(1+(12n)^{-1}+O(n^{-2})).
\end{eqnarray*}
So we have
\begin{eqnarray*}
&&{{2n+k-a-1}\choose{n-a}}\cr
&&\hskip .5in
=\biggl(\frac{2n+k-a-1}{n-a}\biggr)^{n-a}\biggl(\frac{2n+k-a-1}{n+k-1}\biggr)^{n+k-1}\biggl(\frac{2n+k-a-1}{2\pi(n+k-1)(n-a)}\biggr)^{1/2}\times
\cr
&&\hskip .75in\times\biggl(1-(8n)^{-1}+O(n^{-2})\biggr)
\cr
&&\cr
&&\hskip .5in
=\frac{2^{2n+k-1-a}}{\sqrt{\pi n}}\biggl(1+\frac{(a+k-1)^2}{4(n-a)(n+k-1)}\biggr)^n
\biggl(1-\frac{k+a-1}{2(n+k-1)}\biggr)^{k-1}\times\cr
&&\hskip .75in\times\biggl(1-\frac{n+k-1}{2n+k-a-1)}\biggr)^a
\biggl(\frac{1}{1-a/n}\biggl(\frac{k+a-1}{2(n+k-1)}\biggr)\biggr)^{1/2}\biggl(1-(8n)^{-1}+O(n^{-2})\biggr)
\cr
&&\cr
&&\hskip .5in
=\frac{2^{2n+k-1-a}}{\sqrt{\pi n}}\biggl(1+\frac{n(a+k-1)^2}{4(n-a)(n+k-1)}\biggr)
\biggl(1-\frac{(k-1)(k+a-1)}{2(n+k-1)}\biggr)\times\cr
&&\hskip .75in\times\biggl(1-\frac{a(n+k-1)}{2n+k-a-1)}\biggr)
\biggl(1+\frac{a-k+1}{4n}\biggr)\biggl(1-(8n)^{-1}+O(n^{-2})\biggr)
\cr
&&\cr
&&\hskip .5in
=\frac{2^{2n+k-1-a}}{\sqrt{\pi n}}\biggl(1-\frac{1}{8n}+\frac{1}{4n}(k+3a-(k+a)^2)+O(n^{-2})\biggr).
\end{eqnarray*}

Using this asymptotic formula we can compute an asymptotic formula for the sum $I_{n+k}(n)$ given in equation (\ref{eq:in+k}):
\begin{eqnarray*}
I_{n+k}(n)&=&\frac{2^{2n+k-1}}{\sqrt{\pi n}}Q\biggl(1-\frac{C_1}{n}+\frac{C_2 k -k^2}{4n}+O(n^{-2})\biggr)
\end{eqnarray*}
where 
\begin{eqnarray*}
Q&=&\prod_{j=1}^\infty \biggl(1-\frac{1}{2^j}\biggr)\cr
&=&\sum_{i=1}^\infty(-1)^i\biggl(2^{-i(3i-1)/2}+2^{-i(3i+1)/2}\biggr)
\cr
&\approx&
0.2887880951
\end{eqnarray*}
is a digital search tree constant \cite{constants},
and $C_1$ and $C_2$ are given by the convergent sums
\begin{eqnarray*}
C_1&=&\frac{1}{8}-\frac{1}{4Q}
\sum_{i=1}^\infty(-1)^i\biggl(2^{-i(3i-1)/2}(3(i(3i-1)/2)-(i(3i-1)/2)^2)\biggr.\cr
&&\biggl.+2^{-i(3i+1)/2}(3(i(3i+1)/2)-(i(3i+1)/2)^2)\biggr)
\cr
&\approx&
1.855938894,
\end{eqnarray*}
and
\begin{eqnarray*}
C_2&=&1+\frac{1}{Q}
\sum_{i=1}^\infty(-1)^i(2^{-i(3i-1)/2}(i(3i-1))+2^{-i(3i+1)/2}(i(3i+1)))
\cr
&\approx&
6.488067775,
\end{eqnarray*}
respectively.  We summarize a less precise result in the following theorem:
\begin{theorem}
\begin{eqnarray*}
I_{n+k}(n)&=&\frac{2^{2n+k-1}}{\sqrt{\pi n}}Q\biggl(1+O(n^{-1})\biggr),\;\;k\ge 0,
\end{eqnarray*}
where $Q=\prod_{j=1}^\infty \biggl(1-\frac{1}{2^j}\biggr)$.
\end{theorem}

This formula provides asymptotic estimates for the sequences A000707, A001892, A001893, A001894, A005283, A005284 and 
A005285
of \cite{eis}.


The figure below shows the behavior of the tail of the number of permutations with 
$k$ inversions for $k\le n$.  The blue curve is $n!$ times normal density
with mean $n(n-1)/4$ and variance $\frac{2n^3+3n^2-5n}{72}$, that is, the
blue curve is the estimate of $I_n(k)$ based on the normal density.  The red
dots are the values of the asymptotic estimate; and the green dots are the 
exact values of $I_n(k)$.  Where the red and green dots are not both visible,
one dot covers the other.  The figure shows the tail for $n=8$ and $n=16$.

\noindent
{\bf Figure 4.} Comparison of normal density estimate to asymptotic formula and actual inversion numbers

%\includegraphics*[35mm,10mm][160mm,85mm]{tail8.eps}
\centerline{\psfig{file=tail8.eps,width=4in}}

%\includegraphics*[35mm,10mm][160mm,85mm]{tails16a.eps}
\centerline{\psfig{file=tails16a.eps,width=4in}}


From our asymptotic formula for $I_n(n)$ we can
see that
\begin{eqnarray*}
\lim_{n\rightarrow\infty}\frac{I_n(n)}{I_{n-1}(n-1)}=4,
\end{eqnarray*}
but the normal density approximation for the ratio $\frac{I_n(n)}{I_{n-1}(n-1)}$ gives the estimate $ne^{-9/8}$ as $n$ tends to infinity.
Hence the normal 
density approximation grows much faster than the inversion numbers in the tails
do.



%error for $k=1$ is $(1-0.4838/n)$ approximately, ($n=5000$).
%error for $k=2$ is $(1+0.38839/n)$ approximately, ($n=5000$).



\begin{thebibliography}{99}

\bibitem{Andrews}G. E. Andrews, {\bf The Theory of Partitions}, Cambridge University
Press, 1998.

\bibitem{comtet} L. Comtet, {\bf Advanced Combinatorics}, Reidel, 1974, p. 240.

\bibitem{davidbarton1} F. N. David, M. G. Kendall and D. E. Barton, {\bf Symmetric Function and Allied Tables}, Cambridge, 1966, p. 241.

\bibitem{feller}W. Feller, {\bf An Introduction to Probability Theory and 
Its Applications}, second edition, John Wiley and Sons, New York, NY, 1971.

\bibitem{constants} S. Finch,
{\bf Digital Search Tree Constants},
published electronically at 
http://pauillac.inria.fr/algo/bsolve/constant/dig/dig.html.

\bibitem{grahamknuthpatashnik} R. L. Graham, D. E. Knuth and O. Patashnik, {\bf Concrete Mathematics}, 2d Ed., Addison-Wesley
Publishing Company, Inc., Reading, MA, 1994.

\bibitem{HardyWright} G. H. Hardy and E. M. Wright, {\bf An Introduction to the Theory of Numbers}, Oxford, Clarendon Press, 1954.

\bibitem{knuth} D. E. Knuth, {\bf The Art of Computer Programming}. Addison-Wesley, Reading, MA, Vol. 3, p. 15.
           
\bibitem{moritzwilliams} R. H. Moritz and R. C. Williams, ``A coin-tossing problem and some related combinatorics", Math. Mag., 61 (1988), 24-29.

\bibitem{muir} Muir, ``On a simple term of a determinant," {\it
Proc. Royal S. Edinborough}, 21 (1898-9), 441-477.

\bibitem{netto} E. Netto, {\bf Lehrbuch der Combinatorik.} 2nd ed., Teubner, Leipzig, 1927, p. 96.

\bibitem{sachkov} V. N. Sachkov, {\bf Probabilistic Methods in 
Combinatorial Analysis},  Cambridge University Press, New York, NY, 1997.

\bibitem{eis} N. J. A. Sloane, {\bf The On-Line Encyclopedia of 
Integer Sequences},
published electronically at http://www.research.att.com/~njas/sequences/, 2001.

\end{thebibliography}

\vspace*{+.5in}
\centerline{\rule{6.5in}{.01in}}

\vspace*{+.1in}
\noindent
{\small
(Concerned with sequence
\htmladdnormallink{A000707}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000707},
\htmladdnormallink{A001318}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=001318},
\htmladdnormallink{A001892}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=001892},
\htmladdnormallink{A001893}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=001893},
\htmladdnormallink{A001894}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=001894},
\htmladdnormallink{A005283}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=005283},
\htmladdnormallink{A005284}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=005284},
\htmladdnormallink{A005285}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=005285},
\htmladdnormallink{A008302}{http://www.research.att.com:80/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=008302}.)

\centerline{\rule{6.5in}{.01in}}

\vspace*{+.1in}
\noindent
Received May 30, 2001; revised version received July 9, 2001.
Published in Journal of Integer Sequences, Nov. 8, 2001.

\centerline{\rule{6.5in}{.01in}}

\vspace*{+.1in}
\noindent
Return to \htmladdnormallink{Journal of Integer Sequences home
page}{http://www.
research.att.com/~njas/sequences/JIS/}.

\centerline{\rule{6.5in}{.01in}}



\end{document}


.