The Number of Inversions in Permutations: A Saddle Point Approach

Guy Louchard Département d’Informatique CP 212, Boulevard du Triomphe B-1050 Bruxelles Belgium 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 helmut@maths.wits.ac.za

Abstract 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.

1 Introduction

Let a_{1} ⋯ a_{n} be a permutation of the set {1, …, n}. If a_{i} > a_{k} and i < k, the pair (a_{i}, a_{k}) is called an inversion; I_{n}(j) is the number of permutations of length n with j inversions. In a recent paper [7], several facts about these numbers are nicely reviewed, and—as new results—asymptotic formulæ for the numbers I_{n+k}(n) for fixed k and n → ∞ are derived. This is done using Euler’s pentagonal theorem, which leads to a handy explicit formula for I_{n}(j), valid for j ≤ n only.

Figure 1: |Φ_{10}(z)/z^{11}| and the path of integration

Here, we show how to extend these results using the saddle point method. This leads, e. g., to asymptotics for I_{αn+β}(γn + δ), for integer constants α, β, γ, δ 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

Φ_{n}(z) = ∑_{j≥0} I_{n}(j)z^{j} = (1 − z)^{−n} ∏_{i=1}^{n}(1 − z^{i}).

By Cauchy’s theorem,

I_{n}(j) = \frac{1}{2πi} ∫_{C} Φ_{n}(z)\frac{dz}{z^{j+1}} ,

where C is, say, a circle around the origin passing (approximately) through the saddle point. In Figure 1, the saddle point (near z = \frac{1}{2}) is shown for n = j = 10.

As general references for the application of the saddle point method in enumeration we cite [4, 8].

Actually, we obtain here local limit theorems with some corrections (=lower order terms). For other such theorems in large deviations of combinatorial distributions, see, for instance, Hwang [5].

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 = αn − x, α > 0. Section 5 is devoted to the moderate large deviation, and Section 6 to the large deviation. Section 7 concludes the paper.

2 The Gaussian limit, j = m + xσ, m = n(n − 1)/4

The Gaussian limit of I_{n}(j) is easily derived from the generating function Φ_{n}(z) (using the Lindeberg-Lévy conditions, see for instance, Feller [3]); this is also reviewed in Margolius’ paper, following Sachkov’s book [9]. Another analysis is given in Bender [2]. Indeed, this generating function corresponds to a sum for i = 1, …, n of independent, uniform [0..i − 1] random variables. As an exercise, let us recover this result with the saddle point method, with an additional correction of order 1/n. We have, with J_{n} := I_{n}/n!,

m := 𝔼(J_{n}) = n(n − 1)/4,
σ^{2} := 𝕍(J_{n}) = n(2n + 5)(n − 1)/72.

We know that

I_{n}(j) = \frac{1}{2πi} ∫_{Ω} \frac{e^{S(z)}}{z^{j+1}} dz

where Ω is inside the analyticity domain of the integrand and encircles the origin. Since Φ_{n}(z) is just a polynomial, the analyticity restriction can be ignored. We split the exponent of the integrand S = ln(Φ_{n}(z)) − (j + 1) ln z as follows:

S := S_{1} + S_{2},  (1)
S_{1} := ∑_{i=1}^{n} ln(1 − z^{i}),
S_{2} := −n ln(1 − z) − (j + 1) ln z.

Set

S^{(i)} := \frac{d^{i}S}{dz^{i}} .

To use the saddle point method, we must find the solution of

S^{(1)}(z̃) = 0.  (2)

