\input style
\chapnotrue\chapno=5\subchno=1\subsubchno=2

РАВНО ЧИСЛУ ПЕРЕСТАНОВОК ЭТИХ ЦИКЛОВ (МУЛЬТИНОМИАЛЬНОМУ КОЭФФИЦИЕНТУ),
ПРОСУММИРОВАННОМУ ПО ВСЕМ ЗНАЧЕНИЯМ~$k$:
$$
\eqalignno{
N(A, B, C, m) &=
\sum_k { (C+m-k)! \over (m-k)! (C-A+m-k)! (C-B+m-k)!k! (A+B-C-2m+k)!}=\cr
&= \sum_k \perm{m}{k}\perm{A}{m}\perm{A-m}{C-B+m-k}\perm{C+m-k}{A}. &(25) \cr
}
$$
сРАВНИВАЯ ЭТО С~(23), ОБНАРУЖИВАЕМ, ЧТО ДОЛЖНО ВЫПОЛНЯТЬСЯ
ТОЖДЕСТВО
$$
\sum_k \perm{m}{k} \perm{A-m}{C-B+m-k}\perm{C+m-k}{A}=
\perm{B}{C-A+m}\perm{C}{B-m}.
\eqno(26)
$$
оКАЗЫВАЕТСЯ, С ЭТИМ ТОЖДЕСТВОМ МЫ ВСТРЕЧАЛИСЬ В УПР.~1.2.6-31:
$$
\sum_j \perm{M-R+S}{j} \perm{N+R-S}{N-j}\perm{R+j}{M+N}=
\perm{R}{M}\perm{S}{N},
\eqno(27)
$$
ГДЕ $M=A+B-C-m$, $N=C-B+m$, $R=B$, $S=C$, А~$j=C-B+m-k$.

аНАЛОГИЧНО МОЖНО ПОДСЧИТАТЬ ЧИСЛО ПЕРЕСТАНОВОК
МУЛЬТИМНОЖЕСТВА~$\set{A\cdot a, B\cdot b, C\cdot c, D\cdot d}$, ЕСЛИ
КОЛИЧЕСТВО СТОЛБЦОВ РАЗЛИЧНЫХ ТИПОВ В НИХ ЗАДАНО СЛЕДУЮЩИМ ОБРАЗОМ:
$$\let\ds=\displaystyle
\matrix{
\hbox{сТОЛБЕЦ:}\hfill   & a & a   & b & b   & c     & c   & d   & d    \cr
                        & d & b   & a & c   & b     & d   & a   & c    \cr
\hbox{кОЛИЧЕСТВО:}\hfill& r & A-r & q & B-q & B-A+r & D-r & A-q & D-A+q\cr
}
\eqno(28)
$$
(зДЕСЬ~$A+C=B+D$.) вОЗМОЖНЫМИ ЦИКЛАМИ В РАЗЛОЖЕНИИ ТАКОЙ ПЕРЕСТАНОВКИ НА
ПРОСТЫЕ МНОЖИТЕЛИ БУДУТ
$$
\matrix{
\hbox{цИКЛ:}\hfill       & (a\, b) & (b\, c) & (c\, d) & (d\, a) & (a\, b\, c\, d) & (d\, c\, b\, a)\cr
\hbox{кОЛИЧЕСТВО:}\hfill & A-r-s   & B-q-s   & D-r-s   & A-q-s   & s               & q-A+r+s \cr
}
\eqno(29)
$$
ПРИ НЕКОТОРОМ~$s$ (СМ.~УПР.~12). в ЭТОМ СЛУЧАЕ ЦИКЛЫ~$(a\, b)$ И~$(c\,d)$
КОММУТИРУЮТ, ТАК ЖЕ КАК И ЦИКЛЫ~$(b\, c)$ И~$(d\,a)$, ПОЭТОМУ
НЕОБХОДИМО ПОДСЧИТАТЬ ЧИСЛО РАЗЛИЧНЫХ РАЗЛОЖЕНИЙ НА ПРОСТЫЕ МНОЖИТЕЛИ.
оКАЗЫВАЕТСЯ (СМ.~УПР.~10), ВСЕГДА СУЩЕСТВУЕТ ЕДИНСТВЕННОЕ РАЗЛОЖЕНИЕ,
ТАКОЕ, ЧТО ЦИКЛ~$(a\, b)$ НИКОГДА НЕ СЛЕДУЕТ НЕПОСРЕДСТВЕННО ЗА~$(c\, d)$,
А~$(b\, c)$ НЕ ВСТРЕЧАЕТСЯ СРАЗУ ПОСЛЕ~$(d\,a)$.
%% 47
оТСЮДА, ПОЛЬЗУЯСЬ РЕЗУЛЬТАТОМ УПР.~13, ПОЛУЧАЕМ ТОЖДЕСТВО
$$
\displaylines{
\sum_{s,t}\perm{B}{t}\perm{A-q-s}{A-r-s-t}\perm{B+D-r-s-t}{B-q-s}\times
{D! \over (D-r-s)!(A-q-s)!s!(q-A+r+s)!}=\hfill\cr
\hfill=\perm{A}{r}\perm{B+D-A}{D-r}\perm{B}{q}\perm{D}{A-q}.\cr
}
$$
вЫНОСЯ ИЗ ОБЕИХ ЧАСТЕЙ МНОЖИТЕЛЬ~$\perm{D}{A-q}$ И СЛЕГКА УПРОЩАЯ
ФАКТОРИАЛЫ, ПРИХОДИМ К СЛОЖНОМУ НА ВИД ПЯТИПАРАМЕТРИЧЕСКОМУ ТОЖДЕСТВУ
БИНОМИАЛЬНЫХ КОЭФФИЦИЕНТОВ:
$$
\sum_{s, t} \perm{B}{t}\perm{A-r-t}{s}\perm{B+D-r-s-t}{D+q-r-t}\times
\perm{D-A+q}{D-r-s}\perm{A-q}{r+t-q}=
\perm{A}{r}\perm{B+D-A}{D-r}\perm{B}{q}.
\eqno(30)
$$
пОЛЬЗУЯСЬ ТОЖДЕСТВОМ~(27), МОЖНО ВЫПОЛНИТЬ СУММИРОВАНИЕ ПО~$s$, А
ПОЛУЧИВШАЯСЯ СУММА ПО~$t$ ЛЕГКО ВЫЧИСЛЯЕТСЯ. тАКИМ ОБРАЗОМ, . ПОСЛЕ ВСЕЙ
ПРОДЕЛАННОЙ РАБОТЫ НАМ НЕ ПОСЧАСТЛИВИЛОСЬ ОБНАРУЖИТЬ КАКОЕ-ЛИБО
ТОЖДЕСТВО, КОТОРОЕ МЫ БЫ ЕЩЕ НЕ УМЕЛИ ВЫВОДИТЬ. нО МЫ ПО КРАЙНЕЙ МЕРЕ
НАУЧИЛИСЬ ПОДСЧИТЫВАТЬ ЧИСЛО ПЕРЕСТАНОВОК ОПРЕДЕЛЕННОГО ВИДА ДВУМЯ
РАЗЛИЧНЫМИ СПОСОБАМИ, А ЭТИ МЕТОДЫ ПОДСЧЕТА---ХОРОШАЯ ПОДГОТОВКА К РЕШЕНИЮ
ЗАДАЧ, КОТОРЫЕ ЕЩЕ ВПЕРЕДИ.

\excercises
\ex[м05] \emph{дА ИЛИ НЕТ?} пУСТЬ~$M_1$  И~$M_2$---МУЛЬТИМНОЖЕСТВА. еСЛИ
$\alpha$---ПЕРЕСТАНОВКА~$M_1$, А~$\beta$---ПЕРЕСТАНОВКА~$M_2$,
ТО~$\alpha\T \beta$---ПЕРЕСТАНОВКА~$M_1\cup M_2$.

\ex[10] сОЕДИНИТЕЛЬНОЕ ПРОИЗВЕДЕНИЕ
ПЕРЕСТАНОВОК~$c\,a\,d\,a\,b$ И~$b\,d\,d\,a\,d$ ВЫЧИСЛЕНО В~(5);
НАЙДИТЕ СОЕДИНИТЕЛЬНОЕ ПРОИЗВЕДЕНИЕ~$b\,d\,d\,a\,d\T c\,a\,d\,a\,b$,
КОТОРОЕ ПОЛУЧАЕТСЯ, ЕСЛИ СОМНОЖИТЕЛИ ПОМЕНЯТЬ МЕСТАМИ.

\ex[м13] вЕРНО ЛИ УТВЕРЖДЕНИЕ, ОБРАТНОЕ~(9)? иНАЧЕ ГОВОРЯ, ЕСЛИ
ПЕРЕСТАНОВКИ~$\alpha$ И~$\beta$ КОММУТАТИВНЫ ОТНОСИТЕЛЬНО ОПЕРАЦИИ
СОЕДИНИТЕЛЬНОГО ПРОИЗВЕДЕНИЯ, ТО СЛЕДУЕТ ЛИ ИЗ ЭТОГО, ЧТО ОНИ НЕ
СОДЕРЖАТ ОБЩИХ БУКВ?

\ex[M11] кАНОНИЧЕСКОЕ РАЗЛОЖЕНИЕ ПЕРЕСТАНОВКИ~(12) В СМЫСЛЕ ТЕОРЕМЫ~A
ПРИ~$a<b<c<d$ ЗАДАЕТСЯ ФОРМУЛОЙ~(17). нАЙДИТЕ СООТВЕТСТВУЮЩЕЕ
КАНОНИЧЕСКОЕ РАЗЛОЖЕНИЕ В СЛУЧАЕ, КОГДА~$d<c<b<a$.

\ex[м23] в УСЛОВИИ~(b) ТЕОРЕМЫ~B ТРЕБУЕТСЯ, ЧТОБЫ~$x<y$; ЧТО БУДЕТ, ЕСЛИ
ОСЛАБИТЬ ЭТО ТРЕБОВАНИЕ, ЗАМЕНИВ ЕГО НА~$x\le y$?

\ex[м15] сКОЛЬКО СУЩЕСТВУЕТ ЦЕПОЧЕК, СОСТОЯЩИХ РОВНО ИЗ~$m$ БУКВ~$a$ И~$n$
БУКВ~$b$, ТАКИХ, ЧТО РОВНО~$k$ БУКВ~$b$ СТОЯТ НЕПОСРЕДСТВЕННО ПЕРЕД
БУКВАМИ~$a$ И НЕТ НИКАКИХ ДРУГИХ БУКВ, КРОМЕ~$a$ И~$b$?

