Вы можете отметить интересные вам фрагменты текста, которые будут доступны по уникальной ссылке в адресной строке браузера.


Перестановка

Перевод
Перестановка

В комбинаторике перестано́вка — это упорядоченный набор чисел 1, 2,\ldots, n, обычно трактуемый как биекция на множестве \{ 1, 2,\ldots, n \}, которая числу i ставит соответствие i-й элемент из набора. Число n при этом называется порядком перестановки. Как синоним слову "перестановка" в этом смысле некоторые авторы используют слово расстановка.

В теории групп под перестановкой произвольного множества подразумевается биекция этого множества на себя. Как синоним слову "перестановка" в этом смысле некоторые авторы используют слово подстановка. (Другие авторы подстановкой называют наглядный способ записи перестановки.)

Содержание

Свойства

P_n=A_n^n=\frac {n!}{(n-n)!}=\frac {n!}{0!}=n!=1\cdot 2\cdot\dots\cdot n.
  • Композиция определяет операцию произведения на перестановках одного порядка: (\pi\cdot\sigma)(k) = \pi(\sigma(k)). Относительно этой операции множество перестановок порядка n образует группу, которую называют симметрической и обычно обозначают S_n.
  • Любая группа является подгруппой группы перестановок множества элементов этой группы (теорема Кэли). При этом каждый элемент a \in G сопоставляется с перестановкой \pi_a, задаваемой тождеством \pi_a(g)=a \circ g, где g — произвольный элемент группы G, а \circ — групповая операция.

Связанные определения

  • Носитель перестановки \pi\colon X\to X — это подмножество множества X, определяемое как \operatorname{supp}(\pi)=\{x\in X\mid\pi(x)\ne x\}.
  • Неподвижной точкой перестановки \pi является всякая неподвижная точка отображения \pi\colon X\to X, то есть элемент множества \{x\in X\mid\pi(x)=x\}. Множество всех неподвижных точек перестановки \pi является дополнением её носителя в X.
  • Инверсией в перестановке \pi порядка n называется всякая пара индексов i, j такая, что 1\leqslant i<j\leqslant n и \pi(i)>\pi(j). Чётность числа инверсий в перестановке определяет чётность перестановки.
  • Знак перестановки определяется как +1 для чётной перестановки и −1 для нечётной, что выражается формулой \sgn(\sigma)=(-1)^{N(\sigma)}, где N(\sigma) — количество инверсий в перестановке \sigma. Знак перестановки \sigma может быть также определен как \sgn(\sigma)=(-1)^m, где m — количество транспозиций в разложении \sigma в произведение транспозиций. Несмотря на то, что такое разложение не единственно, чётность количества транспозиций во всех разложениях \sigma одна и та же, и поэтому знак перестановки корректно определён.

Специальные типы перестановок

  • Инволюция — перестановка \tau, которая является обратной самой себе, то есть \tau\cdot\tau=id.
  • Беспорядок — перестановка без неподвижных точек.
  • Циклом длины \ell называется такая подстановка \pi, которая тождественна на всём множестве X, кроме подмножества \{x_1,x_2,\dots,x_\ell\}\subset X и \pi(x_\ell)=x_1, \pi(x_i)=x_{i+1}. Обозначается (x_1,x_2,\dots,x_\ell).
  • Транспозиция — перестановка элементов множества X, которая меняет местами два элемента. Транспозиция является циклом длины 2.

Подстановки и произведения циклов

Перестановка \pi множества X может быть записана в виде подстановки, например:

\begin{pmatrix} 
x_1 & x_2 & x_3 & \dots & x_n \\ 
y_1 & y_2 & y_3 & \dots & y_n\end{pmatrix},

где \{x_1,\dots, x_n\}=\{y_1,\dots, y_n\}=X и \pi(x_i)=y_i.

Перестановку также можно записать в виде произведения непересекающихся циклов, причём единственным образом с точностью до порядка следования циклов в произведении. Например:

(1, 5, 2)(3, 6)(4)=\begin{pmatrix} 
1 & 2 & 3 & 4 & 5 & 6 \\ 
5 & 1 & 6 & 4 & 2 & 3\end{pmatrix}.

Перестановки с повторением

Рассмотрим n элементов m различных типов, причем в каждом типе все элементы одинаковы. Тогда перестановки из всех этих элементов с точностью до порядка следования однотипных элементов называются перестановками с повторением. Если ki — количество элементов i-го типа, то k_1+k_2+\dots+k_m=n и количество всевозможных перестановок с повторениями равно мультиномиальному коэффициенту \textstyle \binom{n}{k_1,\ k_2,\ \dots,\ k_m} = \frac{n!}{k_1!k_2!\dots k_m!}.

