An Asymptotic Expansion for the Number of Permutations with a Certain Number of Inversions

Lane Clark Department of Mathematics Southern Illinois University Carbondale Carbondale, IL 62901-4408 USA

                             lclark@math.siu.edu

Submitted: December 17, 1998; Accepted: August 8, 2000

Abstract

Let b(n, k) denote the number of permutations of {1, …, n} with precisely k inversions. We represent b(n, k) as a real trigonometric integral and then use the method of Laplace to give a complete asymptotic expansion of the integral. Among the consequences, we have a complete asymptotic expansion for b(n, k)/n! for a range of k including the maximum of the b(n, k)/n!.

AMS Subject Classification: 05A16, 05A15, 05A10

A permutation σ = (σ(1), …, σ(n)) of [n] = {1, …, n} has an inversion at (i, j), where 1 ≤ i < j ≤ n, if and only if σ(i) > σ(j). Let b(n, k) denote the number of permutations of [n] with precisely k inversions. Then b(n, k) = b(n, \binom{n}{2} − k) for all integers k, while, b(n, k) ≠ 0 if and only if 0 ≤ k ≤ \binom{n}{2}. Bender [2; p. 110] showed that the b(n, k) are log concave in k. Hence, the maximum B(n) of the b(n, k) occurs at k = ⌊\binom{n}{2}/2⌋, as well as ⌈\binom{n}{2}/2⌉ for odd \binom{n}{2}. See [3; pps. 236–240] for further results.

Random permutations show (see [3; pps. 282–283], for example) that the b(n, k) satisfy a central limit theorem with μ_{n} = \binom{n}{2}/2 and σ_{n}^{2} = n(n − 1)(2n + 5)/72 (see [2; Theorem 1]). Bender [2; p. 109] remarks that “the theorems of Section 4 do not apply” to the b(n, k). He then shows [2; p. 110] that the b(n, k) are log concave in k “so that Lemma 2 applies.” This will give a (first term) asymptotic formula for b(n, k)/n! when k = ⌊μ_{n} + xσ_{n}⌋ where x is a fixed real number.

In this paper, we represent b(n, k) as a real trigonometric integral. We then use the method of Laplace to give a complete asymptotic expansion of this integral in terms of the Bernoulli numbers and Hermite polynomials. Hence, we have the complete asymptotic expansion

\frac{b(n, k)}{n!} = 6(2π)^{−1/2}n^{−3/2}e^{−x^{2}/2} \{1 + ∑_{q=1}^{2m−2}(−2)^{−q}S_{2q}(n)H_{2q}(2^{−1/2}x)\}

+ O (\frac{ln^{2m^{2}+1} n}{n^{m+3/2}}) as n → ∞ ,  (1)

when 2k = \binom{n}{2} ± xn^{3/2}/3 where x^{2} = x^{2}(n) ≤ ln n and m is a fixed integer at least 2. Here, H_{2q} are the Hermite polynomials defined before Theorem 1 and the S_{2q} are defined in Theorem 3. In particular, we have a complete asymptotic expansion for B(n)/n! when \binom{n}{2} is even. See Corollaries 2, 4 for other asymptotic expansions.

In what follows, k, ℓ and n are integers with 0 ≤ k ≤ \binom{n}{2} and 2 ≤ ℓ ≤ n. We denote the nonnegative integers by ℕ. All asymptotic formulas are for n → ∞.

Muir [5] (see also [3; p. 239]) showed that b(n, k) is the coefficient of z^{k} in ∏_{ℓ=2}^{n}(1 + z + ⋯ + z^{ℓ−1}). Then,

b(n, k) = \frac{1}{2πi} ∮_{C} \frac{∏_{ℓ=2}^{n}(1 + z + ⋯ + z^{ℓ−1})}{z^{k+1}} dz

= \frac{1}{2πi} ∮_{C} z^{−k−1} ∏_{ℓ=2}^{n} (\frac{z^{ℓ} − 1}{z − 1}) dz,

where C is the unit circle. Hence,

b(n, k) = \frac{2n!}{π} ∫_{0}^{π/2} ∏_{ℓ=2}^{n} (\frac{sin ℓt}{ℓ sin t}) cos (((n 2) − 2k) t) dt,  (2)