\ex[м21] сКОЛЬКО ЦЕПОЧЕК ИЗ БУКВ~$a$, $b$, $c$, УДОВЛЕТВОРЯЮЩИХ
УСЛОВИЯМ~(18), НАЧИНАЕТСЯ С БУКВЫ~$a$? С БУКВЫ~$b$? С БУКВЫ~$c$?

\rex[20] нАЙДИТЕ ВСЕ РАЗЛОЖЕНИЯ ПЕРЕСТАНОВКИ~(12) НА ДВА
МНОЖИТЕЛЯ~$\alpha\T \beta$.

%%48
\ex[33] нАПИШИТЕ ПРОГРАММЫ ДЛЯ эвм, КОТОРЫЕ БЫ ПРОИЗВОДИЛИ РАЗЛОЖЕНИЯ
ЗАДАННОЙ ПЕРЕСТАНОВКИ МУЛЬТИМНОЖЕСТВА, ОПИСАННЫЕ В ТЕОРЕМАХ~A И~C.

\rex[M30] \emph{дА ИЛИ НЕТ?} сОГЛАСНО ТЕОРЕМЕ~C, РАЗЛОЖЕНИЕ НА ПРОСТЫЕ
МНОЖИТЕЛИ НЕ ВПОЛНЕ ОДНОЗНАЧНО, ТЕМ НЕ МЕНЕЕ МОЖНО СЛЕДУЮЩИМ ОБРАЗОМ
ОБЕСПЕЧИТЬ ЕДИНСТВЕННОСТЬ. "сУЩЕСТВУЕТ ЛИНЕЙНОЕ УПОРЯДОЧЕНИЕ~$\prec$ НА
МНОЖЕСТВЕ ПРОСТЫХ ПЕРЕСТАНОВОК, ТАКОЕ, ЧТО КАЖДАЯ ПЕРЕСТАНОВКА
МУЛЬТИМНОЖЕСТВА ИМЕЕТ ЕДИНСТВЕННОЕ
РАЗЛОЖЕНИЕ~$\sigma_1 \T \sigma_2 \T \ldots \T \sigma_n$ НА ПРОСТЫЕ МНОЖИТЕЛИ,
УДОВЛЕТВОРЯЮЩЕЕ
УСЛОВИЮ~$\sigma_i \preceq \sigma_{i+1}$, ЕСЛИ $\sigma_i$ КОММУТИРУЕТ
С~$\sigma_{i+1}$, ПРИ~$1\le i < n$".

\ex[м26] пУСТЬ~$\sigma_1$, $\sigma_2$,~\dots, $\sigma_t$---ЦИКЛЫ БЕЗ
ПОВТОРЯЮЩИХСЯ ЭЛЕМЕНТОВ. оПРЕДЕЛИМ ЧАСТИЧНОЕ УПОРЯДОЧЕНИЕ~$\prec$ НА
МНОЖЕСТВЕ $t$~ЭЛЕМЕНТОВ $\set{x_1, \ldots, x_t}$, ПОЛАГАЯ~$x_i\prec x_j$,
ЕСЛИ~$i<j$ И $\sigma_i$  ИМЕЕТ ПО КРАЙНЕЙ МЕРЕ ОДНУ ОБЩУЮ БУКВУ
С~$\sigma_j$. дОКАЖИТЕ СЛЕДУЮЩУЮ СВЯЗЬ МЕЖДУ ТЕОРЕМОЙ~C И ПОНЯТИЕМ
"ТОПОЛОГИЧЕСКОЙ СОРТИРОВКИ" (П.~2.2.3): \dfn{ЧИСЛО РАЗЛИЧНЫХ РАЗЛОЖЕНИЙ
ПЕРЕСТАНОВКИ~$\sigma_1\T \sigma_2 \T \ldots \T \sigma_t$ НА ПРОСТЫЕ
МНОЖИТЕЛИ РАВНО КОЛИЧЕСТВУ СПОСОБОВ ТОПОЛОГИЧЕСКИ ОТСОРТИРОВАТЬ ДАННОЕ
ЧАСТИЧНОЕ УПОРЯДОЧЕНИЕ.} (нАПРИМЕР, В СООТВЕТСТВИИ С~(22) СУЩЕСТВУЕТ ПЯТЬ
СПОСОБОВ ТОПОЛОГИЧЕСКИ ОТСОРТИРОВАТЬ УПОРЯДОЧЕНИЕ~$x_1\prec x_3$,
$x_2\prec x_4$, $x_1\prec x_4$.) оБРАТНО, ЕСЛИ НА МНОЖЕСТВЕ ИЗ
$t$~ЭЛЕМЕНТОВ ЗАДАНО КАКОЕ-ТО ЧАСТИЧНОЕ УПОРЯДОЧЕНИЕ, ТО СУЩЕСТВУЕТ
МНОЖЕСТВО ЦИКЛОВ
$$
\set{\sigma_1, \sigma_2,\ldots, \sigma_t},
$$
КОТОРОЕ ОПРЕДЕЛЯЕТ ЭТО ЧАСТИЧНОЕ УПОРЯДОЧЕНИЕ УКАЗАННЫМ СПОСОБОМ.

\ex[м16] пОКАЖИТЕ, ЧТО СООТНОШЕНИЯ~(29) ЯВЛЯЮТСЯ СЛЕДСТВИЯМИ ПРЕДПОЛОЖЕНИЙ~(28).

\ex[м21] дОКАЖИТЕ, ЧТО ЧИСЛО ПЕРЕСТАНОВОК
МУЛЬТИМНОЖЕСТВА~$\set{A\cdot a, B\cdot b, C\cdot c, D\cdot d, E\cdot e, F\cdot f}$,
НЕ СОДЕРЖАЩИХ ПАР СТОЯЩИХ РЯДОМ БУКВ~$c\,a$ И~$d\,b$, РАВНО
$$
\sum_t \perm{D}{A-t}\perm{A+B+E+F}{t}\perm{A+B+C+E+F-t}{B}\perm{C+D+E+F}{C,D,E,F}.
$$

\ex[M30] оДИН ИЗ СПОСОБОВ ОПРЕДЕЛИТЬ ПЕРЕСТАНОВКУ~$\pi^{-1}$,
"ОБРАТНУЮ" ПЕРЕСТАНОВКЕ~$\pi$, КОТОРЫЙ ПОДСКАЗАН НАМ ДРУГИМИ ОПРЕДЕЛЕНИЯМИ
ЭТОГО ПУНКТА, ЭТО ПОМЕНЯТЬ МЕСТАМИ СТРОКИ ДВУСТРОЧНОГО ПРЕДСТАВЛЕНИЯ~$\pi$
И ЗАТЕМ ВЫПОЛНИТЬ УСТОЙЧИВУЮ СОРТИРОВКУ СТОЛБЦОВ, ТАК ЧТОБЫ ЭЛЕМЕНТЫ
ВЕРХНЕЙ СТРОКИ РАСПОЛОЖИЛИСЬ В НЕУБЫВАЮЩЕМ ПОРЯДКЕ. нАПРИМЕР,
ЕСЛИ~$a<b<c<d$, ТО ИЗ ЭТОГО ОПРЕДЕЛЕНИЯ СЛЕДУЕТ,
ЧТО~$c\,a\,b\,d\,d\,a\,b\,d\,a\,d^{-1}=a\,c\,d\,a\,d\,a\,b\,b\,d\,d$.

иССЛЕДУЙТЕ СВОЙСТВА ЭТОЙ ОПЕРАЦИИ ОБРАЩЕНИЯ; ИМЕЕТСЯ ЛИ, НАПРИМЕР,
КАКАЯ-НИБУДЬ ПРОСТАЯ СВЯЗЬ МЕЖДУ НЕЙ И СОЕДИНИТЕЛЬНЫМ
ПРОИЗВЕДЕНИЕМ? мОЖНО ЛИ ПОДСЧИТАТЬ ЧИСЛО ПЕРЕСТАНОВОК, ТАКИХ,
ЧТО~$\pi=\pi^{-1}$?

\rex[м25] дОКАЖИТЕ, ЧТО ПЕРЕСТАНОВКА~$a_1\ldots{}a_n$ МУЛЬТИМНОЖЕСТВА
$$
\set{n_1\cdot x_1, n_2\cdot x_2, \ldots, n_m\cdot x_m},
$$
ГДЕ~$x_1<x_2<\ldots<x_n$ И~$n_1+n_2+\cdots+n_m=n$, ЯВЛЯЕТСЯ ЦИКЛОМ ТОГДА И
ТОЛЬКО ТОГДА, КОГДА НАПРАВЛЕННЫЙ ГРАФ С ВЕРШИНАМИ~$\set{x_1, x_2,~\ldots, x_m}$
И ДУГАМИ ИЗ~$x_j$ В~$a_{n_1+\cdots+n_j}$ СОДЕРЖИТ РОВНО ОДИН
ОРИЕНТИРОВАННЫЙ ЦИКЛ. в ЭТОМ СЛУЧАЕ ЧИСЛО
СПОСОБОВ ПРЕДСТАВИТЬ ПЕРЕСТАНОВКУ В ВИДЕ ЦИКЛА РАВНО ДЛИНЕ ЭТОГО
ОРИЕНТИРОВАННОГО ЦИКЛА. нАПРИМЕР, НАПРАВЛЕННЫМ ГРАФОМ, СООТВЕТСТВУЮЩИМ ПЕРЕСТАНОВКЕ
$$
\pmatrix{
a & a & a & b & b & c & c & c & d & d \cr
d & c & b & a & c & a & a & b & d & c \cr
}, \hbox{БУДЕТ}
$$
% !!! КАРТИНКУ ВНУТРЬ
\picture{p. 48}
А ДВА СПОСОБА ПРЕДСТАВИТЬ ПЕРЕСТАНОВКУ В ВИДЕ
ЦИКЛА---ЭТО~$(b\,a\,d\,d\,c\,a\,c\,a\,b\,c)$
И~$(c\,a\,d\,d\,c\,a\,c\,b\,a\,b)$.

%%49
\ex[м35] в ПРЕДЫДУЩЕМ ПУНКТЕ, ФОРМУЛА~(8), МЫ НАШЛИ ПРОИЗВОДЯЩУЮ ФУНКЦИЮ
ДЛЯ \emph{ИНВЕРСИЙ} ПЕРЕСТАНОВОК В ЧАСТНОМ СЛУЧАЕ, КОГДА В
ПЕРЕСТАНОВКЕ УЧАСТВУЮТ ЭЛЕМЕНТЫ МНОЖЕСТВА. пОКАЖИТЕ, ЧТО В ОБЩЕМ СЛУЧАЕ
ПЕРЕСТАНОВОК \emph{МУЛЬТИМНОЖЕСТВА} ПРОИЗВОДЯЩАЯ ФУНКЦИЯ ДЛЯ ИНВЕРСИЙ
РАВНА "$z\hbox{-МУЛЬТИНОМИАЛЬНОМУ}$ КОЭФФИЦИЕНТУ"
$$
\perm{n}{n_1, n_2,~\ldots}_z={n!_z\over n_1!_z n_2!_z\ldots},
\rem{ГДЕ~$m!_z=(1-z)(1-z^2)\ldots(1-z^m)$.}
$$ [сР.~С~(3); $z\hbox{-БИНОМИАЛЬНЫЕ}$ КОЭФФИЦИЕНТЫ ОПРЕДЕЛЕНЫ В
ФОРМУЛЕ~(1.2.6-37).]

