naturals-permutations.tex

\section{Перестановки}

Мы часто переставляем физические предметы местами: тасуем карты, перекладываем деньги в кошельке, сортируем данные в компьютере, ставим книги на полке, меняем жизненные приоритеты. Эти действия отражены в математическом понятии перестановок, которым мы и займёмся. Чтобы не было путаницы, мы более не будем придерживаться аксиоматического задания натуральных чисел (если не оговорено обратное), и в этом и последующих параграфах будем использовать обозначение $[n]$ для множества чисел от 1 до $n$.

\begin{definition}
\term{$n$-элементной перестановкой} называется биекция $[n]\to[n]$. Множество всех $n$-элементных перестановок будем обозначать как $S_n$.
\end{definition}

Перестановку удобно записывать в виде строки. Например: $\pi = 35124 \in S_5$. Эта запись означает, что на первой позиции оказался элемент, который раньше стоял на третьей позиции, вслед за ним идёт элемент, которые ранее стоял пятым и т.д.

Как и для любых функций, для перестановок можно рассматривать их композицию (в случае перестановок её часто называют \term{умножением}). Пусть, например, перестановка $\pi$ задана как выше и дана перестановка $\rho = 45231$. В этом случае мы получаем $\pi \circ \rho = 24513$. Для понимания этого примера важно помнить, что $(\pi\circ\rho)(x) = \pi(\rho(x))$, то есть для того, чтобы получить позицию элемента, надо вначале применить перестановку $\rho$, а затем только $\pi$. Такой <<обратный порядок>> применения перестановок может показаться непривычным, но это стандартная форма записи функций, как мы узнали во второй главе. Вот так например можно получить позицию единицы в искомой перестановке:

$$(\pi\circ\rho) (1) = \pi(\rho(1)) = \pi(5) = 2$$

Хотя для композиции функций принято обозначение $\pi\circ\rho$, для умножения перестановок мы будем опускать символ $\circ$ и писать просто $\pi\rho$.

Из того, что перестановка~--- это функция, сразу следует ассоциативность перемножения перестановок (см.~\S2.4): для любых $\rho, \pi, \delta$ мы имеем тождество
$$(\rho\pi)\delta = \rho(\pi\delta) = \rho\pi\delta$$

\begin{exercise}
Покажите, что умножение перестановок не коммутативно, то есть что в общем случае $\rho\pi \not= \pi\rho$
\end{exercise}

\begin{exercise}
Придумайте сами каких-нибудь перестановок и поэкспериментируйте с ними.
\end{exercise}

\begin{thm}\label{thm:perminv}
$(\rho\pi)^{-1} = \pi^{-1}\rho^{-1}$
\end{thm}
\begin{proof}
$$(\rho\pi)(\pi^{-1}\rho^{-1}) = \rho(\pi\pi^{-1})\rho^{-1} = \rho\rho^{-1} = 1_{[n]}$$
\end{proof}

Если вам здесь что-то стало не очень понятно или сложно~--- перечитайте~\S2.4, все обозначения и термины являются непосредственным отражением того, что обсуждалось когда мы говорили об обыкновенных функциях.

Подсчитаем мощность множества $S_n$. На первую позицию мы можем поставить один из $n$ доступных нам элементов. На вторую позицию мы можем выбрать один из оставшихся $n-1$ элементов (итого способов расставить первые два элемента $n(n-1)$). Затем на третью позицию мы можем поставить один из $n-2$ элементов (итого имеем $n(n-1)(n-2)$ расстановок). Продолжая так до конца, на последнюю $n$-ю позицию мы ставим один оставшийся элемент. Для формулировки полученного результата полезно следующее обозначение:

\begin{definition}
Факториалом $n!$ называется величина $$n(n-1)(n-2)\ldots 2\cdot 1$$
Так же считаем, что $0! = 1$.
\end{definition}

Значение для $0!$ оправдано с той точки зрения, что на пустом множестве формально можно задать единственную функцию, которая так же будет биекцией (хоть она ничего и не отображает, формально она есть; см. аналогию с $n^0$ в~\S1).

