Алгебра : Теоремы и алгоритмы. Яцкин Н.И. - 193 стр.

§ 21             Число инверсий в перестановке                  193

   Среди инверсий обязательно найдется такая, которая реализует-
ся на соседних номерах i, i + 1 (1 6 i 6 n − 1). (В противном случае
перестановка ϕ была бы строго возрастающей функцией и, следова-
тельно, равнялась бы ε; см. замечание 21.1.)
   Выберем какую-либо из таких инверсий, т. е. пару соседних номе-
ров i, i + 1 , для которой ϕ(i) > ϕ(i + 1).
   Рассмотрим перестановку

                          ϕ1 = ϕ (i, i + 1).                   (21.5)

  На номера j, отличные от i и i + 1, перестановка ϕ1 действует так
же, как и ϕ : ϕ1 (j) = ϕ(j). На номерах i, i + 1 получим:

                 ϕ1 (i) = ϕ(i + 1); ϕ1 (i + 1) = ϕ(i),
и следовательно, ϕ1 (i) < ϕ1 (i + 1), т. е. в перестановке ϕ1 на этих
соседних номерах инверсии не будет.
   Другие же инверсии сохранятся. (Почему?)
   Стало быть, перестановка ϕ1 будет иметь на одну инверсию мень-
ше, чем ϕ.
   Если ϕ1 еще не равна ε, то и в ней найдется "инверсия соседей"
и процесс можно будет продолжить.
   (Чем он закончится? Завершите рассуждение.) ¤
   Пример 21.2. Знак перестановки из примера 21.1:

                  sgn(ϕ) = (−1)ι(ϕ) = (−1)16 = 1.

   Замечание 21.2 (для служебного пользования). В подавляющем
числе учебников по алгебре (например, в [3]) второй способ опреде-
ления знака излагается как основной. Мы предпочли последовать
методике курса [2] по следующим причинам.
   1. Нам представляется очень красивым, поучительным (и непри-
вычным для школярского мышления) доказательство предложения
19.4.
   2. При избранном нами подходе обоснование главного свойства
знака (см. предложение 20.1) совершенно тривиально, в то время как
при втором способе именно этот факт вызывает наибольшие (хотя,
конечно, преодолимые) трудности.
   Кстати, есть еще и третий способ, совершенно заформализован-
ный и вряд ли приемлемый для изложения первокурсникам (см.,
например, [7]).