\ex[M24] пОЛЬЗУЯСЬ ПРОИЗВОДЯЩЕЙ ФУНКЦИЕЙ, НАЙДЕННОЙ В УПР.~16, ВЫЧИСЛИТЕ
СРЕДНЕЕ ЗНАЧЕНИЕ И ДИСПЕРСИЮ ДЛЯ ЧИСЛА ИНВЕРСИЙ В СЛУЧАЙНОЙ ПЕРЕСТАНОВКЕ
МУЛЬТИМНОЖЕСТВА.

\ex[M30] (п.~а.~мАК-мАГОН.) \emph{иНДЕКС}
ПЕРЕСТАНОВКИ~$a_1\,a_2\ldots{}a_n$ БЫЛ ОПРЕДЕЛЕН В ПРЕДЫДУЩЕМ ПУНКТЕ;
МЫ ДОКАЗАЛИ, ЧТО ЧИСЛО
ПЕРЕСТАНОВОК ДАННОГО МНОЖЕСТВА, ИМЕЮЩИХ ДАННЫЙ ИНДЕКС~$k$, РАВНО ЧИСЛУ
ПЕРЕСТАНОВОК, ИМЕЮЩИХ $k$~ИНВЕРСИЙ. вЕРНО ЛИ ЭТО ДЛЯ ПЕРЕСТАНОВОК
ЗАДАННОГО МУЛЬТИМНОЖЕСТВА?

\ex[вм28] оПРЕДЕЛИМ \emph{ФУНКЦИЮ мИБИУСА}~$\mu(\pi)$ ПЕРЕСТАНОВКИ~$\pi$:
ОНА РАВНА~$0$, ЕСЛИ $\pi$~СОДЕРЖИТ ПОВТОРЯЮЩИЕСЯ ЭЛЕМЕНТЫ, И~$(-1)^k$ В
ПРОТИВНОМ СЛУЧАЕ, ЕСЛИ~$\pi$---ПРОИЗВЕДЕНИЕ $k$~ПРОСТЫХ ПЕРЕСТАНОВОК.
(сР.\ С ОПРЕДЕЛЕНИЕМ ОБЫЧНОЙ ФУНКЦИИ мИБИУСА, УПР.~4.5.2-10.) (a)~дОКАЖИТЕ,
ЧТО ЕСЛИ~$\pi\ne\varepsilon$, ТО
$$
\sum \mu(\lambda)=0,
$$
ГДЕ СУММА БЕРЕТСЯ ПО ВСЕМ ПЕРЕСТАНОВКАМ~$\lambda$, ЯВЛЯЮЩИМСЯ ЛЕВЫМИ
СОМНОЖИТЕЛЯМИ В РАЗЛОЖЕНИИ~$\pi$ (Т.~Е.~$\lambda\T\rho=\pi$,
ГДЕ~$\rho$---НЕКОТОРАЯ ПЕРЕСТАНОВКА) (b)~дОКАЖИТЕ, ЧТО
ЕСЛИ~$x_1<x_2<\ldots<x_m$ И~$\pi=x_{i_1} x_{i_2} \ldots x_{i_n}$,
ГДЕ~$1\le i_l \le m$ ПРИ~$1\le j \le n$, ТО
$$
\mu(\pi)=(-1)^m \varepsilon (i_1 i_2 \ldots i_n),
\rem{ГДЕ~$\varepsilon(i_1 i_2 \ldots i_n)=\sign \prod_{1\le j < k \le n} (i_k-i_j)$.}
$$


\ex[вм33] (д.~фОАТА.) пУСТЬ~$(a_{ij})$---ПРОИЗВОЛЬНАЯ МАТРИЦА
ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ. пОЛЬЗУЯСЬ ОБОЗНАЧЕНИЯМИ УПР.~19~(b),
ОПРЕДЕЛИМ~$\nu(\pi)=a_{i_1 j_1}\ldots a_{i_n j_n}$, ЕСЛИ ДВУСТРОЧНОЕ
ПРЕДСТАВЛЕНИЕ ПЕРЕСТАНОВКИ~$\pi$ ТАКОВО:
$$
\pmatrix{
x_{i_1} & x_{i_2} & \ldots & x_{i_n} \cr
x_{j_1} & x_{j_2} & \ldots & x_{j_n} \cr
}.
$$
эТА ФУНКЦИЯ ПОЛЕЗНА ПРИ ВЫЧИСЛЕНИИ ПРОИЗВОДЯЩИХ ФУНКЦИЙ ДЛЯ ПЕРЕСТАНОВОК
МУЛЬТИМНОЖЕСТВА, ПОТОМУ ЧТО~$\sum \nu(\pi)$, ГДЕ СУММА БЕРЕТСЯ ПО ВСЕМ
ПЕРЕСТАНОВКАМ~$\pi$ МУЛЬТИМНОЖЕСТВА
$$
\set{n_1\cdot x_1, \ldots, n_m\cdot x_m},
$$
БУДЕТ ПРОИЗВОДЯЩЕЙ ФУНКЦИЕЙ ДЛЯ ЧИСЛА ПЕРЕСТАНОВОК, УДОВЛЕТВОРЯЮЩИХ
НЕКОТОРЫМ ОГРАНИЧЕНИЯМ. нАПРИМЕР, ЕСЛИ ПОЛОЖИТЬ~$a_{ij}=z$ ПРИ~$i=j$
И~$a_{ij}=1$  ПРИ~$i\ne j$, ТО~$\sum \nu(\pi)$---ПРОИЗВОДЯЩАЯ ФУНКЦИЯ ДЛЯ
ЧИСЛА "НЕПОДВИЖНЫХ ТОЧЕК" (СТОЛБЦОВ, В КОТОРЫХ ВЕРХНИЙ И НИЖНИЙ ЭЛЕМЕНТЫ
РАВНЫ). чТОБЫ МОЖНО БЫЛО ИССЛЕДОВАТЬ~$\sum \nu(\pi)$ ДЛЯ ВСЕХ
МУЛЬТИМНОЖЕСТВ ОДНОВРЕМЕННО, РАССМОТРИМ ФУНКЦИЮ
$$
G=\sum \pi\nu(\pi),
$$
ГДЕ СУММА БЕРЕТСЯ ПО ВСЕМ~$\pi$ ИЗ МНОЖЕСТВА~$\set{x_1,~\ldots, x_m}^*$
ВСЕХ ПЕРЕСТАНОВОК МУЛЬТИМНОЖЕСТВ, СОДЕРЖАЩИХ ЭЛЕМЕНТЫ~$x_1$,~\dots, $x_m$,
И ПОСМОТРИМ НА КОЭФФИЦИЕНТЫ ПРИ~$x_1^{n_1}\ldots x_m^{nm}$ В~$G$.

%%50

в ЭТОЙ ФОРМУЛЕ ДЛЯ~$G$ БУДЕМ РАССМАТРИВАТЬ~$\pi$ КАК ПРОИЗВЕДЕНИЕ
ПЕРЕМЕННЫХ~$x$. нАПРИМЕР, ПРИ~$m=2$ ИМЕЕМ
$$
\eqalign{
G &= 1 + x_1\nu(x_1) +x_2\nu(x_2) +x_1x_1\nu(x_1x_1) +x_1x_2\nu(x_1x_2)+
x_2x_1\nu(x_2x_1) +x_2 x_2 \nu(x_2 x_2)+\ldots=\cr
&=1+ x_1 a_{11} +x_2 a_{22} +x_1^2 a_{11}^2  +x_1 x_2 a_{11}a_{22} +x_1
x_2 a_{21} a_{12} +x_2^2 a_{22}^2 +\ldots\,.\cr
}
$$
тАКИМ ОБРАЗОМ, КОЭФФИЦИЕНТ ПРИ~$x_1^{n_1}\ldots{}x_m^{n_m}$ В~$G$ РАВЕН
СУММЕ~$\sum \nu(\pi)$ ПО ВСЕМ ПЕРЕСТАНОВКАМ~$\pi$
МУЛЬТИМНОЖЕСТВА~$\set{n_1\cdot x_1,~\ldots, n_m\cdot x_m}$. нЕТРУДНО
ВИДЕТЬ, ЧТО
ЭТОТ КОЭФФИЦИЕНТ РАВЕН ТАКЖЕ КОЭФФИЦИЕНТУ ПРИ~$x_1^{n_1}\ldots{}x_m^{n_m}$
В ВЫРАЖЕНИИ
$$
(a_{11} x_1 +\cdots+ a_{1m} x_m)^{n_1}
(a_{21} x_1 +\cdots+ a_{2m} x_m)^{n_2} \ldots
(a_{m_1} x_1 +\cdots+ a_{mm} x_m)^{n_m}.
$$

цЕЛЬ ЭТОГО УПРАЖНЕНИЯ---ДОКАЗАТЬ ТО, ЧТО п.~а.~мАК-мАГОН В СВОЕЙ
КНИГЕ Combinatory Analysis (1915), ТОМ~1, РАЗД.~3, НАЗВАЛ "ОСНОВНОЙ
ТЕОРЕМОЙ", А ИМЕННО ФОРМУЛУ
$$
G=1/D, \rem{ГДЕ
$\displaystyle D=\det \pmatrix{
1-a_{11} x_1 &  -a_{12} x_2 & \ldots &  -a_{1m} x_m \cr
 -a_{21} x_1 & 1-a_{22} x_2 & \ldots &  -a_{2m} x_m \cr
  \vdots     &              &        &  \vdots \cr
 -a_{m1} x_1 &  -a_{m2} x_2 & \ldots & 1-a_{mm} x_m\cr
}.$}
$$
нАПРИМЕР, ЕСЛИ~$a_{ij}=1$ ПРИ ВСЕХ~$i$, $j$, ТО ЭТА ФОРМУЛА ДАЕТ
$$
G=1/(1-(x_1+x_2+\cdots+x_m)),
$$
И КОЭФФИЦИЕНТ ПРИ~$x_1^{n_1}\ldots x_m^{n_m}$ ОКАЗЫВАЕТСЯ
РАВНЫМ~$(n_1+\cdots+n_m)!/n_1!\ldots n_m!$,
КАК ЕМУ И ПОЛОЖЕНО.