Set z̃:= z^{∗} −ε, where, here, z^{∗} = 1. (This notation always means that z^{∗} is the approximate saddle point and z̃ 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

[(n + 1)^{2}/4 − 3n/4 − 5/4 − j] + [−(n + 1)^{3}/36 + 7(n + 1)^{2}/24 − 49n/72 − 91/72 − j]ε = 0. (3)

Set j = m + xσ in (3). This shows that, asymptotically, ε is given by a 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 (2), i.e., we first obtain

[(n + 1)^{2}/4 − 3n/4 − 5/4 − j] + [−(n + 1)^{3}/36 + 7(n + 1)^{2}/24 − 49n/72 − 91/72 − j]ε

+ [−j − 61/48 − (n + 1)^{3}/24 + 5(n + 1)^{2}/16 − 31n/48]ε^{2} = 0.  (4)

More generally, even powers ε^{2k} lead to a O(n^{2k+1}) · ε^{2k} term and odd powers ε^{2k+1} lead to a O(n^{2k+3}) · ε^{2k+1} term. Now we set j = m + xσ, expand into powers of n^{−1/2} and equate each coefficient with 0. This leads successively to a full expansion of ε. Note that to obtain a given precision of ε, it is enough to compute a given finite number of terms in the generalization of (4). We obtain

ε = −6x/n^{3/2} + (9x/2 − 54/25x^{3})/n^{5/2} − (18x^{2} + 36)/n^{3}
+ x[−30942/30625x^{4} + 27/10x^{2} − 201/16]/n^{7/2} + O(1/n^{4}).  (5)

We have, with z̃:= z^{∗} − ε,

J_{n}(j) = \frac{1}{n!2πi} ∫_{Ω} exp [S(z̃) + S^{(2)}(z̃)(z − z̃)^{2}/2! + ∑_{l=3}^{∞} S^{(l)}(z̃)(z − z̃)^{l}/l!]dz

(note carefully that the linear term vanishes). Set z = z̃ + iτ. This gives

J_{n}(j) = \frac{1}{n!2π} exp[S(z̃)] ∫_{−∞}^{∞} exp [S^{(2)}(z̃)(iτ)^{2}/2! + ∑_{l=3}^{∞} S^{(l)}(z̃)(iτ)^{l}/l!]dτ.  (6)

Let us first analyze S(z̃). We obtain

S_{1}(z̃) = ∑_{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 + O(n^{−3/2}),
S_{2}(z̃) = [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 + O(n^{−3/2}),

and so

S(z̃) = −x^{2}/2 + ln(n!) + O(n^{−3/2}).

Also,

S^{(2)}(z̃) = n^{3}/36 + (1/24 − 3/100x^{2})n^{2} + O(n^{3/2}),
S^{(3)}(z̃) = O(n^{7/2}),
S^{(4)}(z̃) = −n^{5}/600 + O(n^{4}),
S^{(l)}(z̃) = O(n^{l+1}), l ≥ 5.

We can now compute (6), for instance by using the classical trick of setting

S^{(2)}(z̃)(iτ)^{2}/2! + ∑_{l=3}^{∞} S^{(l)}(z̃)(iτ)^{l}/l! = −u^{2}/2,

computing τ as a truncated series in u, setting dτ = \frac{dτ}{du}du, expanding with respect to n and integrating on [u = −∞..∞]. (This amounts to the reversion of a series.) Finally, (6) leads to

J_{n} ∼ e^{−x^{2}/2} · exp[(−51/50 + 27/50x^{2})/n + O(n^{−3/2})]/(2πn^{3}/36)^{1/2}.  (7)

Figure 2: J_{n}(j) (circle) and the asymptotics (7) (line), without the 1/n term, n = 60

Note that S^{(3)}(z̃) does not contribute to the 1/n correction.

To check the effect of the correction, we first give in Figure 2, for n = 60, the comparison between J_{n}(j) and the asymptotics (7), without the 1/n term. Figure 3 gives the same comparison, with the constant term −51/(50n) in the correction. Figure 4 shows the quotient of J_{n}(j) and the asymptotics (7), with the constant term −51/(50n). The “hat” behaviour, already noticed by Margolius, is apparent. Finally, Figure 5 shows the quotient of J_{n}(j) and the asymptotics (7), with the full correction.

3 The case j = n − k

Figure 6 shows the real part of S(z) as given by (1), together with a path Ω through the saddle point.

It is easy to see that here, we have z^{∗} = 1/2. We obtain, to first order,

[C_{1,n} − 2j − 2 + 2n] + [C_{2,n} − 4j − 4 − 4n]ε = 0

with

C_{1,n} = C_{1} + O(2^{−n}),
C_{1} = ∑_{i=1}^{∞} \frac{−2i}{2^{i} − 1} = −5.48806777751 …,
C_{2,n} = C_{2} + O(2^{−n}),
C_{2} = ∑_{i=1}^{∞} 4\frac{i(i2^{i} − 2^{i} + 1)}{(2^{i} − 1)^{2}} = 24.3761367267 ….

Figure 3: J_{n}(j) (circle) and the asymptotics (7) (line), with the constant in the 1/n term, n = 60

Figure 4: Quotient of J_{n}(j) and the asymptotics (7), with the constant in the 1/n term, n = 60 Figure 5: Quotient of J_{n}(j) and the asymptotics (7), with the full 1/n term, n = 60

Figure 6: Real part of S(z). Saddle-point and path, n = 10, k = 0 Set j = n − k. This shows that, asymptotically, ε 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]ε + [C_{3} + 8n − 8j − 8]ε^{2} = 0

for some constant C_{3}. More generally, powers ε^{2k} lead to a O(1) · ε^{2k} term, powers ε^{2k+1} lead to a O(n) · ε^{2k+1} term. This gives the estimate

ε = (k − 1 + C_{1}/2)/(4n) + (2k − 2 + C_{1})(4k − 4 + C_{2})/(64n^{2}) + O(1/n^{3}).

Now we derive

S_{1}(z̃) = ln(Q) − C_{1}(k − 1 + C_{1}/2)/(4n) + O(1/n^{2})

with Q := ∏_{i=1}^{∞}(1 − 1/2^{i}) = .288788095086 . . .. Similarly,

S_{2}(z̃) = 2 ln(2)n + (1 − k) ln(2) + (−k^{2}/2 + k − 1/2 + C_{1}^{2}/8)/(2n) + O(1/n^{2})

and so

S(z̃) = ln(Q) + 2 ln(2)n + (1 − k) ln(2) + (A_{0} + A_{1}k − k^{2}/4)/n + O(1/n^{2})

with

A_{0} := −(C_{1} − 2)^{2}/16,
A_{1} := (−C_{1}/2 + 1)/2.

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)}(z̃) = O(1). This leads to

