Feladat: 14.23. [
84]
IMO 1989. New York, javaslat
Határozzuk meg az
1,
2, ... ,
n számok véletlen permutációjában az inverziók számának várható értékét! Az
(
i1
,
i2
,…,
in
) permutáció inverziói mindazok az
1≤k≠m≤n számpárok, amelyekre
k<m, de
ik
>
im
(tehát mindazon számpárok száma, amelyek nagyságrendjükkel ellentétes sorrendben állnak a permutációban). Az
1,
2,
3,
4 számok
(2413) permutációjában az alábbi párok állnak inverzióban:
(21),
(41),
(43), tehát az inverziók száma itt
3.
Megoldás: 14.23
Párosítsuk a permutációkat! Az
(
i1
,
i2
,…,
in-1
,
in
) permutáció párja legyen az
(
in
,
in-1
,…,
i2
,
i1
) permutáció. Minden számpár e két permutáció közül pontosan az egyikben áll inverzióban, tehát a kettőben együtt összesen
(
n
2
)=
n(n-1)
2
inverzió van. Így egy permutációban átlagosan ennek a fele, azaz
n(n-1)
4
inverzió van.