дЛЯ ДОКАЗАТЕЛЬСТВА ОСНОВНОЙ ТЕОРЕМЫ мАК-мАГОНА ПОКАЖИТЕ,
ЧТО (a)~$\nu(\pi\T\rho)=\nu(\pi)\nu(\rho)$; (b)~В~ОБОЗНАЧЕНИЯХ УПР.~19
$D=\sum \pi \mu(\pi)\nu(\pi)$, ГДЕ СУММА БЕРЕТСЯ ПО ВСЕМ ПЕРЕСТАНОВКАМ~$\pi$
ИЗ МНОЖЕСТВА
$$
\set{x_1,\ldots, x_m}^*,
$$
И, НАКОНЕЦ, (c)~$D\cdot G=1$.

\subsubchap{*оТРЕЗКИ} % 5.1.3.
в П.~3.3.2 МЫ РАССМОТРЕЛИ "НЕУБЫВАЮЩИЕ ОТРЕЗКИ" КАК ОДИН ИЗ МЕТОДОВ,
ПОЗВОЛЯЮЩИХ ПРОВЕРИТЬ СЛУЧАЙНОСТЬ ПОСЛЕДОВАТЕЛЬНОСТИ. еСЛИ ПОМЕСТИТЬ
ВЕРТИКАЛЬНЫЕ ЧЕРТОЧКИ С ОБОИХ КОНЦОВ ПЕРЕСТАНОВКИ~$a_1 a_2 \ldots a_n$, А
ТАКЖЕ МЕЖДУ~$a_j$ И~$a_{j+1}$, КОГДА~$a_j>a_{j+1}$, ТО \dfn{ОТРЕЗКАМИ}
БУДУТ НАЗЫВАТЬСЯ СЕГМЕНТЫ, ОГРАНИЧЕННЫЕ ПАРАМИ ЧЕРТОЧЕК. нАПРИМЕР, В ПЕРЕСТАНОВКЕ
$$
\vert 3\; 5\; 7\;\vert\;1\;6\; 8\; 9\;\vert\; 4\; 2\;
$$
---ЧЕТЫРЕ ОТРЕЗКА. мЫ НАШЛИ СРЕДНЕЕ ЧИСЛО ОТРЕЗКОВ ДЛИНЫ~$k$ В СЛУЧАЙНОЙ
ПЕРЕСТАНОВКЕ МНОЖЕСТВА~$\set{1, 2,~\ldots, n}$, А ТАКЖЕ КОВАРИАЦИЮ ЧИСЛА
ОТРЕЗКОВ ДЛИНЫ~$j$ И ДЛИНЫ~$k$. оТРЕЗКИ ВАЖНЫ ПРИ ИЗУЧЕНИИ АЛГОРИТМОВ
СОРТИРОВКИ, ТАК КАК ОНИ ПРЕДСТАВЛЯЮТ
%%51
УПОРЯДОЧЕННЫЕ СЕГМЕНТЫ ДАННЫХ. пОЭТОМУ-ТО МЫ ТЕПЕРЬ ВНОВЬ ВЕРНЕМСЯ К
ВОПРОСУ ОБ ОТРЕЗКАХ. оБОЗНАЧИМ ЧЕРЕЗ
$$
\eul{n}{k}
\eqno(1)
$$
ЧИСЛО ПЕРЕСТАНОВОК МНОЖЕСТВА~$\set{1, 2,~\ldots, n}$, ИМЕЮЩИХ
РОВНО~$k$ ВОЗРАСТАЮЩИХ ОТРЕЗКОВ. тАКИЕ ЧИСЛА~$\eul{n}{k}$ ВОЗНИКАЮТ И В ДРУГИХ
КОНТЕКСТАХ; ИХ ОБЫЧНО НАЗЫВАЮТ \dfn{ЧИСЛАМИ эЙЛЕРА,} ПОТОМУ ЧТО эЙЛЕР
ОБСУДИЛ ИХ В СВОЕЙ ЗНАМЕНИТОЙ КНИГЕ Institutiones calculi differentialis
(St.~Petersburg, 1755), 485--487
[Euler, {\sl Opera Omnia,\/} (1) {\bf 10} (1913), 373--375]; ИХ СЛЕДУЕТ
ОТЛИЧАТЬ ОТ "ЭЙЛЕРОВЫХ ЧИСЕЛ", О КОТОРЫХ ИДЕТ РЕЧЬ В УПР.~5.1.4-22.

иЗ ЛЮБОЙ ДАННОЙ ПЕРЕСТАНОВКИ МНОЖЕСТВА~$\set{1, 2,~\ldots, n-1}$ МОЖНО
ОБРАЗОВАТЬ $n$~НОВЫХ ПЕРЕСТАНОВОК, ВСТАВЛЯЯ ЭЛЕМЕНТ~$n$ ВО ВСЕ ВОЗМОЖНЫЕ
МЕСТА. еСЛИ В ИСХОДНОЙ ПЕРЕСТАНОВКЕ СОДЕРЖАЛОСЬ $k$~ОТРЕЗКОВ, ТО РОВНО
$k$~НОВЫХ ПЕРЕСТАНОВОК БУДУТ ИМЕТЬ $k$~ОТРЕЗКОВ; В ОСТАЛЬНЫХ
$n-k$~ПЕРЕСТАНОВКАХ БУДЕТ ПО $k+1$~ОТРЕЗКОВ, ПОСКОЛЬКУ ВСЯКИЙ РАЗ, КОГДА
$n$~ВСТАВЛЯЕТСЯ НЕ В КОНЕЦ УЖЕ СУЩЕСТВУЮЩЕГО ОТРЕЗКА, ЧИСЛО ОТРЕЗКОВ
УВЕЛИЧИВАЕТСЯ НА ЕДИНИЦУ. нАПРИМЕР, СРЕДИ ШЕСТИ ПЕРЕСТАНОВОК, ПОЛУЧЕННЫХ
ИЗ ПЕРЕСТАНОВКИ~$3\,1\,2\,4\,5$,
$$
\matrix{
6\,3\,1\,2\,4\,5, & 3\,6\,1\,2\,4\,5, & 3\,1\,6\,2\,4\,5,\cr
3\,1\,2\,6\,4\,5, & 3\,1\,2\,4\,6\,5, & 3\,1\,2\,4\,5\,6;\cr
}
$$
ВСЕ, КРОМЕ ВТОРОЙ И ПОСЛЕДНЕЙ, СОДЕРЖАТ ПО ТРИ ОТРЕЗКА ВМЕСТО ИСХОДНЫХ
ДВУХ. оТСЮДА ИМЕЕМ РЕКУРРЕНТНОЕ СООТНОШЕНИЕ
$$
\eul{n}{k}=k\eul{n-1}{k}+(n-k+1)\eul{n-1}{k-1},
\rem{ГДЕ $n$~ЦЕЛОЕ, $n\ge 1$; $k$~ЦЕЛОЕ.}
\eqno (2)
$$
уСЛОВИМСЯ, ЧТО
$$
\eul{0}{k}=\delta_{1k},
\eqno(3)
$$
Т.~Е.~БУДЕМ СЧИТАТЬ, ЧТО В ПУСТОЙ ПЕРЕСТАНОВКЕ СОДЕРЖИТСЯ ОДИН ОТРЕЗОК.
чИТАТЕЛЬ, ВОЗМОЖНО, НАЙДЕТ НЕБЕЗЫНТЕРЕСНЫМ СРАВНИТЬ~(2) С РЕКУРРЕНТНЫМ
СООТНОШЕНИЕМ ДЛЯ ЧИСЕЛ сТИРЛИНГА [ФОРМУЛЫ~(1.2.6-42)]. в ТАБЛ.~1 ПРИВЕДЕНЫ
ЧИСЛА эЙЛЕРА ДЛЯ МАЛЫХ~$n$.

в ТАБЛ.~1 МОЖНО ЗАМЕТИТЬ НЕКОТОРЫЕ ЗАКОНОМЕРНОСТИ. пО ОПРЕДЕЛЕНИЮ ИМЕЕМ
$$
\eqalignno{
& \eul{n}{0}+\eul{n}{1}+\cdots+\eul{n}{n}=n!; & (4)\cr
& \eul{n}{0}=0, \quad \eul{n}{1}=1; & (5) \cr
& \eul{n}{n}=1 \rem{ПРИ $n\ge 1$.} & (6) \cr
}
$$
%% 52
\htable{тАБЛИЦА~1}%
{чИСЛА эЙЛЕРА}%
{\hfil$#$&&\bskip\hfil$\displaystyle #$\bskip\cr
n & \eul{n}{0} &\eul{n}{1} &\eul{n}{2} &\eul{n}{3} &\eul{n}{4} &\eul{n}{5} &\eul{n}{6} &\eul{n}{7}\cr
\noalign{\hrule}
0 & 0 & 1 &   0 &    0 &    0 &    0 &   0 & 0 \cr
1 & 0 & 1 &   0 &    0 &    0 &    0 &   0 & 0 \cr
2 & 0 & 1 &   1 &    0 &    0 &    0 &   0 & 0 \cr
3 & 0 & 1 &   4 &    1 &    0 &    0 &   0 & 0 \cr
4 & 0 & 1 &  11 &   11 &    1 &    0 &   0 & 0 \cr
5 & 0 & 1 &  26 &   66 &   26 &    1 &   0 & 0 \cr
6 & 0 & 1 &  57 &  302 &  302 &   57 &   1 & 0 \cr
7 & 0 & 1 & 120 & 1191 & 2416 & 1191 & 120 & 1 \cr
\noalign{\hrule}
}
вЫПОЛНЯЕТСЯ ТАКЖЕ СВОЙСТВО СИММЕТРИИ
$$
\eul{n}{k}=\eul{n}{n+1-k}, \rem{$n\ge1$,}
\eqno(7)
$$
КОТОРОЕ ВЫТЕКАЕТ ИЗ ТОГО ФАКТА, ЧТО КАЖДОЙ
ПЕРЕСТАНОВКЕ~$a_1\,a_2\,\ldots{}\,a_n$, СОДЕРЖАЩЕЙ $k$~ОТРЕЗКОВ, СООТВЕТСТВУЕТ
ПЕРЕСТАНОВКА~$a_n\,\ldots{}a_2\,a_1$, СОДЕРЖАЩАЯ $n+1-k$~ОТРЕЗКОВ.