S^{(2)}(z̃) = 8n + (−C_{2} − 4k + 4) + O(1/n),
S_{2}^{(3)}(z̃) = O(1),
S_{2}^{(4)}(z̃) = 192n + O(1),
S_{2}^{(l)}(z̃) = O(n), l ≥ 5.

We denote by S^{(2,1)} the dominant term of S^{(2)}(z̃), i.e., S^{(2,1)} := 8n. We now compute (S_{2}^{(3)}(z̃) is not necessary here)

\frac{1}{2π} exp[S(z̃)] ∫_{−∞}^{∞} exp[S^{2}(z̃)(iτ)^{2}/2!] exp[S^{4}(z̃)(iτ)^{4}/4! + O(nτ^{5})]dτ

which gives

I_{n}(n − k) ∼ e^{2 ln(2)n+(1−k) ln(2)} \frac{Q}{(2πS^{(2,1)})^{1/2}} ·
exp {[(A_{0} + 1/8 + C_{2}/16) + (A_{1} + 1/4)k − k^{2}/4] /n + O(1/n^{2})} . (8)

To compare our result with Margolius’, we replace n by n + k and find

I_{n+k}(n) = \frac{2^{2n+k−1}}{\sqrt{πn}} (q_{0} − \frac{q_{0} + q_{2} − 2q_{1}}{8n} + \frac{(q_{0} − q_{1})k}{4n} − \frac{q_{0}k^{2}}{n} + O(n^{−2})).

We have

q_{0} = Q = ∏_{i=1}^{∞}(1 − 2^{−i}),

and

q_{1} = −2q_{0} ∑_{i=1}^{∞} \frac{i}{2^{i} − 1},

and

\frac{q_{2}}{2q_{0}} = − ∑_{i=1}^{∞} \frac{i(i − 1)}{2^{i} − 1} + ( ∑_{i=1}^{∞} \frac{i}{2^{i} − 1})^{2} − ∑_{i=1}^{∞} \frac{i^{2}}{(2^{i} − 1)^{2}} .

Margolius’ form of the constants follows from Euler’s pentagonal theorem, [1]

Q(z) = ∏_{i=1}^{∞}(1 − z^{i}) = ∑_{i∈ℤ}(−1)^{i}z^{\frac{i(3i−1)}{2}}

and differentiations:

q_{1} = ∑_{i∈ℤ}(−1)^{i}i(3i − 1)2^{− \frac{i(3i−1)}{2}} ,

respectively,

q_{2} = ∑_{i∈ℤ}(−1)^{i}i(3i − 1)(\frac{i(3i − 1)}{2} − 1)2^{− \frac{i(3i−1)}{2}} .

In our formula, k can be negative as well (which was excluded in Margolius’ analysis).

