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

Разделы:

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

6 перестановок 3 шаров

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

Содержание

1 Свойства
2 Связанные определения
3 Перестановки с повторением
4 Случайная перестановка
5 См. также
6 Примечания
7 Литература
8 Ссылки

Свойства

Число всех перестановок порядка n{displaystyle n} $n$ равно числу размещений из n по n, то есть факториалу:[1][2][3][4]

Pn=Ann=n!(n−n)!=n!0!=n!=1⋅2⋅⋯⋅n.{displaystyle P_{n}=A_{n}^{n}={frac {n!}{(n-n)!}}={frac {n!}{0!}}=n!=1cdot 2cdot dots cdot n.}

P_{n}=A_{n}^{n}={frac {n!}{(n-n)!}}={frac {n!}{0!}}=n!=1cdot 2cdot dots cdot n.

Композиция определяет операцию произведения на перестановках одного порядка: (π⋅σ)(k)=π(σ(k)).{displaystyle (pi cdot sigma )(k)=pi (sigma (k)).} $(pi cdot sigma )(k)=pi (sigma (k)).$ Относительно этой операции множество перестановок порядка n образует группу, которую называют симметрической и обычно обозначают Sn{displaystyle S_{n}} $S_{n}$ .
Любая конечная группа порядка n изоморфна некоторой подгруппе группы перестановок из n чисел (теорема Кэли). При этом каждый элемент a∈G{displaystyle ain G} $ain G$ сопоставляется с перестановкой πa{displaystyle pi _{a}} $pi _{a}$ , задаваемой тождеством πa(g)=a∘g,{displaystyle pi _{a}(g)=acirc g,} $pi _{a}(g)=acirc g,$ где g — произвольный элемент группы G, а ∘{displaystyle circ } $circ$ — групповая операция.

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

Носитель перестановки π:X→X{displaystyle pi colon Xto X} $pi colon Xto X$ — это подмножество множества X{displaystyle X} $X$ , определяемое как supp⁡(π)={x∈X∣π(x)≠x}.{displaystyle operatorname {supp} (pi )={xin Xmid pi (x)neq x}.} $operatorname {supp}(pi )={xin Xmid pi (x)neq x}.$
Неподвижной точкой перестановки π{displaystyle pi } $pi$ является всякая неподвижная точка отображения π:X→X{displaystyle pi colon Xto X} $pi colon Xto X$ , то есть элемент множества {x∈X∣π(x)=x}.{displaystyle {xin Xmid pi (x)=x}.} ${xin Xmid pi (x)=x}.$ Множество всех неподвижных точек перестановки π{displaystyle pi } $pi$ является дополнением её
носителя в X{displaystyle X} $X$ .
Инверсией в перестановке π{displaystyle pi } $pi$ порядка n называется всякая пара индексов i,j{displaystyle i,j} $i,j$ такая, что 1⩽i<j⩽n{displaystyle 1leqslant i<jleqslant n} $1leqslant i<jleqslant n$ и π(i)>π(j){displaystyle pi (i)>pi (j)} $pi (i)>pi (j)$ . Чётность числа инверсий в перестановке определяет чётность перестановки.

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

Тождественная перестановка — перестановка e,{displaystyle e,} $e,$ которая каждый элемент x∈X{displaystyle xin X} $xin X$ отображает в себя: e(x)=x.{displaystyle e(x)=x.} $e(x)=x.$
Инволюция — перестановка τ,{displaystyle tau ,} $tau ,$ которая является обратной самой себе, то есть τ⋅τ=e.{displaystyle tau cdot tau =e.} $tau cdot tau =e.$
Беспорядок — перестановка без неподвижных точек.
Циклом длины ℓ{displaystyle ell } $ell$ называется такая подстановка π,{displaystyle pi ,} $pi ,$ которая тождественна на всём множестве X,{displaystyle X,} $X,$ кроме подмножества {x1,x2,…,xℓ}⊂X{displaystyle {x_{1},x_{2},dots ,x_{ell }}subset X} ${x_{1},x_{2},dots ,x_{ell }}subset X$ и π(xℓ)=x1,π(xi)=xi+1.{displaystyle pi (x_{ell })=x_{1},pi (x_{i})=x_{i+1}.} $pi (x_{ell })=x_{1},pi (x_{i})=x_{{i+1}}.$ Обозначается (x1,x2,…,xℓ).{displaystyle (x_{1},x_{2},dots ,x_{ell }).} $(x_{1},x_{2},dots ,x_{ell }).$ . Число перестановок, содержащих k циклов, — есть числа Стирлинга первого рода
Транспозиция — перестановка элементов множес
тва X{displaystyle X} $X$ , которая меняет местами два элемента. Транспозиция является циклом длины 2.

Подстановка

Перестановка π{displaystyle pi }

$pi$ множества X{displaystyle X} $X$ может быть записана в виде подстановки, например:

(x1x2x3…xny1y2y3…yn),{displaystyle {begin{pmatrix}x_{1}&x_{2}&x_{3}&dots &x_{n}\y_{1}&y_{2}&y_{3}&dots &y_{n}end{pmatrix}},}