upon parameterizing C (z = e^{it}; t ∈ [0, 2π]) and using the symmetry of the integrand. For an integer n ≥ 2 and real numbers a, b and x, let

I(n, x, a, b) := ∫_{a}^{b} ∏_{ℓ=2}^{n} (\frac{sin ℓt}{ℓ sin t}) cos (\frac{xtn^{3/2}}{3} ) dt

and

I(n, x) := I (n, x, 0, \frac{π}{2} )

(where all discontinuities of the integrand have been removed). Then (2) gives

\frac{b(n, k)}{n!} = \frac{2}{π} I(n, x),  (3)

for all integers k, n where 0 ≤ k ≤ \binom{n}{2}, n ≥ 2 and 2k = \binom{n}{2} ± xn^{3/2}/3.

For a nonnegative integer q and real number x, let

F_{q}(x) := ∫_{0}^{∞} exp(−u^{2}/2)u^{q} cos(ux) du

denote the Fourier cosine transform of exp(−u^{2}/2)u^{q}. Then F_{2q}(x) = (−1)^{q}π^{1/2}2^{−q−1/2}e^{−x^{2}/2}H_{2q}(2^{−1/2}x). Here H_{n}(x) are the Hermite polynomials given by H_{n}(x) = ∑_{k=0}^{⌊n/2⌋}(−1)^{k}n!(2x)^{n−2k}/k!(n − 2k)! (see [4; pps. 60-64]).

We use the following Taylor series approximations which are valid for all real numbers t.

sin t = t − \frac{t^{3}}{6} + a(t); |a(t)| ≤ \frac{t^{4}}{24} for all real t and a(t) ≥ 0 for t ∈ [0, π]; (4)

cos t = 1 − \frac{t^{2}}{2} + b(t); 0 ≤ b(t) ≤ t^{3} for t ∈ [0, π];  (5)

and for an integer m ≥ 1,

e^{t} = 1 + t + ⋯ + \frac{t^{m−1}}{(m − 1)!} + c_{m}(t); |c_{m}(t)| ≤ e^{|t|} |t|^{m} .  (6)

Of course, our error terms a, b and c_{m} are all infinitely-differentiable functions over the reals. We also require the following inequality (integration by parts). For a real number x > 0,

∫_{x}^{∞} e^{−t^{2}/2} dt ≤ \frac{1}{x} e^{−x^{2}/2}.  (7)

We now give our first result.

Theorem 1. For x^{2} = x^{2}(n) ≤ ln n, we have the asymptotic expansion

I(n, x) = 3 (\frac{π}{2} )^{1/2} n^{−3/2}e^{−x^{2}/2}\{1 − \frac{1}{100n}(9x^{4} − 129x^{2} + 102)

+ \frac{1}{980000n^{2}} (3969x^{8} − 141282x^{6} + 1340865x^{4}

− 4579480x^{2} + 2259370)\} + O (\frac{ln^{19} n}{n^{9/2}}) as n → ∞.

Proof. We use the method of Laplace. For 0 < a ≤ 1 and an integer ℓ ≥ 2, let M_{ℓ}(a) := max{| sin ℓt/ sin t| : t ∈ [a, π/2]} and b := cos a ∈ (0, 1). For all integers ℓ ≥ 2, M_{ℓ}(a) ≤ b^{ℓ−1}+b^{ℓ−2}+⋯+b+1 ≤ min{ℓ, (1−b)^{−1}} by induction on ℓ, while a^{2}/3 ≤ 1−b. Here,

∏_{ℓ=2}^{n} |\frac{sin ℓt}{ℓ sin t}| ≤ \frac{(1 − b)^{−n}}{n!} ≤ (\frac{3e}{a^{2}n})^{n} ,

and, hence, for all n ≥ 9 and all real numbers x,

|I(n, x, 3n^{−0.5}, π/2)| ≤ 2 (\frac{e}{3} )^{n} .  (8)

For all integers ℓ and all real numbers t with sin t ≠ 0, (4) gives sin ℓt/ℓ sin t = 1 − (ℓ^{2} − 1)t^{2}/6 + d(ℓ, t) where |d(ℓ, t)| ≤ ℓ^{3}t^{3}/12 for t ∈ (0, 1] and ℓ ≥ 2. Hence,