Рассуждения, приведенные выше, теперь можно сформулировать таким образом:

\begin{thm}\label{thm:symgrpord}
$|S_n| = n!$
\end{thm}

\begin{exercise}
Докажите, что при разложении на простые множители значения $n!$, множитель $p$ встретится ровно
$$\sum_{i=1}^\infty \left\lfloor {n \over p^i} \right\rfloor$$
раз, где как обычно через $\lfloor {a\over b}\rfloor$ обозначается целая часть от деления $a$ на $b$.
\end{exercise}

Помимо представления перестановки в виде строки, их удобно рассматривать в виде \term{циклов}. Рассмотрим опять перестановку $\rho = 45231$. Мы видим, что при этой перестановке 1 переходит на позицию 5, 5 переходит на позицию 2, 2 на позицию 3, 3 на 4, которая переходит опять на позицию 1. Эти переходы записываются строкой чисел в круглых скобках: $\rho = (15234)$. Здесь за каждым числом $x$ следует число $\rho(x)$. Последнее значение переходит на позицию, обозначенную первым числом, что замыкает цикл.

Рассмотрим теперь перестановку $\pi = 35124$. Здесь $\pi(1) = 3$ и $\pi(3) = 1$, что даёт цикл $(13)$. Сюда, однако, вошли не все элементы множества. Рассмотрим оставшиеся элементы: $\pi(2) = 4$, $\pi(4) = 5$, $\pi(5) = 2$, что даёт цикл $(245)$. Итого перестановка представляется в виде произведения двух циклов: $\pi = (13)(245)$.

Количество элементов в цикле мы будем называть его длиной. Если какой-то элемент $x$ отображается сам в себя (то есть $\pi(x) = x$), то мы будем говорить, что перестановка имеет цикл длины 1 $(x)$.

\begin{exercise}
Пусть $\sigma$~--- некоторая перестановка и $(x y \ldots z)$~--- некоторый цикл. Докажите, что
$$\sigma(x y \ldots z)\sigma^{-1} = (\sigma x \:\: \sigma y \ldots \sigma z)$$
(Подсказка: рассмотрите как эта перестановка действует на элемент $\sigma x$).
\end{exercise}

\begin{definition}
\term{Типом перестановки} называется набор $(c_1, c_2, \ldots, c_n)$ , где $c_k$~--- количество циклов длины $k$ заданной перестановки.
\end{definition}

\begin{definition}
\term{Циклической перестановкой} $[n]$ называется перестановка типа $(0, 0, \ldots, 0, 1)$, то есть перестановка, состоящая из единственного цикла, сдвигающего все элементы.
\end{definition}

\begin{example}
Типом перестановки $\pi$, используемой выше, будет $(0, 1, 1, 0, 0)$, типом перестановки $\rho$~--- $(0, 0, 0, 0, 1)$. Тривиальная перестановка $1_{[n]}$, которая оставляет все элементы на месте, имеет тип $(n, 0, 0, 0, 0)$, то есть она состоит из $n$ циклов вида $(a)$.
\end{example}

\begin{exercise}
Покажите, что для любого типа $(c_1, c_2, \ldots, c_n)$ всегда выполнено соотношение
$$\sum_{i=1}^n ic_i = n$$
\end{exercise}

\begin{thm}
Существует
$${n!\over c_1!c_2!\ldots c_n!1^{c_1}2^{c_2}\ldots n^{c_n}}$$
перестановок типа $(c_1, c_2, \ldots, c_n)$
\end{thm}
\begin{proof}
В качестве рабочего примера будем считать, что мы ищем все перестановки типа $(1, 2, 1, 0, 0, 0, 0, 0)$ множества $[8]$.

