Спирина, М.С. Дискретная математика

Следствие. Одна инверсия меняет знак подстановки и знак функции е(о). Любая перемена сг, и а, местами называется транспозицией. Оче­ видно, что инверсия — частный случай транспозиции. Поэтому нечетное „ меняет „ — число транспозиции метное не мен ет знак подстановки. При­ ведем о из задачи 13 к единичной подстановке с помощью транс­ позиций: Г1 2 3 4 5 6> Г1 2 3 4 5 6 ] Г1 2 3 4 5 6А о = 6 4 3 1 2 5, — - ----3 к\ 4 3 6 2 5 , — -— > J 2 3 6 4 5 , з , Г1 2 3 4 5 6^ 4 v ( \ 2 3 4 5 6^ [ l 2 3 4 6 5 j [ l 2 3 4 5 6 ) В этом случае четное число транспозиций (л = 4) также приво­ дит к четной подстановке. Отсюда видно, что с помощью транс­ позиций находить четность проще. Следствие. Число четных и нечетных подстановок п -й степени одинаково и равно п \ / 2. Подстановки тесно связаны с одним из самых общих высоко­ абстрактных разделов математики — с теорией групп. Этот р а з ­ дел математики дал возможность осуществить перенос фунда­ ментальных базовых выводов теории множеств на отдельные множества, обладающие иной природой, но по своим свойствам схожих между собой. В частности, дискретная симметрия в п ри ­ роде описывается различными подмножествами множества всех подстановок S2 х S2 х Sn х Рассмотрим симметричное отношение R. Симметричность означает, что, если в выражение xRy с произвольными х, у вместо х вставить у, а вместо у — х, то отношение также будет выполняться: xRy = yRx. Это означает, что выражение xRy инвариантно (не меняет своего значения) относительно подстановки \У Аналогично будем называть выражение F( x{, х2, ..., х„) симметричным по своим переменным, если любая подстановка а е Sn оставляет значение F неизмен­ ным: F(xu х2, ..., х„) = F(xoU), х0(2), ..., хо(п)). Например, числовое выражение / ’ = x3 + y3 + z3 - 5 ( x + y + z) симметрично по х, у, z. Также выражение может быть симметрично по некоторым из сво ­ их переменных. В настоящее время подстановки и композиции находят широкое при­ менение в теории алгоритмов. Так, российский математик А.А. Марков (1903— 1979) использовал систему допустимых подстановок для формализации понятия «алгоритм», что служит универсальным методом переработки информации. 59