0 < \frac{sin ℓt}{ℓ sin t} ≤ 1 − \frac{ℓ^{2}t^{2}}{24} ≤ exp (−\frac{ℓ^{2}t^{2}}{24} ) for ℓt ∈ [0, 1] and ℓ ≥ 2.  (9)

(Naturally, we define sin ℓt/ℓ sin t = 1 when t = 0 to remove that discontinuity.) For all n ≥ 144 and all real numbers x, (9) gives

|I(n, x, n^{−0.7}, 3n^{−0.5})| ≤ ∫_{n^{−0.7}}^{3n^{−0.5}} ∏_{ℓ=2}^{⌊n^{0.5}/3⌋} \frac{sin ℓt}{ℓ sin t} dt ≤ exp (\frac{−n^{0.1}}{4608} ) ,  (10)

|I(n, x, n^{−1}, n^{−0.7})| ≤ ∫_{n^{−1}}^{n^{−0.7}} ∏_{ℓ=2}^{⌊n^{0.7}⌋} \frac{sin ℓt}{ℓ sin t} dt ≤ exp (\frac{−n^{0.1}}{576} ) ,  (11)

and

|I(n, x, n^{−3/2} ln n, n^{−1})| ≤ ∫_{n^{−3/2} ln n}^{n^{−1}} ∏_{ℓ=2}^{n} \frac{sin ℓt}{ℓ sin t} dt ≤ exp (−\frac{ln^{2} n}{72}) .  (12)

Recall that cot t = t^{−1} + ∑_{k=1}^{∞}(−4)^{k}B_{2k}t^{2k−1}/(2k)!, for real t with 0 < |t| < π. Here B_{n} are the Bernoulli numbers defined by z/(e^{z} − 1) = ∑_{n=0}^{∞} B_{n}z^{n}/n! for complex z with |z| < 2π (see [3; pps. 48, 88]). Then, \frac{d}{dt}\{ ln(sin ℓt/ℓ sin t)\} = ℓ cot ℓt − cot t = ∑_{k=1}^{∞}(−4)^{k}B_{2k}(ℓ^{2k} − 1)t^{2k−1}/(2k)! for 0 < |ℓt| < π, hence,

ln (\frac{sin ℓt}{ℓ sin t}) = ∑_{k=1}^{∞}(−4)^{k}B_{2k}(ℓ^{2k} − 1)\frac{t^{2k}}{(2k)(2k)!} for |ℓt| < π.  (13)

For a nonnegative integer m, |ℓt| ≤ 1 and ℓ ≥ 1 (see [1; p. 805]),

| ∑_{k=m+1}^{∞}(−4)^{k}B_{2k}(ℓ^{2k} − 1)\frac{t^{2k}}{(2k)(2k)!}| ≤ ℓ^{2m+2}t^{2m+2}.  (14)

For n ≥ 2 and θ_{k}(n) := ∑_{ℓ=2}^{n}(ℓ^{k} − 1) (see [3; p. 155]), (13), (14; m = 3) and (6; m = 1) give

I(n, x, 0, n^{−3/2} ln n)

= ∫_{0}^{n^{−3/2} ln n}exp \{−∑_{ℓ=2}^{n} (\frac{ℓ^{2} − 1}{6}t^{2} + \frac{ℓ^{4} − 1}{180}t^{4} + \frac{ℓ^{6} − 1}{2835}t^{6} + O(n^{8}t^{8}))\} cos (\frac{xtn^{3/2}}{3} ) dt

= ∫_{0}^{n^{−3/2} ln n}exp \{−\frac{θ_{2}(n)t^{2}}{6} − \frac{θ_{4}(n)t^{4}}{180} − \frac{θ_{6}(n)t^{6}}{2835} + O(n^{9}t^{8})\} cos (\frac{xtn^{3/2}}{3} ) dt

= ∫_{0}^{n^{−3/2} ln n}exp \{−\frac{θ_{2}(n)t^{2}}{6} − \frac{θ_{4}(n)t^{4}}{180} − \frac{θ_{6}(n)t^{6}}{2835} \} cos (\frac{xtn^{3/2}}{3} ) dt + O (\frac{ln^{9} n}{n^{9/2}})

= \frac{3}{n^{3/2}} ∫_{0}^{ln n/3}exp (−\frac{u^{2}}{2} ) exp \{R_{2}(n)u^{2} + R_{4}(n)u^{4} + R_{6}(n)u^{6}\} cos(ux) du

