\input style
\chapnotrue\chapno=5\subchno=1\subsubchno=3
сОПОСТАВИМ С НЕЙ ДРУГУЮ ПЕРЕСТАНОВКУ ТОГО ЖЕ МУЛЬТИМНОЖЕСТВА:
$$
\pmatrix{
1       & \ldots & 1       & 2       & \ldots & 2       & \ldots & m       & \ldots & m \cr
x'_{11} & \ldots & x'_{1p} & x'_{m1} & \ldots & x'_{mp} & \ldots & x'_{21} & \ldots & x'_{2p} \cr
},
\eqno(33)
$$
ГДЕ~$x'=m+1-x$. еСЛИ ПЕРЕСТАНОВКА~(32) СОДЕРЖИТ $k$~СТОЛБЦОВ ВИДА~$y \atop x$, 
ТАКИХ, ЧТО~$x<y$, ТО~(33) СОДЕРЖИТ~$(m-1)p-k$ ТАКИХ
СТОЛБЦОВ, ПОТОМУ ЧТО НЕОБХОДИМО РАССМОТРЕТЬ ЛИШЬ СЛУЧАЙ~$y>1$, А 
НЕРАВЕНСТВО~$x<y$ ЭКВИВАЛЕНТНО~$x' \ge m+2-y$. 
пОСКОЛЬКУ~(32) СООТВЕТСТВУЕТ ПЕРЕСТАНОВКЕ С $k+1$~ОТРЕЗКАМИ, 
А~(33)---ПЕРЕСТАНОВКЕ С $mp-p-k+1$~ОТРЕЗКАМИ И ПРЕОБРАЗОВАНИЕ, 
ПЕРЕВОДЯЩЕЕ~(32) В~(33), ОБРАТИМО (ОНО ЖЕ ПЕРЕВОДИТ~(33) В~(32)), ТО ТЕМ 
САМЫМ ДОКАЗАНО УСЛОВИЕ СИММЕТРИИ мАК-мАГОНА. пРИМЕР ЭТОГО ПОСТРОЕНИЯ 
СОДЕРЖИТСЯ В УПР.~14.

в СИЛУ СВОЙСТВА СИММЕТРИИ СРЕДНЕЕ ЧИСЛО ОТРЕЗКОВ В СЛУЧАЙНОЙ 
ПЕРЕСТАНОВКЕ ДОЛЖНО 
РАВНЯТЬСЯ~${1\over2}(( k+1)+(mp-p-k+1))=1+{1\over2}p(m-1)$. нАПРИМЕР, ДЛЯ 
СТАНДАРТНОЙ КОЛОДЫ СРЕДНЕЕ
ЧИСЛО СТОПОК В ПАСЬЯНСЕ нЬЮКОМБА РАВНО~$25$ (ТАК ЧТО РАСКЛАДЫВАНИЕ ЭТОГО 
ПАСЬЯНСА ВРЯД ЛИ ПОКАЖЕТСЯ СТОЛЬ УЖ УВЛЕКАТЕЛЬНЫМ ЗАНЯТИЕМ).

нА САМОМ ДЕЛЕ, ИСПОЛЬЗУЯ ВЕСЬМА ПРОСТОЕ РАССУЖДЕНИЕ, МОЖНО ОПРЕДЕЛИТЬ 
СРЕДНЕЕ ЧИСЛО ОТРЕЗКОВ В ОБЩЕМ СЛУЧАЕ ДЛЯ \emph{ЛЮБОГО} ДАННОГО 
МУЛЬТИМНОЖЕСТВА~$\set{n_1\cdot x_1, n_2\cdot x_2,~\ldots, n_m\cdot x_m}$, 
ГДЕ ВСЕ~$x$ РАЗЛИЧНЫ. пУСТЬ~$n=n_1+n_2+\cdots+n_m$, И ПРЕДСТАВИМ СЕБЕ, 
ЧТО ВСЕ ПЕРЕСТАНОВКИ~$a_1\,a_2\,\ldots\,a_n$ ЭТОГО МУЛЬТИМНОЖЕСТВА 
ЗАПИСАНЫ В ЯВНОМ ВИДЕ; ПОСМОТРИМ, КАК ЧАСТО $a_i$ ОКАЗЫВАЕТСЯ 
БОЛЬШЕ~$a_{i+1}$ ПРИ КАЖДОМ ФИКСИРОВАННОМ ЗНАЧЕНИИ~$i$, $1 \le i < n$. 
чИСЛО СЛУЧАЕВ, КОГДА~$a_i>a_{i+1}$, РАВНО В ТОЧНОСТИ ПОЛОВИНЕ ЧИСЛА 
СЛУЧАЕВ, КОГДА~$a_i \ne a_{i+1}$, И НЕТРУДНО ВИДЕТЬ, ЧТО~$a_i=a_{i+1}=x_j$ 
РОВНО В $N n_j(n_j-1)/n(n-1)$~СЛУЧАЯХ, ГДЕ~$N$---ОБЩЕЕ ЧИСЛО ПЕРЕСТАНОВОК. 
сЛЕДОВАТЕЛЬНО, $a_i=a_{i+1}$ РОВНО В
$$
{N\over n(n-1)}(n_1(n_1-1)+\cdots+n_m(n_m-1))={N\over n(n-1)}(n_1^2+\cdots+n_m^2-n)
$$
СЛУЧАЯХ, a~$a_i>a_{i+1}$ РОВНО В
$$
{N\over 2n(n-1)}(n^2-(n_1^2+\cdots+n_m^2))
$$
СЛУЧАЯХ. сУММИРУЯ ПО~$i$ И ПРИБАВЛЯЯ~$N$, ПОТОМУ ЧТО В КАЖДОЙ ПЕРЕСТАНОВКЕ 
ОДИН ОТРЕЗОК КОНЧАЕТСЯ ЭЛЕМЕНТОМ~$a_n$, ПОЛУЧИМ ОБЩЕЕ ЧИСЛО ОТРЕЗКОВ ВО 
ВСЕХ~$N$ ПЕРЕСТАНОВКАХ:
$$
N\left({n\over2}-{1\over 2n}(n_1^2+\cdots+n_m^2)+1\right).
\eqno(34)
$$
пОДЕЛИВ НА~$N$, ПОЛУЧИМ ИСКОМОЕ СРЕДНЕЕ ЧИСЛО ОТРЕЗКОВ. 
%%62

тАК КАК ОТРЕЗКИ ВАЖНЫ ПРИ ИЗУЧЕНИИ "ПОРЯДКОВЫХ СТАТИСТИК", ИМЕЕТСЯ ВЕСЬМА 
ОБШИРНАЯ ЛИТЕРАТУРА, ПОСВЯЩЕННАЯ ИМ, В ТОМ ЧИСЛЕ И НЕКОТОРЫМ ДРУГИМ ТИПАМ 
ОТРЕЗКОВ, НЕ РАССМОТРЕННЫМ ЗДЕСЬ. дОПОЛНИТЕЛЬНУЮ ИНФОРМАЦИЮ МОЖНО НАЙТИ В 
КНИГЕ ф.~н.~дЭВИД И~д.~э.~бАРТОНА Combinatorial Chance (London: Griffin, 1962), 
ГЛ.~10, И В ОБЗОРНОЙ СТАТЬЕ д.~э.~бАРТОНА И~к.~л.~мЭЛЛОУЗА 
[{\sl Annals of Math. Statistics,\/} {\bf 36} (1965), 236--260]. 
дАЛЬНЕЙШИЕ СВЯЗИ МЕЖДУ ЧИСЛАМИ эЙЛЕРА И ПЕРЕСТАНОВКАМИ РАССМАТРИВАЮТСЯ В 
РАБОТЕ д.~фОАТЫ И~м.~п.~шЮЦЕНБЕРЖЕ Th\'eorie G\'eom\'etrique des Polyn\^omes 
Eul\'eriens (Lecture Notes in Math., 138 (Berlin: Springer, 1970), 94~СТР.).

\excercises
\ex[м26] вЫВЕДИТЕ ФОРМУЛУ эЙЛЕРА~(13).

\rex[м22] (А)~пОПЫТАЙТЕСЬ ДАЛЬШЕ РАЗВИТЬ ИДЕЮ, ИСПОЛЬЗОВАННУЮ В ТЕКСТЕ ПРИ 
ДОКАЗАТЕЛЬСТВЕ ТОЖДЕСТВА~(8): РАССМОТРИТЕ ПОСЛЕДОВАТЕЛЬНОСТИ~$a_1\,a_2\,
\ldots\,a_n$, СОДЕРЖАЩИЕ РОВНО~$q$ РАЗЛИЧНЫХ ЭЛЕМЕНТОВ, И ДОКАЖИТЕ, ЧТО
$$
\sum_k \eul{n}{k} \perm{k-1}{n-q}=\Stir{n}{q}q!.
$$
(b)~иСПОЛЬЗУЯ ЭТО ТОЖДЕСТВО, ДОКАЖИТЕ, ЧТО
$$
\sum_k \eul{n}{k}\perm{k}{m}=\Stir{n+1}{n+1-m}(n-m)!
\rem{ПРИ~$n\ge m$.}
$$

\ex[вм25] вЫЧИСЛИТЕ СУММУ~$\sum_k \eul{n}{k}(-1)^k$.

\ex[м21] чЕМУ РАВНА СУММА
$$
\sum_k (-1)^k\Stir{n}{k}k!\perm{n-k}{m}?
$$

\ex[м20] нАЙДИТЕ ЗНАЧЕНИЕ~$\eul{p}{k}\bmod p$, ЕСЛИ~$p$---ПРОСТОЕ ЧИСЛО. 

\rex[м21] мИСТЕР тУПИЦА ЗАМЕТИЛ, ЧТО ИЗ ФОРМУЛ~(4) И~(13) МОЖНО ПОЛУЧИТЬ
$$
n!=\sum_{k\ge0} \eul{n}{k}=\sum_{k\ge0}\sum_{j\ge0} (-1)^{k-j}\perm{n+1}{k-j}j^n.
$$
пРОИЗВЕДЯ СУММИРОВАНИЕ СНАЧАЛА ПО~$k$, ЗАТЕМ ПО~$j$, ОН ОБНАРУЖИЛ, 
ЧТО~$\sum_{k\ge0} (-1)^{k-j}\perm{n+1}{k-j}=0$ ПРИ ВСЕХ~$j\ge0$, 
ОТСЮДА~$n!=0$ ПРИ ЛЮБОМ~$n\ge0$. нЕ ДОПУСТИЛ ЛИ ОН КАКОЙ-НИБУДЬ ОШИБКИ?

\ex[вм40] яВЛЯЕТСЯ ЛИ РАСПРЕДЕЛЕНИЕ ВЕРОЯТНОСТЕЙ ДЛЯ ОТРЕЗКОВ, 
ЗАДАВАЕМОЕ ФОРМУЛОЙ~(14), АСИМПТОТИЧЕСКИ НОРМАЛЬНЫМ? (сР.~С~УПР.~1.2.10-13.)

\ex[м24] (п.~а.~мАК-мАГОН ) пОКАЖИТЕ, ЧТО ВЕРОЯТНОСТЬ ТОГО, ЧТО 
ДЛИНА ПЕРВОГО ОТРЕЗКА ДОСТАТОЧНО ДЛИННОЙ ПЕРЕСТАНОВКИ ЕСТЬ~$l_1$, ДЛИНА 
ВТОРОГО 
%%63
ЕСТЬ~$l_2$,~\dots, А ДЛИНА $k\hbox{-ГО ОТРЕЗКА}\ge l_k$, РАВНА
$$
\det\pmatrix{
1/l_1! & 1/(l_1+l_2)! & 1/(l_1+l_2+l_3)! & \ldots & 1/(l_1+l_2+l_3+\cdots+l_k)!\cr
1      & 1/l_2!       & 1/(l_2+l_3)!     & \ldots & 1/(l_2+l_3+\cdots+l_k)! \cr
0      & 1            & 1/l_3!           & \ldots & 1/(l_3+\cdots+l_k)!\cr
\vdots &              &                  &        & \vdots\cr
0      & 0            & \ldots           & 1      & 1/l_k! \cr
}.
$$

\ex[M30] пУСТЬ~$h_k(z)=\sum p_{km} z^m$, ГДЕ~$p_{km}$---ВЕРОЯТНОСТЬ ТОГО, 
ЧТО ОБЩАЯ ДЛИНА ПЕРВЫХ $k$~ОТРЕЗКОВ (БЕСКОНЕЧНОЙ) СЛУЧАЙНОЙ 
ПОСЛЕДОВАТЕЛЬНОСТИ РАВНА~$m$. нАЙДИТЕ "ПРОСТЫЕ" ВЫРАЖЕНИЯ ДЛЯ~$h_1(z)$, 
$h_2(z)$ И ДЛЯ ПРОИЗВОДЯЩИХ ФУНКЦИЙ~$h(z, x)=\sum_k h_k(z) x^k$ ОТ ДВУХ ПЕРЕМЕННЫХ.

\ex[BM30] оПРЕДЕЛИТЕ АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ СРЕДНЕГО ЗНАЧЕНИЯ 
И ДИСПЕРСИИ РАСПРЕДЕЛЕНИЯ~$h_k(z)$ ИЗ ПРЕДЫДУЩЕГО УПРАЖНЕНИЯ ПРИ БОЛЬШИХ~$k$.

\ex[м40] пУСТЬ~$H_k(z)=\sum p_{km} z^m$,  ГДЕ~$p_{km}$---ВЕРОЯТНОСТЬ ТОГО, 
ЧТО ДЛИНА $k\hbox{-ГО}$~ОТРЕЗКА В СЛУЧАЙНОЙ (БЕСКОНЕЧНОЙ) 
ПОСЛЕДОВАТЕЛЬНОСТИ РАВНА~$m$. вЫРАЗИТЕ~$H_1(z)$, $H_2(z)$ И ПРОИЗВОДЯЩУЮ 
ФУНКЦИЮ~$H(z, x)=\sum_k H_k(z) x^k$ ОТ ДВУХ ПЕРЕМЕННЫХ ЧЕРЕЗ ИЗВЕСТНЫЕ ФУНКЦИИ.

\ex[M33] (п.а.~мАК-мАГОН.) оБОБЩИТЕ ФОРМУЛУ~(13) НА СЛУЧАЙ ПЕРЕСТАНОВОК 
МУЛЬТИМНОЖЕСТВА, ДОКАЗАВ, ЧТО ЧИСЛО ПЕРЕСТАНОВОК 
МУЛЬТИМНОЖЕСТВА~$\set{n_1\cdot 1, n_2\cdot 2,~\ldots, n_m\cdot m}$, 
ИМЕЮЩИХ РОВНО $k$~ОТРЕЗКОВ, РАВНО
$$
\sum_{0\le j \le k} (-1)^i \perm{n+1}{j} \perm{n_1-1+k-j}{n_1} 
\perm{n_2-1+k-j}{n_2} \cdots \perm{n_m-1+k-j}{n_m},
$$
ГДЕ~$n=n_1+n_2+\cdots+n_m$.

\ex[05] кАКИМ БУДЕТ СРЕДНЕЕ ЧИСЛО СТОПОК В ПАСЬЯНСЕ нЬЮКОМБА, 
ЕСЛИ ПОЛЬЗОВАТЬСЯ ОБЫЧНОЙ КОЛОДОЙ ДЛЯ БРИДЖА (ИЗ 52~КАРТ), ИГНОРИРУЯ 
СТАРШИНСТВО КАРТ, НО СЧИТАЯ, ЧТО
$$
\clubsuit < \diamondsuit < \heartsuit < \spadesuit?
$$

\ex[M17]  пЕРЕСТАНОВКА~$3\,1\,1\,1\,2\,3\,1\,4\,2\,3\,3\,4\,2\,2\,4\,4$ 
СОДЕРЖИТ $5$~ОТРЕЗКОВ; НАЙДИТЕ С ПОМОЩЬЮ ПРИВЕДЕННОГО В ТЕКСТЕ ПОСТРОЕНИЯ 
ДЛЯ УСЛОВИЯ СИММЕТРИИ мАК-мАГОНА СООТВЕТСТВУЮЩУЮ ПЕРЕСТАНОВКУ С $9\hbox{-Ю}$~ОТРЕЗКАМИ.

\rex[м21] \exhead(пЕРЕМЕЖАЮЩИЕСЯ ОТРЕЗКИ.) в КЛАССИЧЕСКОЙ ЛИТЕРАТУРЕ 
$19\hbox{-ГО}$~ВЕКА ПО КОМБИНАТОРНОМУ АНАЛИЗУ НЕ ИЗУЧАЛСЯ ВОПРОС ОБ 
ОТРЕЗКАХ В ПЕРЕСТАНОВКАХ, КОТОРЫЕ РАССМАТРИВАЕМ МЫ, НО БЫЛО НЕСКОЛЬКО 
СТАТЕЙ, ПОСВЯЩЕННЫХ ПОПЕРЕМЕННО ВОЗРАСТАЮЩИМ И УБЫВАЮЩИМ "ОТРЕЗКАМ". тАК, 
СЧИТАЛОСЬ, ЧТО ПЕРЕСТАНОВКА~$5\,3\,2\,4\,7\,6\,1\,8$ СОДЕРЖИТ $4$~ОТРЕЗКА
$$
5\,3\, 2, \quad     2\,4\,7,\quad    7\,6\,1,\quad    1\,8.
$$
(пЕРВЫЙ ОТРЕЗОК БУДЕТ ВОЗРАСТАЮЩИМ ИЛИ УБЫВАЮЩИМ В ЗАВИСИМОСТИ ОТ ТОГО,
$a_1<a_2$ ИЛИ~$a_1>a_2$; ТАКИМ ОБРАЗОМ, ПЕРЕСТАНОВКИ~$a_1\,a_2\ldots\, a_n$, 
$a_n\,\ldots\,a_2\,a_1$ И~$(n+1-a_1)\,(n+1-a_2)\ldots (n+1-a_n)$ ВСЕ 
СОДЕРЖАТ ОДИНАКОВОЕ ЧИСЛО ПЕРЕМЕЖАЮЩИХСЯ ОТРЕЗКОВ.) мАКСИМАЛЬНОЕ ЧИСЛО 
ОТРЕЗКОВ ЭТОГО ТИПА В ПЕРЕСТАНОВКЕ $n$~ЭЛЕМЕНТОВ РАВНО~$n-1$.

нАЙДИТЕ СРЕДНЕЕ ЧИСЛО ПЕРЕМЕЖАЮЩИХСЯ ОТРЕЗКОВ В СЛУЧАЙНОЙ 
ПЕРЕСТАНОВКЕ МНОЖЕСТВА~$\set{1, 2,~\ldots, n}$. 
[\emph{уКАЗАНИЕ:} РАЗБЕРИТЕ ВЫВОД ФОРМУЛЫ~(34).]

\ex[M30] пРОДОЛЖИМ ПРЕДЫДУЩЕЕ УПРАЖНЕНИЕ. пУСТЬ~$\Eul{n}{k}$---ЧИСЛО ПЕРЕСТАНОВОК
%%64
МНОЖЕСТВА~$\set{1, 2,~\ldots, n}$, КОТОРЫЕ ИМЕЮТ РОВНО 
$k$~ПЕРЕМЕЖАЮЩИХСЯ ОТРЕЗКОВ. нАЙДИТЕ РЕКУРРЕНТНОЕ СООТНОШЕНИЕ, С ПОМОЩЬЮ 
КОТОРОГО МОЖНО
ВЫЧИСЛИТЬ ТАБЛИЦУ ЗНАЧЕНИЙ~$\Eul{n}{k}$; НАЙДИТЕ ТАКЖЕ СООТВЕТСТВУЮЩЕЕ 
РЕКУРРЕНТНОЕ СООТНОШЕНИЕ ДЛЯ ПРОИЗВОДЯЩЕЙ 
ФУНКЦИИ~$G_n(z)=\sum_k \Eul{n}{k} z^k \big / n!$. иСПОЛЬЗУЯ ЭТО ПОСЛЕДНЕЕ 
РЕКУРРЕНТНОЕ СООТНОШЕНИЕ, НАЙДИТЕ ПРОСТУЮ ФОРМУЛУ ДЛЯ \emph{ДИСПЕРСИИ} ЧИСЛА 
ПЕРЕМЕЖАЮЩИХСЯ ОТРЕЗКОВ В СЛУЧАЙНОЙ ПЕРЕСТАНОВКЕ МНОЖЕСТВА~$\set{1,2,
~\ldots, n}$.

\ex[M25] сУЩЕСТВУЕТ ВСЕГО~$2^n$ ПОСЛЕДОВАТЕЛЬНОСТЕЙ $a_1\,a_2\,a_n$, ГДЕ 
КАЖДЫЙ ЭЛЕМЕНТ~$a_j$---ЛИБО~$0$, ЛИБО~$1$. сКОЛЬКО СРЕДИ НИХ 
ПОСЛЕДОВАТЕЛЬНОСТЕЙ, СОДЕРЖАЩИХ РОВНО $k$~ОТРЕЗКОВ (Т.~Е.~СОДЕРЖАЩИХ 
РОВНО~$k-1$  ЭЛЕМЕНТОВ~$a_j$, ТАКИХ, ЧТО~$a_j>a_{j+1}$)?

\ex[M27] сУЩЕСТВУЕТ ВСЕГО~$n!$ ПОСЛЕДОВАТЕЛЬНОСТЕЙ~$a_1\,a_2\,\ldots\,a_n$,
ГДЕ КАЖДЫЙ ЭЛЕМЕНТ~$a_j$---ЦЕЛОЕ ЧИСЛО, ЛЕЖАЩЕЕ В 
ДИАПАЗОНЕ~$0 \le a_j \le n-j$; СКОЛЬКО СРЕДИ НИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, 
СОДЕРЖАЩИХ РОВНО 
$k$~ОТРЕЗКОВ (Т.~Е.~СОДЕРЖАЩИХ РОВНО~$k-1$ ЭЛЕМЕНТОВ~$a_j$, ТАКИХ, ЧТО~$a_j>a_{j+1}$)?

\rex[M26] (дЖ.~рИОРДАН.) (А)~сКОЛЬКИМИ СПОСОБАМИ МОЖНО РАСПОЛОЖИТЬ 
$n$~НЕАТАКУЮЩИХ ЛАДЕЙ (Т.~Е.~НИКАКИЕ ДВЕ НЕ ДОЛЖНЫ НАХОДИТЬСЯ НА ОДНОЙ ВЕРТИКАЛИ
\picture{
 рИС.~4. нЕАТАКУЮЩИЕ ЛАДЬИ НА ШАХМАТНОЙ ДОСКЕ ПРИ ЗАДАННОМ ЧИСЛЕ 
 ЛАДЕЙ НИЖЕ ГЛАВНОЙ ДИАГОНАЛИ.
}
ИЛИ ГОРИЗОНТАЛИ) НА ШАХМАТНОЙ ДОСКЕ РАЗМЕРА~$n\times n$ ТАК, ЧТОБЫ 
РОВНО~$k$ ИЗ НИХ НАХОДИЛИСЬ НА ЗАДАННОЙ СТОРОНЕ ОТ ГЛАВНОЙ ДИАГОНАЛИ? 
(b)~сКОЛЬКИМИ СПОСОБАМИ МОЖНО РАСПОЛОЖИТЬ $k$~НЕАТАКУЮЩИХ ЛАДЕЙ НА 
ЗАДАННОЙ СТОРОНЕ ОТ ГЛАВНОЙ ДИАГОНАЛИ ШАХМАТНОЙ ДОСКИ РАЗМЕРА~$n\times n$?

