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

В курсе математического анализа доказывается формула Стирлинга

где $e=2,718281 \ldots$ — основание натурального логарифма, $\pi =3,141592 \ldots$; символ $\sim$ здесь означает, что отношение $\sqrt{2 \pi n} n^{n} e^{-n} / n$ ! стремится к 1 при $n \rightarrow \infty$.

При помощи формулы Стирлинга, дающей приближение с недостатком, проверить, что $100 !>(9,33 \ldots ) 10^{157}$. Сколько в $S_{100}$ циклов длины $100?$

Найти порядок перестановки (4) и перестановки

Перестановка $\pi$ вида (3) с $m$ независимыми циклами оставляет

символов (или точек) на месте. Число $d(\pi )=n-\left(m+m^{\prime }\right)$ называется декрементом перестановки $\pi$. Проверить, что $\varepsilon_{\pi }=(-1)^{d(\pi )}$.

Найти знак перестановки

Пусть $\Omega =\left\{ 1,2, \ldots , n\right\} , \Omega \times \Omega$ — декартов квадрат. Будем называть пару $(i, j) \in \Omega \times \Omega$ инверсией относительно перестановки $\sigma \in S_{n}$ (или, короче: $\sigma$-инверсией), если $i<j$, но $\sigma (i)>\sigma (j)$. Положим

Так как $(\sigma (j)-\sigma (i)) /(j-i)$ — отличное от нуля рациональное число, являющееся отрицательным в точности тогда, когда $(i, j)$ будет $\sigma$-инверсией, и так как $\sigma : \Omega \rightarrow \Omega$ — биективное отображение, то $\operatorname {sgn} \sigma =(-1)^{k}$, где $k$ — общее число $\sigma$-инверсий. Если $\tau =(i j)$ — транспозиция, то $\operatorname {sgn} \tau =-1$. Как легко видеть,

так что $\sigma$-инверсия $(i, j$) перестает быть инверсией относительно перестановки $\tau \sigma$, где $\tau =(\sigma (j) \sigma (i))$ — транспозиция.

Показать, что найдутся $k$ транспозиций $\tau_{1}, \ldots , \tau_{k}$, для которых

• единичная перестановка. Стало быть, $\sigma =\tau_{1} \ldots \tau_{k-1} \tau_{k}$ и $\operatorname {sgn} \sigma =(-1)^{k}=\varepsilon_{\sigma }$ два равноправных обозначения одного и того же инварианта перестановки; sgn (от signum (лат.)) — знак. Мы получили еще один удобный способ определения знака перестановки. Скажем, относительно перестановки (4) множество инверсий состоит из пяти пар $(1,5),(2,5),(3,5),(4,5),(6,7)$, так что $\operatorname {sgn} \pi =-1$. Практически дело сводится к подсчёту в нижней строке перестановки $\pi$ количества чисел $j$, больших $i$, но стоящих перед $i$, для $i=1,2, \ldots , n-1$.