дРУГОЕ ВАЖНОЕ СВОЙСТВО ЧИСЕЛ эЙЛЕРА ВЫРАЖАЕТСЯ ФОРМУЛОЙ
$$
\sum_k \eul{n}{k}\perm{m+k-1}{n}=m^n, \rem{$n\ge0$,}
\eqno(8)
$$
КОТОРУЮ МОЖНО ДОКАЗАТЬ, ИСПОЛЬЗУЯ ПОНЯТИЕ СОРТИРОВКИ. рАССМОТРИМ
$m^n$~ПОСЛЕДОВАТЕЛЬНОСТЕЙ $a_1\,a_2\ldots{}a_n$, ГДЕ~$1\le a_i \le m$.
лЮБУЮ ТАКУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ МОЖНО УСТОЙЧИВО ОТСОРТИРОВАТЬ ТАКИМ
ОБРАЗОМ, ЧТОБЫ ЭЛЕМЕНТЫ РАСПОЛОЖИЛИСЬ В НЕУБЫВАЮЩЕМ ПОРЯДКЕ:
$$
a_{i_1}\le a_{i_2}\le \ldots \le a_{i_n},
\eqno(9)
$$
ГДЕ~$i_1\,i_2\,\ldots{}\,i_n$---ОДНОЗНАЧНО ОПРЕДЕЛЕННАЯ ПЕРЕСТАНОВКА
МНОЖЕСТВА~$\set{1, 2,~\ldots, n}$, ТАКАЯ, ЧТО~$i_j<i_{j+1}$,
ЕСЛИ~$a_{i_j}=a_{i_{j+1}}$; ДРУГИМИ СЛОВАМИ, ИЗ~$i_j>i_{j+1}$
СЛЕДУЕТ~$a_{i_j}<a_{i_{j+1}}$. пОКАЖЕМ, ЧТО ЕСЛИ В
ПЕРЕСТАНОВКЕ~$i_1\,i_2\,\ldots\,i_n$ СОДЕРЖИТСЯ $k$~ОТРЕЗКОВ, ТО ЧИСЛО
СООТВЕТСТВУЮЩИХ ЕЙ
ПОСЛЕДОВАТЕЛЬНОСТЕЙ~$a_1\,a_2\ldots{}a_n$ РАВНО~$\perm{m+n-k}{n}$; ТЕМ
САМЫМ БУДЕТ ДОКАЗАНА ФОРМУЛА~(8), ЕСЛИ ЗАМЕНИТЬ~$k$ НА~$n+1-k$.

пУСТЬ, НАПРИМЕР, $n=9$, $i_1\,i_2\ldots{}i_n=3\,5\,7\,1\,6\,8\,9\,4\,2$ И
ТРЕБУЕТСЯ ПОДСЧИТАТЬ ЧИСЛО ПОСЛЕДОВАТЕЛЬНОСТЕЙ~$a_1a_2\ldots{}a_9$,
ТАКИХ, ЧТО
$$
1\le a_3 \le a_5 \le a_7 < a_1 \le a_6 \le a_8 \le a_9 < a_4 < a_2 \le m;
\eqno (10)
$$
ОНО РАВНО ЧИСЛУ ПОСЛЕДОВАТЕЛЬНОСТЕЙ~$b_1\,b_2\ldots{}b_9$, ТАКИХ, ЧТО
$$
1\le b_1 < b_2 < b_3 < b_4 < b_5 < b_6 < b_7 < b_8 < b_9 \le m+5,
$$
%%53
ТАК КАК МОЖНО ПОЛОЖИТЬ~$b_1=a_3$, $b_2=a_5+1$, $b_3=a_7+2$, $b_4=a_1+2$,
$b_5=a_6+3$ И~Т.~Д. чИСЛО СПОСОБОВ, КОТОРЫМИ МОЖНО ВЫБРАТЬ ЭЛЕМЕНТЫ~$b$,
РАВНО ПРОСТО-НАПРОСТО ЧИСЛУ СПОСОБОВ ВЫБРАТЬ 9~ПРЕДМЕТОВ ИЗ~$m+5$,
Т.~Е.~$\perm{m+5}{9}$; АНАЛОГИЧНОЕ ДОКАЗАТЕЛЬСТВО ГОДИТСЯ
ДЛЯ ПРОИЗВОЛЬНЫХ~$n$ И~$k$ И ЛЮБОЙ ПЕРЕСТАНОВКИ~$i_1\,i_2\ldots{}i_n$
С $k$~ОТРЕЗКАМИ.

тАК КАК В ОБЕИХ ЧАСТЯХ РАВЕНСТВА~(8) СТОЯТ ПОЛИНОМЫ ОТ~$m$, ТО ВМЕСТО~$m$
МОЖНО ПОДСТАВИТЬ ЛЮБОЕ ДЕЙСТВИТЕЛЬНОЕ ЧИСЛО, ПОЛУЧИВ ИНТЕРЕСНОЕ ВЫРАЖЕНИЕ
СТЕПЕНЕЙ ЧЕРЕЗ ПОСЛЕДОВАТЕЛЬНЫЕ БИНОМИАЛЬНЫЕ КОЭФФИЦИЕНТЫ:
$$
x^n=\eul{n}{1}\perm{x}{n}+\eul{n}{2}\perm{x+1}{n}+\cdots+\eul{n}{n}\perm{x+n-1}{n},
\rem{$n\ge1$.}
\eqno(11)
$$
нАПРИМЕР,
$$
x^3=\perm{x}{3}+4\perm{x+1}{3}+\perm{x+2}{3}.
$$
в ОСНОВНОМ БЛАГОДАРЯ ИМЕННО ЭТОМУ СВОЙСТВУ ЧИСЛА эЙЛЕРА ВЕСЬМА ПОЛЕЗНЫ ПРИ
ИЗУЧЕНИИ ДИСКРЕТНОЙ МАТЕМАТИКИ. пОЛОЖИВ В~(11) $x=1$, ДОКАЖЕМ ЕЩЕ РАЗ, ЧТО
$$
\eul{n}{n}=1,
$$
ПОСКОЛЬКУ БИНОМИАЛЬНЫЕ КОЭФФИЦИЕНТЫ ОБРАЩАЮТСЯ В~$0$ ВО ВСЕХ СЛАГАЕМЫХ,
КРОМЕ ПОСЛЕДНЕГО. пОЛОЖИВ~$x=2$, ПОЛУЧИМ
$$
\eul{n}{n-1}=2^n-n-1, \rem{$n\ge1$.}
\eqno(12)
$$
пОДСТАВИВ~$x=3$, $4$,~\dots, УБЕДИМСЯ, ЧТО ВСЕ ЧИСЛА~$\eul{n}{k}$ ПОЛНОСТЬЮ
ОПРЕДЕЛЯЮТСЯ СООТНОШЕНИЕМ~(11), И ПРИДЕМ К ФОРМУЛЕ, ВПЕРВЫЕ НАЙДЕННОЙ эЙЛЕРОМ:
$$
\eqalignno{
\eul{n}{k}&= k^n-(k-1)^n\perm{n+1}{1}+(k-2)^n\perm{n+1}{2}-\cdots+(-1)^k0^n\perm{n+1}{k}=\cr
&=\sum_{0\le j \le k} (-1)^j(k-j)^n\perm{n+1}{j},\rem{$n\ge0$, $k\ge 0$.} & (13)\cr
}
$$

иЗУЧИМ ТЕПЕРЬ ПРОИЗВОДЯЩУЮ ФУНКЦИЮ ДЛЯ ОТРЕЗКОВ. еСЛИ ПОЛОЖИТЬ
$$
g_n(z)=\sum_k \eul{n}{k} z^k/n!,
\eqno(14)
$$
%%54
ТО КОЭФФИЦИЕНТ ПРИ~$z^k$ РАВЕН ВЕРОЯТНОСТИ ТОГО, ЧТО
СЛУЧАЙНАЯ ПЕРЕСТАНОВКА МНОЖЕСТВА~$\set{1, 2,~\ldots, n}$ СОДЕРЖИТ РОВНО
$k$~ОТРЕЗКОВ. пОСКОЛЬКУ $k$~ОТРЕЗКОВ В ПЕРЕСТАНОВКЕ СТОЛЬ ЖЕ ВЕРОЯТНЫ,
КАК И~$n+1-k$, ТО СРЕДНЕЕ ЧИСЛО ОТРЕЗКОВ ДОЛЖНО
РАВНЯТЬСЯ~${1\over2}(n+1)$, И, СЛЕДОВАТЕЛЬНО, $g'_n(1)={1\over2}(n+1)$. в
УПР.~2(b) ПОКАЗАНО, ЧТО ИМЕЕТ МЕСТО ПРОСТАЯ ФОРМУЛА ДЛЯ \emph{ВСЕХ}
ПРОИЗВОДНЫХ ФУНКЦИИ~$g_n(z)$ В ТОЧКЕ~$z=1$:
$$
g_n^{(m)}(1)=\Stir{n+1}{n+1-m}/\perm{n}{m}, \rem{$n\ge m$.}
\eqno(15)
$$
тАК, В ЧАСТНОСТИ, ДИСПЕРСИЯ~$g''_n(1)+g'_n(1)-g'_n(1)^2$ РАВНА~$(n+1)/12$
ПРИ~$n\ge2$, ЧТО УКАЗЫВАЕТ НА ДОВОЛЬНО УСТОЙЧИВОЕ РАСПРЕДЕЛЕНИЕ ОКОЛО
СРЕДНЕГО ЗНАЧЕНИЯ. (мЫ НАШЛИ ЭТУ ЖЕ ВЕЛИЧИНУ В УПР.~3.3.2-18; ТАМ ОНА
НАЗЫВАЛАСЬ~$\covar(R'_1, R'_1)$.) фУНКЦИЯ~$g_n(z)$---ПОЛИНОМ, ПОЭТОМУ С
ПОМОЩЬЮ ФОРМУЛЫ~(15) МОЖНО РАЗЛОЖИТЬ ЕЕ В РЯД тЕЙЛОРА
$$
\eqalignno{
g_n(z)&={1\over n!}\sum_{0\le k \le n} (z-1)^{n-k} k! \Stir{n+1}{k+1}=\cr
      &={1\over n!}\sum_{0\le k \le n} z^{k+1}(1-z)^{n-k} k! \Stir{n+1}{k+1}. &(16)\cr
}
$$
вТОРОЕ РАВЕНСТВО СЛЕДУЕТ ИЗ ПЕРВОГО, ТАК КАК ПО СВОЙСТВУ СИММЕТРИИ~(7)
$$
g_n(z)=z^{n+1} g_n(1/z), \rem{$n\ge1$.}
\eqno(17)
$$
иЗ РЕКУРРЕНТНОГО СООТНОШЕНИЯ ДЛЯ ЧИСЕЛ сТИРЛИНГА
$$
\Stir{n+1}{k+1}=(k+1)\Stir{n}{k+1}+\Stir{n}{k}
$$
ПОЛУЧАЮТСЯ ДВА ЧУТЬ БОЛЕЕ ПРОСТЫХ ПРЕДСТАВЛЕНИЯ:
$$
\eqalignno{
g_n(z)&={1\over n!}\sum_{0\le k \le n} z(z-1)^{n-k} k! \Stir{n}{k}=\cr
&={1\over n!}\sum_{0\le k \le n} z^k (1-z)^{n-k} k! \Stir{n}{k}. & (18)\cr
}
$$