Случайная перестановка

Случайной перестановкой называется случайный вектор \xi=(\xi_1, \ldots , \xi_n), все элементы которого принимают натуральные значения от 1 до n, и при этом вероятность совпадения любых двух элементов равна 0.

Независимой случайной перестановкой называется такая случайная перестановка \xi, для которой

P\{\xi=\sigma\}=\frac{p_{1\sigma(1)}\ldots p_{n\sigma(n)}}{\sum\limits_{\pi \in S_n}p_{1\pi(1)}\ldots p_{n\pi(n)}}

для некоторых p_{ij}, таких что

\forall i (1\leqslant i \leqslant n): p_{i1}+\ldots + p_{in}=1
\sum\limits_{\pi \in S_n}p_{1\pi(1)}\ldots p_{n\pi(n)}>0.

Если при этом p_{ij} не зависят от i, то перестановку \xi называют одинаково распределённой. Если же нет зависимости от j, то есть \scriptstyle \forall i,j (1\le i,j \le n): p_{ij}=1/n, то \xi называют однородной.

См. также

Примечания

  1. Виленкин Н.Я. Глава III. Комбинаторика кортежей и множеств. Размещения с повторениями // Популярная комбинаторика. — М.: Наука, 1975. — С. 80. — 208 с.
  2. Теория конфигураций и теория перечислений
  3. Глава 3. Элементы комбинаторики. // Лекции по теории вероятностей.
  4. Дональд Э. Кнут — Искусство программирования. Том 1. Основные алгоритмы. 1.2.5. Перестановки и факториалы

Литература

  • Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0

Ссылки


Wikimedia Foundation. 2010.

Синонимы:

См. также в других словарях:

  • ПЕРЕСТАНОВКА — ПЕРЕСТАНОВКА, перестановки, жен. 1. только ед. Действие по гл. переставить переставлять. Перестановка мебели. Перестановка слов в предложении. Перестановка классовых сил. 2. только ед. Результат этого действия. В комнате полная перестановка. 3.… …   Толковый словарь Ушакова

  • перестановка — изменение, переключение, коммутация, транспозиция, перемещение, перегруппировка, коммутирование; передвижение, перекомпоновка, передислокация, метатеза, гипертеза, смешивание, движение, анаграмма, перетаскивание Словарь русских синонимов.… …   Словарь синонимов

  • Перестановка — криптографическая операция, связанная с изменением порядка следования отдельных битов или символов в блоке данных. По английски: Permutation См. также: Шифры Криптографические алгоритмы Финансовый словарь Финам …   Финансовый словарь

  • ПЕРЕСТАНОВКА — в математике, см. Комбинаторика …   Большой Энциклопедический словарь

  • перестановка — ПЕРЕСТАВИТЬ, влю, вишь; вленный; сов., кого что. Поставить на другое место; поменять местами. П. стул. П. мебель. П. слагаемые. Толковый словарь Ожегова. С.И. Ожегов, Н.Ю. Шведова. 1949 1992 …   Толковый словарь Ожегова

  • ПЕРЕСТАНОВКА — из пэлементов конечная последовательность длины п, все элементы к рой различны, т. е. П. это размещение без повторения из пэлементов по п. Число перестановок равно п! Обычно в качестве элементов П. берут элементы множества Zn={1, 2, . ..,… …   Математическая энциклопедия

  • перестановка — ПЕРЕСТАНО/ВКА и; мн. род. вок, дат. вкам; ж. 1. Изменение расстановки, расположения чего л. П. мебели. // Изменение порядка следования кого , чего л., замена одного другим. П. слов в предложении. От перестановки слагаемых сумма не меняется. 2.… …   Энциклопедический словарь

  • перестановка — 1. Изменение расположения (порядка следования) языковых элементов в ПЯ по сравнению с ИЯ. 2. Грамматические трансформации при переводе, к которым прибегают из за расхождения в лексико семантической сочетаемости систем двух языков ПЯ и ИЯ. 3.… …   Толковый переводоведческий словарь

  • перестановка — information security eng.permutation rus.перестановка ukr.переставляння Криптографическая операция, связанная с изменением порядка следования отдельных битов или символов в блоке данных …   English-Russian dictionary of information security

  • Перестановка —         n элементов, расположение этих элементов в каком либо порядке. Всего существует n! = 1•2•...•n различных П. из n элементов. См. Комбинаторика, Подстановка, Соединения …   Большая советская энциклопедия

Фильмы

  • Соло трубы., 1986 — Фильм о семье старых большевиков Федотовых, их сыне Льве, одаренном в искусстве, науке.

Книги

Другие книги по запросу «Перестановка» >>