+ O (\frac{ln^{9} n}{n^{9/2}}) ,  (15)

upon setting u = n^{3/2}t/3, where R_{2}(n) = −3/4n + 5/4n^{2}, R_{4}(n) = −9/100n − 9/40n^{2} − 3/20n^{3} + 93/200n^{5} and R_{6}(n) = −9/245n^{2} − 9/70n^{3} − 9/70n^{4} + 3/70n^{6} + 123/490n^{8}. It is readily seen that the error term in (15) is at most e n^{−9/2} ln^{9} n for all n ≥ 2 and all real numbers x. For 0 ≤ u ≤ ln n/3, (6; m = 3) gives

exp {R_{2}(n)u^{2} + R_{4}(n)u^{4} + R_{6}(n)u^{6}}
= 1 + S_{2}(n)u^{2} + S_{4}(n)u^{4} + S_{6}(n)u^{6} + S_{8}(n)u^{8} + O (\frac{ln^{18} n}{n^{3}}) ,  (16)

where S_{2}(n) = −3/4n + 5/4n^{2}, S_{4}(n) = −9/100n + 9/160n^{2}, S_{6}(n) = 603/19600n^{2} and S_{8}(n) = 81/20000n^{2}. Hence, (15) and (16) give

I(n, x, 0, n^{−3/2} ln n)

= \frac{3}{n^{3/2}} ∫_{0}^{ln n/3} exp (−\frac{u^{2}}{2} ) \{1 + S_{2}(n)u^{2} + S_{4}(n)u^{4} + S_{6}(n)u^{6} + S_{8}(n)u^{8}

+ O (\frac{ln^{18} n}{n^{3}}) \} cos(ux) du + O (\frac{ln^{9} n}{n^{9/2}})

= \frac{3}{n^{3/2}} ∫_{0}^{ln n/3} exp (−\frac{u^{2}}{2} ) \{1 + S_{2}(n)u^{2} + S_{4}(n)u^{4} + S_{6}(n)u^{6} + S_{8}(n)u^{8}\} cos(ux) du

+ O (\frac{ln^{19} n}{n^{9/2}})

= \frac{3}{n^{3/2}} ∫_{0}^{∞} exp (−\frac{u^{2}}{2} ) \{1 + S_{2}(n)u^{2} + S_{4}(n)u^{4} + S_{6}(n)u^{6} + S_{8}(n)u^{8}\} cos(ux) du

+ O (∫_{ln n/3}^{∞} exp (−\frac{u^{2}}{4} ) du) + O (\frac{ln^{19} n}{n^{9/2}})

= \frac{3}{n^{3/2}} ∫_{0}^{∞} exp (−\frac{u^{2}}{2} ) \{1 + S_{2}(n)u^{2} + S_{4}(n)u^{4} + S_{6}(n)u^{6} + S_{8}(n)u^{8}\} cos(ux) du

+ O (\frac{ln^{19} n}{n^{9/2}}) ,  (17)

where the last equation follows from (7). The error term in the first equation holds uniformly for all real numbers x by the comments after (15) and, since | cos(ux)| ≤ 1, the error term in the second equation holds uniformly for all real numbers x by (16) as does the error term in the third equation involving the integral. Then (8), (10–12) and (17) give

I(n, x) = \frac{3}{n^{3/2}} \{F_{0}(x) + S_{2}(n)F_{2}(x) + S_{4}(n)F_{4}(x) + S_{6}(n)F_{6}(x) + S_{8}(n)F_{8}(x)\}
+ O (\frac{ln^{19} n}{n^{9/2}}) ,  (18)

where our error term holds uniformly for all real numbers x. Hence, after simplifying (18) we obtain

I(n, x) =3 (\frac{π}{2} )^{1/2} n^{−3/2}e^{−x^{2}/2}\{1 − \frac{1}{100n}(9x^{4} − 129x^{2} + 102)

+ \frac{1}{980000n^{2}} (3969x^{8} − 141282x^{6} + 1340865x^{4}

− 4579480x^{2} + 2259370)\} + O (\frac{ln^{19} n}{n^{9/2}}) ,  (19)