пРОИЗВОДЯЩАЯ ФУНКЦИЯ ОТ ДВУХ ПЕРЕМЕННЫХ\note{1}%
{в ОРИГИНАЛЕ "super generating function". сООТВЕТСТВУЮЩЕГО ТЕРМИНА
В ОТЕЧЕСТВЕННОЙ ЛИТЕРАТУРЕ НЕ СУЩЕСТВУЕТ.---{\sl пРИМ. РЕД.\/}}
$$
g(z, x)=\sum_{n\ge 0} g_n(z)x^n =\sum_{k, n \ge 0} \eul{n}{k} z^k x^n \Big/ n!
\eqno(19)
$$
%%55
РАВНА, СЛЕДОВАТЕЛЬНО,
$$
z\sum_{k, n\ge 0} {((z-1)x)^n \over (z-1)^k}\Stir{n}{k}{k!\over n!}=
z\sum_{k\ge0}\left({e^{(z-1)x}-1\over z-1}\right)^k= {z(1-z)\over e^{(z-1)x}-z};
\eqno(20)
$$
ЭТО ЕЩЕ ОДНО СООТНОШЕНИЕ, ОБСУЖДАВШЕЕСЯ эЙЛЕРОМ.

дРУГИЕ СВОЙСТВА ЧИСЕЛ эЙЛЕРА МОЖНО НАЙТИ В ОБЗОРНОЙ СТАТЬЕ  л.~кАРЛИЦА
[{\sl Math. Magazine,\/} {\bf 33} (1959), 247--260]; СМ.~ТАКЖЕ дЖ.~рИОРДАН,
вВЕДЕНИЕ В КОМБИНАТОРНЫЙ АНАЛИЗ, ил, м., 1963, СТР.~50, 253, 254.

рАССМОТРИМ ТЕПЕРЬ ДЛИНУ ОТРЕЗКОВ; КАКОВА В СРЕДНЕМ ДЛИНА ОТРЕЗКА? в
П.~3.3.2 МЫ УЖЕ ИЗУЧИЛИ МАТЕМАТИЧЕСКОЕ ОЖИДАНИЕ ЧИСЛА ОТРЕЗКОВ ДАННОЙ
ДЛИНЫ; СРЕДНЯЯ ДЛИНА ОТРЕЗКА РАВНА ПРИМЕРНО~2 В СОГЛАСИИ С ТЕМ ФАКТОМ,
ЧТО В СЛУЧАЙНОЙ ПЕРЕСТАНОВКЕ
ДЛИНЫ~$n$ СОДЕРЖИТСЯ В СРЕДНЕМ ${1\over2}(n+1)$~ОТРЕЗКОВ. пРИМЕНИТЕЛЬНО
К АЛГОРИТМАМ СОРТИРОВКИ ПОЛЕЗНА НЕСКОЛЬКО ОТЛИЧНАЯ ТОЧКА ЗРЕНИЯ;
РАССМОТРИМ ДЛИНУ $k\hbox{-ГО}$~СЛЕВА ОТРЕЗКА ПЕРЕСТАНОВКИ
ПРИ~$k=1$, $2$,~$\ldots\,$.

кАКОВА, НАПРИМЕР, ДЛИНА ПЕРВОГО (КРАЙНЕГО СЛЕВА) ОТРЕЗКА СЛУЧАЙНОЙ
ПЕРЕСТАНОВКИ~$a_1\,a_2\,\ldots\,a_n$? еГО ДЛИНА ВСЕГДА~$\ge 1$; ОНА~$\ge2$
РОВНО В ПОЛОВИНЕ СЛУЧАЕВ (А ИМЕННО, ЕСЛИ~$a_1<a_2$). еГО ДЛИНА~$\ge3$
РОВНО ДЛЯ $1/6$~СЛУЧАЕВ (ЕСЛИ~$a_1<a_2<a_3$). вООБЩЕ ЕГО ДЛИНА~$\ge m$ С
ВЕРОЯТНОСТЬЮ~$q_m=1/m!$ ПРИ~$1\le m \le n$. сЛЕДОВАТЕЛЬНО, ВЕРОЯТНОСТЬ
ТОГО, ЧТО ДЛИНА ЭТОГО ОТРЕЗКА РАВНА В ТОЧНОСТИ~$m$, ЕСТЬ
$$
\eqalignno{
p_m &= q_m-q_{m+1}=1/m!-1/(m+1)! \rem{ПРИ $1\le m < n$;} \cr
p_n &= 1/n!. & (21) \cr
}
$$
сРЕДНЯЯ ДЛИНА РАВНА, ТАКИМ ОБРАЗОМ,
$$
\eqalignno{
p_1+2p_2+\cdots+np_n &= \cr
&=(q_1-q_2)+2(q_2-q_3)+\cdots+(n-1)(q_{n-1}-q_n)+nq_n=\cr
&=q_1+q_2+\cdots+q_n=\cr
&={1\over 1!}+{1\over 2!}+\cdots+{1\over n!}. & (22) \cr
}
$$
пРЕДЕЛ ПРИ~$n\to\infty$ РАВЕН~$e-1=1.71828\ldots$, А ДЛЯ КОНЕЧНЫХ~$n$  ЭТО
ЗНАЧЕНИЕ РАВНО~$e-1-\delta_n$, ГДЕ $\delta_n$~ДОВОЛЬНО МАЛО:
$$
\delta_n={1\over (n+1)!)}\left(1+{1\over n+2}+{1\over
(n+2)(n+3)}+\cdots\right)< {e-1\over (n+1)!}.
$$
пОЭТОМУ ДЛЯ ПРАКТИЧЕСКИХ ЦЕЛЕЙ УДОБНО РАССМОТРЕТЬ ОТРЕЗКИ СЛУЧАЙНОЙ
\emph{БЕСКОНЕЧНОЙ} ПОСЛЕДОВАТЕЛЬНОСТИ РАЗЛИЧНЫХ ЧИСЕЛ
$$
a_1, a_2, a_3, \ldots;
$$
ПОД "СЛУЧАЙНОСТЬЮ" ПОСЛЕДОВАТЕЛЬНОСТИ МЫ ЗДЕСЬ ПОДРАЗУМЕВАЕМ ТО, ЧТО ВСЕ
$n!$~ВОЗМОЖНЫХ ВЗАИМНЫХ РАСПОЛОЖЕНИИ ПЕРВЫХ~$n$
%%56
ЭЛЕМЕНТОВ ПОСЛЕДОВАТЕЛЬНОСТИ РАВНОВЕРОЯТНЫ. тАК ЧТО СРЕДНЯЯ ДЛИНА ПЕРВОГО
ОТРЕЗКА СЛУЧАЙНОЙ БЕСКОНЕЧНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ РАВНА~$e-1$.

нЕСКОЛЬКО УСОВЕРШЕНСТВОВАВ ЭТОТ МЕТОД, МОЖНО УСТАНОВИТЬ СРЕДНЮЮ ДЛИНУ
$k\hbox{-ГО}$~ОТРЕЗКА СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ.
пУСТЬ $q_{km}$---ВЕРОЯТНОСТЬ ТОГО, ЧТО ОБЩАЯ ДЛИНА ПЕРВЫХ~$k$ ОТРЕЗКОВ~$\ge m$;
ТОГДА $q_{km}$~РАВНО ВЕЛИЧИНЕ~$1/m!$, УМНОЖЕННОЙ НА ЧИСЛО
ПЕРЕСТАНОВОК МНОЖЕСТВА~$\set{1, 2, \ldots, m}$, СОДЕРЖАЩИХ НЕ БОЛЕЕ $k$~ОТРЕЗКОВ:
$$
q_{km}=\left(\eul{m}{1}+\cdots+\eul{m}{k}\right)\Big/ m!.
\eqno(23)
$$
вЕРОЯТНОСТЬ ТОГО, ЧТО ОБЩАЯ ДЛИНА ПЕРВЫХ $k$~ОТРЕЗКОВ РАВНА~$m$,
 ЕСТЬ~$q_{km}-q_{k(m+1)}$. сЛЕДОВАТЕЛЬНО, ОБОЗНАЧИВ ЧЕРЕЗ~$L_k$
