
420 Combinatorics of Permutations, Second Edition
patterns for the triple p
i
p
j
p
l
are favorable (the ones in which p
i
is the
largest of the three entries). Similarly, we have E(Z
i,j
Z
k,l
)=1/3if
j = l but i = k. Each of these possibilities occur in 2
n
3
cases. Finally,
it can also happen that j = k,inwhichcaseE(Z
i,j
Z
k,l
)=1/6 (the
pattern p
i
p
j
p
l
has to be decreasing) or that i = l, in which case again,
E(Z
i,j
Z
k,l
)=1/6 (the pattern p
k
p
i
p
j
has to be decreasing). Each of
these scenarios occur
n
3
times. Therefore, we have
E(Z
2
)=
i<j
E(Z
2
i,j
)+
(i,j)=(k,l)
E(Z
i,j
Z
k,l
)
=
1
2
n
2
+
1
4
n
2
n − 2
2
+
5
3
n
3
,
and consequently,
Var(Z)=E(Z
2
) − E(Z)
2
=
1
2
n
2
+
1
4
n
2
n − 2
2
+
5
3
n
3