Лекции по геометрии и алгебре. Карчевский Е.М - 64 стр.

§ 1. Перестановки                                                               63




Рис. 1. Пример перестановки из десяти элементов (a). Перестановка b получена из пе-
рестановки a транспозицией (4,8).


поставить первым, вторым, и, наконец, последним, т. е. n-ым (здесь
хорошо представить себе спортсмена, опоздавшего к построению ко-
манды). Понятно, что таким образом можно создать n перестановок
по каждой перестановке множества Mn−1 , и, поскольку по индуктив-
ному предположению Pn−1 = (n − 1)!, то формула (1.4) доказана.
   2. Будем говорить, что элементы ni , nj , i < j, перестановки (1.3)
образуют инверсию, если ni > nj . Например, в перестановке (1.1) нет
инверсий, а в перестановке (1.2) только одна инверсия, ее образуют
элементы n1 , n2 . Полезно отметить, что если соединить отрезком на
графике перестановки точки (i, ni ) и (j, nj ), то он будет иметь отри-
цательный наклон для пар точек, образующих инверсию.
   Количество всех инверсий данной перестановки будем обозначать
                               σ(n1 , n2 , . . . , nn )
и называть сигнатурой перестановки.
    Перестановка называется четной, если ее сингнатура — четное
число (нуль, как обычно, полагаем четным числом). В противном слу-
чае перестановка называется нечетной.
    Таким образом, все перестановки разбиваются на два непустых
класса: четные перестановки и нечетные перестановки. Например, пе-
рестановка (1.1) четная, а перестановка (1.2) нечетная.
    Говорят, что в перестановке выполнена транспозиция, если поме-
няли местами два ее элемента. Чтобы определить транспозицию дан-
ной перестановки, нужно задать номера двух, переставляемых эле-
ментов. Например, можно сказать, что перестановка (1.2) получена
из перестановки (1.1) транспозицией (1,2). Еще один пример транс-
позиции показан на рисунке 1.