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

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

Перестановка nn объектов — способ последовательного расположения этих объектов с учётом их порядка.

Например, все возможные перестановки 33 объектов a,b,ca, b, c:

abc,acb,bac,bca,cab,cbaabc, \quad acb, \quad bac, \quad bca, \quad cab, \quad cba

Количество всевозможных перестановок nn объектов — факториал числа nn

n!   ⁣=def   ⁣n⋅(n−1)⋅(n−2)⋅(n−3)⋯3⋅2⋅1=∏k=1nkn! \defeq n \cdot (n-1) \cdot (n-2) \cdot (n-3) \dotsb 3 \cdot 2 \cdot 1 = \prod\limits_{k=1}^n k

При этом 0!=10! = 1, ведь есть только один способ расположить 00 объектов — никак.

Получаем рекуррентное тождество, справедливое для всех целых n⩾1n \ge 1

n!=n⋅(n−1)!n! = n \cdot (n-1)!

Автоморфизмы множеств

Перестановки переставляют объекты. Давайте формализуем этот процесс перестанавливания объектов. Каждую перестановку элементов множества SS можно задать с помощью правила, которое говорит, на место какого элемента перешёл какой элемент. Получается, что перестановка задаётся каким-то отображением S→SS \to S, при этом понятно, что это отображение должно иметь какие-то дополнительные свойства.

Возьмём какое-то множество SS. Эндоморфизм множества SS — отображение f ⁣:S→Sf \colon S \to S множества SS на себя.

Эндоморфизмы можно итерировать. Итерация эндоморфизма ff — композиционная степень ff

fn=f∘f∘f∘⋯∘f⏟n разf^n = \underbrace{f \compose f \compose f \compose \dotsb \compose f}_{n ~\text{раз}}

Итерации одного множества коммутируют

fn∘fm=fm∘fn=fn+mf^n \compose f^m = f^m \compose f^n = f^{n+m}

Для любого эндоморфизма f ⁣:S→Sf \colon S \to S конечного множества SS найдутся два неравных числа nn и mm таких, что

∀ x∈Sfn(x)=fm(x)\forall\, x \in S \? f^n (x) = f^m (x)

Автоморфизм множества SS — обратимый эндоморфизм множества SS, или, другими словами, биекция S↔SS \bijto S множества SS на себя.

Автоморфизмы тоже можно итерировать, потому что это эндоморфизмы. Но итерации автоморфизмов не могут «сжать» множество SS, то есть если ff — автоморфизм SS, то f[S]=Sf[S] = S.

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

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

Перестановка множества SS — автоморфизм SS. В переводе с пришельского на русский, перестановка — это переупорядочивание элементов множества SS. Это переупорядочивание, а также сама перестановка, записываются как

σ=(a1a2a3⋯an−1anb1b2b3⋯bn−1bn)\sigma = \pmatrix{a_1 & a_2 & a_3 & \cdots & a_{n-1} & a_n \\ b_1 & b_2 & b_3 & \cdots & b_{n-1} & b_n}

Эта запись означает, что при автоморфизме σ\sigma

a1↦b1a2↦b2a3↦b3⋯an−1↦bn−1an↦bna_1 \mapsto b_1 \quad a_2 \mapsto b_2 \quad a_3 \mapsto b_3 \quad \cdots \quad a_{n-1} \mapsto b_{n-1} \quad a_n \mapsto b_n

Обычно элементы в записи перестановки превращают в цифры и сортируют первую строку. Получается вот так

σ=(123⋯n−1nσ(1)σ(2)σ(3)⋯σ(n−1)σ(n))\sigma = \pmatrix{1 & 2 & 3 & \cdots & n-1 & n \\ \sigma(1) & \sigma(2) & \sigma(3) & \cdots & \sigma(n-1) & \sigma(n)}

Под действием перестановки какие-то элементы передвигаются, а какие-то, возможно, остаются на месте.

Носитель перестановки

Носитель перестановки σ\sigma — множество тех объектов, которые передвигаются под действием σ\sigma. Обозначается supp⁡σ\supp \sigma.

supp⁡σ   ⁣=def   ⁣{j:σ(j)≠j}\supp \sigma \defeq \{ j : \sigma(j) \neq j \}

Композиция перестановок

Точно так же, как и для обычных отображений, для перестановок определяется операция композиции. Композиция двух перестановок σ\sigma и τ\tau — перестановка σ∘τ\sigma \compose \tau.

