2014-06-08
Строка $(i_{1}; i_{2}; \cdots; i_{n})$ составлена из $n$ первых натуральных чисел, расположенных в случайном порядке. Найти среднее число инверсий (беспорядков) в этой строке, если инверсией называть каждую пару чисел $i_{j} > i_{k}$, для которой $j < k$.
Решение:
Разобьем все строки на пары взаимно «обратных» строк: $(i_{1}; \cdots; i_{n})$ и $(i_{n}; \cdots; i_{1})$. Любые два натуральных числа $m > l$, не превосходящие $n$, образуют инверсию ровно в одной из строк каждой такой пары. Следовательно, в каждой такой паре строк имеется ровно $n(n - 1)/2$ инверсий (столько, сколько существует способов выбрать в строке указанные числа $m, l$). Поэтому среднее число инверсий для каждой пары строк равно $n(n - 1)/4$. Тому же значению равно и среднее число инверсий по всем строкам.