arXiv:1611.07336v1 [] 22 Nov 2016

Asymptotic expansions for factorial moments of some distributions
in the analysis of algorithms
Sumit Kumar Jha
Abstract. We establish asymptotic expansions for factorial moments of following distributions:
number of cycles in a random permutation, number of inversions in a random permutation, and
number of comparisons used by the randomized quick sort algorithm. To achieve this we use
singularity analysis of certain type of generating functions due to Flajolet and Odlyzko.

1. Introduction
We consider three different distributions arising in the analysis of algorithms in each of the
following sections:
1. Number of cycles in a random permutation.
2. Number of inversions in a random permutation
3. Number of comparisons used by the randomized quick sort algorithm.
For each of the above distributions, we establish asymptotic expansions for factorial moments
using a unified framework developed by Kirschenhofer, Prodinger and Tichy in [3], and singularity
analysis of certain type of generating functions due to Flajolet and Odlyzko in [1].
Notation: Let Sn the set of all n! permutations of {1, 2, · · · , n}. The Euler’s constant is
γ = 0.577 · · · . Let Rp,q (u) be an unspecified linear combination of terms of the form


1
log
1−u

i

(1 − u)−j−1

where i, j are integers with either j < q and i is arbitrary, or j = q and i ≤ p
We would use the following result throughout:
Theorem 1.1 (Flajolet and Odlyzko [1]). Let
(1.1)

1
fα,β (u) ≡ f (u) =
(1 − u)α



1
log
1−u

β
,

where α is a positive integer and β is a non-negative integer. The coefficient of un in f (u), denoted
[un ]f (u), admits the asymptotic expansion


nα−1
C1 β
C2 (β)(β − 1)
(1.2)
[un ]f (u) ∼
(log n)β 1 +
+
+
·
·
·
,
(α − 1)!
1! log n
2! log2 (n)
where
dk 1
Ck = (α − 1)!
dxk Γ(x)


and Γ(·) is the gamma function.
1


x=α

2

SUMIT KUMAR JHA

2. Number of cycles in a random permutation
Let Cn,k be the number of permutations in Sn with exactly k cycles. We use the following
lemma from [6]:
Lemma 2.1. We have
Cn,k = (n − 1) · Cn−1,k + Cn−1,k−1

(2.1)

(n, k ≥ 1),

with the initial conditions Cn,k = 0 if n < k or k = 0, except C0,0 = 1.
Let sth factorial moment of number of cycles in a random permutation be
X
Cn,k
βs (n) =
(k)s
n!
k≥0

where (k)s = (k)(k − 1) · · · (k − s + 1) and (k)0 = 1.
Theorem 2.2. We have
βs (n) = logs (n) + γs logs−1 (n) + O(logs−2 (n))
for integers s ≥ 1.
Proof. We start by defining the corresponding probability generating function:
X Cn,k
zk ,
Gn (z) =
n!
k≥0

with G0 (z) = 1. After equation (2.1), we have
X Cn,k
n − 1 X Cn−1,k · z k
z X
z k−1
Gn (z) =
zk =
·
+ ·
Cn−1,k−1 ·
n!
n
(n − 1)!
n
(n − 1)!
k≥1

k≥1

k≥1

z+n−1
· Gn−1 (z)
n
for n ≥ 1. Next we consider the bi-variate generating function defined by:
X
H(z, u) =
Gn (z)un .
=

n≥0

We then have
X
X
∂
H(z, u) =
n · Gn (z)un−1 =
(z + n − 1) · Gn−1 (z)un−1
∂u
n≥1
n≥1
X
= z · H(z, u) + u ·
(n − 1) · Gn−1 (z)un−2
n≥1

= z · H(z, u) + u ·
which gives
∂H(z, u)
z
=
· H(z, u)
∂u
1−u
P
with H(1, u) = n≥0 un = (1 − u)−1 .
Solving equation 2.2 gives
(2.2)

(2.3)
Now note that

H(z, u) = (1 − u)−z .


ds
βs (n) =
Gn (z)
.
dz s
z=1
The generating functions fs (u) of βs (n) are defined by
X
fs (u) =
βs (n)un .


n≥0

∂H(z, u)
∂u

ASYMPTOTIC EXPANSIONS FOR FACTORIAL MOMENTS

3