нАПРИМЕР, НА РИС.~4 ПОКАЗАН ОДИН ИЗ $15619$~СПОСОБОВ РАСПОЛОЖИТЬ 
ВОСЕМЬ НЕАТАКУЮЩИХ ЛАДЕЙ НА ОБЫЧНОЙ ШАХМАТНОЙ ДОСКЕ С ТРЕМЯ ЛАДЬЯМИ НА 
НЕЗАШТРИХОВАННОМ УЧАСТКЕ НИЖЕ ГЛАВНОЙ ДИАГОНАЛИ, А ТАКЖЕ ОДИН ИЗ 
$1050$~СПОСОБОВ РАСПОЛОЖИТЬ ТРИ НЕАТАКУЮЩИЕ ЛАДЬИ НА ТРЕУГОЛЬНОЙ ДОСКЕ.

\rex[м21] гОВОРЯТ, ЧТО ПЕРЕСТАНОВКА ТРЕБУЕТ $k$~\emph{ЧТЕНИЙ,} ЕСЛИ ЕЕ 
НУЖНО ПРОСМОТРЕТЬ $k$~РАЗ, СЛЕВА НАПРАВО, ЧТОБЫ ПРОЧИТАТЬ ВСЕ ЭЛЕМЕНТЫ В 
НЕУБЫВАЮЩЕМ ПОРЯДКЕ. нАПРИМЕР, ПЕРЕСТАНОВКА
$$
4\,9\,1\,8\,2\,5\,3\,6\,7
$$
%%65
ТРЕБУЕТ ЧЕТЫРЕХ ЧТЕНИЙ: ПРИ ПЕРВОМ ЧТЕНИИ ПОЛУЧАЕМ~$1,2,3$; ПРИ 
ВТОРОМ---$4, 5, 6, 7$; ЗАТЕМ~$8$; ЗАТЕМ~$9$. нАЙДИТЕ СВЯЗЬ МЕЖДУ ОТРЕЗКАМИ 
И ЧТЕНИЯМИ.

\ex[M22] еСЛИ ПЕРЕСТАНОВКА~$a_1\,a_2\,\ldots\,a_n$ 
МНОЖЕСТВА~$\set{1, 2, ~\ldots, n}$ СОДЕРЖИТ $k$~ОТРЕЗКОВ И ТРЕБУЕТ $j$~ЧТЕНИЙ 
В СМЫСЛЕ УПР.~20, ТО ЧТО МОЖНО СКАЗАТЬ О ПЕРЕСТАНОВКЕ~$a_n\,\ldots\,a_2\,a_1$?

\ex[M26] (л.~кАРЛИЦ, д.~п.~рОЗЕЛЬ И~р.~а.~сКОУВИЛЛ.) пОКАЖИТЕ, ЧТО НЕ 
СУЩЕСТВУЕТ ПЕРЕСТАНОВКИ МНОЖЕСТВА~$\set{1, 2,~\ldots, n}$ С 
$n+1-r$~ОТРЕЗКАМИ, ТРЕБУЮЩЕЙ $s$~ЧТЕНИЙ, ЕСЛИ~$rs<n$, ОДНАКО ТАКАЯ 
ПЕРЕСТАНОВКА СУЩЕСТВУЕТ, ЕСЛИ~$n\ge n+1-r\ge s \ge 1$, $rs\ge n$.

\ex[BM42] (вАЛЬТЕР вЕЙССБЛЮМ.) "уДЛИНЕННЫЕ ОТРЕЗКИ" 
ПЕРЕСТАНОВКИ~$a_1\,a_2\,\ldots\,a_n$ ПОЛУЧАЮТСЯ, ЕСЛИ ВСТАВЛЯТЬ ВЕРТИКАЛЬНЫЕ 
ЧЕРТОЧКИ В ТЕХ МЕСТАХ, ГДЕ НАРУШАЕТСЯ УСТАНОВИВШАЯСЯ МОНОТОННОСТЬ; УДЛИНЕННЫЕ 
ОТРЕЗКИ БЫВАЮТ КАК ВОЗРАСТАЮЩИМИ, ТАК И УБЫВАЮЩИМИ В ЗАВИСИМОСТИ ОТ ТОГО, В 
КАКОМ ПОРЯДКЕ РАСПОЛОЖЕНЫ ПЕРВЫЕ ДВА ЭЛЕМЕНТА, ТАК ЧТО ДЛИНА КАЖДОГО УДЛИНЕННОГО 
ОТРЕЗКА (КРОМЕ, ВОЗМОЖНО, ПОСЛЕДНЕГО)${}\ge2$. нАПРИМЕР, 
ПЕРЕСТАНОВКА~$7\,5\vert6\,2\vert3\,8\,9\vert1\,4$ СОДЕРЖИТ ЧЕТЫРЕ УДЛИНЕННЫХ 
ОТРЕЗКА. нАЙДИТЕ СРЕДНИЕ ДЛИНЫ ПЕРВЫХ ДВУХ УДЛИНЕННЫХ ОТРЕЗКОВ БЕСКОНЕЧНОЙ 
ПЕРЕСТАНОВКИ И ДОКАЖИТЕ, ЧТО В ПРЕДЕЛЕ ДЛИНА УДЛИНЕННОГО ОТРЕЗКА РАВНА
$$
\left(1+\ctg{1\over2}\right)\Big/\left(3-\ctg{1\over2}\right)\approx 2.4202.
$$

\ex[M30] вЫРАЗИТЕ В ВИДЕ ФУНКЦИИ ОТ~$p$ СРЕДНЕЕ ЧИСЛО ОТРЕЗКОВ В 
ПОСЛЕДОВАТЕЛЬНОСТЯХ, ПОЛУЧЕННЫХ МЕТОДОМ, КОТОРЫЙ ОПИСАН В УПР.~5.1.1-18.

\subsubchap{*тАБЛО И ИНВОЛЮЦИИ} %5.1.4.
в ЗАКЛЮЧЕНИЕ НАШЕГО ОБЗОРА КОМБИНАТОРНЫХ СВОЙСТВ ПЕРЕСТАНОВОК ОБСУДИМ 
НЕКОТОРЫЕ ЗАМЕЧАТЕЛЬНЫЕ ОТНОШЕНИЯ, СВЯЗЫВАЮЩИЕ ПЕРЕСТАНОВКИ С МАССИВАМИ 
ЦЕЛЫХ ЧИСЕЛ, НАЗЫВАЕМЫМИ ТАБЛО. \dfn{тАБЛО яНГА ФОРМЫ~$(n_1, n_2,~\ldots, n_m)$,}  
ГДЕ~$n_1\ge n_2 \ge \ldots \ge n_m \ge 0$, ЭТО РАСПОЛОЖЕНИЕ 
$n_1+n_2+\cdots+n_m$~РАЗЛИЧНЫХ ЦЕЛЫХ ЧИСЕЛ В МАССИВ СТРОК, ВЫРОВНЕННЫХ 
ПО ЛЕВОМУ КРАЮ, ГДЕ В $i\hbox{-Й}$~СТРОКЕ СОДЕРЖИТСЯ $n_i$~ЭЛЕМЕНТОВ; 
ПРИ ЭТОМ В КАЖДОЙ СТРОКЕ ЭЛЕМЕНТЫ ВОЗРАСТАЮТ СЛЕВА НАПРАВО, А ЭЛЕМЕНТЫ 
КАЖДОГО СТОЛБЦА ВОЗРАСТАЮТ СВЕРХУ ВНИЗ. нАПРИМЕР,
$$
\tableau{
1 & 2 & 5 & 9 & 10 & 15 \cr
3 & 6 & 7 & 13 \cr
4 & 8 & 12 & 14 \cr
11 \cr
}
\eqno(1)
$$
---ТАБЛО яНГА ФОРМЫ~$(6, 4, 4, 1)$. тАКИЕ РАСПОЛОЖЕНИЯ ВВЕЛ аЛЬФРЕД яНГ 
В~1900~Г. В КАЧЕСТВЕ ВСПОМОГАТЕЛЬНОГО СРЕДСТВА ПРИ ИЗУЧЕНИИ МАТРИЧНОГО 
ПРЕДСТАВЛЕНИЯ ПЕРЕСТАНОВОК. 
[сМ., НАПРИМЕР, D.~е.~Rutherford, Substitutional Analysis (New York: Hafiier,
%%66
1968)]. дЛЯ КРАТКОСТИ МЫ БУДЕМ ВМЕСТО "ТАБЛО яНГА" ГОВОРИТЬ ПРОСТО "ТАБЛО".

\dfn{иНВОЛЮЦИЯ}---ЭТО ПЕРЕСТАНОВКА, ОБРАТНАЯ САМОЙ СЕБЕ. нАПРИМЕР, 
СУЩЕСТВУЕТ 10 ИНВОЛЮЦИЙ МНОЖЕСТВА~$\set{1, 2, 3, 4}$:
$$
\displaynarrow{
\pmatrix{
1 & 2 & 3 & 4 \cr
1 & 2 & 3 & 4 \cr
}
\pmatrix{
1 & 2 & 3 & 4 \cr
2 & 1 & 3 & 4 \cr
}
\pmatrix{
1 & 2 & 3 & 4 \cr
3 & 2 & 1 & 4 \cr
}
\pmatrix{
1 & 2 & 3 & 4 \cr
4 & 2 & 3 & 1 \cr
}
\pmatrix{
1 & 2 & 3 & 4 \cr
1 & 3 & 2 & 4 \cr
}
\cr
\pmatrix{
1 & 2 & 3 & 4 \cr
1 & 4 & 3 &  2\cr
}
\pmatrix{
1 & 2 & 3 & 4 \cr
1 & 2 & 4 & 3 \cr
}
\pmatrix{
1 & 2 & 3 & 4 \cr
2 & 1 & 4 & 3 \cr
}
\pmatrix{
1 & 2 & 3 & 4 \cr
3 & 4 & 1 & 2 \cr
}
\pmatrix{
1 & 2 & 3 & 4 \cr
4 & 3 & 2 & 1 \cr
}
}
\eqno(2)
$$
тЕРМИН "ИНВОЛЮЦИЯ" ПЕРВОНАЧАЛЬНО ИСПОЛЬЗОВАЛСЯ В КЛАССИЧЕСКИХ ЗАДАЧАХ 
ГЕОМЕТРИИ; ИНВОЛЮЦИИ В ОБЩЕМ СМЫСЛЕ, РАССМАТРИВАЕМЫЕ ЗДЕСЬ, БЫЛИ ВПЕРВЫЕ 
ИЗУЧЕНЫ X.~а.~рОТЕ, КОГДА ОН ВВЕЛ ПОНЯТИЕ ОБРАТНОЙ ПЕРЕСТАНОВКИ (СМ.~П.~5.1.1).

мОЖЕТ ПОКАЗАТЬСЯ СТРАННЫМ, ЧТО МЫ РАССМАТРИВАЕМ ТАБЛО И ИНВОЛЮЦИИ ВМЕСТЕ, 
НО СУЩЕСТВУЕТ УДИВИТЕЛЬНАЯ СВЯЗЬ МЕЖДУ ЭТИМИ ПОНЯТИЯМИ, НЕ ИМЕЮЩИМИ, 
КАЗАЛОСЬ БЫ, ДРУГ К ДРУГУ НИКАКОГО ОТНОШЕНИЯ: \dfn{ЧИСЛО ИНВОЛЮЦИЙ 
МНОЖЕСТВА~$\set{1, 2,~\ldots, n}$ РАВНО ЧИСЛУ ТАБЛО, КОТОРЫЕ МОЖНО 
СФОРМИРОВАТЬ ИЗ ЭЛЕМЕНТОВ~$\set{1,2,~\ldots, n}$.} нАПРИМЕР, 
ИЗ~$\set{1, 2, 3, 4}$ МОЖНО СФОРМИРОВАТЬ РОВНО 10~ТАБЛО
$$
\displaynarrow{
\tableau{1& 2 & 3 & 4 \cr}\quad
\tableau{
1 & 3 & 4 \cr
2 \cr
}\quad
\tableau{
1 & 4 \cr
2 \cr
3 \cr
}\quad
\tableau{
1 & 3 \cr
2 \cr
4 \cr
}\quad
\tableau{
1 & 2 & 4 \cr
3 \cr
}\quad
\cr
\tableau{ 
1 & 2 \cr
3 \cr
4 \cr
 }\quad
\tableau{
1 & 2 & 3 \cr
4 \cr
}\quad
\tableau{
1 & 3 \cr
2  & 4 \cr
}\quad
\tableau{
1 & 2 \cr
3 & 4 \cr
}\quad
\tableau{
1 \cr
2 \cr
3 \cr
4 \cr
}\quad
\cr
}
\eqno (3)
$$
ЧТО СООТВЕТСТВУЕТ 10~ИНВОЛЮЦИЯМ~(2).

эТА СВЯЗЬ МЕЖДУ ИНВОЛЮЦИЯМИ И ТАБЛО ОТНЮДЬ НЕ ОЧЕВИДНА, И, ПО-ВИДИМОМУ, НЕ 
СУЩЕСТВУЕТ ПРОСТОГО СПОСОБА ЕЕ ДОКАЗАТЬ. дОКАЗАТЕЛЬСТВО, КОТОРОЕ МЫ 
ОБСУДИМ, ВКЛЮЧАЕТ ИНТЕРЕСНЫЙ АЛГОРИТМ ПОСТРОЕНИЯ ТАБЛО, ОБЛАДАЮЩИЙ И 
НЕКОТОРЫМИ ДРУГИМИ НЕОЖИДАННЫМИ СВОЙСТВАМИ; ОН ОСНОВАН НА ОСОБОЙ 
ПРОЦЕДУРЕ ВСТАВКИ В ТАБЛО НОВЫХ ЭЛЕМЕНТОВ.

%% 67

пРЕДПОЛОЖИМ, НАПРИМЕР, ЧТО НУЖНО ВСТАВИТЬ ЭЛЕМЕНТ~8 В ТАБЛО
$$
\tableau{
1 & 3 & 5 & 9 & 12 & 16 \cr
2 & 6 & 10 & 15 \cr
4 & 13 & 14 \cr
11 \cr
17 \cr
}
\eqno (4)
$$
мЕТОД, КОТОРЫМ МЫ БУДЕМ ПОЛЬЗОВАТЬСЯ, СОСТОИТ В ТОМ, ЧТОБЫ СНАЧАЛА 
ПОМЕСТИТЬ~8 В $1\hbox{-Ю}$~СТРОКУ, В КЛЕТКУ, РАНЕЕ ЗАНИМАЕМУЮ~$9$,
ПОСКОЛЬКУ~$9$---НАИМЕНЬШИЙ ИЗ ЭЛЕМЕНТОВ ЭТОЙ СТРОКИ, 
БОЛЬШИХ~$8$. эЛЕМЕНТ~$9$ "ВЫТЕСНЯЕТСЯ" ВНИЗ, В СТРОКУ~$2$, ГДЕ ОН 
ЗАМЕЩАЕТ~$10$. зАТЕМ~$10$ "ВЫТЕСНЯЕТ"~$13$ ИЗ $3\hbox{-Й}$~СТРОКИ В 
$4\hbox{-Ю}$ И, ПОСКОЛЬКУ В $4\hbox{-Й}$~СТРОКЕ НЕТ ЭЛЕМЕНТА БОЛЬШЕ~$13$, 
ПРОЦЕСС ЗАВЕРШАЕТСЯ ДОБАВЛЕНИЕМ~$13$ В ПРАВЫЙ КОНЕЦ СТРОКИ~$4$. нАШЕ ТАБЛО 
ПРЕОБРАЗОВАЛОСЬ В
$$
\tableau{
1 & 3 & 5 & 8 & 12 & 16 \cr
2 & 6 & 9 & 15 \cr
4 & 10 & 14 \cr
11 & 13 \cr
17 \cr
}
\eqno (5)
$$

тОЧНОЕ ОПИСАНИЕ ЭТОГО ПРОЦЕССА С ДОКАЗАТЕЛЬСТВОМ ТОГО, ЧТО ОН ВСЕГДА 
СОХРАНЯЕТ СВОЙСТВА ТАБЛО, СОДЕРЖИТСЯ В АЛГОРИТМЕ~I.

\alg I.(вСТАВКА В ТАБЛО.) пУСТЬ~$P=(P_{ij})$---ТАБЛО ЦЕЛЫХ ПОЛОЖИТЕЛЬНЫХ 
ЧИСЕЛ, А~$x$---ЦЕЛОЕ ПОЛОЖИТЕЛЬНОЕ ЧИСЛО, НЕ СОДЕРЖАЩЕЕСЯ В~$P$. эТОТ 
АЛГОРИТМ ПРЕОБРАЗУЕТ~$P$ В ДРУГОЕ ТАБЛО, СОДЕРЖАЩЕЕ~$x$ НАРЯДУ С ИСХОДНЫМИ 
ЭЛЕМЕНТАМИ~$P$. нОВОЕ ТАБЛО ИМЕЕТ ТУ ЖЕ ФОРМУ, ЧТО И СТАРОЕ, С ТОЙ ЛИШЬ 
РАЗНИЦЕЙ, ЧТО НА ПЕРЕСЕЧЕНИИ СТРОКИ~$s$ И СТОЛБЦА~$t$ ПОЯВИЛСЯ НОВЫЙ 
ЭЛЕМЕНТ, ГДЕ~$s$ И~$t$---ВЕЛИЧИНЫ, ОПРЕДЕЛЯЕМЫЕ АЛГОРИТМОМ.

(в ЭТОМ АЛГОРИТМЕ ЗАМЕЧАНИЯ В КРУГЛЫХ СКОБКАХ ПРЕДНАЗНАЧЕНЫ ДЛЯ 
ДОКАЗАТЕЛЬСТВА ЕГО ПРАВИЛЬНОСТИ, ПОСКОЛЬКУ ПО ИНДУКЦИИ ЛЕГКО ПРОВЕРИТЬ, 
ЧТО ЭТИ ЗАМЕЧАНИЯ СПРАВЕДЛИВЫ И ЧТО МАССИВ~$P$ ПРОДОЛЖАЕТ ОСТАВАТЬСЯ 
ТАБЛО НА ПРОТЯЖЕНИИ ВСЕГО ПРОЦЕССА. дЛЯ УДОБСТВА БУДЕМ ПРЕДПОЛАГАТЬ, ЧТО 
ТАБЛО ОГРАНИЧЕНО
%% 68
НУЛЯМИ СВЕРХУ И СЛЕВА И СИМВОЛАМИ~$\infty$ СПРАВА И СНИЗУ, ТАК 
ЧТО ЭЛЕМЕНТ~$P_{ij}$ ОПРЕДЕЛЕН ПРИ ВСЕХ~$i$,~$j\ge 0$. еСЛИ ВВЕСТИ ОТНОШЕНИЕ
$$
a \simlt b \rem{ТОГДА И ТОЛЬКО ТОГДА, КОГДА~$a<b$ ИЛИ~$a=b=\infty$,}
\eqno (6)
$$
ТО НЕРАВЕНСТВА ДЛЯ ТАБЛО МОЖНО ВЫРАЗИТЬ В УДОБНОЙ ФОРМЕ:
$$
\displaynarrow{
P_{ij}=0, \rem{ЕСЛИ~$i=0$ ИЛИ~$j=0$;}\cr
P_{ij}\simlt P_{i(j+1)} \rand P_{ij} \simlt P_{(i+1)j} 
\rem{ПРИ ВСЕХ~$i, j\ge 0$.}\cr
}
\eqno(7)
$$
уТВЕРЖДЕНИЕ "$x\notin P$" ОЗНАЧАЕТ, ЧТО ЛИБО~$x=\infty$, ЛИБО~$x$ НЕ 
РАВНО~$P_{ij}$ НИ ПРИ КАКИХ~$i, j\ge 0$.)

\st[вВЕСТИ~$x$.] уСТАНОВИТЬ~$i\asg 1$, $x_1\asg x$, А $j$~УСТАНОВИТЬ 
РАВНЫМ НАИМЕНЬШЕМУ ЗНАЧЕНИЮ, ТАКОМУ, ЧТО~$P_{1j}=\infty$.

\st[нАЙТИ~$x_{i+1}$.] (в ЭТОТ МОМЕНТ~$P_{(i-1)j} < x_i < P_{ij}$ 
И~$x_i\notin P$.) еСЛИ ~$x_i<P_{i(j-1)}$, ТО УМЕНЬШИТЬ~$j$ НА~$1$ И 
ПОВТОРИТЬ ЭТОТ ШАГ. в ПРОТИВНОМ СЛУЧАЕ УСТАНОВИТЬ~$x_{i+1}\asg P_{ij}$  
И~$r_i\asg j$.

\st[зАМЕНИТЬ НА~$x_i$.] (тЕПЕРЬ~$P_{i(j-1)}< x_i < x_{i+1}=P_{ij}\simlt P_{i(j+1)}$, 
$P_{(i-1) j} < x_i < x_{i+1} = P_{ij} \simlt P_{(i+1)j}$ 
И~$r_i=j$.) уСТАНОВИТЬ~$P_{ij}\asg x_i$.

\st[$x_{i+1}=\infty$?] 
(тЕПЕРЬ~$P_{i(j-1)}<P_{ij}=x_i < x_{i+1} \simlt P_{i(j-1)}$, 
$P_{(i-1)j}<P_{ij}=x_i<x_{i+1}\simlt P_{(i+1)j}$, $r_i=j$ 
И~$x_{i+1}\notin P$.) еСЛИ~$x_{i+1}\ne \infty$, ТО УВЕЛИЧИТЬ~$i$ НА~$1$ И 
ВЕРНУТЬСЯ К ШАГУ~\stp{2}.

\st[оПРЕДЕЛИТЬ~$s$, $t$.] уСТАНОВИТЬ~$s\asg i$, $t\asg j$ И ЗАКОНЧИТЬ 
РАБОТУ АЛГОРИТМА. (к ЭТОМУ МОМЕНТУ ВЫПОЛНЯЮТСЯ УСЛОВИЯ
$$
P_{st}\ne\infty, P_{(s+1)t}=P_{s(t+1)}=\infty.)
\eqno(8)
$$
\algend

