Cтраница 3
А), ( /, / о) содержатся в множестве А по определению графа Пойа. Ik удовлетворяют условиям леммы, транспозиция ( / о, Ik) раскладывается в произведение остальных транспозиций этой последовательности. [31]
Но тогда, по доказанной выше лемме, транспозиция ( /, /) раскладывается в произведение этих транспозиций из А. Поскольку вершины /, / выбраны произвольно, отсюда получаем, что любая транспозиция из Тп раскладывается в произведение транспозиций из А. Так как Тп порождает Sn, то А является системой образующих этой группы. Предположим теперь, что граф Пойа множества А несвязан. [32]
Для этого сначала покажем, что любую подстановку можно разложить в произведение некоторых простых подстановок, называемых циклами, а затем убедимся в том, что каждый цикл является произведением транспозиций. [33]
В Sn имеется ровно п ( п - 1) / 2 транспозиций. Любая подстановка у из SF ( X) представима в виде произведения транспозиций. Sn есть произведение транспозиций. [34]
Отсюда, согласно теореме 5.1.1, любая конечная подстановка представима в виде произведения транспозиций. Произведение черного числа транспозиций - четная подстановка, нечетного числа - - нечетная. Итак, хотя представление подстановки в виде произведения транспозиций и неоднозначно, число транспозиций, участвующих в произведении, всегда имеет одну и ту же четность. [35]
Мы ограничимся рассмотрением случая трех переменных, но наши рассуждения без труда переносятся и на случай п переменных. Если некоторая подстановка р не изменяет многочлена g 3, то любое ее представление в виде произведения транспозиций должно содержать четное число транспозиций. Если же р преобразует многочлен g3 в - из, то любое представление ее с помощью транспозиций будет содержать нечетное число транспозиций. [36]
Ясно, что способ, удлиняющий разложения, всегда приводит лишь к четному числу транспозиций. Но если мы разложим подстановку в произведение независимых циклов, то транспозиции, входящие в такое разложение, уже не будут иметь фиксированного общего элемента. Тем не менее существует способ, позволяющий для любой подстановки получать разложение заданного цикла в такое произведение транспозиций, в котором любые две транспозиции содержат заранее выбранный общий элемент. Пусть, например, мы рассматриваем цикл ( 12345) и число 0 -тот элемент, который должен входить во все транспозиции. [37]