σ∘τ=(12⋯nσ(1)σ(2)⋯σ(n))∘(12⋯nτ(1)τ(2)⋯τ(n))=(12⋯nσ(τ(1))σ(τ(2))⋯σ(τ(n)))\sigma \compose \tau = \pmatrix{1 & 2 & \cdots & n \\ \sigma(1) & \sigma(2) & \cdots & \sigma(n)} \compose \pmatrix{1 & 2 & \cdots & n \\ \tau(1) & \tau(2) & \cdots & \tau(n)} = \pmatrix{1 & 2 & \cdots & n \\ \sigma\big(\tau(1)\big) & \sigma\big(\tau(2)\big) & \cdots & \sigma\big(\tau(n)\big)}

Обратите внимание: при композиции перестановок σ∘τ\sigma \compose \tau сначала применяется перестановка τ\tau, и только потом перестановка σ\sigma. А именно образ элемента x∈Sx \in S при перестановке σ∘τ\sigma \compose \tau равен

(σ∘τ)(x)=σ(τ(x))(\sigma \compose \tau) (x) = \sigma \bigl( \tau (x) \bigr)

Давайте разберём конкретный пример. найдём композицию перестановок

σ=(1234552134)иτ=(1234554321)\sigma = \pmatrix{1 & 2 & 3 & 4 & 5 \\ 5 & 2 & 1 & 3 & 4} \quad\text{и}\quad \tau = \pmatrix{1 & 2 & 3 & 4 & 5 \\ 5 & 4 & 3 & 2 & 1}

Композиция равна

σ∘τ=(1234552134)∘(1234554321)=(1234543125)\sigma \compose \tau = \pmatrix{1 & 2 & 3 & 4 & 5 \\ 5 & 2 & 1 & 3 & 4} \compose \pmatrix{1 & 2 & 3 & 4 & 5 \\ 5 & 4 & 3 & 2 & 1} = \pmatrix{1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 1 & 2 & 5}

Вычислял я композицию тут поочерёдно для всех элементов:

(σ∘τ)(1)=σ(τ(1))=σ(5)=4(σ∘τ)(2)=σ(τ(2))=σ(4)=3(σ∘τ)(3)=σ(τ(3))=σ(3)=1(σ∘τ)(4)=σ(τ(4))=σ(2)=2(σ∘τ)(5)=σ(τ(5))=σ(1)=5\align{ (\sigma \compose \tau) (1) &= \sigma \bigl( \tau (1) \bigr) = \sigma (5) = 4 \\ (\sigma \compose \tau) (2) &= \sigma \bigl( \tau (2) \bigr) = \sigma (4) = 3 \\ (\sigma \compose \tau) (3) &= \sigma \bigl( \tau (3) \bigr) = \sigma (3) = 1 \\ (\sigma \compose \tau) (4) &= \sigma \bigl( \tau (4) \bigr) = \sigma (2) = 2 \\ (\sigma \compose \tau) (5) &= \sigma \bigl( \tau (5) \bigr) = \sigma (1) = 5 \\ }

Свойства композиции. Композиция перестановок ассоциативна, но не коммутативна

σ∘(τ∘ρ)=(σ∘τ)∘ρиσ∘τ≠τ∘σ\sigma \compose (\tau \compose \rho) = (\sigma \compose \tau) \compose \rho \qquad\text{и}\qquad \sigma \compose \tau \neq \tau \compose \sigma

Ассоциативность перестановок следует из ассоциативности композиции обычных отображений, а некоммутативность можно доказать простым контрпримером

(123213)∘(123132)=(123231)но(123132)∘(123213)=(123312)\pmatrix{1 & 2 & 3 \\ 2 & 1 & 3} \compose \pmatrix{1 & 2 & 3 \\ 1 & 3 & 2} = \pmatrix{1 & 2 & 3 \\ 2 & 3 & 1} \quad\text{но}\quad \pmatrix{1 & 2 & 3 \\ 1 & 3 & 2} \compose \pmatrix{1 & 2 & 3 \\ 2 & 1 & 3} = \pmatrix{1 & 2 & 3 \\ 3 & 1 & 2}

Нейтральный элемент. По операции композиции есть нейтральный элемент 1\1, называемый единичной перестановкой

1=(123⋯n−1n123⋯n−1n)\1 = \pmatrix{1 & 2 & 3 & \cdots & n-1 & n \\ 1 & 2 & 3 & \cdots & n-1 & n}

Эта единичная перестановка оставляет все элементы на своих местах, по этому для любой перестановки σ\sigma выполнено равенство

σ∘1=1∘σ=σ\sigma \compose \1 = \1 \compose \sigma = \sigma

Обратная перестановка. По операции композиции перестановок для любой перестановки σ\sigma можно найти обратную перестановку σ−1\sigma^{-1}:

σ∘σ−1=σ−1∘σ=1\sigma \compose \sigma^{-1} = \sigma^{-1} \compose \sigma = \1

