Теоремы о транспозициях и перестановках
Date: 2015-10-07; view: 536.
Теорема 1. Любая транспозиция изменяет четность перестановки.
Доказательство.
Утверждение теоремы представляется вполне очевидным в случае транспозиции соседних элементов, поскольку взаимная перестановка элементов ij и ij+1 приводит к появлению или исчезновению инверсии между ними.
Транспозицию элементов ij и ij+k можно рассматривать как результат k последовательных транспозиций элемента ij с соседними элементами, расположенными справа от ij , и последующих k - 1 транспозиций элемента ij+k с соседними элементами, расположенными слева от ij+k :
Полное число транспозиций k + (k - 1) = 2 k - 1 является нечетным числом, что означает изменение четности перестановки.
| <== previous lecture | | | next lecture ==> |
| Перестановки и транспозиции | | | Следствия. |