By the Taylor series we have
X Gn (z) n X X (z − 1)s
X (z − 1)s
H(z, u) =
=
βs (n) · un =
fs (u)
u
s!
s!
n≥0

n≥0 s≥0

s≥0

which gives

fs (u) =



s
1
∂s
1
H(z,
u)
=
log
.
∂z s
1−u
1−u
z=1

Now using equation (1.2) (with α = 1 and β = s) we conclude the assertion after noting γ =
C1 .

3. Number of inversions in a random permutation
In a permutation σ = (a1 , a2 , · · · , an ) a pair (ai , aj ), i < j is called inversion if ai > aj . Let
In,k be the number of permutations in Sn having a total of k inversions. Then we have from [4]
In,k = In−1,k + In−1,k−1 + · · · + In−1,k−(n−1)

(n, k ≥ 1),

with the initial conditions In,k = 0 if n < k or k = 0, except I0,0 = 1.
The corresponding probability generating function is
X In,k
zk ,
Gn (z) =
n!
k≥0

with G0 (z) = 1. Then we have
Gn (z) =

X In,k
k≥0

n!

zk =

X

(In−1,k + In−1,k−1 + · · · + In−1,k−(n−1) ) ·

k≥0

=

zk
n!

1 + z + z 2 + · · · + z n−1
· Gn−1 (z)
n
1 − zn
Gn−1 (z).
=
n(1 − z)

for n ≥ 1. Next we consider the bi-variate generating function defined by:
X
H(z, u) =
Gn (z)un .
n≥0

We then have
X
X 1 − zn
∂
H(z, u) z · H(z, zu)
H(z, u) =
nGn (z)un−1 =
Gn−1 (z)un−1 =
−
∂u
1−z
1−z
1−z
n≥0

n≥0

which gives
(3.1)

(1 − z) ·

∂
H(z, u) = H(z, u) − z · H(z, zu)
∂u

P
with H(1, z) = n≥0 un = (1 − u)−1 .
Let sth factorial moment of number of inversions in a random permutation be
X
In,k
βs (n) =
(k)s
n!
k≥0

where (k)s = (k)(k − 1) · · · (k − s + 1) and (k)0 = 1. We would prove here that
Theorem 3.1. We have
βs (n) =
for integers s ≥ 1.

n2s
s(2s − 11) 2s−1
+
n
+ O(n2s−2 )
4s
9 · 4s

4

SUMIT KUMAR JHA

Proof. First note that


ds
βs (n) =
Gn (z)
.
dz s
z=1
The generating functions fs (u) of βs (n) are defined by
X
fs (u) =
βs (n)un .


n≥0

By the Taylor series we have
X
X X (z − 1)s
X (z − 1)s
βs (n) · un =
fs (u).
H(z, u) =
Gn (z)un =
s!
s!
n≥0

n≥0 s≥0

s≥0

After equation (3.1) we have
X (z − 1)s+1
s!

s≥0

=z·

X (z − 1)s
s≥0

=z·

=

i≥0

s!

fs (uz) −

X (z − 1)r
r≥0

r!

fr (u)

X (z − 1)s X fs(m) (u)(z − 1)m um X (z − 1)r
−
fr (u)
s!
m!
r!
s≥0

X

fs0 (u) = z · H(z, zu) − H(z, u)

m≥0

r≥0

X (z − 1)s X fs(m) (u)(z − 1)m um X (z − 1)r
ai (z − 1)i ·
−
fr (u)
s!
m!
r!
s≥0

m≥0

r≥0

X (z − 1)j X fj(m) (u)(z − 1)m um X (z − 1)r
i
−
fr (u)
=
ai (z − 1) ·
j!
m!
r!
m≥0
r≥0
i≥0
j≥0


X  X ai · fj(m) · um
fs (u) 
=
−
(z − 1)s ,


j!
·
m!
s!
i+j+m=s
X

s≥0

P
where to deduce the third step we used Taylor series, and then we replaced z by i ai (z − 1)i
where a0 = a1 = 1 and ai = 0 for i ≥ 2. The above after comparison of coefficients on both sides
gives



 X ai · f (m) · um
f
(u)
s
j
0
−
,
fs−1
(u) = (s − 1)! ·

j! · m!
s! 
i+j+m=s
for s ≥ 1, which is




(m)
m

a
·
f
·
u
f
(u)
i
s+1
j
−
fs0 (u) = s! ·

j! · m!
(s + 1)! 
i+j+m=s+1