Вначале выпишем произвольную строку чисел, являющуюся перестановкой $[n]$ (например, 18356724), способов сделать это $n!$. Расставим теперь в этой записи круглые скобки по очереди: вначале $c_1$ скобок с одним элементом внутри, затем $c_2$ скобок с двумя элементами внутри, потом $c_3$ с тремя элементами внутри и так далее. Для нашего примера получится запись
$$(1)(83)(56)(724)$$
Таким образом мы получаем одну из возможных перестановок требуемого типа. Однако, не только первоначально выписанная перестановка даёт нам такое циклическое представление. Во-первых, если мы поменяем местами любые два цикла длины $k$, то мы получим отличное представление той же самой перестановки. Например, мы можем поменять местами две перестановки длины 2:
$$(1)(56)(83)(724)$$
Это ровно та же самая перестановка, но получающаяся из другой строки. Таким образом, поскольку у нас имеется $c_k$ циклов длины $k$, нам необходимо поделить общее количество первоначальных перестановок на $c_k!$.

Во-вторых, каждая из перестановок может быть циклически сдвинута на k элементов. Например, мы так могли бы сдвинуть наш пример, получив тот же результат:
$$(1)(56)(38)(472)$$
Опять же это та же самая перестановка. Для каждого цикла длины $k$ мы имеем $k$ способов произвести такой сдвиг. По этой причине имеющееся у нас количество искомых перестановок надо поделить на $k^{c_k}$ для каждой длины цикла $k$.
\end{proof}
\begin{corollary}
Существует $(n-1)!$ циклических перестановок множества $[n]$.
\end{corollary}
\begin{proof}
В качестве упражнения.
\end{proof}

\begin{exercise}
\term{Порядком перестановки} $|\pi|$ называется такое число $n$, что $\pi^n = 1_{[n]}$ (то есть под $\pi^n(x) = x$ подразумевается $n$-кратное применение перестановки $\pi$). Докажите, что для перестановки $\pi$ типа $(c_1, \ldots, c_n)$  выполняется соотношение
$$|\pi| = \lcm\{c_i\}$$
\end{exercise}

\begin{definition}
\term{Транспозицией} называется перестановка типа $(n-2, 1, 0, \ldots, 0)$, то есть это перестановка, меняющая местами лишь два элемента.
\end{definition}

\begin{exercise}
Докажите, что любая перестановка может быть представлена композицией транспозиций.
\end{exercise}

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

$$(13)(34) = (23)(14)(24)(23)$$

Интересно, однако, что количество транспозиций для любой заданной перестановки всегда либо чётное, либо нечётное. Это не совсем очевидно и требует доказательства, которое предсталено следующим определением с прилагающимися упражнениями.

\begin{definition}
\term{Инверсией} перестановки называется такая пара $i<j$, что $\pi(i) > \pi(j)$.
\end{definition}

Инверсии~--- это такие пары элементов, которые при применении перестановки меняют свой относительный порядок. Например, для перестановки 35124 имеется 5 инверсий: 3 и 1, 3 и 2, 5 и 1, 5 и 2, 5 и 4. Инверсии имеют важное значение при анализе быстродействия компьютерных алгоритмов, однако нас само количество инверсий интересовать не будет, нас будет интересовать лишь то, чётное это количество или нет.

\begin{definition}
Перестановка называется \term{чётной} (\term{нечётной}), если она имеет \term{чётное} (соответственно \term{нечётное}) число инверсий.
\end{definition}

\begin{exercise}
Докажите, что любая транспозиция~--- это нечётная перестановка.
\end{exercise}

\begin{exercise}
Докажите, что произведение чётных перестановок даёт чётную перестановку, произведение нечётных~--- тоже чётную, а произведениче чётной и нечётной перестановки~--- нечётную перестановку.
\end{exercise}

Тривиальная перестановка, которая оставляет все элементы на месте, чётная. Если умножить её на транспозицию~--- получаем нечётную перестановку. Умножная её на транспозицию ещё раз~--- опять получаем чётную перестановку. Поскольку любая перестановка однозначно либо чётная либо нечётная, то, рассуждая по индукции, приходим к ожидаемому: любая перестановка всегда представлена в виде транспозиций либо чётным их числом, либо нечётным.