зАМЕТИМ, ЧТО ЭТОТ АЛГОРИТМ ОПРЕДЕЛЯЕТ "ПОСЛЕДОВАТЕЛЬНОСТЬ ВЫТЕСНЕНИИ"
$$
x=x_1<x_2<\ldots<x_s<x_{s+1}=\infty,
\eqno(9)
$$
А ТАКЖЕ ВСПОМОГАТЕЛЬНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ ИНДЕКСОВ СТОЛБЦОВ
$$
r_1\ge r_2 \ge \ldots \ge r_s = t;
\eqno(10)
$$
ПРИ ЭТОМ ЭЛЕМЕНТ~$P_{ir_i}$ МЕНЯЕТ СВОЕ ЗНАЧЕНИЕ С~$x_{i+1}$ НА~$x_i$, 
$1\le i \le s$. нАПРИМЕР, КОГДА В ТАБЛО~(4) ВСТАВЛЯЛСЯ ЭЛЕМЕНТ~$8$, 
ПОСЛЕДОВАТЕЛЬНОСТЬЮ ВЫТЕСНЕНИЙ БЫЛА~$8$, $9$, $10$, $13$, $\infty$, А 
ВСПОМОГАТЕЛЬНОЙ ПОСЛЕДОВАТЕЛЬНОСТЬЮ---$4$, $3$, $2$, $2$. мЫ МОГЛИ БЫ 
ПЕРЕФОРМУЛИРОВАТЬ АЛГОРИТМ ТАК, ЧТОБЫ ОН РАСХОДОВАЛ МЕНЬШЕ 
ВРЕМЕННОЙ ПАМЯТИ (НЕОБХОДИМО ХРАНИТЬ ТОЛЬКО ТЕКУЩИЕ ЗНАЧЕНИЯ~$j$, $x_i$, $x_{i+1}$);
ПОСЛЕДОВАТЕЛЬНОСТИ~(9) И~(10) БЫЛИ ВВЕДЕНЫ С ТОЙ ЛИШЬ ЦЕЛЬЮ, ЧТОБЫ МОЖНО 
БЫЛО ДОКАЗАТЬ НЕКОТОРЫЕ ИНТЕРЕСНЫЕ ФАКТЫ, КАСАЮЩИЕСЯ ЭТОГО АЛГОРИТМА.

оСНОВНОЕ СВОЙСТВО АЛГОРИТМА~I, КОТОРЫМ МЫ НЕ ПРЕМИНЕМ ВОСПОЛЬЗОВАТЬСЯ, 
СОСТОИТ В ТОМ, ЧТО АЛГОРИТМ МОЖНО "ПРОКРУТИТЬ" В ОБРАТНОМ НАПРАВЛЕНИИ: 
ПО ЗАДАННЫМ~$s$ И~$t$, ОПРЕДЕЛЕННЫМ
%% 69
В ШАГЕ~I5, МОЖНО ПРЕОБРАЗОВАТЬ~$P$ К ИСХОДНОМУ ВИДУ, НАЙДЯ И УДАЛИВ 
ЭЛЕМЕНТ~$x$, КОТОРЫЙ БЫЛ ВСТАВЛЕН. рАССМОТРИМ, НАПРИМЕР, (5), И ПУСТЬ 
НАМ ИЗВЕСТНО, ЧТО ЭЛЕМЕНТ~$13$ ЗАНИМАЕТ ПОЗИЦИЮ, КОТОРАЯ РАНЬШЕ БЫЛА 
ПУСТА. тОГДА ЭЛЕМЕНТ~$13$, ДОЛЖНО БЫТЬ, БЫЛ ВЫТЕСНЕН ВНИЗ ИЗ 3-Й СТРОКИ 
ЧИСЛОМ~$10$, ПОТОМУ ЧТО $10$---НАИБОЛЬШИЙ ЭЛЕМЕНТ В ЭТОЙ СТРОКЕ, 
МЕНЬШИЙ~$13$; АНАЛОГИЧНО, ЭЛЕМЕНТ~$10$, ПО-ВИДИМОМУ, БЫЛ ВЫТЕСНЕН ИЗ 2-Й 
СТРОКИ ЧИСЛОМ~$9$, КОТОРОЕ В СВОЮ ОЧЕРЕДЬ БЫЛО ВЫТЕСНЕНО ИЗ 1-Й СТРОКИ 
ЧИСЛОМ~$8$. тАКИМ ОБРАЗОМ, ОТ~(5) МОЖНО ВЕРНУТЬСЯ ОБРАТНО К~(4). в 
СЛЕДУЮЩЕМ АЛГОРИТМЕ ПОДРОБНО ОПИСАН ЭТОТ ПРОЦЕСС.

\alg D.(уДАЛЕНИЕ ИЗ ТАБЛО.) пО ЗАДАННОМУ ТАБЛО~$P$ И ЦЕЛЫМ ПОЛОЖИТЕЛЬНЫМ 
ЧИСЛАМ~$s$ И~$t$, УДОВЛЕТВОРЯЮЩИМ УСЛОВИЯМ~(8), ЭТОТ АЛГОРИТМ 
ПРЕОБРАЗУЕТ~$P$ В ДРУГОЕ ТАБЛО ПОЧТИ ТАКОЙ ЖЕ ФОРМЫ, НО С~$\infty$ НА 
ПЕРЕСЕЧЕНИИ СТОЛБЦА~$t$ И СТРОКИ~$s$. оПРЕДЕЛЕННЫЙ АЛГОРИТМОМ 
ЭЛЕМЕНТ~$x$ УДАЛЯЕТСЯ ИЗ ТАБЛО~$P$.

(кАК И В АЛГОРИТМЕ~I, ПОЯСНЕНИЯ В КРУГЛЫХ СКОБКАХ ВКЛЮЧЕНЫ ДЛЯ 
ОБЛЕГЧЕНИЯ ДОКАЗАТЕЛЬСТВА ТОГО, ЧТО МАССИВ~$P$ ПРОДОЛЖАЕТ ОСТАВАТЬСЯ 
ТАБЛО НА ПРОТЯЖЕНИИ ВСЕГО ПРОЦЕССА.)

\st[вВЕСТИ~$s$, $t$.] уСТАНОВИТЬ~$j\asg t$, $i\asg s$, $x_{s+1}\asg\infty$. 

\st[нАЙТИ~$x_i$.] (в ЭТОТ МОМЕНТ~$P_{ij}<x_{i+1}\simlt P_{(i+1)j}$ 
И~$x_{i+1}\notin P$.) еСЛИ~$P_{i(j+1)}<x_{i+1}$, ТО УВЕЛИЧИТЬ~$j$ НА~$1$ И 
ПОВТОРИТЬ ЭТОТ ШАГ. в ПРОТИВНОМ СЛУЧАЕ УСТАНОВИТЬ~$x_i\asg P_{ij}$ 
И~$r_i\asg j$.

\st[зАМЕНИТЬ НА~$x_{i+1}$.] (тЕПЕРЬ~$P_{i(j-1)}<P_{ij}=x_i<x_{i+1}\simlt P_{i(j+1)}$,
$P_{(i-1)j}<P_{ij}=x_i<x_{i+1}\simlt P_{(i+1)j}$ И~$r_i=j$.)   
уСТАНОВИТЬ~$P_{ij}\asg x_{i+1}$.

\st[$i=1$?] (тЕПЕРЬ~$P_{i(j-1)}<x_i<x_{i+1}=P_{ij}\simlt P_{i(j+1)}$,  
$P_{(i-1)j}<x_i<x_{i+1}=P_{ij}\simlt P_{(i+1)j}$ И~$r_i=j$.) еСЛИ~$i>1$, 
ТО УМЕНЬШИТЬ~$t$ НА~$1$ И ВЕРНУТЬСЯ К ШАГУ~\stp{2}.

\st[оПРЕДЕЛИТЬ~$x$.] уСТАНОВИТЬ~$x\asg x_1$ И ЗАКОНЧИТЬ РАБОТУ АЛГОРИТМА.
 (тЕПЕРЬ~$0 < x < \infty$.)
\algend

пОЯСНЕНИЯ К АЛГОРИТМАМ~I И~D, ЗАКЛЮЧЕННЫЕ В КРУГЛЫЕ СКОБКИ, НЕ ТОЛЬКО 
ПОЛЕЗНЫ ДЛЯ ДОКАЗАТЕЛЬСТВА ТОГО ФАКТА, ЧТО ЭТИ АЛГОРИТМЫ СОХРАНЯЮТ 
СТРУКТУРУ ТАБЛО, НО ОНИ ПОЗВОЛЯЮТ УБЕДИТЬСЯ, ЧТО 
\emph{АЛГОРИТМЫ~I И~D ВЗАИМНО ОБРАТНЫ.} еСЛИ СНАЧАЛА ВЫПОЛНИТЬ АЛГОРИТМ~I 
С ДАННЫМ ТАБЛО~$P$ И 
НЕКОТОРЫМ ЦЕЛЫМ ПОЛОЖИТЕЛЬНЫМ ЧИСЛОМ~$x\notin P$, ТО ОН ВСТАВИТ~$x$ В~$P$ 
И ОПРЕДЕЛИТ ЦЕЛЫЕ ПОЛОЖИТЕЛЬНЫЕ ЧИСЛА~$s$, $t$, УДОВЛЕТВОРЯЮЩИЕ 
УСЛОВИЯМ~(8). аЛГОРИТМ~D, ПРИМЕНЕННЫЙ К ПОЛУЧЕННОМУ РЕЗУЛЬТАТУ, 
ВОССТАНОВИТ ЗНАЧЕНИЯ~$x$ И ПЕРВОНАЧАЛЬНЫЙ ВИД~$P$. оБРАТНО, ЕСЛИ 
СНАЧАЛА ВЫПОЛНИТЬ АЛГОРИТМ~D С ДАННЫМ ТАБЛО~$P$ И НЕКОТОРЫМИ ЦЕЛЫМИ 
ПОЛОЖИТЕЛЬНЫМИ ЧИСЛАМИ~$s$, $t$, УДОВЛЕТВОРЯЮЩИМИ УСЛОВИЯМ~(8), ТО ОН 
МОДИФИЦИРУЕТ~$P$, УДАЛИВ НЕКОТОРОЕ ЦЕЛОЕ ПОЛОЖИТЕЛЬНОЕ ЧИСЛО~$x$. 
аЛГОРИТМ~I, ПРИМЕНЕННЫЙ К ПОЛУЧЕННОМУ РЕЗУЛЬТАТУ, ВОССТАНОВИТ ЗНАЧЕНИЯ~$s$,
 $t$ И ПЕРВОНАЧАЛЬНЫЙ ВИД~$P$.
%% 70
пРИЧИНА ЗАКЛЮЧАЕТСЯ В ТОМ, ЧТО СОДЕРЖАНИЕ ПОЯСНЕНИЙ К ШАГАМ~I3 И~D4 
СОВПАДАЕТ ТАК ЖЕ, КАК И К ШАГАМ~I4 И~D3; ОНИ ОДНОЗНАЧНО ОПРЕДЕЛЯЮТ 
ЗНАЧЕНИЕ~$j$. сЛЕДОВАТЕЛЬНО, ВСПОМОГАТЕЛЬНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ~(9), 
(10) ОДИНАКОВЫ, В ОБОИХ СЛУЧАЯХ.

тЕПЕРЬ МЫ ПОДГОТОВЛЕНЫ К ДОКАЗАТЕЛЬСТВУ ОСНОВНОГО СВОЙСТВА ТАБЛО.

\proclaim тЕОРЕМА~A. сУЩЕСТВУЕТ ВЗАИМНО ОДНОЗНАЧНОЕ СООТВЕТСТВИЕ МЕЖДУ 
МНОЖЕСТВОМ ВСЕХ ПЕРЕСТАНОВОК МНОЖЕСТВА~$\set{1, 2,~\ldots, n}$ И 
МНОЖЕСТВОМ ВСЕХ УПОРЯДОЧЕННЫХ ПАР ТАБЛО~$(P, Q)$, ГДЕ~$P$ 
И~$Q$---ТАБЛО ОДИНАКОВОЙ ФОРМЫ ИЗ ЭЛЕМЕНТОВ~$\set{1, 2,~\ldots, n}$.

(пРИМЕР К ЭТОЙ ТЕОРЕМЕ СОДЕРЖИТСЯ В ПРИВЕДЕННОМ НИЖЕ ДОКАЗАТЕЛЬСТВЕ.)

\proof уДОБНЕЕ ДОКАЗАТЬ НЕСКОЛЬКО БОЛЕЕ ОБЩИЙ РЕЗУЛЬТАТ. пО 
ПРОИЗВОЛЬНОМУ ДВУСТРОЧНОМУ МАССИВУ
$$
\pmatrix{
q_1 & q_2 & \ldots & q_n \cr
p_1 & p_2 & \ldots & p_n \cr
},\qquad
\matrix{q_1 < q_2 < \ldots < q_n,\hfill\cr
p_1, p_2, \ldots, p_n \hbox{ ВСЕ РАЗНЫЕ},\hfill\cr
}
\eqno (11)
$$
ПОСТРОИМ СООТВЕТСТВУЮЩИЕ ДВА ТАБЛО~$P$ И~$Q$, ГДЕ $P$~СОСТОИТ 
ИЗ ЭЛЕМЕНТОВ~$\set{p_1, p_2,~\ldots, p_n}$, А~$Q$---ИЗ 
ЭЛЕМЕНТОВ~$\set{q_1, q_2,~\ldots, q_n}$, ПРИЧЕМ~$P$ И~$Q$ ИМЕЮТ ОДИНАКОВУЮ ФОРМУ.

пУСТЬ~$P$ И~$Q$ ВНАЧАЛЕ ПУСТЫ. пРИ~$i=1$, $2$,~\dots, $n$ (ИМЕННО В ТАКОМ 
ПОРЯДКЕ) ПРОДЕЛАЕМ СЛЕДУЮЩУЮ ОПЕРАЦИЮ: ВСТАВИМ~$P_i$ В ТАБЛО~$P$ ПРИ 
ПОМОЩИ АЛГОРИТМА~I; ЗАТЕМ УСТАНОВИМ~$Q_{st}\asg q_l$, ГДЕ~$s$ И~$t$ 
ОПРЕДЕЛЯЮТ ВНОВЬ ЗАПОЛНЕННУЮ ПОЗИЦИЮ В~$P$.

нАПРИМЕР, ЕСЛИ ЗАДАНА ПЕРЕСТАНОВКА~$
\pmatrix{
1 & 3 & 5 & 6 & 8 \cr
7 & 2 & 9 & 5 & 3 \cr
}$, ДЕЙСТВУЕМ СЛЕДУЮЩИМ ОБРАЗОМ:

{\tdim=\hsize \advance\tdim by -\parindent \divide\tdim by 3
\def\+#1\cr{\line{\indent\vbox{\halign{\hbox to \tdim{##\hfil}&\hbox to \tdim{##\hfil}&\hbox to \tdim{##\hfil}\cr#1\cr}}\hfill}\smallskip}
\vskip\abovedisplayskip
\+ &  $P$ \hfil & $Q$ \hfil \cr
\+ вСТАВКА~7: &
\tableau{
 7 \cr
} & 
\tableau{
1 \cr
}\cr
\+ вСТАВКА~2: &
\tableau{
2 \cr
7 \cr
} &
\tableau {
1 \cr
3 \cr
}
\cr
\+ вСТАВКА~9: &
\tableau{
2 & 9 \cr
7 \cr
} &
\tableau{
1 & 5 \cr
3 \cr
}
\cr
%% 71
\+ вСТАВКА~5: &
\tableau{
2 & 5 \cr
7 & 9 \cr
} &
\tableau{
1 & 5 \cr
3 & 6 \cr
} \cr
\rightline{(12)}
\+ вСТАВКА~3: &
\tableau{
2& 3 \cr
5 & 9 \cr
7\cr
} &
\tableau{
1 & 5 \cr
3 & 6 \cr
8 \cr
} \cr
\vskip\belowdisplayskip
}

сЛЕДОВАТЕЛЬНО, ПАРА ТАБЛО~$(P, Q)$, СООТВЕТСТВУЮЩАЯ ПЕРЕСТАНОВКЕ
$\pmatrix{
1 & 3 & 5 & 6 & 8 \cr
7 & 2 & 9 & 5 & 3 \cr
}$, ТАКОВА:
$$
P=\tableau{
2 & 3 \cr
5 & 9 \cr
7 \cr
}\,, \qquad
Q=\tableau{
1 & 5 \cr
3 & 6 \cr
8 \cr
}\,.
\eqno(13)
$$

иЗ ПОСТРОЕНИЯ ЯСНО, ЧТО~$P$ И~$Q$ ВСЕГДА ИМЕЮТ ОДИНАКОВУЮ ФОРМУ. кРОМЕ 
ТОГО, ПОСКОЛЬКУ ЭЛЕМЕНТЫ ВСЕГДА ДОБАВЛЯЮТСЯ НА ГРАНИЦУ~$Q$ И В 
ВОЗРАСТАЮЩЕМ ПОРЯДКЕ, ТО~$Q$---ТАБЛО.

оБРАТНО, ЕСЛИ ЗАДАНЫ ДВА ТАБЛО ОДИНАКОВОЙ ФОРМЫ, ТО СООТВЕТСТВУЮЩИЙ 
ДВУСТРОЧНЫЙ МАССИВ~(11) МОЖНО ПОСТРОИТЬ ТАК. пУСТЬ
$$
q_1 < q_2 < \ldots < q_n
$$%
---ЭЛЕМЕНТЫ~$Q$. пУСТЬ ПРИ~$i=n$,~\dots, $2$, $1$ (ИМЕННО В ТАКОМ ПОРЯДКЕ) 
$p_i$---ЭЛЕМЕНТ~$x$, КОТОРЫЙ УДАЛЯЕТСЯ ИЗ~$P$ ПО АЛГОРИТМУ~D С 
ИСПОЛЬЗОВАНИЕМ ЗНАЧЕНИЙ~$s$, $t$, ТАКИХ, ЧТО~$Q_{st}=q_i$.

нАПРИМЕР, ЕСЛИ ПРИМЕНИТЬ ЭТО ПОСТРОЕНИЕ К ТАБЛО~(13) И ПРОИЗВОДИТЬ 
ВЫЧИСЛЕНИЯ, ОБРАТНЫЕ~(12), ДО ТЕХ ПОР, ПОКА~$P$ НЕ ИСЧЕРПАЕТСЯ, ТО 
ПОЛУЧИТСЯ МАССИВ $\pmatrix{
1 & 3 & 5 & 6 & 8 \cr
7 & 2 & 9 & 5 & 3 \cr
}$.

пОСКОЛЬКУ АЛГОРИТМЫ~I И~D ВЗАИМНО ОБРАТНЫ, ТО ВЗАИМНО ОБРАТНЫ И ОПИСАННЫЕ 
ЗДЕСЬ ДВА ПОСТРОЕНИЯ; ТАКИМ ОБРАЗОМ, ТРЕБУЕМОЕ ВЗАИМНО ОДНОЗНАЧНОЕ 
СООТВЕТСТВИЕ УСТАНОВЛЕНО.
\proofend

сООТВЕТСТВИЕ, ОПРЕДЕЛЕННОЕ В ДОКАЗАТЕЛЬСТВЕ ТЕОРЕМЫ~A, ОБЛАДАЕТ 
МНОЖЕСТВОМ ПОРАЗИТЕЛЬНЫХ СВОЙСТВ, И ТЕПЕРЬ МЫ ПРИСТУПИМ К ВЫВОДУ 
НЕКОТОРЫХ ИЗ НИХ. уБЕДИТЕЛЬНАЯ ПРОСЬБА К ЧИТАТЕЛЮ, ПРЕЖДЕ ЧЕМ ДВИГАТЬСЯ 
ДАЛЬШЕ, ИСПЫТАТЬ СЕБЯ НА ПРИМЕРАХ ИЗ УПР.~1, ЧТОБЫ ОСВОИТЬСЯ С ЭТИМИ ПОСТРОЕНИЯМИ.

%%72

кАК ТОЛЬКО ЭЛЕМЕНТ ВЫТЕСНЕН ИЗ СТРОКИ~1 В СТРОКУ~2, ОН УЖЕ БОЛЬШЕ НЕ 
ВЛИЯЕТ НА СТРОКУ~1; КРОМЕ ТОГО, СТРОКИ~2, 3,~\dots{} СТРОЯТСЯ ИЗ 
ПОСЛЕДОВАТЕЛЬНОСТИ "ВЫТЕСНЕННЫХ" ЭЛЕМЕНТОВ ТОЧНО ТАК ЖЕ, КАК СТРОКИ~1, 2,~\dots{} 
СТРОЯТСЯ ИЗ ИСХОДНОЙ ПЕРЕСТАНОВКИ. эТИ ФАКТЫ НАВОДЯТ НА МЫСЛЬ О 
ТОМ, ЧТО НА ПОСТРОЕНИЕ В ТЕОРЕМЕ~A МОЖНО ВЗГЛЯНУТЬ ИНАЧЕ, ОБРАЩАЯ 
ВНИМАНИЕ ЛИШЬ НА ПЕРВЫЕ СТРОКИ~$P$ И~$Q$. нАПРИМЕР, ПЕРЕСТАНОВКА 
$\pmatrix{
1 & 3 & 5 & 6 & 8\cr
7 & 2 & 9 & 5 & 3 \cr
}$
ВЫЗЫВАЕТ СЛЕДУЮЩИЕ ДЕЙСТВИЯ НАД СТРОКОЙ~1 [СР.~С~(12)]:
$$
\vcenter{\halign{
#\hfil\bskip&\bskip #\hfil\bskip&\bskip$#$\hfil\cr
1: вСТАВИТЬ~$7$, & УСТАНОВИТЬ & Q_{11}\asg 1. \cr
3: вСТАВИТЬ~$2$, & ВЫТЕСНИТЬ~$7$. \cr
5: вСТАВИТЬ~$9$, & УСТАНОВИТЬ & Q_{12}\asg 5. \cr
6: вСТАВИТЬ~$5$, & ВЫТЕСНИТЬ~$9$. \cr
8: вСТАВИТЬ~$3$, & ВЫТЕСНИТЬ~$5$.\cr
}}
\eqno(14)
$$
тАКИМ ОБРАЗОМ, ПЕРВАЯ СТРОКА~$P$---ЭТО~$2~3$, А ПЕРВАЯ СТРОКА~$Q$---ЭТО~$1~5$. 
кРОМЕ ТОГО, ОСТАЛЬНЫЕ СТРОКИ~$P$ И~$Q$ СОСТАВЛЯЮТ ТАБЛО, СООТВЕТСТВУЮЩИЕ 
"ВЫТЕСНЕННОМУ" ДВУСТРОЧНОМУ МАССИВУ
$$
\pmatrix{
3 & 6 & 8 \cr
7 & 9 & 5 \cr
},
\eqno (15)
$$

