Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/s43/math/uroki/2010_2011/10mat_1011/spec/oct_02_permutations.pdf Дата изменения: Sun Sep 2 21:16:50 2012 Дата индексирования: Tue Feb 5 07:55:54 2013 Кодировка: Windows-1251 Поисковые слова: туманность андромеды

Гимназия 1543, 10-В класс, 2 октября. на множестве M называется биекция M M . Мы будем обычно рассматривать подстановки на конечных множествах. Для удобства в качестве конечного множества мощности n мы будем рассматривать диапазон 1, n. Подстановку f мы будем обозначать символом [f (1), f (2), . . . f (n)]. В силу биективности, для любой подстановки существует единственная подстановка, дающая в композиции с ней тождественную подстановку. называется подстановка, которая меняет местами некоторую пару разных чисел i и j (обозначение ij ). То есть, ij (i) = j , ij (j ) = i, остальные числа переходят в себя. называется подстановка, переставляющая некоторые числа циклически (обозначение (i0 , i1 , i2 , . . . im-1 )). При применении цикла число ik переходит в i(k+1 mod m) , остальные числа остаются на месте. подстановки f называется пара чисел i < j таких, что f (i) > f (j ). подстановки называется ч?тность числа инверсий этой подстановки. Ч?тных подстановок на неодноэлементном множестве столько же, сколько и неч?тных. Любая нетождественная подстановка может быть представлена в виде композиции циклов, множества подвижных точек которых не пересекаются. Любые два таких представления отличаются лишь порядком циклов в композиции. Любая подстановка представима в виде композиции транспозиций. Ч?тность количества транспозиций в любом таком представлении совпадает с ч?тностью подстановки. 1) Найдите композицию подстановок [2, 5, 3, 1, 4] и [4, 2, 1, 5, 3]. Изменится ли результат, если поменять подстановки местами? 2) Найдите подстановку, обратную [2, 5, 3, 1, 6, 4]. Разложите обе эти подстановки на независимые циклы. В последующих задачах речь будет идти о геометрических фигур (многоугольников и многогранников). Под самосовмещением геометрической фигуры мы понимаем движение, переводящее эту фигуру в себя. Заметим, что любое такое движение переводит вершины в вершины (более того, однозначно определяется образами вершин), задавая таким образом подстановку на множестве вершин. Поэтому каждому самосовмещению соответствует некоторая подстановка. 3) Опишите (назовите движение) и запишите в виде подстановки все самосовмещения: а) правильного треугольника; б) квадрата; в) свастики; г) правильного пятиугольника. 4) Рассмотрим правильный шестиугольник 123456. Обозначим через a осевую симметрию [165432], а через b осевую симметрию [543216]. Все ли самосовмещения шестиугольника можно получить, применяя в некоторой последовательности только эти два преобразования? 5) Сколько самосовмещений у: а) правильного n-угольника? б) правильного тетраэдра? Гимназия 1543, 10-В класс, 2 октября.
Подстановкой обратная Траспозицией Циклом Инверсией Ч?тностью Теорема о разложении подстановки на независимые циклы. Теорема о ч?тности подстановки. самосовмещениях

Подстановки и самосовмещения.

на множестве M называется биекция M M . Мы будем обычно рассматривать подстановки на конечных множествах. Для удобства в качестве конечного множества мощности n мы будем рассматривать диапазон 1, n. Подстановку f мы будем обозначать символом [f (1), f (2), . . . f (n)]. В силу биективности, для любой подстановки существует единственная подстановка, дающая в композиции с ней тождественную подстановку. называется подстановка, которая меняет местами некоторую пару разных чисел i и j (обозначение ij ). То есть, ij (i) = j , ij (j ) = i, остальные числа переходят в себя. называется подстановка, переставляющая некоторые числа циклически (обозначение (i0 , i1 , i2 , . . . im-1 )). При применении цикла число ik переходит в i(k+1 mod m) , остальные числа остаются на месте. подстановки f называется пара чисел i < j таких, что f (i) > f (j ). подстановки называется ч?тность числа инверсий этой подстановки. Ч?тных подстановок на неодноэлементном множестве столько же, сколько и неч?тных. Любая нетождественная подстановка может быть представлена в виде композиции циклов, множества подвижных точек которых не пересекаются. Любые два таких представления отличаются лишь порядком циклов в композиции. Любая подстановка представима в виде композиции транспозиций. Ч?тность количества транспозиций в любом таком представлении совпадает с ч?тностью подстановки. 1) Найдите композицию подстановок [2, 5, 3, 1, 4] и [4, 2, 1, 5, 3]. Изменится ли результат, если поменять подстановки местами? 2) Найдите подстановку, обратную [2, 5, 3, 1, 6, 4]. Разложите обе эти подстановки на независимые циклы. В последующих задачах речь будет идти о геометрических фигур (многоугольников и многогранников). Под самосовмещением геометрической фигуры мы понимаем движение, переводящее эту фигуру в себя. Заметим, что любое такое движение переводит вершины в вершины (более того, однозначно определяется образами вершин), задавая таким образом подстановку на множестве вершин. Поэтому каждому самосовмещению соответствует некоторая подстановка. 3) Опишите (назовите движение) и запишите в виде подстановки все самосовмещения: а) правильного треугольника; б) квадрата; в) свастики; г) правильного пятиугольника. 4) Рассмотрим правильный шестиугольник 123456. Обозначим через a осевую симметрию [165432], а через b осевую симметрию [543216]. Все ли самосовмещения шестиугольника можно получить, применяя в некоторой последовательности только эти два преобразования? 5) Сколько самосовмещений у: а) правильного n-угольника? б) правильного тетраэдра?
Подстановкой обратная Траспозицией Циклом Инверсией Ч?тностью Теорема о разложении подстановки на независимые циклы. Теорема о ч?тности подстановки. самосовмещениях

Подстановки и самосовмещения.