{begin{pmatrix}x_{1}&x_{2}&x_{3}&dots &x_{n}\y_{1}&y_{2}&y_{3}&dots &y_{n}end{pmatrix}},

где {x1,…,xn}={y1,…,yn}=X{displaystyle {x_{1},dots ,x_{n}}={y_{1},dots ,y_{n}}=X}

${x_{1},dots ,x_{n}}={y_{1},dots ,y_{n}}=X$ и π(xi)=yi.{displaystyle pi (x_{i})=y_{i}.} $pi (x_{i})=y_{i}.$

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

Любая перестановка π{displaystyle pi }

$pi$ может быть разложена в произведение (композицию) непересекающихся циклов длины l⩾2{displaystyle lgeqslant 2} $lgeqslant 2$ , причём единственным образом с точностью до порядка следования циклов в произведении. Например:

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

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

Часто считают, что неподвижные точки перестановки представляют собой самостоятельные циклы длины 1, и дополняют ими цикловое разложение перестановки. Для приведенного выше примера таким дополненным разложением будет (1,5,2)(3,6)(4){displaystyle (1,5,2)(3,6)(4)}

${displaystyle (1,5,2)(3,6)(4)}$ . Количество циклов разной длины, а именно набор чисел c1,c2,…{displaystyle c_{1},c_{2},dots } ${displaystyle c_{1},c_{2},dots }$ , где cl{displaystyle c_{l}} ${displaystyle c_{l}}$ — это количество циклов длины l{displaystyle l} $l$ , определяет цикловую структуру перестановки. При этом величина 1⋅c1+2⋅c2+…{displaystyle 1cdot c_{1}+2cdot c_{2}+dots } ${displaystyle 1cdot c_{1}+2cdot c_{2}+dots }$ равна порядку перестановки, а величина c1+c2+…{displaystyle c_{1}+c_{2}+dots } ${displaystyle c_{1}+c_{2}+dots }$ равна общему количеству циклов. Количество перестановок порядка n с k циклами даётся числом Стирлинга первого рода без знака [nk]{displaystyle {begin{bmatrix}n\kend{bmatrix}}} ${displaystyle {begin{bmatrix}n\kend{bmatrix}}}$ .

Любой цикл может быть разложен в произведение (не обязательно непересекающихся) транспозиций. При этом цикл длины 1 (являющийся по сути тождественной перестановкой
e) можно представить как шаблон не поддерживает такой синтаксис транспозиций или, например, как квадрат любой транспозиции: (1,2)(1,2)=(2,3)(2,3)=e.{displaystyle (1,2)(1,2)=(2,3)(2,3)=e.}

$(1,2)(1,2)=(2,3)(2,3)=e.$ Цикл длины l⩾2{displaystyle lgeqslant 2} $lgeqslant 2$ можно разложить в произведение l−1{displaystyle l-1} ${displaystyle l-1}$ транспозиций следующим образом:

(x1,…,xl)=(x1,xl)(x1,xl−1)…(x1,x2).{displaystyle (x_{1},dots ,x_{l})=(x_{1},x_{l})(x_{1},x_{l-1})dots (x_{1},x_{2}).}

(x_{1},dots ,x_{l})=(x_{1},x_{l})(x_{1},x_{{l-1}})dots (x_{1},x_{2}).

Следует заметить, что разложение циклов на произведение транспозиций не является единственным:

(1,2,3)=(1,3)(1,2)=(2,3)(1,3)=(1,3)(2,4)(2,4)(1,2).{displaystyle (1,2,3)=(1,3)(1,2)=(2,3)(1,3)=(1,3)(2,4)(2,4)(1,2).}

{displaystyle (1,2,3)=(1,3)(1,2)=(2,3)(1,3)=(1,3)(2,4)(2,4)(1,2).}

Таким образом, любая перестановка может быть разложена в произведение транспозиций. Хотя это можно сделать многими способами, чётность количества транспозиций во всех таких разложениях одинакова. Это позволяет определить знак перестановки (чётностью перестановки или сигнатурой перестановки) π{displaystyle pi }

$pi$ как

επ=(−1)t,{displaystyle varepsilon _{pi }=(-1)^{t},}

{displaystyle varepsilon _{pi }=(-1)^{t},}

где t{displaystyle t}

$t$ — количество транспозиций в каком-то разложении π{displaystyle pi } $pi$ . При этом π{displaystyle pi } $pi$ называют чётной перестановкой, если επ=1,{displaystyle varepsilon _{pi }=1,} $varepsilon _{{pi }}=1,$ и нечётной перестановкой, если επ=−1.{displaystyle varepsilon _{pi }=-1.} $varepsilon _{{pi }}=-1.$

Эквивалентно, знак перестановки π{displaystyle pi }

$pi$ можно определить через её цикловую структуру:

επ=(−1)n−k,{displaystyle varepsilon _{pi }=(-1)^{n-k},}

{displaystyle varepsilon _{pi }=(-1)^{n-k},}