чТОБЫ ПОНЯТЬ, КАК СТРОИТСЯ СТРОКА~1, МОЖНО ИЗУЧИТЬ ЭЛЕМЕНТЫ, ПОПАДАЮЩИЕ 
В ДАННЫЙ СТОЛБЕЦ ЭТОЙ СТРОКИ. бУДЕМ ГОВОРИТЬ, ЧТО ПАРА~$(q_i, p_i)$ 
ПРИНАДЛЕЖИТ КЛАССУ~$t$ ОТНОСИТЕЛЬНО ДВУСТРОЧНОГО МАССИВА
$$
\pmatrix{
q_1 & q_2 & \ldots & q_n \cr
p_1 & p_2 & \ldots & p_n \cr
},
\qquad\matrix{
q_1<q_2<\ldots<q_n,\hfill\cr
p_1, p_2, \ldots, p_n \hbox{ ВСЕ РАЗНЫЕ,}\hfill\cr
}
\eqno(16)
$$
ЕСЛИ~$p_i=P_{1t}$ ПОСЛЕ ПРИМЕНЕНИЯ АЛГОРИТМА~I ПОСЛЕДОВАТЕЛЬНО К~$p_1$, 
$p_2$,~\dots, $p_i$, НАЧИНАЯ С ПУСТОГО ТАБЛО~$P$. (нАПОМНИМ, ЧТО
АЛГОРИТМ~I ВСЕГДА ВСТАВЛЯЕТ ДАННЫЙ ЭЛЕМЕНТ В 1-Ю СТРОКУ.)

лЕГКО ВИДЕТЬ, ЧТО~$(q_i, p_i)$ ПРИНАДЛЕЖИТ КЛАССУ~1 ТОГДА И ТОЛЬКО ТОГДА, 
КОГДА $p_i$~ИМЕЕТ $(i-1)$~ИНВЕРСИЙ, 
Т.~Е.~$p_i=\min\set{p_1, p_2,~\ldots, p_i}$---"ЛЕВОСТОРОННИЙ МИНИМУМ". еСЛИ 
В МАССИВЕ~(16) ВЫЧЕРКНУТЬ СТОЛБЦЫ КЛАССА~1, ТО ПОЛУЧИТСЯ 
ДРУГОЙ ДВУСТРОЧНЫЙ МАССИВ:
$$
\pmatrix{
q'_1 & q'_2 & \ldots & q'_m \cr
p'_1 & p'_2 & \ldots & p'_m \cr
}
\eqno(17)
$$
ТАКОЙ, ЧТО ПАРА~$(q, p)$ ПРИНАДЛЕЖИТ КЛАССУ~$t$ ОТНОСИТЕЛЬНО~(17) ТОГДА И 
ТОЛЬКО ТОГДА, КОГДА ОНА ПРИНАДЛЕЖИТ КЛАССУ~$t+1$ ОТНОСИТЕЛЬНО 
МАССИВА~(16). оПЕРАЦИЯ ПЕРЕХОДА ОТ~(16) К~(17) СООТВЕТСТВУЕТ
%%73
УДАЛЕНИЮ КРАЙНЕЙ ЛЕВОЙ ПОЗИЦИИ СТРОКИ~1. эТО 
ДАЕТ СИСТЕМАТИЧЕСКИЙ СПОСОБ ОПРЕДЕЛЕНИЯ КЛАССОВ. нАПРИМЕР, В ПЕРЕСТАНОВКЕ 
$\pmatrix{
1 & 3 & 5 & 6 & 8 \cr
7 & 2 & 9 & 5 & 3 \cr
}$ 
ЛЕВОСТОРОННИМИ МИНИМУМАМИ ЯВЛЯЮТСЯ ЭЛЕМЕНТЫ~$7$ И~$2$, ТАК ЧТО 
КЛАСС~1---ЭТО~$\set{(1, 7), (3, 2)}$; В ОСТАВШЕМСЯ МАССИВЕ
$\pmatrix{
5 & 6 & 8 \cr
9 & 5 & 3 \cr
}$
ВСЕ ЭЛЕМЕНТЫ МИНИМАЛЬНЫ, ТАК ЧТО КЛАСС~2---ЭТО~$\set{(5, 9), (6, 5), (8, 3)}$. 
в "ВЫТЕСНЕННОМ" МАССИВЕ~(15) КЛАСС~1---ЭТО~$\set{(3, 7), (8, 5)}$, А 
КЛАСС~2---$\set{(6, 9)}$.

дЛЯ ЛЮБОГО ФИКСИРОВАННОГО~$t$ ЭЛЕМЕНТЫ КЛАССА~$t$ МОЖНО ПОМЕТИТЬ
$$
(q_{i_1}, p_{i_1}), \ldots, (q_{i_k}, p_{i_k}),
$$
ТАК ЧТОБЫ ВЫПОЛНЯЛИСЬ НЕРАВЕНСТВА
$$
\eqalign{
q_{i_1}<q_{i_2}<\ldots<q_{i_k},\cr
p_{i_1}>p_{i_2}>\ldots>p_{i_k},\cr
}
\eqno(18)
$$
ПОСКОЛЬКУ ПРИ РАБОТЕ АЛГОРИТМА ВСТАВКИ ПОЗИЦИЯ ТАБЛО~$P_{1t}$ ПРИНИМАЕТ 
УБЫВАЮЩУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ ЗНАЧЕНИЙ~$p_{i_1}$,~\dots, $p_{i_k}$. в КОНЦЕ ПОСТРОЕНИЯ
$$
p_{1t}=p_{i_k}, \quad Q_{1t}=q_{i_1},
\eqno(19)
$$
А ВЫТЕСНЕННЫЙ ДВУСТРОЧНЫЙ МАССИВ, КОТОРЫМ ОПРЕДЕЛЯЮТСЯ СТРОКИ~2, 3,~\dots{} 
ТАБЛО~$P$ И~$Q$, СОДЕРЖИТ СТОЛБЦЫ
$$
\pmatrix{
q_{i_2} & q_{i_3} & \ldots & q_{i_k} \cr
p_{i_1} & p_{i_2} & \ldots & p_{i_k-1}\cr
},
\eqno(20)
$$
А ТАКЖЕ ДРУГИЕ СТОЛБЦЫ, АНАЛОГИЧНЫМ ОБРАЗОМ ПОЛУЧЕННЫЕ ИЗ ДРУГИХ КЛАССОВ.

эТИ НАБЛЮДЕНИЯ ПРИВОДЯТ К ПРОСТОМУ МЕТОДУ ВЫЧИСЛЕНИЯ~$P$ И~$Q$ ВРУЧНУЮ 
(СМ.~УПР.~3), А ТАКЖЕ ПРЕДОСТАВЛЯЮТ СРЕДСТВА ДЛЯ ДОКАЗАТЕЛЬСТВА ОДНОГО 
ВЕСЬМА НЕОЖИДАННОГО РЕЗУЛЬТАТА.

\proclaim тЕОРЕМА~B. еСЛИ В ПОСТРОЕНИИ ИЗ ТЕОРЕМЫ~A ПЕРЕСТАНОВКА
$$
\pmatrix{
1 & 2 & \ldots & n \cr
a_1 & a_2 & \ldots & a_n \cr
}
$$
СООТВЕТСТВУЕТ ТАБЛО~$(P, Q)$, ТО ОБРАТНАЯ ЕЙ ПЕРЕСТАНОВКА СООТВЕТСТВУЕТ 
ТАБЛО~$(Q, P)$.

эТО ДОВОЛЬНО УДИВИТЕЛЬНЫЙ ФАКТ, ПОТОМУ ЧТО В ТЕОРЕМЕ~A ТАБЛО~$P$ И~$Q$ 
ФОРМИРУЮТСЯ СОВЕРШЕННО РАЗНЫМИ СПОСОБАМИ, И ОБРАТНАЯ ПЕРЕСТАНОВКА 
ПОЛУЧАЕТСЯ В РЕЗУЛЬТАТЕ ВЕСЬМА ПРИЧУДЛИВОЙ ПЕРЕТАСОВКИ СТОЛБЦОВ 
ДВУСТРОЧНОГО МАССИВА.

%% 74
\proof  пРЕДПОЛОЖИМ, У НАС ЕСТЬ ДВУСТРОЧНЫЙ МАССИВ~(16);
ПОМЕНЯВ МЕСТАМИ ЕГО СТРОКИ И ОТСОРТИРОВАВ СТОЛБЦЫ ТАК, ЧТОБЫ ЭЛЕМЕНТЫ 
НОВОЙ ВЕРХНЕЙ СТРОКИ РАСПОЛОЖИЛИСЬ В НЕУБЫВАЮЩЕМ ПОРЯДКЕ, ПОЛУЧИМ 
"ОБРАТНЫЙ" МАССИВ
$$
\eqalign{
\pmatrix{
q_1 & q_2 & \ldots & q_n \cr
p_1 & p_2 & \ldots & p_n \cr
}^{-1}&=
\pmatrix{
p_1 & p_2 & \ldots & p_n \cr
q_1 & q_2 & \ldots & q_n \cr
}=\cr
&=\pmatrix{
p'_1 & p'_2 & \ldots & p'_n \cr
q'_1 & q'_2 & \ldots & q'_n \cr
},\qquad
\matrix{
p'_1 < p'_2 < \ldots < p'_n; \hfill\cr
q'_1, q'_2, \ldots, q'_n \hbox{ ВСЕ РАЗНЫЕ.}\hfill\cr
}\cr
}
\eqno(21)
$$
пОКАЖЕМ, ЧТО ЭТА ОПЕРАЦИЯ СООТВЕТСТВУЕТ ЗАМЕНЕ~$(P, Q)$ НА~$(Q, P)$ В 
ПОСТРОЕНИИ ИЗ ТЕОРЕМЫ~A.

в УПР.~2 НАШИ ЗАМЕЧАНИЯ ОБ ОПРЕДЕЛЕНИИ КЛАССОВ ПЕРЕФОРМУЛИРОВАНЫ ТАКИМ 
ОБРАЗОМ, ЧТО КЛАСС, К КОТОРОМУ ОТНОСИТСЯ ПАРА~$(q_i, p_i)$, НЕ ЗАВИСИТ ОТ 
ТОГО ФАКТА, ЧТО ЭЛЕМЕНТЫ~$q_1$, $q_2$,~\dots, $q_n$ РАСПОЛОЖЕНЫ В 
ВОЗРАСТАЮЩЕМ ПОРЯДКЕ. пОСКОЛЬКУ РЕЗУЛЬТИРУЮЩИЕ УСЛОВИЯ СИММЕТРИЧНЫ 
ОТНОСИТЕЛЬНО~$p$ И~$q$, ТО ОПЕРАЦИЯ~(21) НЕ НАРУШАЕТ СТРУКТУРУ КЛАССОВ; 
ЕСЛИ~$(q, p)$ ПРИНАДЛЕЖИТ КЛАССУ~$t$ ОТНОСИТЕЛЬНО~(16), ТО~$(p, q)$ 
ПРИНАДЛЕЖИТ КЛАССУ~$t$ ОТНОСИТЕЛЬНО~(21). пОЭТОМУ, ЕСЛИ РАЗМЕСТИТЬ 
ЭЛЕМЕНТЫ ЭТОГО ПОСЛЕДНЕГО КЛАССА~$t$ ТАК, ЧТОБЫ
$$
\eqalign{
p_{i_k}<\ldots< p_{i_2} < p_{i_1}, \cr
q_{i_k}>\ldots> q_{i_2} > q_{i_1}, \cr
}
\eqno(22)
$$
[СР.~С~(18)], ТО ПОЛУЧИМ
$$
P_{1t}=q_{i_1}, Q_{1t}=p_{i_k},
\eqno (23)
$$
КАК В~(19), А СТОЛБЦЫ
$$
\pmatrix{
p_{i_{k-1}} & \ldots & p_{i_2} & p_{i_1} \cr
q_{i_k} & \ldots & q_{i_3} & q_{i_2} \cr
}
\eqno(24)
$$
ВОЙДУТ В ВЫТЕСНЕННЫЙ МАССИВ, КАК В~(20). сЛЕДОВАТЕЛЬНО, ПЕРВЫЕ 
СТРОКИ~$P$ И~$Q$ МЕНЯЮТСЯ МЕСТАМИ. кРОМЕ ТОГО, ВЫТЕСНЕННЫЙ ДВУСТРОЧНЫЙ 
МАССИВ ДЛЯ~(21) ЯВЛЯЕТСЯ ОБРАТНЫМ ПО ОТНОШЕНИЮ К ВЫТЕСНЕННОМУ ДВУСТРОЧНОМУ 
МАССИВУ ДЛЯ~(16), ТАК ЧТО ДОКАЗАТЕЛЬСТВО ЗАВЕРШАЕТСЯ ПРИМЕНЕНИЕМ 
ИНДУКЦИИ ПО ЧИСЛУ СТРОК В ТАБЛО.
\proofend

\proclaim сЛЕДСТВИЕ. кОЛИЧЕСТВО ТАБЛО, КОТОРЫЕ МОЖНО СФОРМИРОВАТЬ ИЗ 
ЭЛЕМЕНТОВ~$\set{1, 2,~\ldots, n}$, РАВНО КОЛИЧЕСТВУ ИНВОЛЮЦИЙ 
МНОЖЕСТВА~$\set{1, 2,~\ldots, n}$.

\proof еСЛИ~$\pi$---ИНВОЛЮЦИЯ, СООТВЕТСТВУЮЩАЯ ПАРЕ ТАБЛО~$(P, Q)$, 
ТО~$\pi=\pi^{-1}$ СООТВЕТСТВУЕТ ПАРЕ~$(Q, P)$. сЛЕДОВАТЕЛЬНО,
%% 75
$P=Q$. оБРАТНО, ЕСЛИ~$\pi$---КАКАЯ-ЛИБО ПЕРЕСТАНОВКА, 
СООТВЕТСТВУЮЩАЯ ПАРЕ~$(P, P)$, ТО~$\pi^{-1}$ ТОЖЕ СООТВЕТСТВУЕТ ПАРЕ~$(P,P)$;
ОТСЮДА~$\pi=\pi^{-1}$. тАКИМ ОБРАЗОМ, СУЩЕСТВУЕТ ВЗАИМНО 
ОДНОЗНАЧНОЕ СООТВЕТСТВИЕ МЕЖДУ ИНВОЛЮЦИЯМИ~$\pi$ И ТАБЛО~$P$.
\proofend

яСНО, ЧТО ЭЛЕМЕНТ В ЛЕВОМ ВЕРХНЕМ УГЛУ ТАБЛО ВСЕГДА НАИМЕНЬШИЙ. эТО 
НАВОДИТ НА МЫСЛЬ О ВОЗМОЖНОМ СПОСОБЕ СОРТИРОВКИ МНОЖЕСТВА ЧИСЕЛ. сНАЧАЛА 
МОЖНО СОСТАВИТЬ ИЗ НИХ ТАБЛО, МНОГОКРАТНО ПРИМЕНЯЯ АЛГОРИТМ~I, В 
РЕЗУЛЬТАТЕ НАИМЕНЬШИЙ ЭЛЕМЕНТ ОКАЖЕТСЯ В УГЛУ. зАТЕМ ЭТОТ НАИМЕНЬШИЙ 
ЭЛЕМЕНТ УДАЛЯЕТСЯ, А ОСТАЛЬНЫЕ ЭЛЕМЕНТЫ ПЕРЕРАЗМЕЩАЮТСЯ ТАК, ЧТОБЫ 
ОБРАЗОВАЛОСЬ ДРУГОЕ ТАБЛО; ПОТОМ УДАЛЯЕТСЯ НОВЫЙ МИНИМАЛЬНЫЙ ЭЛЕМЕНТ И Т.Д.

пОЭТОМУ ДАВАЙТЕ ПОСМОТРИМ, ЧТО ПРОИСХОДИТ, КОГДА МЫ УДАЛЯЕМ УГЛОВОЙ 
ЭЛЕМЕНТ ИЗ ТАБЛО
$$
\tableau{
1 & 3 & 5 & 8 & 12 & 16\cr
2 & 6 & 9 & 15\cr
4 & 10 & 14 \cr
11 & 13 \cr
17\cr
}
\eqno (25)
$$
пОСЛЕ УДАЛЕНИЯ~$1$ НА ОСВОБОДИВШЕЕСЯ МЕСТО НЕОБХОДИМО ПОСТАВИТЬ~$2$. 
зАТЕМ МОЖНО ПОДНЯТЬ~$4$ НА МЕСТО ДВОЙКИ, ОДНАКО~$11$ НЕЛЬЗЯ ПОДНЯТЬ НА 
МЕСТО~$4$, НО НА ЭТО МЕСТО МОЖНО ПОДВИНУТЬ~$10$, А ПОТОМ~$13$ НА 
МЕСТО~$10$. в ОБЩЕМ СЛУЧАЕ ПРИХОДИМ К СЛЕДУЮЩЕЙ ПРОЦЕДУРЕ.

\alg S.(уДАЛЕНИЕ УГЛОВОГО ЭЛЕМЕНТА.) эТОТ АЛГОРИТМ УДАЛЯЕТ ЭЛЕМЕНТ ИЗ 
ЛЕВОГО ВЕРХНЕГО УГЛА ТАБЛО~$P$ И ПЕРЕМЕЩАЕТ ОСТАЛЬНЫЕ ЭЛЕМЕНТЫ ТАК, ЧТОБЫ 
СОХРАНИЛИСЬ СВОЙСТВА ТАБЛО. иСПОЛЬЗУЮТСЯ ТЕ ЖЕ ОБОЗНАЧЕНИЯ, ЧТО И В 
АЛГОРИТМАХ~I И~D.

\st[нАЧАЛЬНАЯ УСТАНОВКА.] уСТАНОВИТЬ~$r\asg 1$, $s\asg 1$.

\st[кОНЕЦ?] еСЛИ~$P_{rs}=\infty$, ТО ПРОЦЕСС ЗАВЕРШЕН.

\st[сРАВНИТЬ.] еСЛИ~$P_{(r+1)s}\simlt P_{r(s+1)}$, ТО ПЕРЕЙТИ К 
ШАГУ~\stp{5}. (сРАВНИВАЕМ ЭЛЕМЕНТЫ СПРАВА И СНИЗУ ОТ СВОБОДНОГО МЕСТА И 
ПЕРЕДВИГАЕМ МЕНЬШИЙ ИЗ НИХ.)

\st[пОДВИНУТЬ ВЛЕВО.] уСТАНОВИТЬ~$P_{rs}\asg P_{r(s+1)}$, $s\asg s+1$  И 
ВЕРНУТЬСЯ К~\stp{3}.

\st[пОДВИНУТЬ ВВЕРХ.] уСТАНОВИТЬ~$P_{rs}\asg P_{(r+1)s}$, $r\asg r+1$ И 
ВЕРНУТЬСЯ К~\stp{2}.
\algend

лЕГКО ДОКАЗАТЬ, ЧТО ПОСЛЕ УДАЛЕНИЯ УГЛОВОГО ЭЛЕМЕНТА С ПОМОЩЬЮ 
АЛГОРИТМА~S, $P$---ПО-ПРЕЖНЕМУ ТАБЛО (СМ.~УПР.~10). тАКИМ
%%76
ОБРАЗОМ, ПРИМЕНЯЯ АЛГОРИТМ~S ДО ТЕХ ПОР, ПОКА~$P$ НЕ ИСЧЕРПАЕТСЯ, МОЖНО 
ПРОЧИТАТЬ ЕГО ЭЛЕМЕНТЫ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ. к СОЖАЛЕНИЮ, ЭТОТ АЛГОРИТМ 
СОРТИРОВКИ ОКАЗЫВАЕТСЯ НЕ СТОЛЬ ЭФФЕКТИВНЫМ, КАК ДРУГИЕ АЛГОРИТМЫ, КОТОРЫЕ 
НАМ ЕЩЕ ПРЕДСТОИТ РАССМОТРЕТЬ. мИНИМАЛЬНОЕ ВРЕМЯ ЕГО РАБОТЫ ПРОПОРЦИОНАЛЬНО~$n^{1.5}$;
АНАЛОГИЧНЫЕ АЛГОРИТМЫ, ИСПОЛЬЗУЮЩИЕ ВМЕСТО ТАБЛО ДЕРЕВЬЯ, ЗАТРАЧИВАЮТ 
ВРЕМЯ ПОРЯДКА~$n\log n$.

аЛГОРИТМ~S, ХОТЯ И НЕ ПРИВОДИТ К ОСОБЕННО ЭФФЕКТИВНОМУ АЛГОРИТМУ 
СОРТИРОВКИ, ОБЛАДАЕТ НЕКОТОРЫМИ ОЧЕНЬ ИНТЕРЕСНЫМИ СВОЙСТВАМИ.

\proclaim тЕОРЕМА~C. (м.~п.~шЮЦЕНБЕРЖЕ.) еСЛИ~$P$---ТАБЛО, ПОСТРОЕННОЕ, КАК 
В ТЕОРЕМЕ~A, ИЗ ПЕРЕСТАНОВКИ~$a_1\,a_2,\ldots\,a_n$, 
И~$a_i=\min\set{a_1, a_2, \ldots, a_n}$, ТО АЛГОРИТМ~S ПРЕОБРАЗУЕТ~$P$ В 
ТАБЛО, СООТВЕТСТВУЮЩЕЕ ПЕРЕСТАНОВКЕ~$a_1\,\ldots\,a_{i-1}\,a_{i+1}\,\ldots\,a_n$.

\proof сМ. УПР. 13.
\proofend

дАВАЙТЕ ПОСЛЕ ПРИМЕНЕНИЯ АЛГОРИТМА~S ПОМЕСТИМ НА ВНОВЬ ОСВОБОДИВШЕЕСЯ 
МЕСТО УДАЛЕННЫЙ ЭЛЕМЕНТ В СКОБКАХ, УКАЗАВ ТАКИМ ОБРАЗОМ, ЧТО НА САМОМ ДЕЛЕ 
ОН НЕ ЯВЛЯЕТСЯ ЧАСТЬЮ ТАБЛО. пРИМЕНИВ, НАПРИМЕР, ЭТУ ПРОЦЕДУРУ К 
ТАБЛО~(25), МЫ ПОЛУЧИЛИ БЫ
$$
\tableau{
2 & 3 & 5 & 8 & 12 & 16\cr
4 & 6 & 9 & 15\cr
10 & 13 & 14 \cr
11 & (1) \cr
17 \cr
}
$$
А ЕЩЕ ДВА ПРИМЕНЕНИЯ ПРИВОДЯТ К
$$
\tableau{
4 &  5 & 8 & 12 & 16 & (2)\cr
6 & 9 & 14 &15\cr
10 & 13 & (3) \cr
11 & (1) \cr
17\cr
}
$$
%% 77
пРОДОЛЖАЯ ДО ТЕХ ПОР, ПОКА ВСЕ ЭЛЕМЕНТЫ НЕ ОКАЖУТСЯ В СКОБКАХ, И УБРАВ 
СКОБКИ, ПОЛУЧИМ КОНФИГУРАЦИЮ
$$
\tableau{
17 & 15 & 14 & 13 & 11 & 2 \cr
16 & 10 & 6 & 4 \cr
12 & 5 & 3 \cr
9 & 1 \cr
8 \cr
}
\eqno(26)
$$
ИМЕЮЩУЮ ТУ ЖЕ ФОРМУ, ЧТО И ИСХОДНОЕ ТАБЛО~(25). эТУ КОНФИГУРАЦИЮ МОЖНО 
НАЗВАТЬ \dfn{ДВОЙСТВЕННЫМ ТАБЛО,} ПОТОМУ ЧТО ОНА ПОХОЖА НА ТАБЛО С ТОЙ 
ЛИШЬ РАЗНИЦЕЙ, ЧТО ПРИМЕНЯЕТСЯ "ДВОЙСТВЕННОЕ ОТНОШЕНИЕ ПОРЯДКА" ($<$ 
И~$>$ ПОМЕНЯЛИСЬ РОЛЯМИ). оБОЗНАЧИМ ДВОЙСТВЕННОЕ ТАБЛО, ПОЛУЧЕННОЕ ИЗ~$P$ 
ТАКИМ СПОСОБОМ, ЧЕРЕЗ~$P^S$.

