Показать страницуИстория страницыСсылки сюдаНаверх Эта страница только для чтения. Вы можете посмотреть её исходный текст, но не можете его изменить. Сообщите администратору, если считаете, что это неправильно. ===== 236. Число инверсий в перестановке ===== ==== Условие задачи ==== Определить число инверсий в перестановках: 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$.