\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$. нАСТОЯТЕЛЬНО РЕКОМЕНДУЕМ ЧИТАТЕЛЮ ИСПЫТАТЬ ЭТИ ПРОЦЕССЫ
НА НЕСКОЛЬКИХ ПРОСТЫХ ПРИМЕРАХ. нЕОБЫЧНАЯ ПРИРОДА ЭТИХ СОВПАДЕНИЙ МОЖЕТ
ВЫЗВАТЬ ПОДОЗРЕНИЕ О ВМЕШАТЕЛЬСТВЕ КАКИХ-ТО КОЛДОВСКИХ СИЛ. дО СИХ ПОР
НЕ ИЗВЕСТНО КАКОГО-ЛИБО ПРОСТОГО ОБRЯСНЕНИЯ ПОДОБНЫХ ЯВЛЕНИЙ; КАЖЕТСЯ, НЕ
СУЩЕСТВУЕТ ПРОСТОГО СПОСОБА ДОКАЗАТЬ ДАЖЕ ТО, ЧТО СЛУЧАЙ~(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 ОСНОВАНЫ НА ОДНОМ
НЕУБЕДИТЕЛЬНОМ ИНДУКТИВНОМ РАССУЖДЕНИИ, КОТОРОЕ НА САМОМ ДЕЛЕ НЕ ОБRЯСНЯЕТ,
ПОЧЕМУ ЖЕ ТЕОРЕМА ВЕРНА (ТАК КАК В НЕМ СОВЕРШЕННО НЕ ИСПОЛЬЗУЮТСЯ
СВОЙСТВА УГОЛКОВ).
сУЩЕСТВУЕТ ИНТЕРЕСНАЯ СВЯЗЬ МЕЖДУ ТЕОРЕМОЙ~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