Figure 7 gives, for n = 300, I_{n}(n − k) normalized by the first two terms of (8) together with the 1/n correction in (8); the result is a bell shaped curve, which is perhaps not too unexpected. Figure 8 shows the quotient of I_{n}(n − k) and the asymptotics (8).

4 The case j = αn − x, α > 0

Of course, we must have that αn−x is an integer. For instance, we can choose α, x integers. But this also covers more general cases, for instance I_{αn+β}(γn + δ), with α, β, γ, δ integers. We have here z^{∗} = α/(1 + α). We derive, to first order,

[C_{1,n}(α) − (j + 1)(1 + α)/α + (1 + α)n] + [C_{2,n}(α) − (j + 1)(1 + α)^{2}/α^{2} − (1 + α)^{2}n]ε = 0

with, setting φ(i, α) := [α/(1 + α)]^{i},

C_{1,n}(α) = C_{1}(α) + O([α/(1 + α)]^{−n}),

Figure 7: normalized I_{n}(n − k) (circle) and the 1/n term in the asymptotics (8) (line), n = 300

Figure 8: Quotient of I_{n}(n − k) and the asymptotics (8), n = 300

C_{1}(α) = ∑_{i=1}^{∞} \frac{i(1 + α)φ(i, α)}{α[φ(i, α) − 1]},
C_{2,n}(α) = C_{2}(α) + O([α/(1 + α)]^{−n}),
C_{2}(α) = ∑_{i=1}^{∞} φ(i, α)i(1 + α)^{2}(i − 1 + φ(i, α))/[(φ(i, α) − 1)^{2}α^{2}].

Set j = αn − x. This leads to

ε = [x + αx − 1 − α + C_{1}α]/[(1 + α)^{3}n] + O(1/n^{2}).

Next, we obtain

[C_{1,n}(α) − (j + 1)(1 + α)/α + (1 + α)n] + [C_{2,n}(α) − (j + 1)(1 + α)^{2}/α^{2} − (1 + α)^{2}n]ε

+ [C_{3,n}(α) + (1 + α)^{3}n − (j + 1)(1 + α)^{3}/α^{3}]ε^{2} = 0

for some function C_{3,n}(α). More generally, powers ε^{k} lead to a O(n) · ε^{k} term. This gives

ε = [x + αx − 1 − α + C_{1}α]/[(1 + α)^{3}n] + (x + xα − 1 − α + C_{1}α) ×

× (x + 2xα + xα^{2} − α^{2} + C_{1}α^{2} − 2α + C_{2}α − 1 − C_{1})/[(1 + α)^{6}n^{2}] + O(1/n^{3}).

Next we derive

S_{1}(z̃) = ln(Q̂(α)) − C_{1}[x + αx − 1 − α + C_{1}α]/[(1 + α)^{3}n] + O(1/n^{2})

with

Q̂(α) := ∏_{i=1}^{∞}(1 − φ(i, α)) = ∏_{i=1}^{∞} (1 − (\frac{α}{1 + α})^{i}) = Q(\frac{α}{1 + α}).

Similarly

S_{2}(z̃) = [− ln(1/(1 + α)) − α ln(α/(1 + α))]n + (x − 1) ln(α/(1 + α))
+ {(C_{1}α + α + 1)(C_{1}α − α − 1)/[2α(1 + α)^{3}] + x/[α(1 + α)]
−x^{2}/[2α(1 + α)]}/n + O(1/n^{2}).

So

S(z̃) = [− ln(1/(1 + α)) − α ln(α/(1 + α))]n + ln(Q̂(α)) + (x − 1) ln(α/(1 + α))
+ {−(C_{1}α − α − 1)^{2}/[2α(1 + α)^{3}] − x(C_{1}α − α − 1)/[α(1 + α)^{2}] − x^{2}/[2α(1 + α)]}/n
+ O(1/n^{2}).

The derivatives of S are computed as follows:

S^{(2)}(z̃) = (1 + α)^{3}/αn − (2xα^{3} + 2C_{1}α^{3} − 2α^{3} + C_{2}α^{2} + 3xα^{2} − 3α^{2} − 2C_{1}α − x + 1)/α^{2} + O(1/n),
S_{2}^{(3)}(z̃) = 2(1 + α^{3})(α^{2} − 1)/α^{2}n + O(1),
S_{2}^{(4)}(z̃) = 6(1 + α)^{4}(α^{3} + 1)/α^{3}n + O(1),
S_{2}^{(l)}(z̃) = O(n), l ≥ 5.