СРЕДНЮЮ ДЛИНУ $k\hbox{-ГО}$~ОТРЕЗКА, НАХОДИМ, ЧТО
$$
\eqalign{
L_1+\cdots+L_k&=\hbox{(СРЕДНЯЯ ОБЩАЯ ДЛИНА ПЕРВЫХ $k$~ОТРЕЗКОВ)} =\cr
&= (q_{k1}-q_{k2}) = 2(q_{k2}-q_{k3})+ 3(q_{k3}-q_{k4})+\cdots=\cr
&= q_{k1}+q_{k2}+q_{k3}+\cdots\,.\cr
}
$$
вЫЧИТАЯ~$L_1+\cdots+L_{k-1}$ И ИСПОЛЬЗУЯ ЗНАЧЕНИЯ~$q_{km}$, ИЗ~(23)
ПОЛУЧАЕМ НУЖНУЮ НАМ ФОРМУЛУ:
$$
L_k={1\over 1!}\eul{1}{k}+{1\over 2!}\eul{2}{k}+{1\over 3!}\eul{3}{k}+\cdots=
\sum_{m\ge1}\eul{m}{k}{1\over m!}.
\eqno(24)
$$
пОСКОЛЬКУ~$\eul{0}{k}=0$ ПРИ~$k\ne 1$, ЗНАЧЕНИЕ~$L_k$ ОКАЗЫВАЕТСЯ РАВНЫМ
КОЭФФИЦИЕНТУ ПРИ~$z^k$ В ПРОИЗВОДЯЩЕЙ ФУНКЦИИ~$g(z, 1)-z$. (СМ.~(19));
ТАКИМ ОБРАЗОМ, ИМЕЕМ
$$
L(z)=\sum_{k\ge0} L_k z^k = {z(1-z) \over e^{z-1}-z}-z.
\eqno(25)
$$
иЗ ФОРМУЛЫ эЙЛЕРА~(13) ПОЛУЧИМ ПРЕДСТАВЛЕНИЕ~$L_k$ В ВИДЕ ПОЛИНОМА ОТ~$e$:
$$
\eqalignno{
L_k &= \sum_{m\ge 0} \sum_{0\le j \le k}(-1)^{k-j}\perm{m+1}{k-j}{j^m\over m!}=\cr
&=\sum_{0\le j \le k} (-1)^{k-j} \sum_{m\ge 0}\perm{m}{k-j}{j^m\over m!}+
 \sum_{0\le j \le k}(-1)^{k-j}\sum_{m\ge0}\perm{m}{k-j-1}{j^m\over m!}=\cr
&= \sum_{0\le j \le k} {(-1)^{k-j} j^{k-j} \over (k-j)!} \sum_{n\ge0}{j^n\over n!}+
 \sum_{0\le j \le k} {(-1)^{k-j} j^{(k-j-1)} \over (k-j-1)!}\sum_{n\ge0}{j^n\over n!}=\cr
&= k \sum_{0\le j \le k} {e^j (-1)^{k-j} j^{k-j-1}\over (k-j)!}. & (26) \cr
}
$$
%%57
эТУ ФОРМУЛУ ДЛЯ~$L_k$ ВПЕРВЫЕ ПОЛУЧИЛА б.~дЖ.~гЭССНЕР
[{\sl CACM,\/} {\bf 10} (1967), 89--93]. иМЕЕМ, В ЧАСТНОСТИ,
$$
\eqalignter{
L_1 &= e-1 & \approx 1.71828\,\ldots; \cr
L_2 &=e^2-2e &\approx 1.95249\,\ldots;\cr
L_3&=e^3-3e^2+{3\over 2}e &\approx 1.99579\,\ldots\,.\cr
}
$$
иТАК, СЛЕДУЕТ ОЖИДАТЬ, ЧТО ВТОРОЙ ОТРЕЗОК БУДЕТ ДЛИННЕЕ ПЕРВОГО, А
ТРЕТИЙ ОТРЕЗОК БУДЕТ В СРЕДНЕМ ЕЩЕ ДЛИННЕЕ! нА ПЕРВЫЙ ВЗГЛЯД ЭТО МОЖЕТ
ПОКАЗАТЬСЯ СТРАННЫМ, НО ПОСЛЕ МИНУТНОГО РАЗМЫШЛЕНИЯ СТАНОВИТСЯ ЯСНО, ЧТО,
ПОСКОЛЬКУ ПЕРВЫЙ ЭЛЕМЕНТ ВТОРОГО ОТРЕЗКА БУДЕТ СКОРЕЕ ВСЕГО МАЛЫМ ЧИСЛОМ
(ИМЕННО ЭТО СЛУЖИТ ПРИЧИНОЙ ОКОНЧАНИЯ ПЕРВОГО ОТРЕЗКА), У ВТОРОГО
ОТРЕЗКА БОЛЬШЕ ШАНСОВ ОКАЗАТЬСЯ ДЛИННЕЕ, ЧЕМ У ПЕРВОГО. тЕНДЕНЦИЯ ТАКОВА,
ЧТО ПЕРВЫЙ ЭЛЕМЕНТ ТРЕТЬЕГО ОТРЕЗКА БУДЕТ ДАЖЕ МЕНЬШЕ, ЧЕМ ПЕРВЫЙ ЭЛЕМЕНТ
ВТОРОГО ОТРЕЗКА.

чИСЛА~$L_k$ ВАЖНЫ В ТЕОРИИ СОРТИРОВКИ ПОСРЕДСТВОМ ВЫБОРА С ЗАМЕЩЕНИЕМ
(П.~5.4.1), ПОЭТОМУ ИНТЕРЕСНО ПОДРОБНО ИЗУЧИТЬ ИХ ЗНАЧЕНИЯ. в ТАБЛ.~2,
ВЫЧИСЛЕННОЙ дЖ.~у.~рЕНЧЕМ~(МЛ.), ПРИВЕДЕНЫ ПЕРВЫЕ~18 ЗНАЧЕНИЙ~$L_k$ С
ТОЧНОСТЬЮ ДО~15 ДЕСЯТИЧНЫХ ЗНАКОВ. рАССУЖДЕНИЯ, ПРИВЕДЕННЫЕ В ПРЕДЫДУЩЕМ
АБЗАЦЕ, МОГУТ ВЫЗВАТЬ ПОДОЗРЕНИЕ, ЧТО~$L_{k+1}>L_k$; НА САМОМ ЖЕ ДЕЛЕ
ЗНАЧЕНИЯ КОЛЕБЛЮТСЯ, ТО ВОЗРАСТАЯ, ТО УБЫВАЯ. зАМЕТИМ, ЧТО~$L_k$
БЫСТРО ПРИБЛИЖАЮТСЯ К ПРЕДЕЛЬНОМУ ЗНАЧЕНИЮ~2; ВЕСЬМА ПРИМЕЧАТЕЛЬНО ТО, ЧТО
ЭТИ НОРМИРОВАННЫЕ ПОЛИНОМЫ ОТ ТРАНСЦЕНДЕНТНОГО ЧИСЛА~$e$ ТАК БЫСТРО
СХОДЯТСЯ К РАЦИОНАЛЬНОМУ ЧИСЛУ~2! пОЛИНОМЫ~(26) ПРЕДСТАВЛЯЮТ НЕКОТОРЫЙ
ИНТЕРЕС И С ТОЧКИ ЗРЕНИЯ ЧИСЛЕННОГО АНАЛИЗА, БУДУЧИ ПРЕКРАСНЫМ ПРИМЕРОМ
ПОТЕРИ ЗНАЧАЩИХ ЦИФР ПРИ ВЫЧИТАНИИ ПОЧТИ РАВНЫХ ЧИСЕЛ; ИСПОЛЬЗУЯ
19-ЗНАЧНУЮ АРИФМЕТИКУ С ПЛАВАЮЩЕЙ ТОЧКОЙ, гЭССНЕР ПРИШЛА К НЕВЕРНОМУ
ЗАКЛЮЧЕНИЮ О ТОМ, ЧТО~$L_{12}>2$, А рЕНЧ ОТМЕТИЛ, ЧТО 42-ЗНАЧНАЯ АРИФМЕТИКА
\htable{тАБЛИЦА~2}%
{сРЕДНИЕ ДЛИНЫ ОТРЕЗКОВ}%
{\hfil$#$\hfil&\hfil\bskip$#$\hfil\hskip 1cm & \hfil$#$\hfil&\hfil\bskip$#$\hfil\cr
k & L_k & k & L_k \cr
\noalign{\hrule}
1& 1.71828\,18284\,59045+ & 10 & 2.00000\,00012\,05997+\cr
2& 1.95249\,24420\,12560- & 11 & 2.00000\,00001\,93672+\cr
3& 1.99579\,13690\,84285- & 12 & 1.99999\,99999\,99909+\cr
4& 2.00003\,88504\,76806- & 13 & 1.99999\,99999\,97022-\cr
5& 2.00005\,75785\,89716+ & 14 & 1.99999\,99999\,99719+\cr
6& 2.00000\,50727\,55710- & 15 & 2.00000\,00000\,00019+\cr
7& 1.99999\,96401\,44022+ & 16 & 2.00000\,00000\,00006+\cr
8& 1.99999\,98889\,04744+ & 17 & 2.00000\,00000\,00000+\cr
9& 1.99999\,99948\,43434- & 18 & 2.00000\,00000\,00000-\cr
\noalign{\hrule}
}
%%58
С ПЛАВАЮЩЕЙ ТОЧКОЙ ДАЕТ~$L_{28}$ ЛИШЬ С ТОЧНОСТЬЮ ДО 29~ЗНАЧАЩИХ ЦИФР.

аСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ~$L_k$ МОЖНО ОПРЕДЕЛИТЬ, ИСХОДЯ ИЗ ПРОСТЫХ
ПОЛОЖЕНИЙ ТЕОРИИ ФУНКЦИЙ КОМПЛЕКСНОГО ПЕРЕМЕННОГО.
\picture{рИС.~3 кОРНИ УРАВНЕНИЯ~$e^{z-1}=z$. пУНКТИРНАЯ ЛИНИЯ СООТВЕТСТВУЕТ
УРАВНЕНИЮ~$e^{x-1}\cos y = x$, СПЛОШНАЯ ЛИНИЯ---УРАВНЕНИЮ~$e^{x-1}\sin y = y$.
}
зНАМЕНАТЕЛЬ В~(25) ОБРАЩАЕТСЯ В НУЛЬ ЛИШЬ ПРИ~$e^{z-1}=z$,
Т.~Е.\ (ПОЛАГАЯ~$z=x+iy$) КОГДА
$$
e^{x-1}\cos y = x \rand e^{x-1}\sin y =y.
\eqno(27)
$$
нА РИС.~3, ГДЕ НАНЕСЕНЫ ОБА ГРАФИКА ЭТИХ УРАВНЕНИЙ, ВИДНО, ЧТО ОНИ
ПЕРЕСЕКАЮТСЯ В ТОЧКАХ~$z=z_0$, $z_1$, $\bar z_1$, $z_2$, $\bar z_2$,~\dots;
ЗДЕСЬ~$z_0=1$,
$$
z_1= (3.08884\,30156\,13044-)+(7.46148\,92856\,54255-)i
\eqno (28)
$$
И ПРИ БОЛЬШИХ~$k$ МНИМАЯ ЧАСТЬ~$\Im(z_{k+1})$ РАВНА ПРИБЛИЗИТЕЛЬНО~$\Im(z_k)+2\pi$.
%% 59
тАК КАК
$$
\lim_{z\to z_k} \left({1-z \over e^{z-1}-z}\right)(z-z_k)=-1
\rem{ПРИ~$k>0$}
$$
И ЭТОТ ПРЕДЕЛ РАВЕН~$-2$ ПРИ~$k=0$, ТО ФУНКЦИЯ
$$
R_m(z)=L(z)+{2\over z-z_0}+{z_1\over z-z_1}+{\bar z_1 \over z-\bar z_1}
 +{z_2\over z-z_2}+{\bar z_2 \over z-\bar z_2}+\cdots+{z_m \over z-z_m}
 +{\bar z_m \over z-\bar z_m}