тАБЛО~$P$ ОПРЕДЕЛЯЕТСЯ ИЗ~$P^S$ ЕДИНСТВЕННЫМ ОБРАЗОМ. в САМОМ ДЕЛЕ, 
ИСХОДНОЕ ТАБЛО МОЖНО ПОЛУЧИТЬ ИЗ~$P^S$ ПРИ ПОМОЩИ ТОГО ЖЕ САМОГО АЛГОРИТМА 
(С ОБРАТНЫМ ОТНОШЕНИЕМ ПОРЯДКА, ПОСКОЛЬКУ $P^S$---ДВОЙСТВЕННОЕ ТАБЛО). 
нАПРИМЕР, ПРИМЕНЕНИЕ К~(26) ДВУХ ШАГОВ ЭТОГО АЛГОРИТМА ДАЕТ
$$
\tableau{
15 & 14 & 13 & 11 & 2 & (16)\cr
12 & 10 & 6 & 4\cr
9 & 5 & 3 \cr
8 & 1 \cr
(17)\cr
}
$$
И В КОНЦЕ КОНЦОВ ОПЯТЬ ПОЛУЧАЕТСЯ ТАБЛО~(25). эТОТ ЗАМЕЧАТЕЛЬНЫЙ 
РЕЗУЛЬТАТ---ОДНО ИЗ СЛЕДСТВИЙ НАШЕЙ СЛЕДУЮЩЕЙ ТЕОРЕМЫ.

{\let\newpar=\par
\proclaim тЕОРЕМА D. (к.~шЕНСТЕД, м.~п.~шЮЦЕНБЕРЖЕ.) пУСТЬ
$$
\pmatrix{
q_1 & q_2 & \ldots & q_n \cr
p_1 & p_2 & \ldots & p_n \cr
}
\eqno(27)
$$
---ДВУСТРОЧНЫЙ МАССИВ, СООТВЕТСТВУЮЩИЙ ПАРЕ ТАБЛО~$(P, Q)$.
%% 78
{\medskip\narrower
\item{a)}еСЛИ ПОЛЬЗОВАТЬСЯ ДВОЙСТВЕННЫМ (ОБРАТНЫМ) ОТНОШЕНИЕМ ПОРЯДКА 
ДЛЯ~$q$, НО НЕ ДЛЯ~$p$, ТО ДВУСТРОЧНЫЙ МАССИВ
$$
\pmatrix{
q_n & \ldots & q_2 & q_1 \cr
p_n & \ldots & p_2 & p_1 \cr
}
\eqno(28)
$$
СООТВЕТСТВУЕТ ПАРЕ~$(P^T, (Q^S)^T)$.
\newpar
{\noindent \rm (кАК ОБЫЧНО, ЧЕРЕЗ~$T$ ОБОЗНАЧЕНА ОПЕРАЦИЯ ТРАНСПОНИРОВАНИЯ;
$P^T$---ТАБЛО, a~$(Q^S)^T$---ДВОЙСТВЕННОЕ ТАБЛО, ПОСКОЛЬКУ 
ЭЛЕМЕНТЫ~$q$ РАСПОЛОЖЕНЫ В ОБРАТНОМ ПОРЯДКЕ.)}
\newpar
\item{b)}еСЛИ ПОЛЬЗОВАТЬСЯ ДВОЙСТВЕННЫМ ОТНОШЕНИЕМ ПОРЯДКА ДЛЯ~$p$, НО НЕ 
ДЛЯ~$q$, ТО ДВУСТРОЧНЫЙ МАССИВ~(37) СООТВЕТСТВУЕТ ПАРЕ~$((P^S)^T, Q^T)$.
\newpar
\item{c)}еСЛИ ПОЛЬЗОВАТЬСЯ ДВОЙСТВЕННЫМ ОТНОШЕНИЕМ ПОРЯДКА КАК ДЛЯ~$p$, 
ТАК И ДЛЯ~$q$, ТО ДВУСТРОЧНЫЙ МАССИВ~(28) СООТВЕТСТВУЕТ ПАРЕ~$(P^S, Q^S)$.
\newpar}
\par
}

\proof нЕ ИЗВЕСТНО ПРОСТОГО ДОКАЗАТЕЛЬСТВА ЭТОЙ ТЕОРЕМЫ. тО, ЧТО 
СЛУЧАЙ~(a) СООТВЕТСТВУЕТ ПАРЕ~$(P^T, X)$, ГДЕ~$X$---НЕКОТОРОЕ ДВОЙСТВЕННОЕ 
ТАБЛО, ДОКАЗАНО В УПР.~6; СЛЕДОВАТЕЛЬНО, ПО ТЕОРЕМЕ~B, СЛУЧАЙ~(b) 
СООТВЕТСТВУЕТ ПАРЕ~$(Y, Q^T)$, ГДЕ~$Y$---НЕКОТОРОЕ ДВОЙСТВЕННОЕ ТАБЛО ТОЙ ЖЕ 
ФОРМЫ, ЧТО И~$P^T$.

пУСТЬ~$p_i=\min\set{p_1,~\ldots, p_n}$; ТАК КАК~$p_i$---"НАИБОЛЬШИЙ" 
ЭЛЕМЕНТ ПРИ ДВОЙСТВЕННОМ ОТНОШЕНИИ ПОРЯДКА, ТО ОН ОКАЖЕТСЯ 
НА ГРАНИЦЕ~$Y$ И НЕ ВЫТЕСНЯЕТ НИКАКИХ ЭЛЕМЕНТОВ ПРИ ПОСТРОЕНИИ ИЗ 
ТЕОРЕМЫ~A. тАКИМ ОБРАЗОМ, ЕСЛИ ПОСЛЕДОВАТЕЛЬНО ВСТАВЛЯТЬ 
ЭЛЕМЕНТЫ~$p_1$,~\dots, $p_{i-1}$, $p_{i+1}$,~\dots, $p_n$, ПРИМЕНЯЯ ДВОЙСТВЕННОЕ 
ОТНОШЕНИЕ ПОРЯДКА, ТО ПОЛУЧИТСЯ~$Y-\set{p_i}$, Т.Е.~$Y$, ИЗ КОТОРОГО 
УДАЛЕН ЭЛЕМЕНТ~$p_i$. пО ТЕОРЕМЕ~C, ЕСЛИ ПОСЛЕДОВАТЕЛЬНО ВСТАВЛЯТЬ 
ЭЛЕМЕНТЫ~$p_1$,~\dots, $p_{i-1}$, $p_{i+1}$,~\dots, $p_n$, ПРИМЕНЯЯ 
ОБЫЧНОЕ ОТНОШЕНИЕ ПОРЯДКА, ПОСТРОИМ ТАБЛО~$d(P)$, КОТОРОЕ ПОЛУЧАЕТСЯ ПУТЕМ 
ПРИМЕНЕНИЯ К~$P$ АЛГОРИТМА~S. иНДУКЦИЯ ПО~$n$ 
ДАЕТ~$Y-\set{p_i}=(d(P)^S)^T$. нО ПОСКОЛЬКУ
$$
(P^S)^T-\set{p_i}=(d(P)^S)^T
\eqno (29)
$$
ПО ОПРЕДЕЛЕНИЮ ОПЕРАЦИИ~$S$, А $Y$~ИМЕЕТ ТУ ЖЕ ФОРМУ, ЧТО И~$(P^S)^T$, ТО 
ДОЛЖНО ИМЕТЬ МЕСТО РАВЕНСТВО~$Y=(P^S)^T$.

тЕМ САМЫМ ДОКАЗАНО УТВЕРЖДЕНИЕ~(b); (a)~ПОЛУЧАЕТСЯ ПРИМЕНЕНИЕМ ТЕОРЕМЫ~B.
пОСЛЕДОВАТЕЛЬНОЕ ПРИМЕНЕНИЕ~(a) И~(b) ПОКАЗЫВАЕТ, ЧТО СЛУЧАЙ~(c) 
СООТВЕТСТВУЕТ ПАРЕ~$(((P^T)^S)^T, ((Q^S)^T)^T)$, a ЭТО РАВНО~$(P^S, Q^S)$, 
ТАК КАК~$(P^S)^T=(P^T)^S$ ВСЛЕДСТВИЕ СИММЕТРИИ ОПЕРАЦИИ~$S$ ПО ОТНОШЕНИЮ К 
СТРОКАМ И СТОЛБЦАМ.
\proofend

эТА ТЕОРЕМА, В ЧАСТНОСТИ, УСТАНАВЛИВАЕТ ДВА УДИВИТЕЛЬНЫХ ФАКТА, КАСАЮЩИХСЯ 
АЛГОРИТМА ВСТАВКИ В ТАБЛО. еСЛИ В РЕЗУЛЬТАТЕ ПОСЛЕДОВАТЕЛЬНОЙ ВСТАВКИ 
РАЗЛИЧНЫХ ЭЛЕМЕНТОВ~$p_1$,~\dots, $p_n$
%% 79
В ПУСТОЕ ТАБЛО ПОЛУЧАЕТСЯ ТАБЛО~$P$, ТО В РЕЗУЛЬТАТЕ ВСТАВКИ ЭТИХ 
ЭЛЕМЕНТОВ В ОБРАТНОМ ПОРЯДКЕ---$p_n$,~\dots, $p_1$, 
ПОЛУЧИТСЯ \dfn{ТРАНСПОНИРОВАННОЕ} ТАБЛО~$P^T$. еСЛИ ЖЕ МЫ НЕ ТОЛЬКО 
СТАНЕМ ВСТАВЛЯТЬ ЭЛЕМЕНТЫ В ПОРЯДКЕ~$p_n$,~\dots, $p_1$, НО И ПОМЕНЯЕМ 
РОЛЯМИ~$<$ И~$>$, А ТАКЖЕ~$0$ И~$\infty$, ТО ПОЛУЧИМ ДВОЙСТВЕННОЕ 
ТАБЛО~$P^S$. нАСТОЯТЕЛЬНО РЕКОМЕНДУЕМ ЧИТАТЕЛЮ ИСПЫТАТЬ ЭТИ ПРОЦЕССЫ 
НА НЕСКОЛЬКИХ ПРОСТЫХ ПРИМЕРАХ. нЕОБЫЧНАЯ ПРИРОДА ЭТИХ СОВПАДЕНИЙ МОЖЕТ 
ВЫЗВАТЬ ПОДОЗРЕНИЕ О ВМЕШАТЕЛЬСТВЕ КАКИХ-ТО КОЛДОВСКИХ СИЛ. дО СИХ ПОР 
НЕ ИЗВЕСТНО КАКОГО-ЛИБО ПРОСТОГО ОБўЯСНЕНИЯ ПОДОБНЫХ ЯВЛЕНИЙ; КАЖЕТСЯ, НЕ 
СУЩЕСТВУЕТ ПРОСТОГО СПОСОБА ДОКАЗАТЬ ДАЖЕ ТО, ЧТО СЛУЧАЙ~(c) СООТВЕТСТВУЕТ 
ТАБЛО ТОЙ ЖЕ \emph{ФОРМЫ,} ЧТО~$P$ И~$Q$.

сООТВЕТСТВИЕ, УСТАНАВЛИВАЕМОЕ ТЕОРЕМОЙ~A, НАЙДЕНО ж.~рОБИНСОНОМ 
[{\sl American J.\ Math.,\/} {\bf 60} (1938), 745--760, Sec.~5]
В НЕСКОЛЬКО ИНОЙ И ДОВОЛЬНО ТУМАННОЙ ФОРМЕ КАК ЧАСТЬ РЕШЕНИЯ ВЕСЬМА 
СЛОЖНОЙ ЗАДАЧИ ИЗ ТЕОРИИ ГРУПП. нЕТРУДНО ПРОВЕРИТЬ, ЧТО ЕГО ПОСТРОЕНИЕ В 
СУЩНОСТИ ИДЕНТИЧНО ПРИВЕДЕННОМУ ЗДЕСЬ. оН СФОРМУЛИРОВАЛ ТЕОРЕМУ~B БЕЗ 
ДОКАЗАТЕЛЬСТВА. мНОГО ЛЕТ СПУСТЯ к.~шЕНСТЕД НЕЗАВИСИМО ЗАНОВО ОТКРЫЛ ЭТО 
СООТВЕТСТВИЕ, КОТОРОЕ ОН СФОРМУЛИРОВАЛ ПО СУЩЕСТВУ В ТОЙ ЖЕ ФОРМЕ, 
КАКУЮ ИСПОЛЬЗОВАЛИ МЫ 
[{\sl Canadian J.\ Math.,\/} {\bf 13} (1961), 179--191]. оН ТАКЖЕ ДОКАЗАЛ 
"$P$"-ЧАСТЬ ТЕОРЕМЫ~D~(a). м.~п.~шЮЦЕНБЕРЖЕ
[{\sl Math. Scand.,\/} {\bf 12} (1963), 117--128] ДОКАЗАЛ ТЕОРЕМУ~B И 
"$Q$"-ЧАСТЬ ТЕОРЕМЫ~D~(a), ИЗ КОТОРОЙ СЛЕДУЮТ~(b) И~(c). эТО 
СООТВЕТСТВИЕ МОЖНО РАСПРОСТРАНИТЬ И НА ПЕРЕСТАНОВКИ МУЛЬТИМНОЖЕСТВ;
СЛУЧАЙ, КОГДА~$p_1$,~\dots, $p_n$ НЕ ОБЯЗАТЕЛЬНО РАЗЛИЧНЫ, 
РАССМОТРЕЛ шЕНСТЕД, А "МАКСИМАЛЬНОЕ" ОБОБЩЕНИЕ НА СЛУЧАЙ, КОГДА И~$p$, 
И~$q$ МОГУТ СОДЕРЖАТЬ ПОВТОРЯЮЩИЕСЯ ЭЛЕМЕНТЫ, ИССЛЕДОВАНО кНУТОМ
[{\sl Pacific J.\ Math.,\/} {\bf 34} (1970), 709--727].

оБРАТИМСЯ ТЕПЕРЬ К РОДСТВЕННОМУ ВОПРОСУ: \emph{СКОЛЬКО ТАБЛО, СОСТАВЛЕННЫХ 
ИЗ ЭЛЕМЕНТОВ~$\set{1, 2,~\ldots, n}$, ИМЕЮТ ДАННУЮ 
ФОРМУ~$(n_1, n_2,~\ldots, n_m)$, ГДЕ~$n_1+n_2+\cdots+n_m=n$?} оБОЗНАЧИМ ЭТО 
ЧИСЛО ЧЕРЕЗ~$f(n_1, n_2,~\ldots, n_m)$; ОНО ДОЛЖНО УДОВЛЕТВОРЯТЬ СООТНОШЕНИЯМ
$$
\displaylines{
f(n_1, n_2, \ldots, n_m)=0, 
\rem{ЕСЛИ НЕ ВЫПОЛНЕНО УСЛОВИЕ~$n_1\ge n_2\ge \ldots\ge n_m\ge 0$;} \hfill \llap{(30)}\cr
f(n_1, n_2, \ldots, n_m, 0)=f(n_1, n_2, \ldots, n_m); \hfill\llap{(31)}\cr
f(n_1, n_2, \ldots, n_m)=f(n_1-1, n_2, \ldots, n_m)
  +f(n_1, n_2-1, \ldots,  n_m)+\cdots+f(n_1, n_2, \ldots, n_m-1),\hfill\cr
\hfill \rem{ЕСЛИ $n_1\ge n_2 \ge \ldots \ge n_m \ge 1$.}\quad (32)\cr
}
$$
пОСЛЕДНЕЕ РЕКУРРЕНТНОЕ СООТНОШЕНИЕ ВЫТЕКАЕТ ИЗ ТОГО ФАКТА, ЧТО ПРИ 
УДАЛЕНИИ НАИБОЛЬШЕГО ЭЛЕМЕНТА ТАБЛО ВСЕГДА СНОВА ПОЛУЧАЕТСЯ ТАБЛО; 
НАПРИМЕР, КОЛИЧЕСТВО ТАБЛО ФОРМЫ~$(6, 4, 4, 1)$ 
РАВНО~$f(5, 4, 4, 1)+f(6, 3, 4, 1)+f(6, 4, 3, 1) + f(6, 4, 4, 0)=f(5, 4, 4, 1)
%%80
+f(6, 4, 3, 1)+f(6, 4, 4)$, ПОТОМУ ЧТО ВСЯКОЕ ТАБЛО ФОРМЫ~$(6, 4, 4, 1)$
ИЗ ЭЛЕМЕНТОВ~$\set{1, 2,~\ldots, 15}$ ПОЛУЧАЕТСЯ В РЕЗУЛЬТАТЕ ВСТАВКИ 
ЭЛЕМЕНТА~$15$ В ПОДХОДЯЩЕЕ МЕСТО В ТАБЛО ФОРМЫ~$(5, 4, 4, 1)$, $(6, 4, 3, 1)$
ИЛИ~$(6, 4, 4)$. иЗОБРАЗИМ ЭТО НА СХЕМЕ
\picture{p. 80, (33)}

фУНКЦИЯ~$f(n_1, n_2,~\ldots, n_m)$, УДОВЛЕТВОРЯЮЩАЯ ТАКИМ СООТНОШЕНИЯМ, 
ИМЕЕТ ДОВОЛЬНО ПРОСТОЙ ВИД:
$$
f(n_1, n_2,~\ldots, n_m)=
{\Delta(n_1+m-1, n_2+m-2, \ldots, n_m) n! \over (n_1+m-1)! (n_2+m-2)! \ldots n_m!}
\rem{ПРИ~$n_1+m-1\ge n_2+m-2 \ge \ldots \ge n_m,$} 
\eqno (34)
$$ ГДЕ ЧЕРЕЗ~$\Delta$ ОБОЗНАЧЕН ДЕТЕРМИНАНТ
$$
\Delta(x_1, x_2, \ldots, x_m)=\det\pmatrix{
x_1^{m-1} & x_2^{m-1} & \ldots & x_m^{m-1}\cr
\vdots    &           &        & \vdots   \cr
x_1^2     & x_2^2     &        & x_m^2    \cr
x_1       & x_2       &        & x_m      \cr
1         & 1         & \ldots & 1        \cr
}=\prod_{1\le i < j \le m} (x_i-x_j)
\eqno(35)
$$
фОРМУЛУ~(34) ВЫВЕЛ ф.~фРОБЕНИУС 
[Sitzungsberichte Preuss. Akad.\ der Wissenchaften (Berlin, 1900), 516--534, Sec.~3], 
ИЗУЧАЯ ЭКВИВАЛЕНТНУЮ ЗАДАЧУ ТЕОРИИ ГРУПП; ОН 
ИСПОЛЬЗОВАЛ ДОВОЛЬНО ГЛУБОКУЮ АРГУМЕНТАЦИЮ, ОПИРАЮЩУЮСЯ НА ТЕОРИЮ ГРУПП. 
кОМБИНАТОРНОЕ ДОКАЗАТЕЛЬСТВО НЕЗАВИСИМО НАШЕЛ мАК-мАГОН 
[{\sl Philosophical Trans.,\/} {\bf A-209} (London, 1909), 153--175]. эТУ 
ФОРМУЛУ МОЖНО ДОКАЗАТЬ ПО ИНДУКЦИИ, ТАК КАК~(30) И~(31) ДОКАЗЫВАЮТСЯ БЕЗ 
ТРУДА, А ФОРМУЛА~(32) ПОЛУЧАЕТСЯ, ЕСЛИ ПОЛОЖИТЬ~$y=-1$ В ТОЖДЕСТВЕ УПР.~17.

иЗ ТЕОРЕМЫ~A В СВЯЗИ С ЭТОЙ ФОРМУЛОЙ ДЛЯ ЧИСЛА ТАБЛО ВЫТЕКАЕТ 
ЗАМЕЧАТЕЛЬНОЕ ТОЖДЕСТВО. вЗЯВ СУММУ ПО ВСЕВОЗМОЖНЫМ %%81
ФОРМАМ ТАБЛО, ПОЛУЧИМ
$$
\eqalign{
n! &= \sum_{\scriptstyle k_1\ge \ldots \ge k_n \ge 0 \atop \scriptstyle 
     k_1+\cdots+k_n=n} f(k_1, \ldots, k_n)^2=\cr
   &= n!^2 \sum_{\scriptstyle k_1\ge \ldots \ge k_n \ge 0 \atop \scriptstyle k_1+\cdots+k_n=n}
      {\Delta(k_1+n-1, \ldots, k_n)^2 \over (k_1+n-1)!^2\ldots k_n!^2}=\cr
   &= n!^2 \sum_{\scriptstyle q_1>q_2>\ldots>q_n\ge 0 \atop \scriptstyle 
      q_1+\cdots+q_n=(n+1)n/2} {\Delta(q_1, \ldots, q_n)^2 \over q_1!^2\ldots q_n!^2};\cr
}
$$
ОТСЮДА
$$
\sum_{\scriptstyle q_1+\cdots+q_n=(n+1)n/2 \atop \scriptstyle q_1 \ldots q_n \ge 0} 
{\Delta(q_1,\ldots, q_n)^2\over q_1!^2 \ldots q_n!^2} = 1.
\eqno(36)
$$
в ПОСЛЕДНЕЙ СУММЕ ОТСУТСТВУЮТ НЕРАВЕНСТВА~$q_1>q_2>\ldots>q_n$, ПОТОМУ ЧТО 
СЛАГАЕМЫЕ---СИММЕТРИЧНЫЕ ОТНОСИТЕЛЬНО~$q$ ФУНКЦИИ, ОБРАЩАЮЩИЕСЯ В~$0$ 
ПРИ~$q_i=q_j$. аНАЛОГИЧНОЕ ТОЖДЕСТВО ПОЯВЛЯЕТСЯ В УПР.~24.