Figure 9: normalized I_{n}(αn − x) (circle) and the 1/n term in the asymptotics (10) (line), α = 1/2, n = 300

We denote by S^{(2,1)} the dominant term of S^{(2)}(z̃), e.g., S^{(2,1)} := n(1 + α)^{3}/α. Note that, now, S_{2}^{(3)}(z̃) = O(n), so we cannot ignore its contribution. Of course, μ_{3} = 0 (third moment of the Gaussian), but μ_{6} ≠ 0, so S_{2}^{(3)}(z̃) contributes to the 1/n term. Finally, Maple gives us

I_{n}(αn − x) ∼ e^{[− ln(1/(1+α))−α ln(α/(1+α))]n+(x−1) ln(α/(1+α))} \frac{Q̂(α)}{(2πS^{(2,1)})^{1/2}} ×
× exp[{−(1 + 3α + 4α^{2} − 12α^{2}C_{1} + 6C_{1}^{2}α^{2} + α^{4} + 3α^{3} − 6C_{2}α^{2}  (9)
−12C_{1}^{3}α)/[12α(1 + α)^{3}]}]

+x(2α^{2} − 2C_{1}α + 3α + 1)/[2α(1 + α)^{2}] − x^{2}/[2α(1 + α)]} /n + O(1/n^{2})] .

Figure 9 gives, for α = 1/2, n = 300, I_{n}(αn − x) normalized by the first two terms of (10) together with the 1/n correction in (10). Figure 10 shows the quotient of I_{n}(αn − x) and the asymptotics (10).

5 The moderate Large deviation, j = m + xn^{7/4}

Now we consider the case j = m + xn^{7/4}. We have here z^{∗} = 1. We observe the same behaviour as in Section 2 for the coefficients of ε in the generalization of (4).

Proceeding as before, we see that asymptotically, ε is now given by a Puiseux series of powers of n^{−1/4}, starting with −36x/n^{5/4}. This leads to

ε = −36x/n^{5/4}−1164/25x^{3}/n^{7/4}+(−240604992/30625x^{5}+54x)/n^{9/4}+F_{1}(x)/n^{5/2}+O(n^{−11/4}),

Figure 10: Quotient of I_{n}(αn − x) and the asymptotics (10), α = 1/2, n = 300

where F_{1} is an (unimportant) polynomial of x. This leads to

S(z̃) = ln(n!) − 18x^{2}\sqrt{n} − 2916/25x^{4} − 27/625x^{2}(69984x^{4} − 625)/\sqrt{n}
− 1458/15625x^{4}(−4375 + 1259712x^{4})/n + O(n^{−5/4}).

Also,

S^{(2)}(z̃) = n^{3}/36 + (1/24 + 357696/30625x^{4})n^{2} − 27/25x^{2}n^{5/2} + O(n^{7/4}),
S^{(3)}(z̃) = −1/12n^{3} + O(n^{15/4}),
S^{(4)}(z̃) = −n^{5}/600 + O(n^{9/2}),
S^{(l)}(z̃) = O(n^{l+1}), l ≥ 5,

and finally we obtain

J_{n} ∼ e^{−18x^{2}\sqrt{n}−2916/25x^{4}} ×
× exp [x^{2}(−1889568/625x^{4} + 1161/25)/\sqrt{n}
+ (−51/50 − 1836660096/15625x^{8} + 17637426/30625x^{4})/n
+ O(n^{−5/4})]/(2πn^{3}/36)^{1/2}.  (10)

Note that S^{(3)}(z̃) 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 11, for n = 60 and x ∈ [−1/4..1/4], the comparison between J_{n}(j) and the asymptotics (10), without the 1/\sqrt{n} and 1/n term. Figure 12 gives the same comparison, with the correction. Figure 13 shows the Figure 11: J_{n}(j) (circle) and the asymptotics (10) (line), without the 1/\sqrt{n} and 1/n term, n = 60

Figure 12: J_{n}(j) (circle) and the asymptotics (10) (line), with the 1/\sqrt{n} and 1/n term, n = 60 Figure 13: Quotient of J_{n}(j) and the asymptotics (10), with the 1/\sqrt{n} and 1/n term, n = 60

quotient of J_{n}(j) and the asymptotics (10), with the 1/\sqrt{n} and 1/n term.

The exponent 7/4 that we have chosen is of course not sacred; any fixed number below 2 could also have been considered.

