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

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

18.12.2020

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

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

Термин перестановка возник потому, что сначала брались объекты, каким-то образом расставленные, а другие способы упорядочения требовали переставить эти объекты. .

Свойства

  • Число всех перестановок из n {displaystyle n} элементов равно числу размещений из n по n, то есть факториалу:
P n = A n n = 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 элементов образует группу, которую называют симметрической и обычно обозначают S n {displaystyle S_{n}} .
  • Любая конечная группа из n элементов изоморфна некоторой подгруппе симметрической группы S n {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 X o X} — это подмножество множества X {displaystyle X} , определяемое как supp ⁡ ( π ) := { x ∈ X ∣ π ( x ) ≠ x } . {displaystyle operatorname {supp} (pi ):={xin Xmid pi (x) eq x}.}
  • Неподвижной точкой перестановки π {displaystyle pi } является всякая неподвижная точка отображения π : X → X {displaystyle pi colon X o 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 au ,} которая является обратной самой себе, то есть τ ⋅ τ = e . {displaystyle au cdot au =e.}
  • Беспорядок — перестановка без неподвижных точек.
  • Циклом длины ℓ {displaystyle ell } называется такая подстановка π , {displaystyle pi ,} которая тождественна на всём множестве X , {displaystyle X,} кроме подмножества { x 1 , x 2 , … , x ℓ } ⊂ X {displaystyle {x_{1},x_{2},dots ,x_{ell }}subset X} и π ( x ℓ ) = x 1 , π ( x i ) = x i + 1 . {displaystyle pi (x_{ell })=x_{1},pi (x_{i})=x_{i+1}.} Обозначается ( x 1 , x 2 , … , x ℓ ) . {displaystyle (x_{1},x_{2},dots ,x_{ell }).} .
  • Транспозиция — перестановка элементов множества X {displaystyle X} , которая меняет местами два элемента. Транспозиция является циклом длины 2.

Подстановка

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

( x 1 x 2 x 3 … x n y 1 y 2 y 3 … y n ) , {displaystyle {egin{pmatrix}x_{1}&x_{2}&x_{3}&dots &x_{n}y_{1}&y_{2}&y_{3}&dots &y_{n}end{pmatrix}},}

где { x 1 , … , x n } = { y 1 , … , y n } = X {displaystyle {x_{1},dots ,x_{n}}={y_{1},dots ,y_{n}}=X} и π ( x i ) = y i . {displaystyle pi (x_{i})=y_{i}.}

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

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

( 1 2 3 4 5 6 5 1 6 4 2 3 ) = ( 1 , 5 , 2 ) ( 3 , 6 ) . {displaystyle {egin{pmatrix}1&2&3&4&5&65&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)} . Количество циклов разной длины, а именно набор чисел ( c 1 , c 2 , … ) {displaystyle (c_{1},c_{2},dots )} , где c ℓ {displaystyle c_{ell }} — это количество циклов длины ℓ {displaystyle ell } , определяет цикловую структуру перестановки. При этом величина 1 ⋅ c 1 + 2 ⋅ c 2 + … {displaystyle 1cdot c_{1}+2cdot c_{2}+dots } равна длине перестановки, а величина c 1 + c 2 + … {displaystyle c_{1}+c_{2}+dots } равна общему количеству циклов. Количество перестановок из n элементов с k циклами даётся числом Стирлинга первого рода без знака [ n k ] {displaystyle {egin{bmatrix}nkend{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} транспозиций следующим образом:

( x 1 , … , x l ) = ( x 1 , x ℓ ) ( x 1 , x ℓ − 1 ) … ( x 1 , x 2 ) . {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 различных типов, причем в каждом типе все элементы одинаковы. Тогда перестановки из всех этих элементов с точностью до порядка следования однотипных элементов называются перестановками с повторением. Если ki — количество элементов i-го типа, то k 1 + k 2 + ⋯ + k m = n {displaystyle k_{1}+k_{2}+dots +k_{m}=n} и количество всевозможных перестановок с повторениями равно мультиномиальному коэффициенту ( n k 1 ,   k 2 ,   … ,   k m ) = n ! k 1 ! k 2 ! … k m ! . {displaystyle extstyle {inom {n}{k_{1}, k_{2}, dots , k_{m}}}={frac {n!}{k_{1}!k_{2}!dots k_{m}!}}.}

Перестановку с повторениями можно также рассматривать как перестановку мультимножества { 1 k 1 , 2 k 2 , … , m k m } {displaystyle {1^{k_{1}},2^{k_{2}},dots ,m^{k_{m}}}} мощности k 1 + k 2 + ⋯ + k m = 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 { ξ = σ } = p 1 σ ( 1 ) … p n σ ( n ) ∑ π ∈ S n p 1 π ( 1 ) … p n π ( 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 i j , {displaystyle p_{ij},} таких, что

∀ i ( 1 ⩽ i ⩽ n ) : p i 1 + … + p i n = 1 {displaystyle forall i(1leqslant ileqslant n):p_{i1}+ldots +p_{in}=1} ∑ π ∈ S n p 1 π ( 1 ) … p n π ( n ) > 0. {displaystyle sum limits _{pi in S_{n}}p_{1pi (1)}ldots p_{npi (n)}>0.}

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