фОРМУЛУ ЧИСЛА ТАБЛО МОЖНО ВЫРАЗИТЬ НЕСКОЛЬКО БОЛЕЕ ИНТЕРЕСНЫМ СПОСОБОМ, 
ЕСЛИ ВВЕСТИ ПОНЯТИЕ "УГОЛКОВ". в \dfn{УГОЛОК,} СООТВЕТСТВУЮЩИЙ
\picture{рИС~5. уГОЛКИ И ДЛИНЫ УГОЛКОВ.}
КЛЕТКЕ ТАБЛО, ВХОДИТ САМА ЭТА КЛЕТКА ПЛЮС ВСЕ КЛЕТКИ, ЛЕЖАЩИЕ СНИЗУ И 
СПРАВА ОТ НЕЕ. нАПРИМЕР, ЗАШТРИХОВАННЫЙ УЧАСТОК НА РИС.~5---УГОЛОК, 
СООТВЕТСТВУЮЩИЙ КЛЕТКЕ~$(2, 3)$ СТРОКИ~2 И СТОЛБЦА~3; ОН СОСТОИТ ИЗ ШЕСТИ 
КЛЕТОК. в КАЖДОЙ КЛЕТКЕ НА РИС.~5 ЗАПИСАНА ДЛИНА СООТВЕТСТВУЮЩЕГО ЕЙ УГОЛКА.

еСЛИ ТАБЛО ИМЕЕТ ФОРМУ~$(n_1, n_2,~\ldots, n_m)$, ГДЕ~$n_m\ge 1$, ТО 
ДЛИНА САМОГО ДЛИННОГО УГОЛКА РАВНА~$n_1+m-1$. дАЛЬНЕЙШЕЕ ИССЛЕДОВАНИЕ 
ДЛИН УГОЛКОВ ПОКАЗЫВАЕТ, ЧТО СТРОКА~1 СОДЕРЖИТ ВСЕ ДЛИНЫ~$n_1+m-1$, 
$n_1+m-2$,~\dots, $1$, \emph{КРОМЕ $(n_1+m-1)-(n_m)$, $(n_1+m-1)-
%%82
-(n_{m-1}+1)$,~\dots, $(n_1+m-1)-(n_2+m-2)$.} нАПРИМЕР, НА РИС.~5 ДЛИНЫ 
УГОЛКОВ В $1\hbox{-Й}$ СТРОКЕ СУТЬ~$12$, $11$, $10$,~\dots, $1$, ЗА 
ИСКЛЮЧЕНИЕМ~$10$, $9$, $6$, $3$, $2$; ЭТИ ИСКЛЮЧЕНИЯ СООТВЕТСТВУЮТ ПЯТИ 
НЕСУЩЕСТВУЮЩИМ УГОЛКАМ, НАЧИНАЮЩИМСЯ В НЕСУЩЕСТВУЮЩИХ КЛЕТКАХ~$(6, 3)$, 
$(5, 3)$, $(4, 5)$, $(3, 7)$, $(2, 7)$ И ЗАКАНЧИВАЮЩИМСЯ В КЛЕТКЕ~$(1, 7)$.
 аНАЛОГИЧНО $j\hbox{-Я}$~СТРОКА СОДЕРЖИТ ВСЕ ДЛИНЫ 
УГОЛКОВ~$n_j+m-j$,~\dots, $1$, КРОМЕ~$(n_j+m-j)-(n_m)$,~\dots, 
$(n_j-m-j)-(n_{j+1}-m-j-1)$. оТСЮДА СЛЕДУЕТ, ЧТО ПРОИЗВЕДЕНИЕ ДЛИН ВСЕХ 
УГОЛКОВ РАВНО
$$
(n_1+m-1)!\ldots{}(n_m)!/\Delta(n_1+m-1,~\ldots, n_m).
$$
эТО ВЫРАЖЕНИЕ ВХОДИТ В ФОРМУЛУ~(34); ОТСЮДА СЛЕДУЕТ

\proclaim тЕОРЕМА~H. (дЖ.~с.~фРЭЙМ, ж.~рОБИНСОН, р.~м.~тРОЛЛ.) 
кОЛИЧЕСТВО ТАБЛО ДАННОЙ ФОРМЫ, СОСТАВЛЕННЫХ ИЗ 
ЭЛЕМЕНТОВ~$\set{1, 2,~\ldots, n}$, РАВНО~$n!$, ДЕЛЕННОМУ НА ПРОИЗВЕДЕНИЕ 
ДЛИН УГОЛКОВ. \endmark

тАКОЙ ПРОСТОЙ РЕЗУЛЬТАТ ЗАСЛУЖИВАЕТ И ПРОСТОГО ДОКАЗАТЕЛЬСТВА; ОДНАКО 
(КАК И ДЛЯ БОЛЬШИНСТВА ДРУГИХ ФАКТОВ, КАСАЮЩИХСЯ ТАБЛО) БОЛЕЕ ПРЯМОГО 
ДОКАЗАТЕЛЬСТВА НЕ ИЗВЕСТНО. кАЖДЫЙ ЭЛЕМЕНТ ТАБЛО---МИНИМАЛЬНЫЙ В СВОЕМ 
УГОЛКЕ; ЕСЛИ ЗАПОЛНИТЬ КЛЕТКИ ТАБЛО СЛУЧАЙНЫМ ОБРАЗОМ, ТО ВЕРОЯТНОСТЬ ТОГО,
ЧТО В КЛЕТКЕ~$(i, j)$ ОКАЖЕТСЯ МИНИМАЛЬНЫЙ ЭЛЕМЕНТ СООТВЕТСТВУЮЩЕГО 
УГОЛКА, ЕСТЬ ВЕЛИЧИНА, ОБРАТНАЯ ДЛИНЕ УГОЛКА. пЕРЕМНОЖЕНИЕ ЭТИХ 
ВЕРОЯТНОСТЕЙ ПО ВСЕМ~$i$, $j$ ДАЕТ ТЕОРЕМУ~H. оДНАКО ТАКОЕ 
РАССУЖДЕНИЕ ОШИБОЧНО, ПОСКОЛЬКУ ЭТИ ВЕРОЯТНОСТИ ОТНЮДЬ НЕ ЯВЛЯЮТСЯ 
НЕЗАВИСИМЫМИ. вСЕ ИЗВЕСТНЫЕ ДОКАЗАТЕЛЬСТВА ТЕОРЕМЫ~H ОСНОВАНЫ НА ОДНОМ 
НЕУБЕДИТЕЛЬНОМ ИНДУКТИВНОМ РАССУЖДЕНИИ, КОТОРОЕ НА САМОМ ДЕЛЕ НЕ ОБўЯСНЯЕТ,
 ПОЧЕМУ ЖЕ ТЕОРЕМА ВЕРНА (ТАК КАК В НЕМ СОВЕРШЕННО НЕ ИСПОЛЬЗУЮТСЯ 
СВОЙСТВА УГОЛКОВ).

сУЩЕСТВУЕТ ИНТЕРЕСНАЯ СВЯЗЬ МЕЖДУ ТЕОРЕМОЙ~H И ПЕРЕЧИСЛЕНИЕМ ДЕРЕВЬЕВ, 
КОТОРОЕ РАССМАТРИВАЛОСЬ В ГЛ.~2. мЫ ВИДЕЛИ, ЧТО БИНАРНЫМ ДЕРЕВЬЯМ С 
$n$~УЗЛАМИ СООТВЕТСТВУЮТ ПЕРЕСТАНОВКИ, КОТОРЫЕ МОЖНО ПОЛУЧИТЬ С ПОМОЩЬЮ 
СТЕКА, И ЧТО ТАКИМ ПЕРЕСТАНОВКАМ СООТВЕТСТВУЮТ 
ПОСЛЕДОВАТЕЛЬНОСТИ~$a_1\,a_2\,\ldots\,a_{2n}$ ЛИТЕР~$S$ И~$X$, ТАКИЕ, ЧТО 
КОЛИЧЕСТВО ЛИТЕР~$S$ НИКОГДА НЕ БЫВАЕТ МЕНЬШЕ КОЛИЧЕСТВА ЛИТЕР~$X$, ЕСЛИ ЧИТАТЬ 
ПОСЛЕДОВАТЕЛЬНОСТЬ СЛЕВА НАПРАВО. (сМ.~УПР.~2.3.1-6 И~2.2.1-3.) тАКИМ 
ПОСЛЕДОВАТЕЛЬНОСТЯМ ЕСТЕСТВЕННЫМ ОБРАЗОМ СОПОСТАВЛЯЮТСЯ ТАБЛО ФОРМЫ~$(n, n)$; 
В 1-Ю СТРОКУ ПОМЕЩАЮТСЯ ИНДЕКСЫ~$i$, ТАКИЕ, ЧТО~$a_i=S$, А ВО 2-Ю 
СТРОКУ---ИНДЕКСЫ, ПРИ КОТОРЫХ~$a_i=X$. нАПРИМЕР, ПОСЛЕДОВАТЕЛЬНОСТИ
$$
S\; S\; S\; X\; X\; S\; S\; X\; X\; S\; X\; X
$$ 
СООТВЕТСТВУЕТ ТАБЛО
$$
\tableau{
1 & 2 & 3 & 6 & 7 & 10 \cr
4 & 5 & 8 & 9 & 11 & 12 \cr
}
\eqno(37)
$$
%%83
уСЛОВИЕ, НАЛАГАЕМОЕ НА СТОЛБЦЫ, УДОВЛЕТВОРЯЕТСЯ В ТАКОМ ТАБЛО В ТОМ И 
ТОЛЬКО ТОМ СЛУЧАЕ, КОГДА ПРИ ЧТЕНИИ СЛЕВА НАПРАВО ЧИСЛО ЛИТЕР~X НИКОГДА НЕ 
ПРЕВЫШАЕТ ЧИСЛА ЛИТЕР~$S$. пО ТЕОРЕМЕ~H КОЛИЧЕСТВО ВСЕВОЗМОЖНЫХ ТАБЛО 
ФОРМЫ~$(n, n)$ РАВНО
$$
(2n)!/(n+1)!n!;
$$
СЛЕДОВАТЕЛЬНО, ТАКОВО ЖЕ И ЧИСЛО БИНАРНЫХ ДЕРЕВЬЕВ С $n$~УЗЛАМИ (ЧТО 
СОГЛАСУЕТСЯ С ФОРМУЛОЙ~(2.3.4.4-13)). бОЛЕЕ ТОГО, ЕСЛИ ВОСПОЛЬЗОВАТЬСЯ 
ТАБЛО ФОРМЫ~$(n, m)$ ПРИ~$n\ge m$, ТО ПРИ ПОМОЩИ ЭТОГО РАССУЖДЕНИЯ МОЖНО 
РЕШИТЬ И БОЛЕЕ ОБЩУЮ "ЗАДАЧУ О БАЛЛОТИРОВКЕ", РАССМОТРЕННУЮ В ОТВЕТЕ К 
УПР.~2.2.1-4. тАКИМ ОБРАЗОМ, ТЕОРЕМА~H В КАЧЕСТВЕ ПРОСТЫХ ЧАСТНЫХ 
СЛУЧАЕВ ВКЛЮЧАЕТ В СЕБЯ НЕКОТОРЫЕ ВЕСЬМА СЛОЖНЫЕ ЗАДАЧИ О ПЕРЕЧИСЛЕНИИ.

вСЯКОМУ ТАБЛО~$A$ ФОРМЫ~$(n, n)$ ИЗ ЭЛЕМЕНТОВ~$\set{1, 2,~\ldots, 2n}$ 
СООТВЕТСТВУЮТ ДВА ТАБЛО~$(P, Q)$ ОДИНАКОВОЙ ФОРМЫ. сЛЕДУЮЩИЙ СПОСОБ 
ПОСТРОЕНИЯ ТАКОГО СООТВЕТСТВИЯ ПРЕДЛОЖЕН мАК-мАГОНОМ 
[Combinatory Analysis, {\bf 1} (1915), 130--131]. пУСТЬ~$P$ СОСТОИТ ИЗ 
ЭЛЕМЕНТОВ~$\set{1,~\ldots, n}$, РАСПОЛОЖЕННЫХ, КАК В~$A$, А~$Q$ ПОЛУЧАЕТСЯ, 
ЕСЛИ ВЗЯТЬ ОСТАЛЬНЫЕ ЭЛЕМЕНТЫ~$A$, ПОВЕРНУТЬ ВСЮ КОНФИГУРАЦИЮ НА~$180^\circ$ 
И ЗАМЕНИТЬ~$n+1$, $n+2$,~\dots, $2n$ НА СООТВЕТСТВЕННО~$n$, $n-1$,~\dots, $1$. 
нАПРИМЕР, ТАБЛО~(37) РАСПАДАЕТСЯ НА
$$
\tableau{
1 & 2 & 3 & 6 \cr
4 & 5 \cr
}
\hbox{ И }
\revtableau{
\omit &\omit \hfil\vrule& 7 & 10 \cr
8 & 9 & 11 & 12\cr
}\,;
$$
ПОСЛЕ ПОВОРОТА И ПЕРЕНУМЕРАЦИИ ИМЕЕМ
$$
P=\tableau{
1 & 2 & 3 & 6 \cr
4 & 5 \cr
},\quad 
Q=\tableau{
1 & 2 & 4 & 5 \cr
3 & 6 \cr
}.
\eqno(38)
$$
нАОБОРОТ, КАЖДОЙ ПАРЕ ТАБЛО ОДИНАКОВОЙ ФОРМЫ, СОСТОЯЩИХ ИА $n$~ЭЛЕМЕНТОВ И 
ИЗ НЕ БОЛЕЕ ДВУХ СТРОК, СООТВЕТСТВУЕТ ТАБЛО ФОРМЫ~$(n, n)$. сЛЕДОВАТЕЛЬНО 
(ИЗ~УПР.~7), \emph{ЧИСЛО ПЕРЕСТАНОВОК~$a_1\,a_2\,\ldots\,a_n$ 
МНОЖЕСТВА~$\set{1, 2,~\ldots, n}$, НЕ СОДЕРЖАЩИХ УБЫВАЮЩИХ 
ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ~$a_i>a_j>a_k$ ПРИ~$i<j<k$, РАВНО ЧИСЛУ 
БИНАРНЫХ ДЕРЕВЬЕВ С $n$~УГЛАМИ.} иНТЕРЕСНОЕ ВЗАИМНО ОДНОЗНАЧНОЕ 
СООТВЕТСТВИЕ МЕЖДУ ТАКИМИ ПЕРЕСТАНОВКАМИ И БИНАРНЫМИ ДЕРЕВЬЯМИ, 
УСТАНОВЛЕННОЕ БОЛЕЕ ПРЯМЫМ СПОСОБОМ, ЧЕМ ТОТ ОКОЛЬНЫЙ ПУТЬ ПОСРЕДСТВОМ 
АЛГОРИТМА~I. КОТОРЫМ ВОСПОЛЬЗОВАЛИСЬ МЫ, НАШЕЛ д.~рОТОМ 
[{\sl Inf.\ Proc.\ Letters,\/} {\bf 4} (1975), 58--61]; АНАЛОГИЧНО, СУЩЕСТВУЕТ 
ДОВОЛЬНО ПРЯМОЕ СООТВЕТСТВИЕ МЕЖДУ БИНАРНЫМИ ДЕРЕВЬЯМИ И ПЕРЕСТАНОВКАМИ, НЕ 
СОДЕРЖАЩИМИ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ~$a_j>a_k>a_i$ И~$i<j<k$ (СМ.~УПР.~2.2.1-5).

%% 84

 чИСЛО СПОСОБОВ ЗАПОЛНИТЬ ТАБЛО ФОРМЫ~$(6, 4, 4, 1)$, ОЧЕВИДНО, РАВНО 
ЧИСЛУ СПОСОБОВ ПОМЕТИТЬ ВЕРШИНЫ НАПРАВЛЕННОГО ГРАФА
\picture{p.84}
ЧИСЛАМИ~$\set{1, 2,~\ldots, 15}$ ТАК, ЧТОБЫ МЕТКА ВЕРШИНЫ~$u$ БЫЛА 
МЕНЬШЕ МЕТКИ ВЕРШИНЫ~$v$, ЕСЛИ~$u\to v$. иНАЧЕ ГОВОРЯ, ОНО РАВНО 
ЧИСЛУ СПОСОБОВ ТОПОЛОГИЧЕСКИ ОТСОРТИРОВАТЬ ЧАСТИЧНОЕ УПОРЯДОЧЕНИЕ~(39) В 
СМЫСЛЕ П.~2.2.3.

в ОБЩЕМ СЛУЧАЕ МОЖНО ЗАДАТЬ ТОТ ЖЕ ВОПРОС ДЛЯ ПРОИЗВОЛЬНОГО 
НАПРАВЛЕННОГО ГРАФА, НЕ СОДЕРЖАЩЕГО ОРИЕНТИРОВАННЫХ ЦИКЛОВ. бЫЛО БЫ ХОРОШО,
ЕСЛИ БЫ СУЩЕСТВОВАЛА КАКАЯ-НИБУДЬ ПРОСТАЯ ФОРМУЛА, ОБОБЩАЮЩАЯ ТЕОРЕМУ~H 
НА СЛУЧАЙ ПРОИЗВОЛЬНОГО ГРАФА; ОДНАКО НЕ ВСЕ ГРАФЫ ОБЛАДАЮТ ТАКИМИ 
ПРИЯТНЫМИ СВОЙСТВАМИ, КАК ГРАФЫ, СООТВЕТСТВУЮЩИЕ ТАБЛО. дРУГИЕ КЛАССЫ 
НАПРАВЛЕННЫХ ГРАФОВ, ДЛЯ КОТОРЫХ ЗАДАЧА О РАЗМЕТКЕ ВЕРШИН ИМЕЕТ ПРОСТОЕ 
РЕШЕНИЕ, ЧАСТИЧНО ОБСУЖДАЮТСЯ В УПРАЖНЕНИЯХ В КОНЦЕ ЭТОГО ПУНКТА. тАМ 
ТАКЖЕ ИМЕЮТСЯ УПРАЖНЕНИЯ, В КОТОРЫХ ПОКАЗАНО, ЧТО В РЯДЕ СЛУЧАЕВ 
НАПРАВЛЕННЫХ ГРАФОВ \emph{НЕ} СУЩЕСТВУЕТ ПРОСТОЙ ФОРМУЛЫ, 
СООТВЕТСТВУЮЩЕЙ ТЕОРЕМЕ~H. нАПРИМЕР, ЧИСЛО СПОСОБОВ ПОМЕТИТЬ ВЕРШИНЫ НЕ 
ВСЕГДА ЯВЛЯЕТСЯ ДЕЛИТЕЛЕМ~$n!$.

зАВЕРШИМ НАШИ ИССЛЕДОВАНИЯ ПОДСЧЕТОМ ОБЩЕГО ЧИСЛА ТАБЛО, КОТОРЫЕ МОЖНО 
СФОРМИРОВАТЬ ИЗ $n$~РАЗЛИЧНЫХ ЭЛЕМЕНТОВ. оБОЗНАЧИМ ЭТО ЧИСЛО ЧЕРЕЗ~$t_n$.
пО СЛЕДСТВИЮ ИЗ ТЕОРЕМЫ~B $t_n$~РАВНО ЧИСЛУ ИНВОЛЮЦИЙ 
МНОЖЕСТВА~$\set{1, 2,~\ldots, n}$. пЕРЕСТАНОВКА ОБРАТНА САМОЙ СЕБЕ ТОГДА И 
ТОЛЬКО ТОГДА, КОГДА ЕЕ ПРЕДСТАВЛЕНИЕ С ПОМОЩЬЮ ЦИКЛОВ СОСТОИТ ТОЛЬКО ИЗ 
ЕДИНИЧНЫХ ЦИКЛОВ (НЕПОДВИЖНЫХ ТОЧЕК) И ЦИКЛОВ ИЗ ДВУХ ЭЛЕМЕНТОВ (ТРАНСПОЗИЦИЙ). 
пОСКОЛЬКУ В~$t_{n-1}$ ИЗ~$t_n$ ИНВОЛЮЦИЙ $(n)$---НЕПОДВИЖНАЯ ТОЧКА, А 
В~$t_{n-2}$ ИЗ НИХ~$(j, n)$---ЦИКЛ ИЗ ДВУХ ЭЛЕМЕНТОВ ПРИ НЕКОТОРОМ 
ФИКСИРОВАННОМ~$j<n$, ТО ПОЛУЧАЕМ ФОРМУЛУ
$$
t_n=t_{n-1}+(n-1)t_{n-2},
\eqno(40)
$$
КОТОРУЮ ВЫВЕЛ рОТЕ В~1800~Г.\ ДЛЯ ПОЛУЧЕНИИ ТАБЛИЦЫ ЗНАЧЕНИЙ~$t_n$ ПРИ 
МАЛЫХ~$n$.

вЫЧИСЛИМ~$t_n$ ДРУГИМ СПОСОБОМ. пУСТЬ ИМЕЕТСЯ $k$~ЦИКЛОВ ИЗ
ДВУХ ЭЛЕМЕНТОВ И $n-2k$~ЕДИНИЧНЫХ ЦИКЛОВ. сУЩЕСТВУЕТ 
$\perm{n}{2k}$~СПОСОБОВ ВЫБРАТЬ НЕПОДВИЖНЫЕ ТОЧКИ, И 
МУЛЬТИНОМИАЛЬНЫЙ КОЭФФИЦИЕНТ~$(2k)!/(2!)^k$ РАВЕН ЧИСЛУ СПОСОБОВ 
ОРГАНИЗОВАТЬ ОСТАЛЬНЫЕ
%%85
ЭЛЕМЕНТЫ В $k$~РАЗЛИЧИМЫХ ТРАНСПОЗИЦИЙ. пОДЕЛИВ НА~$k!$, ЧТОБЫ СДЕЛАТЬ 
ЭТИ ТРАНСПОЗИЦИИ НЕРАЗЛИЧИМЫМИ, ПОЛУЧИМ
$$
t_n=\sum_{k\ge 0} t_n(k), \quad t_n(k)={n!\over (n-2k)!2^k k!}.
\eqno(41)
$$
к СОЖАЛЕНИЮ, НАСКОЛЬКО ЭТО ИЗВЕСТНО, ТАКУЮ СУММУ УЖЕ НЕЛЬЗЯ УПРОСТИТЬ, 
ПОЭТОМУ, ДЛЯ ТОГО ЧТОБЫ ЛУЧШЕ ПОНЯТЬ ПОВЕДЕНИЕ ВЕЛИЧИНЫ~$t_n$, МЫ ПРИМЕНИМ 
ДВА КОСВЕННЫХ ПОДХОДА:
{\medskip\narrower
\item{a)}~мОЖНО НАЙТИ ПРОИЗВОДЯЩУЮ ФУНКЦИЮ
$$
\sum_n t_n z^n/n! = e^{z+z^2/2};
\eqno(42)
$$
СМ.~УПР.~25.

