42
правки
Изменения
Новая страница: «=Умножение перестановок= {{Определение |definition= Умножением (композицией) перестановок назы…»
=Умножение перестановок=
{{Определение
|definition=
Умножением (композицией) перестановок называется перестановка, получающаяся по следующему правилу:
<tex> (a \circ b)_i = a_{b_i} </tex>
}}
{{Утверждение
|statement=
Умножение перестановок ассоциативно:
<tex> (a \circ (b \circ c))_i = ((a \circ b) \circ c)_i </tex>
|proof=
Доказывается простым раскрытием скобок.
# <tex> (a \circ (b \circ c))_i = a_{(b \circ c)_i} = a_{b_{c_i}} </tex>
# <tex> ((a \circ b) \circ c)_i = (a \circ b)_{c_i} = a_{b_{c_i}} </tex>
}}
==Пример==
<tex dpi="130"> a = {{1, 2, 3, 4, 5, 6} \choose {2, 5, 6, 3, 1, 4}},
b = {{1, 2, 3, 4, 5, 6} \choose {4, 1, 3, 6, 5, 2}} </tex>
<tex dpi="130"> {{1, 2, 3, 4, 5, 6} \choose {2, 5, 6, 3, 1, 4}} \circ {{1, 2, 3, 4, 5, 6} \choose {4, 1, 3, 6, 5, 2}} =
{{4, 1, 3, 6, 5, 2} \choose {3, 2, 6, 4, 1, 5}} \circ {{1, 2, 3, 4, 5, 6} \choose {4, 1, 3, 6, 5, 2}} =
{{1, 2, 3, 4, 5, 6} \choose {3, 2, 6, 4, 1, 5}}
</tex>
=Обратная перестановка=
{{Определение
|definition=
Обратной перестановкой <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что:
<tex> (a^{-1} \circ a)_i = (a \circ a^{-1})_i = i </tex>
}}
При представлении перестановки в виде циклов обратную перестановку можно легко получить, инвертировав все ребра в циклах.
<tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex>
=Группа перестановок=
{{Определение
|definition=
Группа - алгебраическая структура, удовлетворяющая следующим свойствам:
Пусть <tex> M </tex> - множество, <tex> M = \{ x, y, z, ... \} </tex>, и на этом множестве задана бинарная операция <tex> \circ </tex>, такая, что <tex> \forall x, y \in M: x \circ y = z \in M </tex>.
Тогда для группы выполняются:
# <tex> (g_1 \circ g_2) \circ g_3 = g_1 \circ (g_2 \circ g_3) </tex> - ассоциативность соответствующей бинарной операции.
# Существование нейтрального элемента <tex> e </tex> относительно <tex> \circ </tex>: <tex> \forall g \in M: g \circ e = e \circ g = g </tex>
# Существование обратного элемента <tex> g^{-1} </tex> : <tex> \forall g \in M: \exists g^{-1} \in M: g \circ g^{-1} = g^{-1} \circ g = e </tex>
}}
{{Утверждение
|statement=
Множество перестановок с <tex> n </tex> элементами с операцией умножения является группой (часто группу перестановок называют симметрической, и обозначают <tex> S_n </tex>).
|proof=
Свойства 1 и 3 выполняются уже по пунктам 1 и 2 выше, а в качестве нейтрального элемента можно брать тождественную перестановку (<tex> \pi_i = i </tex>).
}}
[[Теорема Кэли]] утверждает, что любая конечная группа изоморфна подгруппе соответствующей группе перестановок.
{{Определение
|definition=
Умножением (композицией) перестановок называется перестановка, получающаяся по следующему правилу:
<tex> (a \circ b)_i = a_{b_i} </tex>
}}
{{Утверждение
|statement=
Умножение перестановок ассоциативно:
<tex> (a \circ (b \circ c))_i = ((a \circ b) \circ c)_i </tex>
|proof=
Доказывается простым раскрытием скобок.
# <tex> (a \circ (b \circ c))_i = a_{(b \circ c)_i} = a_{b_{c_i}} </tex>
# <tex> ((a \circ b) \circ c)_i = (a \circ b)_{c_i} = a_{b_{c_i}} </tex>
}}
==Пример==
<tex dpi="130"> a = {{1, 2, 3, 4, 5, 6} \choose {2, 5, 6, 3, 1, 4}},
b = {{1, 2, 3, 4, 5, 6} \choose {4, 1, 3, 6, 5, 2}} </tex>
<tex dpi="130"> {{1, 2, 3, 4, 5, 6} \choose {2, 5, 6, 3, 1, 4}} \circ {{1, 2, 3, 4, 5, 6} \choose {4, 1, 3, 6, 5, 2}} =
{{4, 1, 3, 6, 5, 2} \choose {3, 2, 6, 4, 1, 5}} \circ {{1, 2, 3, 4, 5, 6} \choose {4, 1, 3, 6, 5, 2}} =
{{1, 2, 3, 4, 5, 6} \choose {3, 2, 6, 4, 1, 5}}
</tex>
=Обратная перестановка=
{{Определение
|definition=
Обратной перестановкой <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что:
<tex> (a^{-1} \circ a)_i = (a \circ a^{-1})_i = i </tex>
}}
При представлении перестановки в виде циклов обратную перестановку можно легко получить, инвертировав все ребра в циклах.
<tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex>
=Группа перестановок=
{{Определение
|definition=
Группа - алгебраическая структура, удовлетворяющая следующим свойствам:
Пусть <tex> M </tex> - множество, <tex> M = \{ x, y, z, ... \} </tex>, и на этом множестве задана бинарная операция <tex> \circ </tex>, такая, что <tex> \forall x, y \in M: x \circ y = z \in M </tex>.
Тогда для группы выполняются:
# <tex> (g_1 \circ g_2) \circ g_3 = g_1 \circ (g_2 \circ g_3) </tex> - ассоциативность соответствующей бинарной операции.
# Существование нейтрального элемента <tex> e </tex> относительно <tex> \circ </tex>: <tex> \forall g \in M: g \circ e = e \circ g = g </tex>
# Существование обратного элемента <tex> g^{-1} </tex> : <tex> \forall g \in M: \exists g^{-1} \in M: g \circ g^{-1} = g^{-1} \circ g = e </tex>
}}
{{Утверждение
|statement=
Множество перестановок с <tex> n </tex> элементами с операцией умножения является группой (часто группу перестановок называют симметрической, и обозначают <tex> S_n </tex>).
|proof=
Свойства 1 и 3 выполняются уже по пунктам 1 и 2 выше, а в качестве нейтрального элемента можно брать тождественную перестановку (<tex> \pi_i = i </tex>).
}}
[[Теорема Кэли]] утверждает, что любая конечная группа изоморфна подгруппе соответствующей группе перестановок.