where our error term holds uniformly for all real numbers x. Our result follows since, apart from the error term, the smallest term in (19) has order of magnitude at least n^{−4} for x^{2} = x^{2}(n) ≤ ln n. ■

We note several consequences of Theorem 1.

Corollary 2. For x^{2} = x^{2}(n) ≤ ln n, we have the asymptotic expansion

\frac{b(n, k)}{n!} =6(2π)^{−1/2}n^{−3/2}e^{−x^{2}/2}\{1 − \frac{1}{100n}(9x^{4} − 129x^{2} + 102)

+ \frac{1}{980000n^{2}} (3969x^{8} − 141282x^{6} + 1340865x^{4}

− 4579480x^{2} + 2259370)\} + O (\frac{ln^{19} n}{n^{9/2}}) as n → ∞,

when 2k = \binom{n}{2} ± xn^{3/2}/3. We also have the asymptotic expansion

\frac{b(n, k)}{n!} = 6(2π)^{−1/2}n^{−3/2} (1 − \frac{51}{50n} + \frac{225937}{98000n^{2}} ) + o (\frac{1}{n^{7/2}} ) as n → ∞,

provided 2k = \binom{n}{2} + o(n^{1/2} ln^{−3/2} n). In particular, B(n)/n! has the same asymptotic expansion.

Proof. The asymptotic expansion for b(n, k)/n! when 2k = \binom{n}{2} ± xn^{3/2}/3 where x^{2} = x^{2}(n) ≤ ln n follows immediately from (3) and Theorem 1. For all n ≥ e^{141} and all real numbers x, (8) and (10–12) give

|∫_{n^{−3/2} ln n}^{π/2} ∏_{ℓ=2}^{n} (\frac{sin ℓt}{ℓ sin t}) \{1 − cos (\frac{xtn^{3/2}}{3} )\} dt | ≤ 10 exp (−\frac{ln^{2} n}{72}) .  (20)

For an integer ℓ ≥ 2 and all t ∈ [0, π/2ℓ], sin ℓt/ℓ sin t ∈ [0, 1] by induction on ℓ. Then, for all n ≥ 2 and all x ∈ [0, ln^{−1} n], (5) gives

0 ≤ ∫_{0}^{n^{−3/2} ln n} ∏_{ℓ=2}^{n} (\frac{sin ℓt}{ℓ sin t}) \{1 − cos (\frac{xtn^{3/2}}{3} )\} dt

≤ ∫_{0}^{n^{−3/2} ln n} \frac{x^{2}t^{2}n^{3}}{18} dt = \frac{x^{2} ln^{3} n}{54n^{3/2}}.  (21)

Hence, for all n ≥ e^{141} and all x ∈ [0, ln^{−1} n], (20) and (21) give

|I(n, 0) − I(n, x)| ≤ \frac{x^{2} ln^{3} n}{54n^{3/2}} + 10 exp (−\frac{ln^{2} n}{72}) .  (22)

Assume \binom{n}{2} is even (odd \binom{n}{2} is similar) and n ≥ e^{141}. Let ℓ := ⌊\binom{n}{2}/2 + n^{3/2}/6 ln n⌋ so that 2ℓ = \binom{n}{2} + xn^{3/2}/3 with x ∈ [0, ln^{−1} n]. For \binom{n}{2} ≤ 2k ≤ 2ℓ, log concavity of the b(n, k) implies

b (n, \frac{\binom{n}{2}}{2}) ≥ b(n, k) ≥ b(n, ℓ),

so that (3) and (22) give

\frac{2}{π} I(n, 0) ≥ \frac{b(n, k)}{n!} ≥ \frac{2}{π} I(n, 0) − \frac{x^{2} ln^{3} n}{27πn^{3/2}} − \frac{20}{π} exp (−\frac{ln^{2} n}{72}) .

Hence, Theorem 1 gives

\frac{b(n, k)}{n!} = 6(2π)^{−1/2}n^{−3/2} (1 − \frac{51}{50n} + \frac{225937}{98000n^{2}} ) + o (\frac{1}{n^{7/2}} ) ,

for 2k = \binom{n}{2} + o(n^{1/2} ln^{−3/2} n). ■ Remark. We can replace the o(n^{−7/2}) error term in the asymptotic expansion of B(n)/n! with O(n^{−9/2} ln^{19} n).