Можно явно построить обратную перестановку, если поменять местами строки и отсортировать столбцы. Сортировать столбцы, вообще, не обязательно, ведь сортировка нужна только для удобства восприятия.

σ−1=(σ(1)σ(2)⋯σ(n)12⋯n)\sigma^{-1} = \pmatrix{\sigma(1) & \sigma(2) & \cdots & \sigma(n) \\ 1 & 2 & \cdots & n}
type permutation = table[int: int] function inverse(permutation sigma[n]) -> permutation: permutation inverse for int i = 0; i < n; i++: inverse[sigma[i]] = i return inverse

Множество всех перестановок множества {1,2,…,n}\{1, 2, \dotsc, n\} образуют группу по композиции. Эта группа обозначается Sn\S_n и называется группой перестановок.

Поскольку количество перестановок nn элементов равно n!n!, порядок группы Sn\S_n

∣Sn∣=n!|\S_n| = n!

Инверсии

Инверсия

Пусть σ∈Sn\sigma \in \S_n — какая-то перестановка (σ1,σ2,…,σn)(\sigma_1, \sigma_2, \dotsc, \sigma_n) множества {1,2,…,n}\{1, 2, \dotsc, n\}.

Если i<ji < j и σi>σj\sigma_i > \sigma_j, то пара (σi,σj)(\sigma_i, \sigma_j) называется инверсией перестановки σ\sigma.

Например, у перестановки

σ=(1234531254)\sigma = \pmatrix{1 & 2 & 3 & 4 & 5 \\ 3 & 1 & 2 & 5 & 4}

инверсиями являются пары (3,1)(3,1), (3,2)(3, 2) и (5,4)(5, 4).

Каждая инверсия в перестановке — это пара, «нарушающая порядок». Единственная перестановка, не содержащая инверсий — перестановка 1\1.

inv⁡σ\inv \sigma — число инверсий в перестановке σ\sigma

Число инверсий в перестановке и в ей обратной одинаково: inv⁡σ=inv⁡σ−1\inv \sigma = \inv \sigma^{-1}.

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

Транспозиция

Транспозиция — перестановка в которой меняются местами только 2 элемента.

Транспозиция коротко записывается (i j)(i ~ j), то есть мы меняем местами элементы ii и jj.

Теорема о представлении перестановок

Любая перестановка может быть представлена как композиция транспозиций.

Поместим сначала на первую позицию тот элемент, который там должен стоять, и больше не будем его трогать. Затем на вторую позицию тот элемент, который там должен быть, и так далее, пока все элементы не встанут на свои места.

Можем уточнить количество транспозиций: не более n−1n-1, ведь мы по очереди ставим nn элементов на свои места, а последний элемент встает на место вместе с предпоследним.

Чётность перестановки

Перестановка чётная, если она представляется как произведение чётного числа транспозиций, и нечётная, если она представляется нечётным числом транспозиций.

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

Произведение перестановок одинаковой чётности – чётная перестановка, а разной чётности – нечётная. Обратная перестановка имеет ту же самую чётность, что и исходная.

У перестановок, как у элементов группы перестановок, есть порядок.

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

Порядок перестановки σ\sigma — наименьшая степень перестановки, которая превращает её в тождественную

ord⁡σ=min⁡ {n∈N0:σn=1}\ord \sigma = \min\limits~ \{ n \in \NN_0 : \sigma^n = \1 \}

Это определение полностью совпадает с определением порядка элемента в группе.

Пусть перестановка σ\sigma представлена как композиция двух перестановок τ1\tau_1 и τ2\tau_2 с непересекающимися носителями:

σ=τ1∘τ2где supp⁡τ1∩supp⁡τ2=∅\sigma = \tau_1 \compose \tau_2 \quad\text{где}~ \supp \tau_1 \sect \supp \tau_2 = \nothing

Давайте поймём, как получается порядок перестановки.

Пусть σ∈Sn\sigma \in \S_n — какая-то перестановка nn элементов. Давайте посмотрим на представление этой перестановки в виде композиции ℓ\ell независимых циклов:

σ=(σ1,1,σ1,2,σ1,3,…,σ1,k1) (σ2,1,σ2,2,σ2,3,…,σ2,k2) ⋯ (σℓ,1,σℓ,2,σℓ,3,…,σℓ,kℓ)\sigma = (\sigma_{1, \- 1}, \sigma_{1, \- 2}, \sigma_{1, \- 3}, \dotsc, \sigma_{1, \- k_1}) ~ (\sigma_{2, \- 1}, \sigma_{2, \- 2}, \sigma_{2, \- 3}, \dotsc, \sigma_{2, \- k_2}) ~ \dotsm ~ (\sigma_{\ell, \- 1}, \sigma_{\ell, \- 2}, \sigma_{\ell, \- 3}, \dotsc, \sigma_{\ell, \- k_\ell})

