Rstykt

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

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

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

Свойства |

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

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.}

• 
  Композиция определяет операцию произведения на перестановках одной длины: (π⋅σ)(k)=π(σ(k)).{displaystyle (pi cdot sigma )(k)=pi (sigma (k)).} Относительно этой операции множество перестановок из n элементов образует группу, которую называют симметрической и обычно обозначают Sn{displaystyle S_{n}}.


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

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

• 
  Носитель перестановки π:X→X{displaystyle pi colon Xto X} — это подмножество множества X{displaystyle X}, определяемое как supp⁡(π):={x∈X∣π(x)≠x}.{displaystyle operatorname {supp} (pi ):={xin Xmid pi (x)neq x}.}
  


• 
  Неподвижной точкой перестановки π{displaystyle pi } является всякая неподвижная точка отображения π:X→X{displaystyle pi colon Xto X}, то есть элемент множества {x∈X∣π(x)=x}.{displaystyle {xin Xmid pi (x)=x}.} Множество всех неподвижных точек перестановки π{displaystyle pi } является дополнением её носителя в X{displaystyle X}.


• 
  Инверсией в перестановке π{displaystyle pi } называется всякая пара индексов i,j{displaystyle i,j} такая, что 1⩽i<j⩽n{displaystyle 1leqslant i<jleqslant n} и π(i)>π(j){displaystyle pi (i)>pi (j)}. Чётность числа инверсий в перестановке определяет чётность перестановки.

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

• 
  Тождественная перестановка — перестановка e,{displaystyle e,} которая каждый элемент x∈X{displaystyle xin X} отображает в себя: e(x)=x.{displaystyle e(x)=x.}
  


• 
  Инволюция — перестановка τ,{displaystyle tau ,} которая является обратной самой себе, то есть τ⋅τ=e.{displaystyle tau cdot tau =e.}
  


• 
  Беспорядок — перестановка без неподвижных точек.


• 
  Циклом длины ℓ{displaystyle ell } называется такая подстановка π,{displaystyle pi ,} которая тождественна на всём множестве X,{displaystyle X,} кроме подмножества {x1,x2,…,xℓ}⊂X{displaystyle {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}.} Обозначается (x1,x2,…,xℓ).{displaystyle (x_{1},x_{2},dots ,x_{ell }).}.


• 
  Транспозиция — перестановка элементов множества X{displaystyle X}, которая меняет местами два элемента. Транспозиция является циклом длины 2.

Подстановка |

Перестановка π{displaystyle pi } множества X{displaystyle 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}},}

где {x1,…,xn}={y1,…,yn}=X{displaystyle {x_{1},dots ,x_{n}}={y_{1},dots ,y_{n}}=X} и π(xi)=yi.{displaystyle pi (x_{i})=y_{i}.}

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

Любая перестановка π{displaystyle pi } может быть разложена в произведение (композицию) непересекающихся циклов длины ℓ⩾2{displaystyle ell geqslant 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).}

Часто также считают, что неподвижные точки перестановки представляют собой самостоятельные циклы длины 1, и дополняют ими цикловое разложение перестановки. Для приведенного выше примера таким дополненным разложением будет (1,5,2)(3,6)(4){displaystyle (1,5,2)(3,6)(4)}. Количество циклов разной длины, а именно набор чисел (c1,c2,…){displaystyle (c_{1},c_{2},dots )}, где cℓ{displaystyle c_{ell }} — это количество циклов длины ℓ{displaystyle ell }, определяет цикловую структуру перестановки. При этом величина 1⋅c1+2⋅c2+…{displaystyle 1cdot c_{1}+2cdot c_{2}+dots } равна длине перестановки, а величина c1+c2+…{displaystyle c_{1}+c_{2}+dots } равна общему количеству циклов. Количество перестановок из n элементов с k циклами даётся числом Стирлинга первого рода без знака [nk]{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.} Цикл длины ℓ⩾2{displaystyle ell geqslant 2} можно разложить в произведение ℓ−1{displaystyle ell -1} транспозиций следующим образом:

(x1,…,xl)=(x1,xℓ)(x1,xℓ−1)…(x1,x2).{displaystyle (x_{1},dots ,x_{l})=(x_{1},x_{ell })(x_{1},x_{ell -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 pi } как

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

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

Эквивалентно, знак перестановки определяется её цикловой структурой: знак перестановки π{displaystyle pi } из n{displaystyle n} элементов, состоящий из k{displaystyle k} циклов, равен

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

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

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

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

Рассмотрим n элементов m различных типов, причем в каждом типе все элементы одинаковы. Тогда перестановки из всех этих элементов с точностью до порядка следования однотипных элементов называются перестановками с повторением.
Если k_i — количество элементов i-го типа, то k1+k2+⋯+km=n{displaystyle 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}!}}.}

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

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

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

Независимой случайной перестановкой называется такая случайная перестановка ξ{displaystyle 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)}}}}

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

∀i(1⩽i⩽n):pi1+…+pin=1{displaystyle 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.}

Если при этом pij{displaystyle p_{ij}} не зависят от i{displaystyle i}, то перестановку ξ{displaystyle 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,} то ξ{displaystyle xi } называют однородной.

См. также |

• Гигантская компонента


• Сочетание


• Размещение


• Анаграмма


• Симметрическая группа


• Алгоритм Нарайаны

Примечания |

Литература |

• Дональд Кнут. Искусство программирования, том 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.