\begin{exercise}\label{ex:sgnpermgrp}
Докажите, что для любого $n>1$ количество чётных и нечётных перестановок на $[n]$ одинаково.
\end{exercise}

Пока мы рассмотрели понятие чётности перестановок лишь в качестве упражнения, но довольно скоро вы увидите, что оно играет весьма важную теоретическую роль.

\begin{exercise}
Докажите, что любая чётная перестановка может быть представлена в виде произведения циклов длины 3.
\end{exercise}

\begin{exercise}
Докажите, что с помощью перестановок $(12)$ и $(12\ldots n)$ возможно представить любую перестановку множества $[n]$.
\end{exercise}

\begin{definition}
\term{Беззнаковым числом Стирлинга первого рода} $\fstirling{n}{k}$ называется количество перестановок множества $[n]$, содержащих ровно $k$ циклов.
\end{definition}

Слово <<беззнаковый>> мы будем опускать, поскольку пока оно не имеет для нас никакого смысла (он проявится позже). Прямо из определения следует такое простое соотношение:

\begin{thm}
$$\sum_{k=1}^n \fstirling{n}{k} = n!$$
\end{thm}
\begin{proof}
В качестве упражнения.
\end{proof}

Выше мы уже фактически доказали, что $\fstirling{n}{1} = (n-1)!$. Так же очевидно, что $\fstirling{n}{n} = 1$. Для вычисления остальных значений поможет следующая рекурсивная формула.

\begin{thm}
$$\fstirling{n}{k} = \fstirling{n-1}{k-1} + (n-1)\fstirling{n-1}{k}$$
\end{thm}
\begin{proof}
Рассмотрим какой-нибудь один отдельно взятый элемент $x$ множества $[n]$. Под действием перестановки с $k$ циклами $x$ может либо оставаться на месте, либо куда-то передвигаться. Перестановок, когда $x$ остаётся на месте, ровно $\fstirling{n-1}{k-1}$ штук. Если же $x$ куда-то передвигается, то мы можем рассмотреть перестановку множества $[n-1]$ с $k-1$ циклами: в эту перестановку, записанную в виде циклов, достаточно лишь вставить элемент $x$ после какого-нибудь другого элемента. Всего нам доступно $n-1$ позиций для вставки.
\end{proof}

По этой формуле с помощью компьютера можно сравнительно легко находить числа Стирлинга. Конечно, сами по себе они мало интересны и вряд ли вам придётся когда-либо их вычислять. Интреснее то, как они сочетаются с другими объектами математики, к чему мы вернёмся в последующих главах нашей книги.

\begin{exercise}
Посадил злой вертухай сотню гномиков в тюрьму, каждого пронумеровал и поставил условия:\\
— Завтра каждый из вас по одному будет заходить в специальную камеру, где будет лежать сотня пронумерованных конвертов. В каждом конверте — какой-то номер (просто все числа от одного до ста, разложенные по конвертам случайным образом). Каждый из вас будет иметь право открыть ровно 50 конвертов, чтобы найти свой номер. Если все вы найдете свои номера — освобожу. Если хотя бы один ошибется — казню всех.\\
Гномики после обсуждения общей стратегии больше никак общаться не смогут и вообще друг друга не увидят. Конверты после каждого гномика закрываются обратно, так что входящий в камеру гномик не имеет никакой информации о том, что нашли или не нашли другие гномики и какие конверты они открывали.

Гномикам надо придумать стратегию как искать свой номер, чтобы найти. Если открыть просто наугад 50 из 100 конвертов, то вероятность найти свой номер весьма мала (пополам на пополам). Учитывая, что гномиков сто штук, то их общие шансы при случайной стратегии оказываются вообще ничтожны. Надо поэтому придумать какую-то альтернативную стратегию. (По хорошему в этой задаче еще надо проанализировать в конце полученное решение, но этого пока я от читателя не требую, поскольку я не рассказывал методов, которые позволяют это делать; впрочем, вы можете попытаться дать грубые оценки).
\end{exercise}