Cleveland State University

Cleveland, Ohio 44115

Email address: margolius@math.csuohio.edu

**Abstract:** The number of inversions
in a random permutation is a way to measure the extent to which the permutation
is "out of order". Sequence
A008302 in The On-line
Encyclopedia of Integer Sequences is a triangle of these inversion numbers.
The *k*th entry of the *n*th row of this triangle counts the number
of distinct permutations of *n* elements with *k* inversions.
In this paper, we derive an asymptotic formula for some of the diagonals of
the triangle of the number of inversions in a random permutation. Asymptotic
formulas are provided for the sequences:
A000707,
A001892,
A001893,
A001894,
A005283,
A005284, and
A005285. Asymptotic behavior of the inversion numbers is illustrated with
2 interactive figures.

- Introduction
- Generating Function
- Asymptotic Normality
- An explicit formula for the inversion numbers
- An asymptotic formula for the inversion numbers
- References

- Figure 1. Comparison of the inversion probability mass function to the standard normal density
- 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
- Figure 3. The ratio of the inversion probability mass function to the standard normal density scaled by the nonzero inversion numbers
- Figure 4. Comparison of normal density estimate to asymptotic formula and actual inversion numbers

**Theorem 1**

*[Muir,1898][10] The numbers I _{n}(k) have as
a generating function*

Clearly, the number of permutations with no inversions,* I _{n}(0)*
is 1 for all

Below is a table of values of the number of inversions sequence A008302 in [13], see also [2], [3], [8], and [11]:

Table 1 I_{n}(k) = I_{n}((n(n-1)/2)-k)
| ||||||||||||||

k, number of inversions | ||||||||||||||

n\k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |

1 | 1 | |||||||||||||

2 | 1 | 1 | ||||||||||||

3 | 1 | 2 | 2 | 1 | ||||||||||

4 | 1 | 3 | 5 | 6 | 5 | 3 | 1 | |||||||

5 | 1 | 4 | 9 | 15 | 20 | 22 | 20 | 15 | 9 | 4 | 1 | |||

6 | 1 | 5 | 14 | 29 | 49 | 71 | 90 | 101 | 101 | 90 | 71 | 49 | 29 | 14 |

7 | 1 | 6 | 20 | 49 | 98 | 169 | 259 | 359 | 455 | 531 | 573 | 573 | 531 | 455 |

8 | 1 | 7 | 27 | 76 | 174 | 343 | 602 | 961 | 1415 | 1940 | 2493 | 3017 | 3450 | 3736 |

9 | 1 | 8 | 35 | 111 | 285 | 628 | 1230 | 2191 | 3606 | 5545 | 8031 | 11021 | 14395 | 17957 |

10 | 1 | 9 | 44 | 155 | 440 | 1068 | 2298 | 4489 | 8095 | 13640 | 21670 | 32683 | 47043 | 64889 |

Table 1 (continued) I_{n}(k) = I_{n}((n(n-1)/2)-k)
| ||||||||||

k, number of inversions | ||||||||||

n\k | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |

6 | 5 | 1 | ||||||||

7 | 359 | 259 | 169 | 98 | 49 | 20 | 6 | 1 | ||

8 | 3836 | 3736 | 3450 | 3017 | 2493 | 1940 | 1415 | 961 | 602 | 343 |

9 | 21450 | 24584 | 27073 | 28675 | 29228 | 28675 | 27073 | 24584 | 21450 | 17957 |

10 | 86054 | 110010 | 135853 | 162337 | 187959 | 211089 | 230131 | 243694 | 250749 | 250749 |

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 *F** _{n}(x)* by

Following Vladimir Sachkov, we have the moment generating function [12]

The explicit formula for the generating function of the Bernoulli numbers is

So we have

where the final step follows from integrating both sides and noting that

Using this generating function, we get that the log of the moment generating function is

Now consider ln*M _{n}(t/s)* where s is the standard deviation of the number of inversions in a random equiprobable
permutation with

The sum

for k > 1 is bounded above by the following integral,

so

uniformly for *t* from any bounded set.

**Theorem 2**
*[Sachkov][12] If x _{n} is a random variable representing the number of inversions in a
random equiprobable permutation of n elements, then the random variable *

*has as asymptotically normal distribution with parameters (0,1). *