Все циклы независимы, а значит, порядок перестановки σ\sigma является наименьшим общим кратным порядков составляющих её циклов. А порядок любого цикла равен его длине. Значит

ord⁡σ=lcm⁡(k1,k2,…,kℓ)\ord \sigma = \lcm (k_1, k_2, \dotsc, k_\ell)

Сопряжение

Теорема о представлении сопряжения

Пусть σ,τ∈Sn\sigma, \tau \in \S_n — две какие-то перестановки. Пусть также σ\sigma представлена в виде композиции ℓ\ell независимых циклов:

σ=(σ1,1,σ1,2,σ1,3,…,σ1,k1) (σ2,1,σ2,2,σ2,3,…,σ2,k2) ⋯ (σℓ,1,σℓ,2,σℓ,3,…,σℓ,kℓ)\sigma = (\sigma_{1, \- 1}, \sigma_{1, \- 2}, \sigma_{1, \- 3}, \dotsc, \sigma_{1, \- k_1}) ~ (\sigma_{2, \- 1}, \sigma_{2, \- 2}, \sigma_{2, \- 3}, \dotsc, \sigma_{2, \- k_2}) ~ \dotsm ~ (\sigma_{\ell, \- 1}, \sigma_{\ell, \- 2}, \sigma_{\ell, \- 3}, \dotsc, \sigma_{\ell, \- k_\ell})

Тогда сопряжение с помощью пересановки τ\tau можно выразить формулой

τ∘σ∘τ−1=(τ(σ1,1),τ(σ1,2),…,τ(σ1,k1)) (τ(σ2,1),τ(σ2,2),…,τ(σ2,k2)) ⋯ (τ(σℓ,1),τ(σℓ,2),…,τ(σℓ,kℓ))\tau \compose \sigma \compose \tau^{-1} = \bigl( \tau (\sigma_{1, \- 1}), \tau (\sigma_{1, \- 2}), \dotsc, \tau (\sigma_{1, \- k_1}) \bigr) ~ \bigl( \tau (\sigma_{2, \- 1}), \tau (\sigma_{2, \- 2}), \dotsc, \tau (\sigma_{2, \- k_2}) \bigr) ~ \dotsm ~ \bigl( \tau (\sigma_{\ell, \- 1}), \tau (\sigma_{\ell, \- 2}), \dotsc, \tau (\sigma_{\ell, \- k_\ell}) \bigr)

Доказательство. Достаточно просто посмотреть на действие обоих сторон на произвольный элемент x∈{1,2,…,n}x \in \{1, 2, \dotsc, n\}. Будем смотреть на действие по частям, ведь циклы, составляющие перестановки, не пересекаются.

Рассмотрим один jj-й цикл α=(σj,1,σj,2,σj,kj)\alpha = (\sigma_{j, \- 1}, \sigma_{j, \- 2}, \sigma_{j, \- k_j}).