где n{displaystyle n}

$n$ — порядок перестановки π{displaystyle pi } $pi$ , а k=c1+c2+⋯+cn{displaystyle k=c_{1}+c_{2}+dots +c_{n}} ${displaystyle k=c_{1}+c_{2}+dots +c_{n}}$ — количество циклов в ней.

Знак перестановки π{displaystyle pi }

$pi$ также может быть определен через количество инверсий N(π){displaystyle N(pi )} $N(pi )$ в π{displaystyle pi } $pi$ :

επ=(−1)N(π).{displaystyle varepsilon _{pi }=(-1)^{N(pi )}.}

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

Рассмотрим n элементов m различных типов, причем в каждом типе все элементы одинаковы. Тогда перестановки из всех этих элементов с точностью до порядка следования однотипных элементов называются перестановками с повторением.Если ki — количество элементов i-го типа, то k1+k2+⋯+km=n{displaystyle k_{1}+k_{2}+dots +k_{m}=n}

$k_{1}+k_{2}+dots +k_{m}=n$ и количество всевозможных перестановок с повторениями равно мультиномиальному коэффициенту (nk1, k2, …, km)=n!k1!k2!…km!.{displaystyle textstyle {binom {n}{k_{1}, k_{2}, dots , k_{m}}}={frac {n!}{k_{1}!k_{2}!dots k_{m}!}}.} $textstyle {binom {n}{k_{1}, k_{2}, dots , k_{m}}}={frac {n!}{k_{1}!k_{2}!dots k_{m}!}}.$

Перестановку с повторениями можно также рассматривать как перестановку мультимножества {1k1,2k2,…,mkm}{displaystyle {1^{k_{1}},2^{k_{2}},dots ,m^{k_{m}}}}

${displaystyle {1^{k_{1}},2^{k_{2}},dots ,m^{k_{m}}}}$ мощности k1+k2+⋯+km=n{displaystyle k_{1}+k_{2}+dots +k_{m}=n} $k_{1}+k_{2}+dots +k_{m}=n$ .

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

Основная статья: Случайные перестановки

Случайной перестановкой называетсяслучайный вектор ξ=(ξ1,…,ξn),{displaystyle xi =(xi _{1},ldots ,xi _{n}),}

$xi =(xi _{1},ldots ,xi _{n}),$ все элементы которого принимают натуральные значения от 1 до n,{displaystyle n,} $n,$ и при этом вероятность совпадения любых двух элементов равна 0.

Независимой случайной перестановкой называется такая случайная перестановка ξ{displaystyle xi }

$xi$ , для которой

P{ξ=σ}=p1σ(1)…pnσ(n)∑π∈Snp1π(1)…pnπ(n){displaystyle P{xi =sigma }={frac {p_{1sigma (1)}ldots p_{nsigma (n)}}{sum limits _{pi in S_{n}}p_{1pi (1)}ldots p_{npi (n)}}}}

P{xi =sigma }={frac {p_{{1sigma (1)}}ldots p_{{nsigma (n)}}}{sum limits _{{pi in S_{n}}}p_{{1pi (1)}}ldots p_{{npi (n)}}}}

для некоторых pij,{displaystyle p_{ij},}

$p_{{ij}},$ таких что

∀i(1⩽i⩽n):pi1+…+pin=1{displaystyle forall i(1leqslant ileqslant n):p_{i1}+ldots +p_{in}=1}

forall i(1leqslant ileqslant n):p_{{i1}}+ldots +p_{{in}}=1

∑π∈Snp1π(1)…pnπ(n)>0.{displaystyle sum limits _{pi in S_{n}}p_{1pi (1)}ldots p_{npi (n)}>0.}

sum limits _{{pi in S_{n}}}p_{{1pi (1)}}ldots p_{{npi (n)}}>0.

Если при этом pij{displaystyle p_{ij}}

$p_{{ij}}$ не зависят от i{displaystyle i} $i$ , то перестановку ξ{displaystyle xi } $xi$ называют одинаково распределённой. Если же нет зависимости от j{displaystyle j} , то есть ∀i,j(1≤i,j≤n):pij=1/n,{displaystyle scriptstyle forall i,j(1leq i,jleq n):p_{ij}=1/n,} $scriptstyle forall i,j(1leq i,jleq n):p_{{ij}}=1/n,$ то ξ{displaystyle xi } $xi$ называют однородной.

См. также

Примечания

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

Литература

Дональд Кнут. Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0.
Кострикин А. И. Введение в алгебру. Основы алгебры.. — М.: Физматлит, 1994. — С. 59-71. — 320 с. — ISBN 5-02-014644-7.
Сергей Мельников. Перестановки, сочетания, размещения: вывод всех перестановок // Delphi и Turbo Pascal на занимательных примерах. — БХВ-Петербург, 2012. — 448 с. — ISBN 978-5-94157-886-3.

Ссылки

Аранжеман // Энциклопедический словарь Брокгауза и Ефрона : в 86 т. (82 т. и 4 доп.). — СПб., 1890—1907.