The graph below shows the density for a standard normal random variable in
black. The red curves give a continuous approximation for the discrete probability
mass function for the number of inversions of a random permutation with *n*
elements. Graphs are shown for *n = 10* to* n = 100*. Holding the
mouse over any of the numbers* n = 10* to *n = 100* shown at the bottom
of the figure will show the graph for that *n* value. Note that 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.

Figure 1. Comparison of the inversion probability mass function to the standard normal density

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 one. The graph is scaled so that the *x-*axis is the number
of standard deviations from the mean.

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

The curves are shaped sort of like 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:

Figure 3. The ratio of the inversion probability mass function to the standard normal density scaled by the nonzero inversion numbers

The curves are rescaled in this figure so that 0 inversions is mapped to -0.5,
and *n(n-1)/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

Donald Knuth has made the observation that we may write an explicit formula
for the *k*th coefficient of the generating function when *k £ n*, [4], p.16. In that case,

**Theorem 3**
*[Knuth, Netto][8],[11], The inversion
numbers I _{n}(k) satisfy the formula *

(1) |

The binomial coefficients are defined to be zero when the lower index is negative,
so there are only finitely many nonzero terms:
for the first sum, and for the second. The *u _{j}* are the pentagonal numbers,
sequence A000326 in [13],

Donald Knuth's formula follows from the generating function and Euler's pentagonal number theorem.

Recall the generating function

for |x| < 1. |

The coefficients of 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

The coefficient on *x ^{k}* is given by (1),
for

We are interested in the sequences *I _{n+k}(n)*. For ,
the

(2) |

With *a = u _{j}+j* or

We can approximate the value of this number, by applying Stirling's approximation ([4], p.54 or [6], p.452):

So we have

With this asymptotic formula, we can compute an asymptotic formula for the
sum *I _{n+k}(n)* given in equation (2).

where

is a digital search tree constant [5],
http://pauillac.inria.fr/algo/bsolve/constant/dig/dig.html, and *C _{1}*
and

and

respectively. We summarize a less precise result as the following theorem:

**Theorem 5**

*where *

This formula can be used to provide asymptotic estimates for the sequences:
A000707,
A001892,
A001893,
A001894,
A005283,
A005284, and
A005285. In the formula, take *k* to be one for the first sequence,
and increase k by one for each subsequent sequence.

The figure below shows the tail behavior of the number of permutations with
k inversions for *k £ n*. The blue curve is *n!* times normal density with mean *n(n-1)/*4
and variance *[(2n ^{3}+3n^{2}-5n)/ 72]*, that is, the blue
curve is the estimate of

Figure 4. Comparison of normal density estimate to asymptotic formula and actual inversion numbers

From our asymptotic formula for *I _{n}(n)*, we can see that

but the normal density approximation for the ratio *[(I _{n}(n))/( I_{n-1}(n-1))]*
gives the estimate

- G. E. Andrews,
*The Theory of Partitions*, first paperback edition, Cambridge University Press, 1998. - L. Comtet,
*Advanced Combinatorics*, Reidel, 1974, p. 240. - F. N. David, M. G. Kendall and D. E. Barton,
*Symmetric Function and Allied Tables*, Cambridge, 1966, p. 241. - W. Feller,
*An introduction to probability theory and its applications*, second edition, John Wiley and Sons, New York, NY, 1971. - S. Finch,
*Table of mathematical constants*, published electronically at http://pauillac.inria.fr/algo/bsolve/constant/table.html, 2001. - R. L. Graham, D. E. Knuth and O. Patashnik,
*Concrete Mathematics*, 2d Ed., Addison-Wesley Publishing Company, Inc., Reading, MA, 1994. - G. H. Hardy and E. M. Wright,
*An Introduction to the Theory of Numbers*, Oxford, Clarendon Press, 1954. - D. E. Knuth,
*The Art of Computer Programming*. Addison-Wesley, Reading, MA, Vol. 3, p. 15. - R. H. Moritz and R. C. Williams, "A coin-tossing problem
and some related combinatorics",
*Math. Mag.*, 61 (1988), 24-29. - Muir, "On a simple term of a determinant,"
*Proc. Royal S. Edinborough*,**21**(1898-9), 441-477. - E. Netto,
*Lehrbuch der Combinatorik,.*2nd ed., Teubner, Leipzig, 1927, p. 96. - V. N. Sachkov,
*Probabilistic Methods in Combinatorial Analysis*, Cambridge University Press, New York, NY, 1997. - N. J. A. Sloane,
*The on-line encyclopedia of integer sequences*, published electronically at http://www.research.att.com/~njas/sequences/, 2001.