The following extension of Theorem 1 (the case m = 3) giving a complete asymptotic expansion of I(n, x) can be immediately read out of its proof.

Theorem 3. Fix an integer m ≥ 2. For x^{2} = x^{2}(n) ≤ ln n, we have the asymptotic expansion

I(n, x) = 3 (\frac{π}{2} )^{1/2} n^{−3/2}e^{−x^{2}/2} \{1 + ∑_{q=1}^{2m−2}(−2)^{−q}S_{2q}(n)H_{2q}(2^{−1/2}x)\}

+ O (\frac{ln^{2m^{2}+1} n}{n^{m+3/2}}) as n → ∞.

(The S_{2q}(n) are defined in the proof.)

Proof. For 2 ≤ ℓ ≤ n and t ∈ [0, n^{−1}], (13) and (14) give

ln (\frac{sin ℓt}{ℓ sin t}) = ∑_{k=1}^{m} c_{2k}(ℓ^{2k} − 1)t^{2k} + O(n^{2m+2}t^{2m+2}),  (23)

where c_{2k} := (−4)^{k}B_{2k}/(2k)(2k)! < 0, while,

0 ≤ θ_{2k}(n) = ∑_{ℓ=2}^{n}(ℓ^{2k} − 1) = \frac{1}{2k + 1} ∑_{j=0}^{2k} B_{j}\binom{2k + 1}{j}(n + 1)^{2k+1−j} − n .

Hence, (23) and (6; m = 1) give

I(n, x, 0, n^{−3/2} ln n)

= \frac{3}{n^{3/2}} ∫_{0}^{ln n/3}exp \{∑_{k=1}^{m} 9^{k}c_{2k}θ_{2k}(n)u^{2k}n^{−3k}\} cos(ux) du + O (\frac{ln^{2m+3} n}{n^{m+3/2}})

= \frac{3}{n^{3/2}} ∫_{0}^{ln n/3}exp (−\frac{u^{2}}{2} ) exp \{R_{2}(n)u^{2} + ⋯ + R_{2m}(n)u^{2m}\} cos(ux) du

+ O (\frac{ln^{2m+3} n}{n^{m+3/2}}) ,  (24)

where R_{2}(n) = −3/4n + 5/4n^{2} and, for 2 ≤ k ≤ m,

R_{2k}(n) := \frac{(−36)^{k}B_{2k}}{(2k)(2k + 1)!} ∑_{j=0}^{2k} B_{j}\binom{2k + 1}{j}n^{−3k}(n + 1)^{2k+1−j} − \frac{(−36)^{k}B_{2k}}{(2k)(2k)!} n^{−3k+1}.

The error term in (24) holds uniformly for all real numbers x. For 2 ≤ k ≤ m ≤ n − 1, crude estimates (see [1; p. 805]) give

|R_{2k}(n)| ≤ 60(2k + 1)! n^{−k+1},  (25)

(in fact, R_{2k}(n) involves n^{−k+1} and smaller integer powers of n). For all n ≥ m + 1 and all 0 ≤ u ≤ ln n/3, (25) gives

|R_{2}(n)u^{2} + ⋯ + R_{2m}(n)u^{2m}| ≤ m(2m + 1)! (\frac{ln^{2m} n}{n}) .  (26)

Hence, (6) and (26) give

exp \{R_{2}(n)u^{2} + ⋯ + R_{2m}(n)u^{2m}\} = 1 + ∑_{q=1}^{2m−2} S_{2q}(n)u^{2q} + O (\frac{ln^{2m^{2}} n}{n^{m}}) ,  (27)

where S_{2q}(n) is that part of

∑_{r=1}^{m−1} ∑_{\begin{matrix}(e_{2},...,e_{2m})∈ℕ^{m} \\ e_{2}+···+e_{2m}=r \\ 2e_{2}+···+2me_{2m}=2q \end{matrix}} \frac{R_{2}^{e_{2}}(n) ⋯ R_{2m}^{e_{2m}}(n)}{e_{2}! ⋯ e_{2m}!}

involving only n^{−1}, …, n^{−m+1} upon expansion. Here R_{2}^{e_{2}}(n) ⋯ R_{2m}^{e_{2m}}(n) involves n^{−(e_{2}+···+(m−1)e_{2m})} = n^{−(q−r+e_{2})} and smaller integer powers of n while q − r + e_{2} ≥ m if q ≥ 2m − 1. Then, (24) and (27) give