\item{b)}~мОЖНО ОПРЕДЕЛИТЬ АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ ВЕЛИЧИНЫ~$t_n$. эТО 
ПОУЧИТЕЛЬНАЯ ЗАДАЧА, ЕЕ РЕШЕНИЕ СОДЕРЖИТ НЕСКОЛЬКО ОБЩИХ МЕТОДОВ, КОТОРЫЕ 
БУДУТ ПОЛЕЗНЫ И В СВЯЗИ С ДРУГИМИ ВОПРОСАМИ; ПОЭТОМУ МЫ ЗАКЛЮЧИМ ЭТОТ 
ПУНКТ АНАЛИЗОМ АСИМПТОТИЧЕСКОГО ПОВЕДЕНИЯ~$t_n$.
\medskip}

пЕРВЫЙ ШАГ В АНАЛИЗЕ АСИМПТОТИЧЕСКОГО ПОВЕДЕНИЯ~(41) СОСТОИТ В ВЫДЕЛЕНИИ 
СЛАГАЕМЫХ, ДАЮЩИХ ОСНОВНОЙ ВКЛАД В СУММУ. пОСКОЛЬКУ
$$
{t_n(k+1) \over t_n(k)} = {(n-2k)(n-2k-1)\over 2(k+1)},
\eqno(43)
$$
МОЖНО ВИДЕТЬ, ЧТО СЛАГАЕМЫЕ ПОСТЕПЕННО ВОЗРАСТАЮТ, КОГДА $k$~МЕНЯЕТСЯ 
ОТ~$k=0$ ДО~$k$, РАВНОГО ПРИБЛИЗИТЕЛЬНО~${1\over2}(n-\sqrt{n})$, А ЗАТЕМ 
УБЫВАЮТ ДО НУЛЯ, КОГДА $k$~ДОСТИГАЕТ ЗНАЧЕНИЯ, РАВНОГО 
ПРИМЕРНО~${1\over 2}n$. яСНО, ЧТО ОСНОВНОЙ ВКЛАД ДАЮТ ЧЛЕНЫ В 
ОКРЕСТНОСТИ~$k={1\over2}(n-\sqrt{n})$. дЛЯ АНАЛИЗА, ОДНАКО, УДОБНЕЕ, КОГДА
ОСНОВНОЙ ВКЛАД ДОСТИГАЕТСЯ ПРИ ЗНАЧЕНИИ~$0$, ПОЭТОМУ ПРЕДСТАВИМ~$k$ В ВИДЕ
$$
k={1\over 2}(n-\sqrt{n})+x
\eqno(44)
$$
И ИССЛЕДУЕМ ВЕЛИЧИНУ~$t_n(k)$ КАК ФУНКЦИЮ ОТ~$x$.

чТОБЫ ИЗБАВИТЬСЯ ОТ ФАКТОРИАЛОВ В~$t_n(k)$, ПОЛЕЗНО ВОСПОЛЬЗОВАТЬСЯ 
ФОРМУЛОЙ сТИРЛИНГА (1.2.11.2-18). дЛЯ ЭТОЙ ЦЕЛИ УДОБНО (КАК МЫ ВСКОРЕ 
УВИДИМ) ОГРАНИЧИТЬ ОБЛАСТЬ ИЗМЕНЕНИЯ~$x$ ПРОМЕЖУТКОМ
$$
-(n^{\varepsilon+1/4})\le x \le n^{\varepsilon+1/4},
\eqno(45)
$$
ГДЕ $\varepsilon$~РАВНО, СКАЖЕМ, $0.001$, ТАК ЧТО МОЖНО ВКЛЮЧИТЬ 
СЛАГАЕМОЕ ПОГРЕШНОСТИ. пОСЛЕ ДОВОЛЬНО ТРУДОЕМКИХ ВЫЧИСЛЕНИЙ, КОТОРЫЕ НА 
САМОМ ДЕЛЕ ДОЛЖНЫ БЫЛИ БЫТЬ ПРОДЕЛАНЫ ВЫЧИСЛИТЕЛЬНОЙ
%%86
МАШИНОЙ, ПОЛУЧАЕТСЯ ФОРМУЛА
$$
\displaylines{
t_n(k)=\exp\left({1\over2}n\ln n-{1\over2}n+\sqrt{n}-{1\over4}\ln n -2x^2/\sqrt{n}-\right.\hfill\cr
\hfill\left.-{1\over4}-{1\over2}\ln \pi-{4\over3}x^3/n+2x/\sqrt{n}+{1\over3}/\sqrt{n}-{4\over3}x^4/n\sqrt{n}+O(n^{5\varepsilon-3/4})\right).\quad(46)\cr
}
$$
оГРАНИЧЕНИЕ~(45) НА~$x$ ОПРАВДЫВАЕТСЯ ТЕМ, ЧТО МОЖНО 
ПОЛОЖИТЬ~$x=\pm n^{\varepsilon+1/4}$ ДЛЯ ПОЛУЧЕНИЯ ВЕРХНЕЙ ОЦЕНКИ ВСЕХ 
ОТБРОШЕННЫХ СЛАГАЕМЫХ, ИМЕННО
$$
e^{-2n^{2\varepsilon}}\cdot\exp\left({1\over2}n\ln n-{1\over2}n+\sqrt{n}
-{1\over4}\ln n-{1\over4}-{1\over2}\ln\pi+O(n^{3\varepsilon-1/4})\right),
\eqno(47)
$$
А ЕСЛИ УМНОЖИТЬ ЭТО НА~$n$, ТО ПОЛУЧИТСЯ ВЕРХНЯЯ ОЦЕНКА СУММЫ ИСКЛЮЧЕННЫХ 
СЛАГАЕМЫХ. вЕРХНЯЯ ОЦЕНКА ИМЕЕТ МЕНЬШИЙ ПОРЯДОК, ЧЕМ ТЕ СЛАГАЕМЫЕ, 
КОТОРЫЕ МЫ ВЫЧИСЛИМ ДЛЯ~$x$ В ОГРАНИЧЕННОМ ПРОМЕЖУТКЕ~(45), БЛАГОДАРЯ 
МНОЖИТЕЛЮ~$\exp(-2n^{2\varepsilon})$, КОТОРЫЙ МНОГО МЕНЬШЕ ЛЮБОГО ПОЛИНОМА 
ОТ~$n$. оЧЕВИДНО, МОЖНО ОТБРОСИТЬ В СУММЕ МНОЖИТЕЛЬ
$$
\exp\left({1\over2}n\ln n-{1\over2}n+\sqrt{n}-{1\over4}\ln n-{1\over4}
-{1\over2}\ln\pi+{1\over3}\big/\sqrt{n}\right),
\eqno(48)
$$
ПОСЛЕ ЧЕГО НАМ ОСТАНЕТСЯ ТОЛЬКО ПРОСУММИРОВАТЬ
$$
\displaylines{
\exp\left(-2x^2/\sqrt{n}-{4\over3}x^3/n+2x/\sqrt{n}-{4\over3}x^4/n\sqrt{n}+O(n^{5\varepsilon-3/4})\right)=\hfill\cr
\hfill =\exp\left({-2x^2\over\sqrt{n}}\right)\left(1-{4\over3}{x^3\over n}+{8\over9}{x^6\over n^2}\right)
\times\left(1+2{x\over\sqrt{n}}+2{x^2\over n}\right)\left(1-{4\over3}{x^4\over n\sqrt{n}}\right)(1+O(n^{9\varepsilon-3/4}))
\quad (49)\cr
}
$$
ПО ВСЕМ~$x=\alpha$, $\alpha+1$,~\dots, $\beta-2$, $\beta-1$, ГДЕ~$-\alpha$ 
И~$\beta$  (НЕ ОБЯЗАТЕЛЬНО ЦЕЛЫЕ) РАВНЫ 
ПРИБЛИЗИТЕЛЬНО~$n^{\varepsilon+1/4}$. еСЛИ СМЕСТИТЬ ИНТЕРВАЛ СУММИРОВАНИЯ, 
ТО ФОРМУЛУ СУММИРОВАНИЯ эЙЛЕРА~(1.2.11.2-10) МОЖНО ЗАПИСАТЬ В ВИДЕ
$$
\sum_{\alpha\le x<\beta} f(x)=\int_\alpha^\beta f(x)\,dx
-\left.{1\over2}f(x)\right\vert_\alpha^\beta
+{1\over2}B_2\cdot\left.{f'(x)\over1!}\right\vert_\alpha^\beta+\cdots
+{1\over m+1}B_{m+1}\cdot\left.{f^{(m)}(x)\over m!}\right\vert_\alpha^\beta
+R_{m+1}.
\eqno(50)
$$
зДЕСЬ~$\abs{R_m}\le (4/(2\pi)^m)\int_\alpha^\beta\vert{f^{(m)}(x)}\,dx$.
пОЛАГАЯ~$f(x)=x^t\times \exp(-2^2/\sqrt{n})^\alpha)$, 
ГДЕ~$t$---ФИКСИРОВАННОЕ НЕОТРИЦАТЕЛЬНОЕ ЦЕЛОЕ
%%87
ЧИСЛО, НАЙДЕМ, ЧТО ~$\int_\alpha^\beta f(x)\,dx$ ОТЛИЧАЕТСЯ 
ОТ~$\int_{-\infty}^\infty f(x)\,dx$ НА~$O(\exp(-2\pi^\varepsilon))$, ТАК 
ЧТО МОЖНО ВЗЯТЬ~$\alpha=-\infty$, $\beta=\infty$. в ЭТОМ СЛУЧАЕ ФОРМУЛА 
СУММИРОВАНИЯ эЙЛЕРА ДАСТ АСИМПТОТИЧЕСКИЙ РЯД ДЛЯ~$\sum f(x)$ 
ПРИ~$n\to\infty$, ПОСКОЛЬКУ
$$
f^{(m)}(x)=n^{(t-m)/4} g^{(m)} (n^{-1/4}x),\quad
g(y)=y^i e^{-2y^2},
\eqno(51)
$$
И~$g(y)$---ХОРОШАЯ ФУНКЦИЯ, НЕ ЗАВИСЯЩАЯ ОТ~$n$; ОТСЮДА ВИДНО,
ЧТО~$R_m=O(n^{(t+1-m)/4})$. тАК КАК~$f^{(m)}(-\infty)=f^m(\infty)=0$, МЫ 
ДОКАЗАЛИ, ЧТО
$$
\sum_{\alpha \le x < \beta} f(x)=\int_{-\infty}^{\infty} f(x)\,dx+O(n^{-m})
\rem{ДЛЯ ЛЮБОГО~$m\ge0$;}
\eqno (52)
$$
НА САМОМ ДЕЛЕ ПРИ ЭТОМ КОНКРЕТНОМ ВЫБОРЕ~$f(x)$ СУЩЕСТВЕН ТОЛЬКО ИНТЕГРАЛ! 
иНТЕГРАЛ НЕТРУДНО ВЫЧИСЛИТЬ (СМ.~УПР.~26); ТАКИМ ОБРАЗОМ, МЫ МОЖЕМ 
ВЫПОЛНИТЬ УМНОЖЕНИЕ И СЛОЖЕНИЕ В ФОРМУЛЕ~(49) И ПОЛУЧИТЬ
$$
\displaylines{
\sqrt{\pi\over 2} n^{1/4}\left(1-{1\over24}n^{-1/4}+O(n^{-1/2})\right);\cr
\hfill t_n={1\over \sqrt{2}} n^{n/2} e^{-n/2+\sqrt{n}-1/4}
\left(1+{7\over24} n^{-1/2}+O(n^{-3/4})\right).\hfill\llap{(53)}\cr
}
$$
в ДЕЙСТВИТЕЛЬНОСТИ СЛАГАЕМЫЕ В~$O(n^{-3/4})$ СОДЕРЖАТ ЕЩЕ ЭКСПОНЕНТУ 
ОТ~$9\varepsilon$, НО ИЗ НАШИХ ВЫКЛАДОК ЯСНО, ЧТО ВЕЛИЧИНА~$9\varepsilon$ 
ДОЛЖНА ИСЧЕЗНУТЬ, ЕСЛИ ПРОИЗВЕСТИ ВЫЧИСЛЕНИЯ С БОЛЬШЕЙ ТОЧНОСТЬЮ. в 
ПРИНЦИПЕ ЭТОТ МЕТОД МОЖНО УСИЛИТЬ И ВМЕСТО~$O(n^{-3/4})$ 
ПОЛУЧИТЬ~$O(n^{-k})$ ПРИ ЛЮБОМ~$k$. эТОТ АСИМПТОТИЧЕСКИЙ РЯД ДЛЯ~$t_n$ 
ВПЕРВЫЕ НАШЛИ (ДРУГИМ СПОСОБОМ) мОЗЕР И~уАЙМЭН 
[{\sl Canadian. J.~Math.,\/} {\bf 7} (1955), 159--168]. дРУГИЕ ПРИМЕРЫ И 
УСИЛЕНИЯ МЕТОДА, ПРИМЕНЕННОГО ДЛЯ ВЫВОДА ФОРМУЛЫ~(53), СМ.\ В КОНЦЕ П.~5.2.2.

\excercises
\ex[16] кАКИЕ ТАБЛО~$(P, Q)$ СООТВЕТСТВУЮТ ДВУСТРОЧНОМУ МАССИВУ
$$
\pmatrix{
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \cr
6 & 4 & 9 & 5 & 7 & 1 & 2 & 8 & 3 \cr
}
$$
В ПОСТРОЕНИИ ИЗ ТЕОРЕМЫ~A? кАКОЙ ДВУСТРОЧНЫЙ МАССИВ СООТВЕТСТВУЕТ ПАРЕ ТАБЛО
$$
B=\tableau{
1 & 4 & 7 \cr
2 & 8 \cr
5 & 9 \cr
},\quad
C=\tableau{
1 & 3 & 7 \cr
4 & 5 \cr
8 & 9 \cr
}?
$$

%%88

\ex[м21] дОКАЖИТЕ, ЧТО $(q, p)$~ПРИНАДЛЕЖИТ КЛАССУ~$t$ ОТНОСИТЕЛЬНО 
МАССИВА~(16) ТОГДА И ТОЛЬКО ТОГДА, КОГДА $t$~РАВНО МАКСИМАЛЬНОМУ ЧИСЛУ 
ИНДЕКСОВ~$i_1$,~\dots, $i_t$, ТАКИХ, ЧТО
$$
p_{i_1}<p_{i_2}<\ldots <p_{i_t}=p,\qquad 
q_{i_1}<q_{i_2}<\ldots <q_{i_t}=q.
$$

\rex[м24] пОКАЖИТЕ, ЧТО СООТВЕТСТВИЕ В ТЕОРЕМЕ~A МОЖНО ТАКЖЕ 
УСТАНОВИТЬ ПУТЕМ ПОСТРОЕНИЯ ТАКОЙ ТАБЛИЦЫ:
\ctable{
#\hfil\bskip &\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip\cr
сТРОКА~0 & 1      & 3      & 5      & 6      & 8      \cr
сТРОКА~1 & 7      & 2      & 9      & 5      & 3      \cr
сТРОКА~2 & \infty & 7      & \infty & 9      & 5      \cr
сТРОКА~3 &        & \infty &        & \infty & 7      \cr
сТРОКА~4 &        &        &        &        & \infty \cr
}
зДЕСЬ В СТРОКАХ~0 И~1 ЗАПИСАН ДАННЫЙ ДВУСТРОЧНЫЙ МАССИВ. пРИ~$k\ge1$ 
СТРОКА~$k+1$ ОБРАЗУЕТСЯ ИЗ СТРОКИ~$k$ СЛЕДУЮЩИМ ОБРАЗОМ:
{\medskip\narrower
\item{a)}~уСТАНОВИТЬ~$p\asg\infty$.
%
\item{b)}~пУСТЬ СТОЛБЕЦ~$j$---САМЫЙ ЛЕВЫЙ СТОЛБЕЦ, В КОТОРОМ СТРОКА~$k$ 
СОДЕРЖИТ ЦЕЛОЕ ЧИСЛО~$<p$, А СООТВЕТСТВУЮЩЕЕ МЕСТО В СТРОКЕ~$k+1$ НЕ 
ЗАПОЛНЕНО. еСЛИ ТАКОГО СТОЛБЦА НЕТ И~$p=\infty$, ТО СТРОКА~$k+1$ 
ЗАПОЛНЕНА; ЕСЛИ ТАКОГО СТОЛБЦА НЕТ И~$p<\infty$, ТО ВОЗВРАТИТЬСЯ К~(a).
%
\item{c)}~вСТАВИТЬ~$p$ В СТОЛБЕЦ~$j$ В СТРОКЕ~$k+1$, ПОТОМ УСТАНОВИТЬ~$p$ 
РАВНЫМ ЭЛЕМЕНТУ СТОЛБЦА~$j$ И СТРОКИ~$k$ И ВЕРНУТЬСЯ К~(b).
\medskip}

пОСЛЕ ТОГО КАК ТАБЛИЦА ТАКИМ ОБРАЗОМ ПОСТРОЕНА, СТРОКА~$k$ ТАБЛО~$P$ 
СОСТАВЛЯЕТСЯ ИЗ ТЕХ ЦЕЛЫХ ЧИСЕЛ СТРОКИ~$k$ ЭТОЙ ТАБЛИЦЫ, КОТОРЫЕ 
ОТСУТСТВУЮТ В СТРОКЕ~$(k+1)$; СТРОКА~$k$ ТАБЛО~$Q$ СТРОИТСЯ ИЗ ТЕХ ЦЕЛЫХ 
ЧИСЕЛ СТРОКИ~0, КОТОРЫЕ НАХОДЯТСЯ В СТОЛБЦАХ, СОДЕРЖАЩИХ~$\infty$ В 
СТРОКЕ~$(k+1)$.

\ex[M26] (м.~п.~шЮЦЕНБЕРЖЕ). пУСТЬ~$\pi$---ИНВОЛЮЦИЯ С 
$k$~НЕПОДВИЖНЫМИ ТОЧКАМИ. пОКАЖИТЕ, ЧТО ТАБЛО, СООТВЕТСТВУЮЩЕЕ~$\pi$ В 
ДОКАЗАТЕЛЬСТВЕ СЛЕДСТВИЯ ИЗ ТЕОРЕМЫ~B, СОДЕРЖИТ РОВНО $k$~СТОЛБЦОВ 
НЕЧЕТНОЙ ДЛИНЫ.

\rex[м30] пУСТЬ~$a_1\,\ldots\,a_{j-1}\,a_j\,\ldots\,a_n$---ПЕРЕСТАНОВКА 
РАЗЛИЧНЫХ ЭЛЕМЕНТОВ И~$1<j\le n$.
пЕРЕСТАНОВКА~$a_1\,\ldots\,a_{j-2}\,a_j\,a_{j-1}\,a_{j+1}\,\ldots\,a_n$, 
ПОЛУЧАЮЩАЯСЯ ИЗ ИСХОДНОЙ, ЕСЛИ ПОМЕНЯТЬ МЕСТАМИ~$a_{j-1}$ И~$a_j$, 
НАЗЫВАЕТСЯ "ДОПУСТИМОЙ", ЕСЛИ ЛИБО
{\medskip\narrower
\item{i)}~$j\ge 3$ И~$a_{j-2}$ ЛЕЖИТ МЕЖДУ~$a_{j-1}$ И~$a_j$, ЛИБО
\item{ii)}~$j<n$ И~$a_{j+1}$ ЛЕЖИТ МЕЖДУ~$a_{j-1}$ И~$a_j$.
\medskip}
нАПРИМЕР, В ПЕРЕСТАНОВКЕ~$1\,5\,4\,6\,8\,3\,7$ МОЖНО ПРОИЗВЕСТИ РОВНО 
ТРИ ДОПУСТИМЫЕ ЗАМЕНЫ: МОЖНО ПОМЕНЯТЬ МЕСТАМИ~$1$ И~$5$, ПОСКОЛЬКУ~$1<4<5$;
МОЖНО ПОМЕНЯТЬ МЕСТАМИ~$8$ И~$3$, ПОСКОЛЬКУ~$3<6<8$ (ИЛИ~$3<7<8$); 
ОДНАКО НЕЛЬЗЯ МЕНЯТЬ МЕСТАМИ~$5$ И~$4$ ИЛИ~$3$ И~$7$.
{\medskip\narrower
\item{a)}~дОКАЖИТЕ, ЧТО ПРИ ДОПУСТИМОЙ ЗАМЕНЕ НЕ МЕНЯЕТСЯ ТАБЛО~$P$, 
КОТОРОЕ ПОЛУЧАЕТСЯ ИЗ ПЕРЕСТАНОВКИ ПУТЕМ ПОСЛЕДОВАТЕЛЬНОЙ ВСТАВКИ 
ЭЛЕМЕНТОВ~$a_1$, $a_2$,~\dots, $a_n$ В ПЕРВОНАЧАЛЬНО ПУСТОЕ ТАБЛО.
%
\item{b)}~оБРАТНО, ПОКАЖИТЕ, ЧТО ЛЮБЫЕ ДВЕ ПЕРЕСТАНОВКИ, 
СООТВЕТСТВУЮЩИЕ ОДНОМУ И ТОМУ ЖЕ ТАБЛО~$P$, МОЖНО ПРЕОБРАЗОВАТЬ ОДНУ В 
ДРУГУЮ ПОСЛЕДОВАТЕЛЬНОСТЬЮ ОДНОЙ ИЛИ БОЛЕЕ ДОПУСТИМЫХ ЗАМЕН. [\emph{уКАЗАНИЕ:}
ПОКАЖИТЕ, ЧТО ЕСЛИ ТАБЛО~$P$ ИМЕЕТ ФОРМУ~$(n_1, n_2,~\ldots, n_m)$, ТО 
ЛЮБУЮ СООТВЕТСТВУЮЩУЮ ЕМУ ПЕРЕСТАНОВКУ ПРИ ПОМОЩИ 
ПОСЛЕДОВАТЕЛЬНОСТИ ДОПУСТИМЫХ ЗАМЕН МОЖНО ПРЕОБРАЗОВАТЬ В 
"КАНОНИЧЕСКУЮ ПЕРЕСТАНОВКУ"~$P_{m1}\ldots{}P_{mn_m}\ldots{}P_{21}\ldots{}P_{2n_2}P_{11}\ldots{}P_{1n_1}$.]
\medskip}

\rex[м22] пУСТЬ~$P$---ТАБЛО, СООТВЕТСТВУЮЩЕЕ ПЕРЕСТАНОВКЕ~$a_1\,a_2\,\ldots\,a_n$;
С ПОМОЩЬЮ УПР.~5 ДОКАЖИТЕ, ЧТО ТАБЛО~$P^T$ СООТВЕТСТВУЕТ 
ПЕРЕСТАНОВКЕ~$a_n\,\ldots\,a_2\,a_1$.
%%89