(m)
m
 X f (m) · um
X
fj · u
fs+1 (u) 
j
= s! ·
+
−

j! · m!
j! · m!
(s + 1)! 
j+m=s+1
j+m=s
( s+1
)
(m)
s
(m)
X fs+1−m
X
· um
fs−m · um
fs+1 (u)
= s!
+
−
m! · (s + 1 − m)! m=0 (s − m)! · m! (s + 1)!
m=0
( s+1
)
(m)
s
(m)
X fs+1−m
X
· um
fs−m · um
= s!
+
.
m! · (s + 1 − m)! m=0 (s − m)! · m!
m=1
X

for s ≥ 1. This results in the following linear differential equation
(3.2)

fs0 (u) −

fs (u)
= hs (u)
(1 − u)

ASYMPTOTIC EXPANSIONS FOR FACTORIAL MOMENTS

5

where
1
hs (u) =
1−u

(

)

s+1 
s  
X
1 X s + 1 (m)
s
(m)
m
m
fs+1−m · u +
f
·u
.
s + 1 m=2
m
m s−m
m=1

The linear differential equation (3.2) can be solved as
Z u
1
hs (t)(1 − t)dt.
fs (u) =
1−u 0
It can be proved using induction (see [3] for similar calculation) that
fs (u) =

(2s)!
s
(2s − 1)!
−
(4s + 5) ·
+ R0,2s−1 .
4s (1 − u)2s+1
9 · 4s−1
(1 − u)2s

After this we conclude the result using equation (1.2).



Remark 3.2. See [5] for an alternate calculation.
4. Number of comparisons used by the randomized quick sort algorithm
We assume that input arrays to the basic quick sort algorithm of size n are permutations
in the set Sn with uniform probability distribution (each permutation occurring with probability
1/n! .)
Let an,k be the number of permutations in Sn requiring a total of k comparisons to sort by
the quick sort algorithm. Define sth factorial moment of the number of comparisons by
X
an,k
(4.1)
βs (n) =
(k)s
,
n!
k≥0

where (k)s = k(k − 1)(k − 2) · · · (k − s + 1).
It can be proved (see [2] for an alternate calculation for following) that
Gn (z) =

z n−1 X
Gn−j (z)Gj−1 (z)
n
1≤j≤n

with G0 (z) = 1. And from this
∂H(z, u)
= H 2 (z, zu)
∂u
P
P
a
zk
with H(1, u) = (1 − u)−1 . Here Gn (z) = k≥0 n,k
and H(z, u) = n≥0 Gn (z)un are corren!
sponding probability
P generating function and bi-variate generating function, respectively.
Let fs (u) = n≥0 βs (n)un be the generating functions for factorial moments. It can be proved
using induction and
(k)

(m)

s(Hs − 2) 2s s!
(1 − u)s+1



X

fs0 (u) = s! ·

j+k+l+m=s

fj (u) · fl (u) · uk+m
j! · k! · l! · m!

that
fs (u) =

2s s!
(1 − u)s+1


log

1
1−u

s
+

log

1
1−u

s−1
+ Rs−2,s+1 (u),

after which using equation 1.2 we can conclude
βs (n) = 2s ns logs n + 2s s(γ − 2)ns logs−1 n + O(ns · logs−2 n).

6

SUMIT KUMAR JHA

References
1. Philippe Flajolet and Andrew Odlyzko, Singularity analysis of generating functions, SIAM Journal on discrete
mathematics 3 (1990), no. 2, 216–240.
2. Sumit Kumar Jha, Asymptotic expressions for moments of number of comparisons used by the randomized quick
sort algorithm, (2016 https://arxiv.org/abs/1610.05656)).
3. P. Kirschenhofer, H. Prodinger, and R.F. Tichy, A contribution to the analysis of in situ permutation, Glasnik
Mathematicki 22(42) (1987), 269–278.
4. Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison
Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1998.
5. Wolfgang Panny, A note of the higher moments of the expected behavior of straight insertion sort, Information
processing letters 22 (1986), no. 4, 175–177.
6. Richard P. Stanley, Enumerative combinatorics: Volume 1, 2nd ed., Cambridge University Press, New York,
NY, USA, 2011.
Center for Security, Theory, and Algorithmic Research, International Institute of Information
Technology, Hyderabad, India
E-mail address: kumarjha.sumit@research.iiit.ac.in

