Определить число инверсий в перестановках:

a) $1,3,4,7,8,2,6,9,5$; b) $2,1,7,9,8,6,3,5,4$; c) $9,8,7,6,5,4,3,2,1$.

Для каждого элемента считаем число стоящих правее него и меньших его чисел; сумма таких чисел — число инверсий.

а) $1{:}0,\ 3{:}1,\ 4{:}1,\ 7{:}3,\ 8{:}3,\ 2{:}0,\ 6{:}1,\ 9{:}1,\ 5{:}0$. Сумма $=0+1+1+3+3+0+1+1+0=10$.

b) $2{:}1,\ 1{:}0,\ 7{:}4,\ 9{:}5,\ 8{:}4,\ 6{:}3,\ 3{:}0,\ 5{:}1,\ 4{:}0$. Сумма $=1+0+4+5+4+3+0+1+0=18$.

c) Полностью убывающая перестановка из $9$ чисел: каждая пара — инверсия, число пар $\binom92=36$.

a) $10$; b) $18$; c) $36$.