\ex[м 20] (к.~шЕНСТЕД). пУСТЬ~$P$---ТАБЛО, СООТВЕТСТВУЮЩЕЕ 
ПЕРЕСТАНОВКЕ~$a_1\,a_2\,\ldots\,a_n$. дОКАЖИТЕ, ЧТО ЧИСЛО \emph{СТОЛБЦОВ} 
В~$P$ РАВНО ДЛИНЕ~$c$ МАКСИМАЛЬНОЙ ВОЗРАСТАЮЩЕЙ 
ПОДПОСЛЕДОВАТЕЛЬНОСТИ~$a_{i_1}<a_{i_2}<\ldots<a_{i_c}$, 
ГДЕ~$i_1<i_2<\ldots<i_c$; ЧИСЛО \emph{СТРОК} В~$P$ РАВНО ДЛИНЕ~$r$ 
МАКСИМАЛЬНОЙ УБЫВАЮЩЕЙ 
ПОДПОСЛЕДОВАТЕЛЬНОСТИ~$a_{j_1}>a_{j_2}>\ldots>a_{j_r}$, 
ГДЕ~$j_1<j_2<\ldots<j_r$.

\ex[м18] (п.~эРД╦Ш, г.~сЕКЕРЕШ). дОКАЖИТЕ, ЧТО В ЛЮБОЙ ПЕРЕСТАНОВКЕ,
 СОСТОЯЩЕЙ ИЗ БОЛЕЕ ЧЕМ $n^2$~ ЭЛЕМЕНТОВ, ИМЕЕТСЯ МОНОТОННАЯ 
ПОДПОСЛЕДОВАТЕЛЬНОСТЬ ДЛИНЫ БОЛЕЕ~$n$; ОДНАКО СУЩЕСТВУЮТ ПЕРЕСТАНОВКИ 
$n^2$~ЭЛЕМЕНТОВ, НЕ СОДЕРЖАЩИЕ МОНОТОННЫХ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ ДЛИНЫ 
БОЛЕЕ~$n$. [\emph{уКАЗАНИЕ:} СМ.~ПРЕДЫДУЩЕЕ УПРАЖНЕНИЕ.]

\ex[м24] пРОДОЛЖАЯ УПР.~8, НАЙДИТЕ "ПРОСТУЮ" ФОРМУЛУ ТОЧНОГО 
ЧИСЛА ПЕРЕСТАНОВОК МНОЖЕСТВА~$\set{1, 2,~\ldots, n^2}$, НЕ СОДЕРЖАЩИХ 
МОНОТОННЫХ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ ДЛИНЫ БОЛЕЕ ЧЕМ~$n$.

\ex[м20] дОКАЖИТЕ, ЧТО МАССИВ~$P$ ЯВЛЯЕТСЯ ТАБЛО ПО ОКОНЧАНИИ 
РАБОТЫ АЛГОРИТМА~S, ЕСЛИ ОН БЫЛ ТАБЛО ДО ЭТОГО.

\ex[20] мОЖНО ЛИ ВОССТАНОВИТЬ ИСХОДНЫЙ ВИД ТАБЛО~$P$ ПО ОКОНЧАНИИ РАБОТЫ 
АЛГОРИТМА~S, ЕСЛИ ИЗВЕСТНЫ ТОЛЬКО ЗНАЧЕНИЯ~$r$ И~$s$?

\ex[м24] сКОЛЬКО РАЗ ВЫПОЛНЯЕТСЯ ШАГ~S3, ЕСЛИ АЛГОРИТМ~S 
МНОГОКРАТНО ПРИМЕНЯЕТСЯ ДЛЯ ИСКЛЮЧЕНИЯ ВСЕХ ЭЛЕМЕНТОВ ИЗ ТАБЛО~$P$ 
ФОРМЫ~$(n_1, n_2,~\ldots, n_m)$? кАКОВО МИНИМАЛЬНОЕ ЗНАЧЕНИЕ ЭТОЙ ВЕЛИЧИНЫ 
ПО ВСЕМ ФОРМАМ, ТАКИМ, ЧТО~$n_1+n_2+\cdots+n_m=n$?

\ex[м28] дОКАЖИТЕ ТЕОРЕМУ~C.

\ex[м43] нАЙДИТЕ БОЛЕЕ ПРЯМОЕ ДОКАЗАТЕЛЬСТВО ЧАСТИ~(c) ТЕОРЕМЫ~D.

\ex[м20] сКОЛЬКО ПЕРЕСТАНОВОК 
МУЛЬТИМНОЖЕСТВА~$\set{l\cdot a, m\cdot b, n\cdot c}$ 
ОБЛАДАЮТ ТЕМ СВОЙСТВОМ, ЧТО ЕСЛИ ЧИТАТЬ ПЕРЕСТАНОВКУ СЛЕВА 
НАПРАВО, ТО ЧИСЛО ПРОЧИТАННЫХ БУКВ~$c$ НИКОГДА НЕ ПРЕВЫШАЕТ ЧИСЛА БУКВ~$b$,
КОТОРОЕ В СВОЮ ОЧЕРЕДЬ НЕ ПРЕВЫШАЕТ ЧИСЛА БУКВ~$a$? (нАПРИМЕР, 
ПЕРЕСТАНОВКА~$a\,a\,b\,c\,a\,b\,b\,c\,a\,c\,a$ ОБЛАДАЕТ ЭТИМ СВОЙСТВОМ.)

\ex[м08] сКОЛЬКИМИ СПОСОБАМИ МОЖНО ТОПОЛОГИЧЕСКИ ОТСОРТИРОВАТЬ ЧАСТИЧНОЕ 
УПОРЯДОЧЕНИЕ, ПРЕДСТАВЛЯЕМОЕ ГРАФОМ~(39)?

\ex[вм25] пУСТЬ
$$
g(x_1, x_2, \ldots, x_n; y)=x_1\Delta(x_1+y, x_2, \ldots, x_n)
+x_2\Delta(x_1, x_2+y, \ldots, x_n)+\cdots+x_n\Delta(x_1, x_2, \ldots, x_n+y).
$$
дОКАЖИТЕ, ЧТО
$$
g(x_1, x_2, \ldots, x_n; y)=\left(x_1+x_2+\cdots+x_n+\perm{n}{2}y\right)
\Delta(x_1, x_2, \ldots, x_n).
$$
[\emph{уКАЗАНИЕ:} ПОЛИНОМ~$g$ ОДНОРОДНЫЙ (ВСЕ СЛАГАЕМЫЕ ИМЕЮТ ОДИНАКОВУЮ 
СУММАРНУЮ СТЕПЕНЬ) И АНТИСИММЕТРИЧНЫЙ ПО~$x$ (ЗНАК~$g$ ИЗМЕНИТСЯ, ЕСЛИ 
ПОМЕНЯТЬ МЕСТАМИ~$x_i$ И~$x_j$).]

\ex[вм30] оБОБЩАЯ УПР.~17, ВЫЧИСЛИТЕ ПРИ~$m\ge 0$ СУММУ
$$
x_1^m\Delta(x_1+y, x_2, \ldots, x_n)+\Delta x_2^m(x_1, x_2+y, \ldots, x_n)
+\cdots+x_n^m\Delta(x_1, x_2, \ldots, x_n+y).
$$

\ex[м40] нАЙДИТЕ ФОРМУЛУ ДЛЯ ОПРЕДЕЛЕНИЯ ЧИСЛА СПОСОБОВ, КОТОРЫМИ МОЖНО 
ЗАПОЛНИТЬ МАССИВ, ПОДОБНЫЙ ТАБЛО, НО БЕЗ ПЕРВЫХ ДВУХ КЛЕТОК В ПЕРВОЙ
%%90
СТРОКЕ; НАПРИМЕР, МАССИВ ТАКОЙ ФОРМЫ:
\picture{1. p.90}
(эЛЕМЕНТЫ В СТРОКАХ И СТОЛБЦАХ ДОЛЖНЫ РАСПОЛАГАТЬСЯ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ,
 КАК В ОБЫЧНЫХ ТАБЛО.)

иНАЧЕ ГОВОРЯ, СКОЛЬКО ИЗ~$f(n_1, n_2,~\ldots, n_m)$~ТАБЛО 
ФОРМЫ~$(n_1, n_2,~\ldots, n_m)$, СОСТАВЛЕННЫХ ИЗ 
ЭЛЕМЕНТОВ~$\set{1, 2,~\ldots, n_1+\cdots+n_m}$, 
СОДЕРЖАТ ЭЛЕМЕНТЫ~$1$ И~$2$ В ПЕРВОЙ СТРОКЕ?

\rex[м24] дОКАЖИТЕ, ЧТО ЧИСЛО СПОСОБОВ ПОМЕТИТЬ УЗЛЫ ДАННОГО БИНАРНОГО 
ДЕРЕВА ЭЛЕМЕНТАМИ~$\set{1, 2,~\ldots, n}$ ТАК, ЧТОБЫ МЕТКА КАЖДОГО УЗЛА 
БЫЛА МЕНЬШЕ МЕТКИ ЛЮБОГО ИЗ ЕГО ПОТОМКОВ, РАВНО ЧАСТНОМУ ОТ ДЕЛЕНИЯ~$n!$ 
НА ПРОИЗВЕДЕНИЕ "ДЛИН ПОДДЕРЕВЬЕВ", Т.~Е.~КОЛИЧЕСТВ УЗЛОВ В КАЖДОМ 
ПОДДЕРЕВЕ. (сР.~С~ТЕОРЕМОЙ~н.). нАПРИМЕР, ЧИСЛО СПОСОБОВ ПОМЕТИТЬ УЗЛЫ ДЕРЕВА
\picture{1. p.90}
РАВНО~$10!/10\cdot 4\cdot 5\cdot 1\cdot 2\cdot 3\cdot 1\cdot 1\cdot 1\cdot 1=9\cdot 8\cdot 7\cdot 6$.

\ex[BM3I] (р.~м.~тРОЛЛ). пУСТЬ ЧИСЛА~$n_1>n_2>\ldots>n_m$ ОПИСЫВАЮТ ФОРМУ 
"СДВИНУТОГО ТАБЛО", В КОТОРОМ СТРОКА~$i+1$ НАЧИНАЕТСЯ НА ОДНУ ПОЗИЦИЮ, 
ПРАВЕЕ, ЧЕМ СТРОКА~$i$; НАПРИМЕР, СДВИНУТОЕ ТАБЛО ФОРМЫ~$(7, 5, 4, 1)$
ИЗОБРАЖЕНО НА ДИАГРАММЕ
\picture{3. p.90}
дОКАЖИТЕ, ЧТО ЧИСЛО СПОСОБОВ ЗАПОЛНИТЬ СДВИНУТОЕ ТАБЛО 
ФОРМЫ~$(n_1, n_2,~\ldots, n_m)$ ЧИСЛАМИ~$1$, $2$,~\dots, 
$n=n_1+n_2+\cdots n_m$ ТАК, ЧТОБЫ 
ЧИСЛА ВО ВСЕХ СТРОКАХ И СТОЛБЦАХ РАСПОЛАГАЛИСЬ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ, 
РАВНО ЧАСТНОМУ ОТ ДЕЛЕНИЯ~$n!$ НА ПРОИЗВЕДЕНИЕ "ДЛИН ОБОБЩЕННЫХ 
УГОЛКОВ"; НА РИСУНКЕ ЗАШТРИХОВАН ОБОБЩЕННЫЙ УГОЛОК ДЛИНЫ~$11$, 
СООТВЕТСТВУЮЩИЙ КЛЕТКЕ СТРОКИ~$1$ И СТОЛБЦА~$2$. (уГОЛКИ В ЛЕВОЙ ЧАСТИ 
МАССИВА, ИМЕЮЩЕЙ ВИД "ПЕРЕВЕРНУТОЙ ЛЕСТНИЦЫ", ИМЕЮТ
%% 91
ФОРМУ БУКВЫ~U, ПОВЕРНУТОЙ НА~$90^\circ$, А НЕ БУКВЫ~L.) иТАК, СУЩЕСТВУЕТ
$$
17! / 12\cdot 11\cdot 8\cdot 7\cdot 5\cdot 4\cdot 1\cdot 9\cdot 6\cdot 
5\cdot 3\cdot 2\cdot 5\cdot 4\cdot 2\cdot 1\cdot 1
$$
СПОСОБОВ ЗАПОЛНИТЬ ИЗОБРАЖЕННУЮ ВЫШЕ ФОРМУ ТАК, ЧТОБЫ ЭЛЕМЕНТЫ ВО 
ВСЕХ СТРОКАХ И СТОЛБЦАХ РАСПОЛАГАЛИСЬ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ.

\rex[вм30] (д.~аНДРЭ). чЕМУ РАВНО ЧИСЛО~$A_n$ СПОСОБОВ ЗАПОЛНИТЬ 
ЧИСЛАМИ~$\set{1, 2,~\ldots, n}$ МАССИВ ИЗ $n$~ЯЧЕЕК
\picture{p.91}
ТАК, ЧТОБЫ ВО ВСЕХ СТРОКАХ И СТОЛБЦАХ ОНИ РАСПОЛАГАЛИСЬ В 
ВОЗРАСТАЮЩЕМ ПОРЯДКЕ? нАЙДИТЕ ПРОИЗВОДЯЩУЮ ФУНКЦИЮ~$g(z)=\sum A_n z^n/n!$

\ex[M39] сКОЛЬКИМИ СПОСОБАМИ МОЖНО ЗАПОЛНИТЬ МАССИВ 
ФОРМЫ~$(n_1, n_2,~\ldots, n_m)$ ЭЛЕМЕНТАМИ МНОЖЕСТВА~$\set{1, 2,~\ldots, N}$, \emph{ЕСЛИ 
ДОПУСКАЮТСЯ ОДИНАКОВЫЕ ЭЛЕМЕНТЫ,} ПРИЧЕМ В СТРОКАХ ЭЛЕМЕНТЫ ДОЛЖНЫ 
РАСПОЛАГАТЬСЯ В НЕУБЫВАЮЩЕМ ПОРЯДКЕ, А В СТОЛБЦАХ---В СТРОГО ВОЗРАСТАЮЩЕМ? 
нАПРИМЕР,
ПРОСТУЮ ФОРМУ ИЗ $m$~СТРОК $(1, 1,~\ldots, 1)$ МОЖНО ЗАПОЛНИТЬ $\perm{N}{m}$~СПОСОБАМИ;
ФОРМУ ИЗ ОДНОЙ СТРОКИ~$m$ МОЖНО ЗАПОЛНИТЬ $\perm{m+N-1}{m}$~СПОСОБАМИ; 
ФОРМУ~$(2, 2)$ МОЖНО ЗАПОЛНИТЬ ${1\over3}\perm{N+1}{2}\perm{N}{2}$~СПОСОБАМИ.

\ex[м28] дОКАЖИТЕ, ЧТО
$$
\displaylines{
\sum_{\scriptstyle q_1+\cdots+q_=t \atop \scriptstyle 0\le q_1,~\ldots, q_n\le m}
\perm{m}{q_1}\ldots\perm{m}{q_n}\Delta(q_1,~\ldots, q_n)^2=\hfill\cr
\hfill =n!\perm{nm-(n^2-n)}{t-{1\over 2}(n^2-n)} \perm{m}{n-1} 
\perm{m}{n-2}\ldots \perm{m}{0}\Delta(n-1,~\ldots, 0)^2. \cr
}
$$
[\emph{уКАЗАНИЯ:} ДОКАЖИТЕ, 
ЧТО~$\Delta(k_1+n-1,~\ldots, k_n)=\Delta(m-k_n+n-1,~\ldots, m-k_1)$; 
РАЗЛОЖИТЕ ТАБЛО ФОРМЫ~$n\times (m-n+1)$ СПОСОБОМ, АНАЛОГИЧНЫМ~(38), И 
ПРЕОБРАЗУЙТЕ СУММУ, КАК ПРИ ВЫВОДЕ ТОЖДЕСТВА~(36).]


\ex[м20] пОЧЕМУ~(42) ЯВЛЯЕТСЯ ПРОИЗВОДЯЩЕЙ ФУНКЦИЕЙ ДЛЯ ИНВОЛЮЦИЙ?

\ex[вм21] вЫЧИСЛИТЕ~$\int_{-\infty}^\infty x^t \exp(-2x^2/ \sqrt{n})\,dx$ 
ПРИ НЕОТРИЦАТЕЛЬНОМ ЦЕЛОМ~$t$.

\ex[м24] пУСТЬ~$Q$---ТАБЛО яНГА ИЗ ЭЛЕМЕНТОВ~$\set{1, 2,~\ldots, n}$, И 
ПУСТЬ ЭЛЕМЕНТ~$t$ НАХОДИТСЯ В СТРОКЕ~$r_i$ И СТОЛБЦЕ~$c_i$. мЫ ГОВОРИМ, 
ЧТО~$i$ "ВЫШЕ"~$j$, ЕСЛИ~$r_i<r_j$.
{\medskip\narrower
\item{a)}~дОКАЖИТЕ, ЧТО ПРИ~$1\le i < n$ ЭЛЕМЕНТ~$i$ ВЫШЕ~$i+1$ ТОГДА И 
ТОЛЬКО ТОГДА, КОГДА~$c_i\ge c_{i+1}$.
%%92
\item{b)}~пУСТЬ~$Q$ ТАКОЕ, ЧТО $(P, Q)$~СООТВЕТСТВУЮТ ПЕРЕСТАНОВКЕ
$$
\pmatrix{
1 & 2 & \ldots & n \cr
a_1 & a_2 & \ldots & a_n \cr
}
$$
дОКАЖИТЕ, ЧТО~$i$ ВЫШЕ~$i+1$ ТОГДА И ТОЛЬКО ТОГДА, КОГДА~$a_i>a_{i+1}$.
(сЛЕДОВАТЕЛЬНО, МОЖНО НАЙТИ ЧИСЛО ОТРЕЗКОВ ПЕРЕСТАНОВКИ, ЗНАЯ ТОЛЬКО~$Q$. 
эТОТ РЕЗУЛЬТАТ ПОЛУЧЕН шЮЦЕНБЕРЖЕ.)
%
\item{c)}~дОКАЖИТЕ, ЧТО ПРИ~$1\le i < n$ ЭЛЕМЕНТ~$i$ ВЫШЕ~$i+1$ В~$Q$ 
ТОГДА И ТОЛЬКО ТОГДА, КОГДА~$i+1$ ВЫШЕ~$i$ В~$Q^S$.
\medskip}

\ex[м47] кАКОВО АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ СРЕДНЕЙ ДЛИНЫ МАКСИМАЛЬНОЙ 
ВОЗРАСТАЮЩЕЙ ПОСЛЕДОВАТЕЛЬНОСТИ В СЛУЧАЙНОЙ ПЕРЕСТАНОВКЕ 
МНОЖЕСТВА~$\set{1, 2,~\ldots, n}$? (эТО СРЕДНЯЯ ДЛИНА ПЕРВОЙ СТРОКИ В 
СООТВЕТСТВИИ ИЗ ТЕОРЕМЫ~A. оБШИРНЫЕ ТАБЛИЦЫ, ВЫЧИСЛЕННЫЕ р.~м.~бАЕРОМ 
И~п.~бРОКОМ [{\sl Math. Comp.,\/} {\bf 22} (1968), 385--410], В СВЯЗИ С ТЕМ, 
ЧТО ОНИ НАЗВАЛИ "ЕСТЕСТВЕННОЙ СОРТИРОВКОЙ", ПОЗВОЛЯЮТ ПРЕДПОЛОЖИТЬ, ЧТО 
СРЕДНЕЕ~$l_n$ РАВНО ПРИМЕРНО~$2\sqrt{n}$; л.~шЕПП И~б.~лОГАН ДОКАЗАЛИ, 
ЧТО~$\liminf_{n\to\infty} l_n / \sqrt{n}\ge 2$ (В ПЕЧАТИ).

\ex[м50] иССЛЕДУЙТЕ ТРЕХМЕРНЫЕ МАССИВЫ, С ТЕМ ЧТОБЫ ПОНЯТЬ, КАКИЕ СВОЙСТВА 
ДВУМЕРНЫХ ТАБЛО МОЖНО ОБОБЩИТЬ.

\ex[м42] (м.~п.~шЮЦЕНБЕРЖЕ). пОКАЖИТЕ, ЧТО ОПЕРАЦИЯ ПЕРЕХОДА ОТ~$P$ 
К~$P^S$---ЧАСТНЫЙ СЛУЧАЙ ОПЕРАЦИИ, КОТОРУЮ МОЖНО СВЯЗАТЬ С ЛЮБЫМ КОНЕЧНЫМ 
ЧАСТИЧНО УПОРЯДОЧЕННЫМ МНОЖЕСТВОМ, А НЕ ТОЛЬКО С ТАБЛО. пОМЕТЬТЕ ЭЛЕМЕНТЫ 
ЧАСТИЧНО УПОРЯДОЧЕННОГО МНОЖЕСТВА ЦЕЛЫМИ ЧИСЛАМИ~$\set{1, 2,~\ldots, n}$ 
ТАК, ЧТОБЫ ЭТА СИСТЕМА МЕТОК БЫЛА СОГЛАСОВАНА С ЧАСТИЧНЫМ 
УПОРЯДОЧЕНИЕМ. нАЙДИТЕ ДВОЙСТВЕННУЮ СИСТЕМУ МЕТОК, АНАЛОГИЧНУЮ~(26), ПУТЕМ 
ПОСЛЕДОВАТЕЛЬНОГО УДАЛЕНИЯ МЕТОК~$1$, $2$,~\dots, ПЕРЕДВИГАЯ ПРИ ЭТОМ 
ДРУГИЕ МЕТКИ СПОСОБОМ, ПОДОБНЫМ АЛГОРИТМУ~S, И ПОМЕЩАЯ МЕТКИ~(1), (2),~\dots{} 
НА ОСВОБОДИВШИЕСЯ МЕСТА. пОКАЖИТЕ, ЧТО ЭТА ОПЕРАЦИЯ, ЕСЛИ ЕЕ 
МНОГОКРАТНО ПРИМЕНЯТЬ К ДВОЙСТВЕННОЙ СИСТЕМЕ МЕТОК С ОБРАТНЫМ ОТНОШЕНИЕМ 
ПОРЯДКА ДЛЯ ЧИСЕЛ, ДАЕТ ИСХОДНУЮ СИСТЕМУ МЕТОК; ИССЛЕДУЙТЕ ДРУГИЕ СВОЙСТВА 
ЭТОЙ ОПЕРАЦИИ

\ex[вм30] пУСТЬ~$x_n$---ЧИСЛО СПОСОБОВ РАЗМЕСТИТЬ~$n$ ВЗАИМНО 
НЕАТАКУЮЩИХ ЛАДЕЙ НА ШАХМАТНОЙ ДОСКЕ РАЗМЕРА~$n\times n$ ТАКИМ ОБРАЗОМ, 
ЧТО РАСПОЛОЖЕНИЕ НЕ МЕНЯЕТСЯ ПРИ ОТРАЖЕНИИ ДОСКИ ОТНОСИТЕЛЬНО ОДНОЙ ИЗ 
ГЛАВНЫХ ДИАГОНАЛЕЙ И ПРИ ПОВОРОТЕ НА~$180^\circ$. нАЙДИТЕ АСИМПТОТИЧЕСКОЕ 
ПОВЕДЕНИЕ~$x_n$.

%% 93
\bye