(τ∘α∘τ−1)(x)=τ(α(τ−1(x))(\tau \compose \alpha \compose \tau^{-1}) (x) = \tau(\alpha(\tau^{-1}(x))

Посмотрим как действует цикл (τ(σj,1),τ(σj,2),…,τ(σj,kj))\bigl( \tau(\sigma_{j, \- 1}), \tau(\sigma_{j, \- 2}), \dotsc, \tau(\sigma_{j, \- k_j}) \bigr) на элемент xx.

Если x=τ(σj,i)x = \tau(\sigma_{j, \- i}) для некоторого ii, то (τ∘α∘τ−1)(x)=(τ∘α)(σj,i)=τ(σj,(i+1) mod kj)(\tau \compose \alpha \compose \tau^{-1}) (x) = (\tau \compose \alpha) (\sigma_{j, \- i}) = \tau (\sigma_{j, \- (i+1) \bmod k_j})

Если x∉supp⁡αx \notin \supp \alpha, то (τ∘α∘τ−1)(x)=(τ∘τ−1)(x)=x(\tau \compose \alpha \compose \tau^{-1}) (x) = (\tau \compose \tau^{-1})(x) = x

Теперь возвращаемся к сопряжению τ∘σ∘−1\tau \compose \sigma \compose^{-1}. Перестановка σ\sigma является композицией непересекающихся циклов α1,α2,…,αℓ\alpha_1, \alpha_2, \dotsc, \alpha_\ell, тогда

τ∘σ∘τ−1=(τ∘α1∘τ−1)∘(τ∘α2∘τ−1)∘⋯∘(τ∘αℓ∘τ−1)\tau \compose \sigma \compose \tau^{-1} = (\tau \compose \alpha_1 \compose \tau^{-1}) \compose (\tau \compose \alpha_2 \compose \tau^{-1}) \compose \dotsb \compose (\tau \compose \alpha_\ell \compose \tau^{-1})

Каждая перестановка τ∘αj∘τ−1\tau \compose \alpha_j \compose \tau^{-1} — это цикл, полученный заменой элементов в цикле αj\alpha_j на их образы под действием перестановки τ\tau, как мы это доказывали выше. Поскольку исходные циклы не пересекались, и τ\tau — биекция, их образы тоже не пересекаются. Значит, полученные циклы независимы и их произведение — разложение перестановки τ∘τ−1\tau \compose \tau^{-1} в композицию независимых циклоы.

Фактически, перестановки σ\sigma и τ∘σ∘τ−1\tau \compose \sigma \compose \tau^{-1} отличаются не структурой, а только «углом», под которым вы на эти перестановки смотрите. Формула C⋅A⋅C−1C \cdot A \cdot C^{-1} навеивает ностальгические воспоминания про линейный переход к другому базису. На самом деле здесь это и происходит, если отождествить каждый элемент перестановки jj с базисным вектором ej\e_j, а перестановку σ\sigma с соответствующей матрицей перестановки T=mat⁡σT = \mat \sigma, которая действует на базисных векторах как T(ej)=eσ(j)T(e_j) = e_{\sigma(j)}.

Также из этой формулы следует, что две перестановки из группы Sn\S_n сопряжены тогда и только тогда, когда у них одинаковый циклический тип (одинаковый набор длин циклов при разложении).

Эта формула позволяет очень эффективно вычислять композиции перестановок. Причём не только сопряжения, а вообще любые выражения пытаются максимально сводить к сопряжениям для упрощения и ускорения вычислений. Например, вычисление коммутатора двух перестановок [τ,σ]=τ∘σ∘τ−1∘σ−1[\tau, \sigma] = \tau \compose \sigma \compose \tau^{-1} \compose \sigma^{-1} можно свести к одному вычислению композиции вместо трёх, если выделить сопряжение [τ,σ]=(τ∘σ∘τ−1)∘σ−1[\tau, \sigma] = (\tau \compose \sigma \compose \tau^{-1}) \compose \sigma^{-1}.

0

Докажите (без перебора), что [x2,y2]=1[x^2, y^2] = \1 для любых перестановок x,y∈S3x, y \in \S_3. В переводе с пришельского на русский: квадраты любых двух перестановок трёх элементов коммутируют.

0

Сопряжены ли перестановки (123)(45)(123)(45) и (12)(345)(12)(345)? Если да, то найдите какую-нибудь сопрягающую перестановку.

Инволюция

Инволюция или Инволюционная перестановка — перестановка, равная обратной себе.

Количество инволюций длины nn равно f(n)=f(n−1)+(n−1)⋅f(n−2)f(n) = f(n-1) + (n-1) \cdot f(n-2), а f(0)=f(1)=1f(0)=f(1)=1.

Таблица инверсий

Таблица инверсий

Пусть σ\sigma - перестановка чисел 1,2,3,…,n1, 2, 3, \dots, n.

Таблица инверсий перестановки σ\sigma — последовательность t1,t2,…,tnt_1, t_2, \dotsc, t_n, в которой tjt_j равно числу элементов перестановки σ\sigma, стоящих левее jj и больших jj.

Например, для перестановки 5 9 1 8 2 6 4 7 35\, 9\, 1\, 8\, 2\, 6\, 4\, 7\, 3 таблица инверсий выглядит так: 2 3 6 4 0 2 2 1 02\, 3\, 6\, 4\, 0\, 2\, 2\, 1\, 0

t1=2t_1 = 2, так как перед 11 в перестановке стоят 55 и 99.

t2=3t_2 = 3, так как перед 22 в перестановке стоят 5,9,85, 9, 8. Другие значения считаются аналогично

Таблица инверсий единственным образом определяет перестановку.

Построение за O(n2)O(n^2)

Построить таблицу инверсий за O(n2)O(n^2) можно в лоб по определению. Проходимся по всем элементам перестановки и для каждого считаем, сколько элементов, стоящих левее, его больше.

function inversion_table(array p) -> array: array t = [0] * length(p) for int i = 0 to length(p) - 1: for int j = 0 to i - 1: if p[j] > p[i]: t[p[i] - 1] += 1 return t

Построение за O(nlog⁡n)O(n \log n)

function inversion_table_merge(array t1, array t2) -> array: array t = [] int i1 = 0, i2 = 0 while i1 < length(t1) and i2 < length(t2): if t1[i1][0] < t2[i2][0]: append t1[i1] to t i1 += 1 else: tuple new_element = (t2[i2][0], t2[i2][1] + (length(t1) - i1)) append new_element to t i2 += 1 while i1 < length(t1): append t1[i1] to t i1 += 1 while i2 < length(t2): append t2[i2] to t i2 += 1 return t function inversion_table_get(array p) -> array: if length(p) == 1: return [(p[0], 0)] int mid = length(p) // 2 array left = inversion_table_get(p[0:mid]) array right = inversion_table_get(p[mid:length(p)]) return inversion_table_merge(left, right)

Распределение числа инверсий

Часто пригождается знание о том, сколько существует перестановок nn элементов, имеющих ровно kk инверсий. Это число обозначается In(k)I_n(k).

По определению In(k)=0I_n(k) = 0 при k<0k < 0 и k>(n2)k > \binom{n}{2}. Из таблицы инверсий ясно, что In(0)=1I_n(0) = 1 и In(1)=n−1I_n(1) = n-1, а так же, что InI_n симметрично:

In((n2)−k)=In(k)I_n \Biggl( \binom{n}{2} - k \Biggr) = I_n(k)

Обозначим производящую функцию In(k)I_n(k) за Gn(x)=∑k=0∞In(k)⋅xkG_n(x) = \sum\limits_{k=0}^\oo I_n(k) \cdot x^k.

Значения bkb_k в таблице инверсий мы можем выбирать независимо друг от друга, поэтому

Gn(x)=(1+x+x2+⋯+xn−1)⋅Gn−1(x)G_n(x) = \bigl( 1 + x + x^2 + \dotsb + x^{n-1} \bigr) \cdot G_{n-1} (x)

Отсюда заключаем, что

Gn(x)=∑k=0∞In(k)⋅xk=1(1−x)n⋅∏j=1n(1−xj)=(1−xn) (1−xn−1) ⋯ (1−x2) (1−x)(1−x)nG_n(x) = \sum\limits_{k=0}^\oo I_n(k) \cdot x^k = \frac{1}{(1-x)^n} \cdot \prod\limits_{j=1}^n (1-x^j) = \frac{\bigl( 1-x^n \bigr) \, \bigl( 1-x^{n-1} \bigr) \, \dotsm \, \bigl( 1-x^2 \bigr) \, (1-x)}{(1-x)^n}

Можно раскрыть рекуррентное соотношение для Gn(x)G_n (x) и получить полную формулу

In(k)=∑j=0n−1In−1(k−j)=In−1(k)+In−1(k−1)+⋯+In−1(k−n+1)I_n (k) = \sum\limits_{j=0}^{n-1} I_{n-1} (k-j) = I_{n-1} (k) + I_{n-1} (k-1) + \dotsb + I_{n-1} (k-n+1)

Общая формула для In(k)I_n (k) очень сложная, но почему бы её не привести:

In(k)=∑j=−∞∞(−1)j(n+k−uj−1k−uj)=∑j   ⁣=   ⁣0∞(−1)j⋅((n+k−uj−1k−uj)+(n+k−u−j−1k−u−j))при n⩾kI_n (k) = \sum\limits_{j=-\oo}^\oo (-1)^j \binom{n+k-u_j-1}{k-u_j} = \sum\limits_{j \;\! = \;\! 0}^\oo (-1)^j \cdot \Biggl( \binom{n+k-u_j-1}{k-u_j} + \binom{n+k-u_{-j}-1}{k-u_{-j}} \Biggr) \quad \text{при}~ n \ge k

здесь uj=(3j2−j)/2u_j = (3j^2-j)/2 — пентагональное число.

Разделив Gn(x)G_n (x) на n!n! получим производящую функцию gn(x)g_n (x) распределения числа инверсий в случайной перестановке nn элементов.

gn(x)=Gn(x)/n!=∑k=0∞In(k)n!⋅xkg_n (x) = G_n (x) / n! = \sum\limits_{k=0}^\oo \frac{I_n (k)}{n!} \cdot x^k

Эту производящую функцию gn(x)g_n (x) можно представить в виде произведения функций

gn(x)=1n!⋅∏j=1n(1+x+x2+⋯+xj−1)=∏k=1n1+x+x2+⋯+xk−1k=∏k=1nhk(x)g_n (x) = \frac{1}{n!} \cdot \prod\limits_{j=1}^n \bigl( 1 + x + x^2 + \dotsb + x^{j-1} \bigr) = \prod\limits_{k=1}^n \frac{1 + x + x^2 + \dotsb + x^{k-1}}{k} = \prod\limits_{k=1}^n h_k (x)

Давайте вспомним, что hk(x)=(1+x+x2+⋯+xk−1)/kh_k (x) = \bigl( 1 + x + x^2 + \dotsb + x^{k-1} \bigr) \big/ k — производящая функция равномерно распределённой случайной величины, принимающей неотрицательные целые значения, меньшие kk. Поэтому

mean⁡gn=∑k=1nmean⁡hk=∑k=1n∑j=0k−1jk=n (n−1)4var⁡gn=∑k=1nvar⁡hk=∑k=1nk2−112=n (2n+5) (n−1)72\alignat{2}{ \mean g_n &= \sum\limits_{k=1}^n \mean h_k &&= \sum\limits_{k=1}^n \sum\limits_{j=0}^{k-1} \frac{j}{k} = \frac{n \, (n-1)}{4} \\ \var g_n &= \sum\limits_{k=1}^n \var h_k &&= \sum\limits_{k=1}^n \frac{k^2-1}{12} = \frac{n \, (2n+5) \, (n-1)}{72} }

Получается, что для количество инверсий в случайной перестановке nn элементов

min⁡=0,mean⁡=n (n−1)4,max⁡=(n2),dev⁡=n (2n+5) (n−1)72\min\limits = 0 ,\quad \mean = \frac{n \, (n-1)}{4} ,\quad \max\limits = \binom{n}{2} ,\quad \dev = \sqrt{\frac{n \, (2n+5) \, (n-1)}{72}}

Индексы

Индекс

Индекс ind⁡σ\ind \sigma перестановки σ\sigma — сумма всех jj, для которых σ(j)>σ(j+1)\sigma(j) > \sigma(j+1) при 1⩽j<n1 \le j < n.

Теорема МакМагона

Число перестановок, имеющих данный индекс kk совпадает с числом перестановок с kk инверсиями:

∣{σ∈Sn:ind⁡σ=k}∣=In(k)\bigl| \{ \sigma \in \S_n : \ind \sigma = k \} \bigr| = I_n (k)

Рассмотрим производящую функцию числа перестановок с данным индексом

Hn(x)=∑σ   ⁣∈   ⁣Snxind⁡σH_n (x) = \sum\limits_{\sigma \;\! \in \;\! \S_n} x^{\ind \sigma}

В этой сумме перед xkx^k стоит коэффициент, равный количеству перестановок, имеющий индекс kk.

Для доказательства теоремы нам нужно доказать, что Hn(x)=Gn(x)H_n (x) = G_n (x), где Gn(x)G_n (x) — производящая функция для количества инверсий In(k)I_n (k).

Составим биекцию между nn-мерными строками (q1,q2,…,qn)∈N0n(q_1, q_2, \dotsc, q_n) \in \NN_0^n и парами (σ,(p1,p2,…,pn))∈Sn×N0n\bigl( \sigma, (p_1, p_2, \dotsc, p_n) \bigr) \in \S_n \times \NN_0^n, у которых p1⩾p2⩾⋯⩾pn⩾0p_1 \ge p_2 \ge \dotsb \ge p_n \ge 0.

Биекцию составим так, чтобы

∑j=1nqj=ind⁡σ+∑j=1npj\sum\limits_{j=1}^n q_j = \ind \sigma + \sum\limits_{j=1}^n p_j

Любая nn-мерная строка (q1,q2,…,qn)∈N0n(q_1, q_2, \dotsc, q_n) \in \NN_0^n может быть отсортирована, то есть можно взять какую-то перестановку σ∈Sn\sigma \in \S_n так, чтобы (qσ(1),qσ(2),…,qσ(n))∈N0n(q_{\sigma(1)}, q_{\sigma(2)}, \dotsc, q_{\sigma(n)}) \in \NN_0^n не возрастала, то есть qσ(1)   ⁣⩾   ⁣qσ(2)⩾⋯⩾qσ(n)q_{\sigma(1)} \;\! \ge \;\! q_{\sigma(2)} \ge \dotsb \ge q_{\sigma(n)}. При этом сортировка устойчива, то есть если qσ(j)=qσ(j+1)q_{\sigma(j)} = q_{\sigma(j+1)}, то σ(j)<σ(j+1)\sigma(j) < \sigma(j+1)

Для того, чтобы выполнилось условие для сумм, для каждой пары (σ(j),σ(j+1))\bigl( \sigma(j), \sigma(j+1) \bigr), у которой σ(j)>σ(j+1)\sigma(j) > \sigma(j+1), вычтем 11 из каждого qσ(1),qσ(2),…,qσ(j)q_{\sigma(1)}, q_{\sigma(2)}, \dotsc, q_{\sigma(j)}. После вычитания получим требуемую строку (p1,p2,…,pn)(p_1, p_2, \dotsc, p_n).

Производящая функция из первых наборов

Qn(x)=∑(q1,q2,…,qn)   ⁣∈   ⁣N0nxq1+q2+⋯+qn=1(1−x)nQ_n (x) = \sum\limits_{(q_1, q_2, \dotsc, q_n) \;\! \in \;\! \NN_0^n} x^{q_1 + q_2 + \dotsb + q_n} = \frac{1}{(1-x)^n}

Производящая функция из чисел pp из второго набора совпадает с производящей функцией числа разбиений не более чем на nn частей

Pn(x)=∑(p1,p2,…,pn)∈N0np1⩾p2⩾⋯⩾pn⩾0xp1+p2+⋯+pn=1(1−x) (1−x2) ⋯ (1−xn)P_n (x) = \sum\limits_{\substack{(p_1, p_2, \dotsc, p_n) \;\! \in \;\! \NN_0^n\\[0.4em]p_1 \;\! \ge \;\! p_2 \ge \dotsb \ge p_n \ge 0}} x^{p_1 + p_2 + \dotsb + p_n} = \frac{1}{(1-x) \, \bigl( 1-x^2 \bigr) \, \dotsm \, \bigl( 1-x^n \bigr) }

Поскольку мы установили биекцию, получаем, что

∑j=1nqj=ind⁡σ+∑j=1npj  ⟹  Qn(x)=Hn(x)⋅Pn(x)\sum\limits_{j=1}^n q_j = \ind \sigma + \sum\limits_{j=1}^n p_j \implies Q_n (x) = H_n (x) \cdot P_n(x)

А значит

Hn(x)=Qn(x)Pn(x)=Gn(x)H_n (x) = \frac{Q_n (x)}{P_n (x)} = G_n (x)

Важный результат, получаемый из теоремы Мак-Магона: распределение индекса совпадает с распределением числа инверсий. Это значит, что для индекса случайной перестановки nn элементов

min⁡=0,mean⁡=n (n−1)4,max⁡=(n2),dev⁡=n (2n+5) (n−1)72\min\limits = 0 ,\quad \mean = \frac{n \, (n-1)}{4} ,\quad \max\limits = \binom{n}{2} ,\quad \dev = \sqrt{\frac{n \, (2n+5) \, (n-1)}{72}}

Доминик Фоата и Марсель-Поль Шютценбергер нашли обобщение теоремы Мак-Магона спустя 65 лет.

Теорема Фоата – Шуценберже

Существует биекция между множеством перестановок с kk инверсиями и индексом ll и множеством перестановок с ll инверсиями и индексом kk.

{σ∈Sn:inv⁡σ=k∧ind⁡σ=l}⟷{σ∈Sn:ind⁡σ=k∧inv⁡σ=l}\{\sigma \in \S_n : \inv \sigma = k \land \ind \sigma = l \} \longleftrightarrow \{\sigma \in \S_n : \ind \sigma = k \land \inv \sigma = l\}

Упражнения

    1

    Покажите, что при n>mn > m количество перестановок nn элементов, у которых число инверсий сравнимо с rr по модулю mm равно n!/mn! / m не зависимо от значения rr. Другими словами, покажите, что

    ∣{σ∈Sn:inv⁡σ≡mr}∣=n!/m\bigl| \{ \sigma \in \S_n : \inv \sigma \eqmod{m} r \} \bigr| = n! / m
    2

    Пусть σ∈Sn\sigma \in \S_n — какая-то перестановка nn элементов. Пусть E(σ)E(\sigma) — множество инверсий перестановки σ\sigma и N(σ)N (\sigma) — множество неинверсий перестановки σ\sigma:

    E(σ)   ⁣=def   ⁣{(σ(i),σ(j))∣i<j∧σ(i)>σ(j)}N(σ)   ⁣=def   ⁣{(σ(i),σ(j))∣i>j∧σ(i)>σ(j)}\align{ E (\sigma) &\defeq \Bigl\{ \bigl( \sigma(i), \sigma(j) \bigr) \Bigm| i < j \land \sigma(i) > \sigma(j) \Bigr\} \\ N (\sigma) &\defeq \Bigl\{ \bigl( \sigma(i), \sigma(j) \bigr) \Bigm| i > j \land \sigma(i) > \sigma(j) \Bigr\} }

    Докажите, что E(σ)E(\sigma) и N(σ)N(\sigma) транзитивны как отношения.

    Докажите что «обратное» тоже верно. Посмотрим на множество T={(x,y)∣1⩽y<x⩽n∧x,y∈N}T = \bigl\{ (x, y) \bigm| 1 \le y < x \le n \land x, y \in \NN \bigr\}. Выберем какое-то транзитивное подмножество A⊂TA \subset T, дополнение к которому T∖AT \without A тоже транзитивно. Тогда найдётся такая перестановка σ∈Sn\sigma \in \S_n, что E(σ)=AE(\sigma) = A.