Теоремы о транспозициях и перестановках (примеры)  
  1. Множество S = {1, 2, 3} содержит три элемента, и поэтому число различных перестановок этого множества равно 3! = 6:

    {1, 2, 3},    {1, 3, 2},    {2, 3, 1},    {2, 1, 3},    {3, 1, 2}    {3, 2, 1}.


***
  1. Показать, что перестановка  P = {2, 3, 1} является четной.

    Решение.
    Элементы 2 и 1 образуют инверсию, поскольку число 2 расположено слева от меньшего числа 1.
    Элементы 3 и 1 образуют инверсию, поскольку число 3 расположено слева от меньшего числа 1.

    Таким образом, перестановка  P  содержит четное число инверсий.

    Другое решение.
    Перестановка  P  является четной, поскольку представляет собой результат четного числа последовательных транспозиций элементов множества  S = {1, 2, 3}:

    {1, 2, 3}    ⇒    {1, 3, 2}    ⇒    {2, 3, 1}.

***
  1. Показать, что перестановка  Q = {3, 1, 2} является четной.

    Решение. Достаточно показать, что перестановка  Q  содержит четное число инверсий.

    Элементы 3 и 1 образуют инверсию, поскольку число 3 расположено слева от меньшего числа 1.
    Элементы 3 и 2 образуют инверсию, поскольку число 3 расположено слева от меньшего числа 2.
    Элементы 1 и 2 не образуют инверсию.

    Таким образом, перестановка  Q  содержит четное число инверсий.