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

В комбинаторике перестано́вка — это упорядоченный набор без повторений чисел

$$


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
!



!



=
n
!
=
1
⋅
2
⋅
⋯
⋅
n
.


{\displaystyle P_{n}=A_{n}^{n}={\frac {n!}{(n-n)!}}={\frac {n!}{0!}}=n!=1\cdot 2\cdot \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 a\in G}
  

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

  $$
  
  
  
  π
  
  a
  
  
  
  
  {\displaystyle \pi _{a}}
  

  , задаваемой на элементах G тождеством

  $$
  
  
  
  π
  
  a
  
  
  (
  g
  )
  =
  a
  ∘
  g
  ,
  
  
  {\displaystyle \pi _{a}(g)=a\circ g,}
  

  где

  $$
  
  
  ∘
  
  
  {\displaystyle \circ }
  

   — групповая операция в G.

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

• Носитель перестановки
  $$
  
  
  π
  :
  X
  →
  X
  
  
  {\displaystyle \pi \colon X\to X}
  

   — это подмножество множества

  $$
  
  
  X
  
  
  {\displaystyle X}
  

  , определяемое как

  $$
  
  
  supp
  ⁡
  (
  π
  )
  :=
  {
  x
  ∈
  X
  ∣
  π
  (
  x
  )
  ≠
  x
  }
  .
  
  
  {\displaystyle \operatorname {supp} (\pi ):=\{x\in X\mid \pi (x)\neq x\}.}
  

• Неподвижной точкой перестановки
  $$
  
  
  π
  
  
  {\displaystyle \pi }
  

  является всякая неподвижная точка отображения

  $$
  
  
  π
  :
  X
  →
  X
  
  
  {\displaystyle \pi \colon X\to X}
  

  , то есть элемент множества

  $$
  
  
  {
  x
  ∈
  X
  ∣
  π
  (
  x
  )
  =
  x
  }
  .
  
  
  {\displaystyle \{x\in X\mid \pi (x)=x\}.}
  

  Множество всех неподвижных точек перестановки

  $$
  
  
  π
  
  
  {\displaystyle \pi }
  

  является дополнением её носителя в

  $$
  
  
  X
  
  
  {\displaystyle X}
  

  .

• Инверсией в перестановке
  $$
  
  
  π
  
  
  {\displaystyle \pi }
  

  называется всякая пара индексов

  $$
  
  
  i
  ,
  j
  
  
  {\displaystyle i,j}
  

  такая, что

  
  
  
  1
  ⩽
  i
  <
  j
  ⩽
  n
  
  
  {\displaystyle 1\leqslant i<j\leqslant n}
  

  и

  $$
  
  
  π
  (
  i
  )
  >
  π
  (
  j
  )
  
  
  {\displaystyle \pi (i)>\pi (j)}
  

  . Чётность числа инверсий в перестановке определяет чётность перестановки.

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

• Тождественная перестановка — перестановка
  $$
  
  
  e
  ,
  
  
  {\displaystyle e,}
  

  которая каждый элемент

  $$
  
  
  x
  ∈
  X
  
  
  {\displaystyle x\in X}
  

  отображает в себя:

  $$
  
  
  e
  (
  x
  )
  =
  x
  .
  
  
  {\displaystyle e(x)=x.}
  

• Инволюция — перестановка
  $$
  
  
  τ
  ,
  
  
  {\displaystyle \tau ,}
  

  которая является обратной самой себе, то есть

  $$
  
  
  τ
  ⋅
  τ
  =
  e
  .
  
  
  {\displaystyle \tau \cdot \tau =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 {\begin{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 {\begin{pmatrix}1&2&3&4&5&6\\5&1&6&4&2&3\end{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 1\cdot c_{1}+2\cdot c_{2}+\dots }

равна длине перестановки, а величина

$$



c

1


+

c

2


+
…


{\displaystyle c_{1}+c_{2}+\dots }

равна общему количеству циклов. Количество перестановок из n элементов с k циклами даётся числом Стирлинга первого рода без знака

$$




[



n




k



]




{\displaystyle {\begin{bmatrix}n\\k\end{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 различных типов, причем в каждом типе все элементы одинаковы. Тогда перестановки из всех этих элементов с точностью до порядка следования однотипных элементов называются перестановками с повторением.
Если k_i — количество элементов 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 \textstyle {\binom {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_{1\sigma (1)}\ldots p_{n\sigma (n)}}{\sum \limits _{\pi \in S_{n}}p_{1\pi (1)}\ldots p_{n\pi (n)}}}}

для некоторых

$$



p

i
j


,


{\displaystyle p_{ij},}

таких, что

$$


∀
i
(
1
⩽
i
⩽
n
)
:

p

i
1


+
…
+

p

i
n


=
1


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

$$



∑

π
∈

S

n





p

1
π
(
1
)


…

p

n
π
(
n
)


>
0.


{\displaystyle \sum \limits _{\pi \in S_{n}}p_{1\pi (1)}\ldots p_{n\pi (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(1\leq i,j\leq 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.