$$
НЕ ИМЕЕТ ОСОБЕННОСТЕЙ В КОМПЛЕКСНОЙ ПЛОСКОСТИ ПРИ~$\abs{z}<\abs{z_{m+1}}$.
зНАЧИТ, $R_m(z)$ МОЖНО РАЗЛОЖИТЬ В СТЕПЕННОЙ РЯД~$\sum_k \rho_k z^k$,
КoТopЫЙ СХОДИТСЯ АБСОЛЮТНО ПРИ~$\abs{z}<\abs{z_{m+1}}$; ОТСЮДА СЛЕДУЕТ,
ЧТО~$\rho_k M^k \to 0$ ПРИ~$k\to\infty$, ГДЕ~$M=\abs{z_{m+1}}-\varepsilon$.
кОЭФФИЦИЕНТАМИ ДЛЯ~$L(z)$ СЛУЖАТ КОЭФФИЦИЕНТЫ РАЗЛОЖЕНИЯ ФУНКЦИИ
$$
{2\over 1-z}+{1\over 1-z/z_1}+{1\over z/\bar z_1}+\cdots
+{1\over z-z/z_m}+{1\over z-z/\bar z_m}+R_m z,
$$
А ИМЕННО
$$
L_n= 2+2r_1^{-n}\cos n\theta_1+2r_2^{-n}\cos n\theta_2
+\cdots+2r_m^{-n}\cos n\theta_m + O(r_{m+1}^{-n}),
\eqno (29)
$$
ЕСЛИ ПОЛОЖИТЬ
$$
z_k=r_k e^{i\theta_k}.
\eqno  (30)
$$
оТСЮДА МОЖНО ПРОСЛЕДИТЬ АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ~$L_n$. иМЕЕМ
$$
\displaynarrow{
\eqalign{
r_1 &= 8.07556\,64528\,89526-,\cr
\theta_1 &= 1.17830\,39784\,74668+;\cr
}\cr
\eqalign{
r_2 &= 14.35457-,\cr
r_3 &= 20.62073+,\cr
r_4 &= 26.88795+,\cr
}
\qquad
\eqalign{
\theta_2 &=1.31269-;\cr
\theta_3 &= 1.37428-;\cr
\theta_4 &= 1.41050-;\cr
}\cr
}
\eqno(31)
$$
ТАКИМ ОБРАЗОМ, ГЛАВНЫЙ ВКЛАД В~$L_n-2$ ДАЮТ~$r_1$ И~$\theta_1$, И
РЯД~(29) СХОДИТСЯ ОЧЕНЬ БЫСТРО. пРИВЕДЕННЫЕ ЗДЕСЬ ЗНАЧЕНИЯ~$r_1$
И~$\theta_1$ НАЙДЕНЫ дЖ.~у.~рЕНЧЕМ~(МЛ.) дАЛЬНЕЙШИЙ АНАЛИЗ
[W.~W.~Hooker, {\sl CACM,\/} {\bf 12} (1969), 411--413] ПОКАЗЫВАЕТ,
ЧТО~$R_m(z)\to -z$ ПРИ~$m\to\infty$; СЛЕДОВАТЕЛЬНО,
РЯД~$2\sum_{k\ge 0} z_k^{-n}\cos n\theta_k$  ДЕЙСТВИТЕЛЬНО \emph{СХОДИТСЯ}
К~$L_n$ ПРИ~$n>1$.

мОЖНО ПРОВЕСТИ БОЛЕЕ ТЩАТЕЛЬНОЕ ИССЛЕДОВАНИЕ ВЕРОЯТНОСТЕЙ, ЧТОБЫ ПОЛНОСТЬЮ
ОПРЕДЕЛИТЬ РАСПРЕДЕЛЕНИЕ ВЕРОЯТНОСТЕЙ ДЛЯ  ДЛИНЫ $k\hbox{-ГО}$~ОТРЕЗКА И
ДЛЯ ОБЩЕЙ ДЛИНЫ ПЕРВЫХ~$k$ ОТРЕЗКОВ (СМ.~УПР.~9, 10, 11), оКАЗЫВАЕТСЯ
СУММА~$L_1+\cdots+L_k$ АСИМПТОТИЧЕСКИ ПРИБЛИЖАЕТСЯ К~$2k-1/3$.

%% 60

в ЗАКЛЮЧЕНИЕ ЭТОГО ПУНКТА РАССМОТРИМ СВОЙСТВА ОТРЕЗКОВ В СЛУЧАЕ, КОГДА В
ПЕРЕСТАНОВКЕ ДОПУСКАЮТСЯ ОДИНАКОВЫЕ ЭЛЕМЕНТЫ. бЕСЧИСЛЕННЫЕ ПАСЬЯНСЫ,
КОТОРЫМ ПОСВЯЩАЛ СВОИ ДОСУГИ ЗНАМЕНИТЫЙ АМЕРИКАНСКИЙ АСТРОНОМ 19-ГО ВЕКА
сАЙМОН нЬЮКОМБ, ИМЕЮТ НЕПОСРЕДСТВЕННОЕ ОТНОШЕНИЕ К ИНТЕРЕСУЮЩЕМУ НАС
ВОПРОСУ. оН БРАЛ КОЛОДУ КАРТ И СКЛАДЫВАЛ ИХ В ОДНУ СТОПКУ ДО ТЕХ ПОР,
ПОКА ОНИ ШЛИ В НЕУБЫВАЮЩЕМ ПОРЯДКЕ ПО СТАРШИНСТВУ; КАК ТОЛЬКО СЛЕДУЮЩАЯ
КАРТА ОКАЗЫВАЛАСЬ МЛАДШЕ ПРЕДЫДУЩЕЙ, ОН НАЧИНАЛ НОВУЮ СТОПКУ. оН ХОТЕЛ
НАЙТИ ВЕРОЯТНОСТЬ ТОГО, ЧТО В РЕЗУЛЬТАТЕ ВСЯ КОЛОДА ОКАЖЕТСЯ РАЗЛОЖЕННОЙ В
ЗАДАННОЕ КОЛИЧЕСТВО СТОПОК.

зАДАЧА сАЙМОНА нЬЮКОМБА СОСТОИТ, СЛЕДОВАТЕЛЬНО, В НАХОЖДЕНИИ
РАСПРЕДЕЛЕНИЯ ВЕРОЯТНОСТЕЙ ДЛЯ ОТРЕЗКОВ СЛУЧАЙНОЙ ПЕРЕСТАНОВКИ
МУЛЬТИМНОЖЕСТВА. в ОБЩЕМ СЛУЧАЕ ОТВЕТ ДОВОЛЬНО СЛОЖЕН (СМ. УПР.~12), ХОТЯ
МЫ УЖЕ ВИДЕЛИ, КАК РЕШАТЬ ЗАДАЧУ В ЧАСТНОМ СЛУЧАЕ, КОГДА ВСЕ КАРТЫ
РАЗЛИЧНЫ ПО СТАРШИНСТВУ. мЫ УДОВЛЕТВОРИМСЯ ЗДЕСЬ ВЫВОДОМ ФОРМУЛЫ ДЛЯ
\emph{СРЕДНЕГО} ЧИСЛА СТОПОК В ЭТОМ ПАСЬЯНСЕ.

пУСТЬ ИМЕЕТСЯ $m$ РАЗЛИЧНЫХ ТИПОВ КАРТ И КАЖДАЯ ВСТРЕЧАЕТСЯ РОВНО $p$ РАЗ.
нАПРИМЕР, В ОБЫЧНОЙ КОЛОДЕ ДЛЯ БРИДЖА $m=13$, А $p=4$, ЕСЛИ ПРЕНЕБРЕГАТЬ
РАЗЛИЧИЕМ МАСТИ. зАМЕЧАТЕЛЬНУЮ СИММЕТРИЮ ОБНАРУЖИЛ В ЭТОМ СЛУЧАЕ
п.~а.~мАК-мАГОН [Combinatory Analysis (Cambridge, 1915), ТОМ~1,
СТР.~212--213]: ЧИСЛО ПЕРЕСТАНОВОК С $k+1$~ОТРЕЗКАМИ РАВНО ЧИСЛУ
ПЕРЕСТАНОВОК С $mp-p-k+1$~ОТРЕЗКАМИ. эТО СООТНОШЕНИЕ ЛЕГКО ПРОВЕРИТЬ
ПРИ~$p=1$ (ФОРМУЛА (7)), ОДНАКО ПРИ $p > 1$ ОНО КАЖЕТСЯ ДОВОЛЬНО НЕОЖИДАННЫМ.

мОЖНО ДОКАЗАТЬ ЭТО СВОЙСТВО СИММЕТРИИ, УСТАНОВИВ ВЗАИМНО ОДНОЗНАЧНОЕ
СООТВЕТСТВИЕ МЕЖДУ ПЕРЕСТАНОВКАМИ, ТАКОЕ, ЧТО КАЖДОЙ ПЕРЕСТАНОВКЕ С
$k+1$ ОТРЕЗКАМИ СООТВЕТСТВУЕТ ДРУГАЯ, С $mp-p-k+1$~ОТРЕЗКАМИ. мЫ
НАСТОЙЧИВО РЕКОМЕНДУЕМ ЧИТАТЕЛЮ САМОМУ ПОПРОБОВАТЬ НАЙТИ ТАКОЕ
СООТВЕТСТВИЕ, ПРЕЖДЕ ЧЕМ ДВИГАТЬСЯ ДАЛЬШЕ.

кАКОГО-НИБУДЬ ОЧЕНЬ ПРОСТОГО СООТВЕТСТВИЯ НА УМ НЕ ПРИХОДИТ;
ДОКАЗАТЕЛЬСТВО мАК-мАГОНА ОСНОВАНО НА ПРОИЗВОДЯЩИХ ФУНКЦИЯХ, А НЕ НА
КОМБИНАТОРНОМ ПОСТРОЕНИИ. оДНАКО УСТАНОВЛЕННОЕ фОАТОЙ СООТВЕТСТВИЕ
(ТЕОРЕМА~5.1.2в) ПОЗВОЛЯЕТ УПРОСТИТЬ ЗАДАЧУ, ТАК КАК ТАМ УТВЕРЖДАЕТСЯ
СУЩЕСТВОВАНИЕ ВЗАИМНО ОДНОЗНАЧНОГО СООТВЕТСТВИЯ МЕЖДУ ПЕРЕСТАНОВКАМИ С
$k+1$~ОТРЕЗКАМИ И ПЕРЕСТАНОВКАМИ, В ДВУСТРОЧНОМ ПРЕДСТАВЛЕНИИ КОТОРЫХ
СОДЕРЖИТСЯ РОВНО $k$~СТОЛБЦОВ $y\atop x$, ТАКИХ, ЧТО $x<y$.

пУСТЬ ДАНО МУЛЬТИМНОЖЕСТВО $\set{p\cdot 1, p\cdot2, \ldots, p\cdot m}$;
РАССМОТРИМ ПЕРЕСТАНОВКУ С ДВУСТРОЧНЫМ ОБОЗНАЧЕНИЕМ
$$
\pmatrix{
1 & \ldots & 1 & 2 & \ldots & 2& \ldots & m & \ldots & m\cr
x_{11} & \ldots & x_{1p} &x_{21} & \ldots & x_{2p} &\ldots &x_{m1} & \ldots & x_{mp}\cr
}.
\eqno(32)
$$
%% 61
\bye