6 Large deviations, j = αn(n − 1), 0 < α < 1/2

Here, again, z^{∗} = 1. Asymptotically, ε is given by a Laurent series of powers of n^{−1}, but here the behaviour is quite different: all terms of the series generalizing (4) contribute to the computation of the coefficients. It is convenient to analyze separately S_{1}^{(1)} and S_{2}^{(1)}. This gives, by substituting

z̃:= 1 − ε, j = αn(n − 1), ε = a_{1}/n + a_{2}/n^{2} + a_{3}/n^{3} + O(1/n^{4}),

and expanding with respect to n,

S_{2}^{(1)}(z̃) ∼ (1/a_{1} − α)n^{2} + (α − αa_{1} − a_{2}/a_{1}^{2})n + O(1),
S_{1}^{(1)}(z̃) ∼ ∑_{k=0}^{n−1} f(k),

where

f(k) := −(k + 1)(1 − ε)^{k}/[1 − (1 − ε)^{k+1}]
= −(k + 1)(1 − [a_{1}/n + a_{2}/n^{2} + a_{3}/n^{3} + O(1/n^{4})])^{k}
/{1 − (1 − [a_{1}/n + a_{2}/n^{2} + a_{3}/n^{3} + O(1/n^{4})])^{k+1}}.

This immediately suggests to apply the Euler-Mac Laurin summation formula, which gives, to first order,

S_{1}^{(1)}(z̃) ∼ ∫_{0}^{n} f(k)dk − \frac{1}{2}(f(n) − f(0)),

so we set k = −un/a_{1} and expand −f(k)n/a_{1}. This leads to

∫_{0}^{n} f(k)dk ∼ ∫_{0}^{−a_{1}} [−\frac{ue^{u}}{a_{1}^{2}(1 − e^{u})}n^{2} + \frac{e^{u}[2a_{1}^{2} − 2e^{u}a_{1}^{2} − 2u^{2}a_{2} − u^{2}a_{1}^{2} + 2e^{u}ua_{1}^{2}]}{2a_{1}^{3}(1 − e^{u})^{2}}n] du + O(1)

−\frac{1}{2}(f(n) − f(0))

∼ (\frac{e^{−a_{1}}}{2(1 − e^{−a_{1}})} − \frac{1}{2a_{1}} ) n + O(1).

This readily gives

∫_{0}^{n} f(k)dk ∼ −dilog(e^{−a_{1}})/a_{1}^{2}n^{2}
+ [2a_{1}^{3}e^{−a_{1}} + a_{1}^{4}e^{−a_{1}} − 4a_{2}dilog(e^{−a_{1}}) + 4a_{2}dilog(e^{−a_{1}})e^{−a_{1}}
+ 2a_{2}a_{1}^{2}e^{−a_{1}} − 2a_{1}^{2} + 2a_{1}^{2}e^{−a_{1}}]/[2a_{1}^{3}(e^{−a_{1}} − 1)]n + O(1).

Combining S_{1}^{(1)}(z̃) + S_{2}^{(1)}(z̃) = 0, we see that a_{1} = a_{1}(α) is the solution of

−dilog(e^{−a_{1}})/a_{1}^{2} + 1/a_{1} − α = 0.

We check that lim_{α→0} a_{1}(α) = ∞, lim_{α→1/2} a_{1}(α) = −∞.

Similarly, a_{2}(α) is the solution of the linear equation

α − α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}} + 4a_{2}dilog(e^{−a_{1}})(e^{−a_{1}} − 1) + 2a_{2}a_{1}^{2}e^{−a_{1}} − 2a_{1}^{2} + 2a_{1}^{2}e^{−a_{1}}]/[2a_{1}^{3}(e^{−a_{1}} − 1)]
= 0

and lim_{α→0} a_{2}(α) = −∞, lim_{α→1/2} a_{2}(α) = ∞.