I(n, x, 0, n^{−3/2} ln n)

= \frac{3}{n^{3/2}} ∫_{0}^{ln n/3}exp (−\frac{u^{2}}{2} ) \{1 + ∑_{q=1}^{2m−2} S_{2q}(n)u^{2q}\} cos(ux) du + O (\frac{ln^{2m^{2}+1} n}{n^{m+3/2}})

= \frac{3}{n^{3/2}} ∫_{0}^{∞} exp (−\frac{u^{2}}{2} ) \{1 + ∑_{q=1}^{2m−2} S_{2q}(n)u^{2q}\} cos(ux) du + O (\frac{ln^{2m^{2}+1} n}{n^{m+3/2}}) , (28)

where our error term holds uniformly for all real numbers x. Hence, after simplifying, (8), (10–12) and (28) give

I(n, x) = 3 (\frac{π}{2} )^{1/2} n^{−3/2}e^{−x^{2}/2} \{1 + ∑_{q=1}^{2m−2}(−2)^{−q}S_{2q}(n)H_{2q}(2^{−1/2}x)\}

+ O (\frac{ln^{2m^{2}+1} n}{n^{m+3/2}}) ,  (29)

where our error term holds uniformly for all real numbers x. Our result follows since, apart from the error term, the smallest term in (29) has order of magnitude at least n^{−m−1} for x^{2} = x^{2}(n) ≤ ln n. ■

As a consequence of Theorem 3, we have a complete asymptotic expansion for b(n, k)/n! when 2k = \binom{n}{2} ± xn^{3/2}/3 where x^{2} = x^{2}(n) ≤ ln n, as well as for B(n)/n! when \binom{n}{2} is even.

Corollary 4. Fix an integer m ≥ 2. For x^{2} = x^{2}(n) ≤ ln n, we have the asymptotic expansion

\frac{b(n, k)}{n!} = 6(2π)^{−1/2}n^{−3/2}e^{−x^{2}/2} \{1 + ∑_{q=1}^{2m−2}(−2)^{−q}S_{2q}(n)H_{2q}(2^{−1/2}x)\}

+ O (\frac{ln^{2m^{2}+1} n}{n^{m+3/2}}) as n → ∞,

when 2k = \binom{n}{2} ± xn^{3/2}/3. In particular, we have the asymptotic expansion

\frac{B(n)}{n!} = 6(2π)^{−1/2}n^{−3/2} \{1 + ∑_{q=1}^{2m−2} 2^{−q} \frac{(2q)!}{q!}S_{2q}(n)\} + O (\frac{ln^{2m^{2}+1} n}{n^{m+3/2}}) as n → ∞,

when \binom{n}{2} is even. ■

In the following table we compare the exact value of B(n)/n! (found by expanding the generating function for the b(n, k)) with the approximations (given by Corollary 4 for m = 2, 3) for n = 40 and 80.

B(40)/40!  B(80)/80!
Exact Value  0.009233258744992 ⋯ 0.003303747524408 ⋯
Approximation (m = 2)  0.009220472410157 ⋯ 0.003302581000634 ⋯
Relative Error  0.138481%  0.035309%
Error as a function of n  40−3.05435 ⋯  80−3.11761 ⋯
Approximation (m = 3)  0.009234106075478 ⋯ 0.003303786057784 ⋯
Relative Error  0.009176%  0.001166%
Error as a function of n  40−3.79008 ⋯  80−3.89585 ⋯

Acknowledgement. I wish to thank the referee for numerous comments and suggestions which have led to a substantially improved paper.

References

[1] M. Abramowitz and I.A. Stegun, Eds., Handbook of Mathematical Functions with Formulas, Graphs and Mathematical Tables, Dover Publications, New York, 1966.

[2] E.A. Bender, Central and Local Limit Theorems Applied to Asymptotic Enumeration, J. Combinatorial Theory A 15 (1973), 91–111.

[3] L. Comtet, Advanced Combinatorics, D. Reidel, Boston, 1974.

[4] N.N. Lebedev, Special Functions and Their Applications, Dover Publications, New York, 1972.

[5] T. Muir, On a Simple Term of a Determinant, Proc. Royal Society Edinburg 21 (1898–9), 441–477.