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

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




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 различных типов, причем в каждом типе все элементы одинаковы. Тогда перестановки из всех этих элементов с точностью до порядка следования однотипных элементов называются перестановками с повторением.
Если 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 \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.

Error: 404 Not Found.

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

Поделиться ссылкой:

Смотреть:
722 год