We could proceed in the same manner to derive a_{3}(α) but the computation becomes quite heavy. So we have computed an approximate solution ã_{3}(α) as follows: we have expanded S^{(1)}(z̃) into powers of ε up to ε^{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}(α), a_{2}(α) immediately gives ã_{3}(α). This approximation is satisfactory for α ∈ [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

S(z̃) = ln(n!) + [1/72a_{1}(a_{1} − 18 + 72α)]n
+ [1/72a_{1}^{3} − 1/4a_{2} + 1/4a_{1} − a_{1}α − 5/48a_{1}^{2} + 1/36a_{1}a_{2} + a_{2}α + 1/2a_{1}^{2}α]
+ [1/72a_{2}^{2} + 1/36a_{1}a_{3} − 1/4a_{3} + 1/4a_{2} + a_{1} + a_{3}α + a_{1}a_{2}α + 1/3a_{1}^{3}α
− a_{2}α − 1/2a_{1}^{2}α − 5/24a_{1}a_{2} + 1/24a_{1}^{2}a_{2} + 13/144a_{1}^{2} − 1/16a_{1}^{3}]/n + O(1/n^{2}).

Figure 14: normalized J_{n}(αn(n−1)) (circle) and the 1/n term in the asymptotics (11) (line), n = 80

Note that the three terms of S(z̃) are null for α = 1/4, as expected. This leads to

S^{(2)}(z̃) = n^{3}/36 + (−5/24 + 1/12a_{1} + α)n^{2} + O(n),
S^{(3)}(z̃) = 1/600a_{1}n^{4} + O(n^{3}),
S^{(4)}(z̃) = −n^{5}/600 + O(n^{4}),
S_{2}^{(l)}(z̃) = O(n^{l+1}), l ≥ 5.

Finally,

J_{n}(αn(n − 1))
∼ e^{[1/72a_{1}(a_{1}−18+72α)]n+[1/72a_{1}^{3}−1/4a_{2}+1/4a_{1}−a_{1}α−5/48a_{1}^{2}+1/36a_{1}a_{2}+a_{2}α+1/2a_{1}^{2}α]} \frac{1}{(2πn^{3}/36)^{1/2}} ×

× exp[(1/72a_{2}^{2} + 1/36a_{1}a_{3} − 1/4a_{3} + 1/4a_{2} − 1/2a_{1} + a_{3}α + a_{1}a_{2}α + 1/3a_{1}^{3}α − a_{2}α

− 1/2a_{1}^{2}α − 5/24a_{1}a_{2} + 1/24a_{1}^{2}a_{2} + 1139/18000a_{1}^{2} − 1/16a_{1}^{3} + 87/25 − 18α)/n
+ O(1/n^{2})].  (11)

Note that, for α = 1/4, the 1/n term gives −51/50, again as expected.

Figure 14 gives, for n = 80 and α ∈ [0.15..0.35], J_{n}(αn(n − 1)) normalized by the first two terms of (11) together with the 1/n correction in (11). Figure 15 shows the quotient of J_{n}(αn(n − 1)) and the asymptotics (11).

Figure 15: Quotient of J_{n}(αn(n − 1)) and the asymptotics (11), n = 80

7 Conclusion

Once more the 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æ, 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, [6]).

8 Acknowledgments

The pertinent comments of the referee led to improvements in the presentation.

References

[1] G.E. Andrews. The Theory of Partitions, volume 2 of Encyclopedia of Mathematics and its Applications. Addison–Wesley, 1976.

[2] E.A. Bender. Central and local limit theorems applied to asymptotics enumeration. Journal of Combinatorial Theory, Series A, 15 (1973), 91–111.

[3] W. Feller. Introduction to Probability Theory and its Applications. Vol I. Wiley, 1968.

[4] P. Flajolet and R. Sedgewick. Analytic combinatorics—symbolic combinatorics: Saddle point asymptotics. Technical Report 2376, INRIA, 1994.

[5] H.K. Hwang. Large deviations of combinatorial distributions II: Local limit theorems. Annals of Applied Probability 8 (1998), 163–181.

[6] H. Prodinger Combinatorics of geometrically distributed random variables: Inversions and a parameter of Knuth. Annals of Combinatorics 5 (2001), 241–250.

[7] B.H. Margolius. Permutations with inversions. Journal of Integer Sequences, 4 (2001), 1–13.

[8] A. Odlyzko. Asymptotic enumeration methods. In R. Graham, M. Götschel, and L. Lovász, eds., Handbook of Combinatorics, Elsevier Science, 1995, pp. 1063–1229.

[9] V.N. Sachkov. Probabilistic Methods in Combinatorial Analysis. Cambridge University Press, 1997.

2000 Mathematics Subject Classification: Primary 05A16; Secondary 05A10. Keywords: Inversions, permutations, saddle point method .

Received November 15, 2002; revised version received July 3, 2003. Published in Journal of Integer Sequences, July 22, 2003.

Return to Journal of Integer Sequences home page.