Перестановка | это... Что такое Перестановка? (original) (raw)

В комбинаторике перестано́вка — это упорядоченный набор чисел 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 множества 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. Перестановки и факториалы

Литература

Ссылки