\input style
\chapno=5
\subchno=1
\subsubchno=1
\chapnotrue
\excercises
%% 36
сУЩЕСТВУЕТ ЛИ КОМБИНАТОРНОЕ ДОКАЗАТЕЛЬСТВО ТОЖДЕСТВА яКОБИ, АНАЛОГИЧНОЕ 
ДОКАЗАТЕЛЬСТВУ фРАНКЛИНА ДЛЯ ЧАСТНОГО СЛУЧАЯ УПР.~14? (тАКИМ ОБРАЗОМ,
 НУЖНО РАССМОТРЕТЬ "КОМПЛЕКСНЫЕ РАЗБИЕНИЯ"
$$
m+ni=(p_1+q_1i)+(p_2+q_2i)+\cdots+(p_k+q_ki),
$$
ГДЕ $p_j+q_ji$---РАЗЛИЧНЫЕ НЕНУЛЕВЫЕ КОМПЛЕКСНЫЕ ЧИСЛА; $p_j$, 
$q_j$---НЕОТРИЦАТЕЛЬНЫЕ ЦЕЛЫЕ ЧИСЛА, ПРИЧЕМ $\abs{p_j-q_j}\le 1$. сОГЛАСНО 
ТОЖДЕСТВУ яКОБИ, ЧИСЛО ТАКИХ ПРЕДСТАВЛЕНИЙ С ЧЕТНЫМИ $k$ РАВНО ЧИСЛУ 
ПРЕДСТАВЛЕНИЙ С НЕЧЕТНЫМИ $k$, ЕСЛИ ТОЛЬКО $m$ И~$n$ НЕ ЯВЛЯЮТСЯ СОСЕДНИМИ 
ТРЕУГОЛЬНЫМИ ЧИСЛАМИ!) кАКИМИ ЕЩЕ ЗАМЕЧАТЕЛЬНЫМИ СВОЙСТВАМИ ОБЛАДАЮТ 
КОМПЛЕКСНЫЕ РАЗБИЕНИЯ?

\rex[м25] (г. д. кНОТТ.) пОКАЖИТЕ, ЧТО ПЕРЕСТАНОВКУ $a_1$ \dots $a_n$ 
МОЖНО ПОЛУЧИТЬ С ПОМОЩЬЮ СТЕКА В СМЫСЛЕ УПР. 2.2.1--5 ИЛИ~2.3.1--6 ТОГДА И 
ТОЛЬКО ТОГДА, КОГДА $C_j\le C_{j+1}+1$  ПРИ $1\le j<n$ (СМ. ОБОЗНАЧЕНИЯ В УПР.~7).

\ex[м28] (к. мЕЙЕР.) мЫ ЗНАЕМ, ЧТО ЕСЛИ $m$ И~$n$---ВЗАИМНО ПРОСТЫЕ ЧИСЛА,
 ТО ПОСЛЕДОВАТЕЛЬНОСТЬ $(m \bmod n)$ $(2m \bmod n)$ \dots $((n-1) m\bmod 
n)$ ПРЕДСТАВЛЯЕТ СОБОЙ ПЕРЕСТАНОВКУ МНОЖЕСТВА $\{1, 2, \ldots, n-1\}$. 
пОКАЖИТЕ, ЧТО ЧИСЛО ИНВЕРСИЙ В ЭТОЙ ПЕРЕСТАНОВКЕ МОЖНО ВЫРАЗИТЬ ЧЕРЕЗ 
СУММЫ дЕДЕКИНДА (СР. С П.~3.3.3).

\subsubchap{*пЕРЕСТАНОВКИ МУЛЬТИМНОЖЕСТВА}
дО СИХ ПОР МЫ РАССМАТРИВАЛИ ПЕРЕСТАНОВКИ \emph{МНОЖЕСТВА} ЭЛЕМЕНТОВ; ЭТО 
ЧАСТНЫЙ СЛУЧАЙ ПЕРЕСТАНОВОК \dfn{МУЛЬТИМНОЖЕСТВА}. (мУЛЬТИМНОЖЕСТВО---ЭТО ТО 
ЖЕ САМОЕ, ЧТО И МНОЖЕСТВО, НО В НЕМ МОГУТ СОДЕРЖАТЬСЯ ОДИНАКОВЫЕ ЭЛЕМЕНТЫ. 
нЕКОТОРЫЕ ОСНОВНЫЕ СВОЙСТВА МУЛЬТИМНОЖЕСТВ ОБСУЖДАЛИСЬ В П.~4.6.3.)

рАССМОТРИМ, НАПРИМЕР, МУЛЬТИМНОЖЕСТВО
$$
M=\{a, a, a, b, b, c, d, d, d, d\},
\eqno(1)
$$
В КОТОРОМ СОДЕРЖИТСЯ 3 ЭЛЕМЕНТА $a$, 2 ЭЛЕМЕНТА $b$, 1 ЭЛЕМЕНТ $c$ И 4 
ЭЛЕМЕНТА $d$. пОВТОРЕНИЯ ЭЛЕМЕНТОВ МОЖНО УКАЗАТЬ И ДРУГИМ СПОСОБОМ:
$$
M=\{3\cdot a, 2\cdot b, c, 4\cdot d\}.
\eqno(2)
$$
пЕРЕСТАНОВКА МУЛЬТИМНОЖЕСТВА --- ЭТО НЕКОТОРОЕ РАСПОЛОЖЕНИЕ ЕГО ЭЛЕМЕНТОВ В 
РЯД, НАПРИМЕР
$$
c\ a\ b\ d\ d\ a\ b\ d\ a\ d.
$$
с ДРУГОЙ СТОРОНЫ, ТАКУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ МОЖНО НАЗВАТЬ ЦЕПОЧКОЙ БУКВ, 
СОДЕРЖАЩЕЙ 3 БУКВЫ $a$, 2 БУКВЫ $b$, 1 БУКВУ $c$ И 4 БУКВЫ $d$.

сКОЛЬКО СУЩЕСТВУЕТ ПЕРЕСТАНОВОК МУЛЬТИМНОЖЕСТВА $M$? еСЛИ БЫ МЫ 
РАССМАТРИВАЛИ ВСЕ ЭЛЕМЕНТЫ $M$ КАК РАЗЛИЧНЫЕ, ОБОЗНАЧИВ ИХ $a_1$, $a_2$, 
$a_3$, $b_1$, $b_2$, $c_1$, $d_1$, $d_2$, $d_3$, $d_4$, ТО ПОЛУЧИЛИ БЫ 
$10!=3\ 628\ 800$ ПЕРЕСТАНОВОК, НО ПОСЛЕ ОТБРАСЫВАНИЯ ИНДЕКСОВ МНОГИЕ ИЗ 
НИХ ОКАЗАЛИСЬ БЫ ОДИНАКОВЫМИ. фАКТИЧЕСКИ КАЖДАЯ ПЕРЕСТАНОВКА $M$ 
ВСТРЕТИЛАСЬ БЫ РОВНО $3!2!1!4!=288$ РАЗ, ПОСКОЛЬКУ В ЛЮБОЙ ПЕРЕСТАНОВКЕ 
$M$ ИНДЕКСЫ ПРИ БУКВАХ $a$ МОЖНО РАССТАВИТЬ 31 СПОСОБАМИ,
%% 37
ПРИ $b$ (НЕЗАВИСИМО)---2! СПОСОБАМИ, ПРИ $c$---ОДНИМ СПОСОБОМ, А ПРИ 
$d$---СООТВЕТСТВЕННО 4! СПОСОБАМИ. пОЭТОМУ ЧИСЛО ПЕРЕСТАНОВОК $M$ РАВНО
$$
{10!\over 3!2!1!4!}=12\ 600.
$$
в ПРИМЕНЕНИИ К ОБЩЕМУ СЛУЧАЮ ТЕ ЖЕ РАССУЖДЕНИЯ ДОКАЗЫВАЮТ, ЧТО ЧИСЛО 
ПЕРЕСТАНОВОК ЛЮБОГО МУЛЬТИМНОЖЕСТВА РАВНО МУЛЬТИНОМИАЛЬНОМУ КОЭФФИЦИЕНТУ
$$
\perm{n}{n_1, n_2, \ldots}={n!\over n_1!n_2!\ldots},
$$
ГДЕ $n_1$---ЧИСЛО ЭЛЕМЕНТОВ ПЕРВОГО ТИПА, $n_2$---ЧИСЛО ЭЛЕМЕНТОВ ВТОРОГО ТИПА 
И Т. Д., А $n=n_1+n_2+\cdots$---ОБЩЕЕ ЧИСЛО ЭЛЕМЕНТОВ.

кОЛИЧЕСТВО ПЕРЕСТАНОВОК МНОЖЕСТВА БЫЛО ИЗВЕСТНО ЕЩЕ В ДРЕВНИЕ ВРЕМЕНА. в 
ДРЕВНЕЕВРЕЙСКОЙ 
кНИГЕ тВОРЕНИЯ (ОКОЛО 100 Г. Н. Э.)%
\note{1}{кНИГА тВОРЕНИЯ (йОЦИРА)---ОДНА ИЗ ОСНОВОПОЛАГАЮЩИХ КНИГ 
КАББАЛИСТИКИ.--- {\sl пРИМ. ПЕРЕВ.\/}}, НАИБОЛЕЕ РАННЕМ ЛИТЕРАТУРНОМ 
ПРОИЗВЕДЕНИИ ИУДЕЙСКОГО ФИЛОСОФСКОГО МИСТИЦИЗМА, ДАНЫ ВЕРНЫЕ ЗНАЧЕНИЯ 
ПЕРВЫХ СЕМИ ФАКТОРИАЛОВ, ПОСЛЕ ЧЕГО ГОВОРИТСЯ: "пРОДОЛЖАЙ И ПОЛУЧИШЬ ЧИСЛА,
 КОТОРЫЕ УСТА НЕ МОГУТ ПРОИЗНЕСТИ, А УХО НЕ МОЖЕТ ВОСПРИНЯТЬ." [Sefer 
Yezirah, ed. by R. Mordecai Atia (Jerusalem:
Sh. Monson, 1962), СТИХ 52 (СТР. 107--108); СР. ТАКЖЕ С Solomon Gandz, 
Studies in Hebrew Astronomy and Mathematics (New York:
Ktav, 1970), 494--496. кНИГА тВОРЕНИЯ БЫЛА ОСНОВАНА НА СЧИТАВШИХСЯ ВАЖНЫМИ 
ОТНОШЕНИЯХ МЕЖДУ СЕМЬЮ ПЛАНЕТАМИ, СЕМЬЮ СОГЛАСНЫМИ ЗВУКАМИ С ДВОЙНЫМ 
ПРОИЗНОШЕНИЕМ, СЕМЬЮ ОТВЕРСТИЯМИ В ГОЛОВЕ ЧЕЛОВЕКА И СЕМЬЮ ДНЯМИ 
СОТВОРЕНИЯ МИРА.] эТО ПЕРВЫЙ ИЗВЕСТНЫЙ В ИСТОРИИ ПОДСЧЕТ ЧИСЛА 
ПЕРЕСТАНОВОК. вТОРОЙ ВСТРЕЧАЕТСЯ В ИНДИЙСКОМ КЛАССИЧЕСКОМ ПРОИЗВЕДЕНИИ 
аНУЙОГАДВАРА-СУТРА (ОКОЛО 500~Г.~Н.~Э.), ПРАВИЛО 97, ГДЕ 
ПРИВОДИТСЯ ФОРМУЛА ЧИСЛА ПЕРЕСТАНОВОК ШЕСТИ ЭЛЕМЕНТОВ, КОТОРЫЕ НЕ 
РАСПОЛОЖЕНЫ НИ В ВОЗРАСТАЮЩЕМ, НИ В УБЫВАЮЩЕМ ПОРЯДКЕ:
$$
6\times5\times4\times3\times2\times1-2.
$$
[сМ. G. Chakravarti, {\sl Bull. Calcutta Math. Soc.\/}, {\bf 24} (1932), 
79--88. аНУЙОГАДВАРА-СУТРА---ОДНА ИЗ КНИГ КАНОНОВ ДЖАЙНИЗМА, РЕЛИГИОЗНОЙ 
СЕКТЫ, РАСПРОСТРАНЕННОЙ В иНДИИ.]

сООТВЕТСТВУЮЩЕЕ ПРАВИЛО ДЛЯ МУЛЬТИМНОЖЕСТВ ВПЕРВЫЕ, ПО- ВИДИМОМУ, 
ВСТРЕЧАЕТСЯ В КНИГЕ лИЛАВАТИ, НАПИСАННОЙ бХАСКАРОЙ аХАРЬЕЙ (ОК. 1150~Г.), 
РАЗД.~270--271. у бХАСЖАРЫ ЭТО ПРАВИЛО СФОРМУЛИРОВАНО ВЕСЬМА СЖАТО И 
ПРОИЛЛЮСТРИРОВАНО ЛИШЬ ДВУМЯ ПРОСТЫМИ ПРИМЕРАМИ $\{2, 2, 1, 1\}$ И~$\{4, 8,
 5, 5, 5\}$. в РЕЗУЛЬТАТЕ В АНГЛИЙСКОМ ПЕРЕВОДЕ ЭТО ПРАВИЛО НЕ СФОРМУЛИРОВАНО
%% 38
КОРРЕКТНО, ВПРОЧЕМ, ИМЕЮТСЯ НЕКОТОРЫЕ СОМНЕНИЯ ОТНОСИТЕЛЬНО ТОГО, ПОНИМАЛ 
ЛИ САМ бХАСКАРА, О ЧЕМ ОН ГОВОРИЛ. вСЛЕД ЗА ЭТИМ ПРАВИЛОМ бХАСКАРА 
ПРИВОДИТ ИНТЕРЕСНУЮ ФОРМУЛУ
$$
(4+8+5+5+5)\times 120\times 11111 \over 5\times 6
$$
ДЛЯ СУММЫ 20 ЧИСЕЛ $48\ 555 + 45 855 + \cdots$.

вЕРНОЕ ПРАВИЛО ДЛЯ НАХОЖДЕНИЯ ЧИСЛА ПЕРЕСТАНОВОК В СЛУЧАЕ, КОГДА ТОЛЬКО 
ОДИН ЭЛЕМЕНТ МОЖЕТ ПОВТОРЯТЬСЯ, НАЙДЕНО НЕЗАВИСИМО НЕМЕЦКИМ УЧЕНЫМ 
ИЕЗУИТОМ аТАНАСИУСОМ кИРХЕРОМ В ЕГО МНОГОТОМНОМ ТРУДЕ О МУЗЫКЕ Musurgia 
Universalis (Rome, 1650), ТОМ~2, СТР.~5--7. кИРХЕРА ИНТЕРЕСОВАЛ ВОПРОС О 
КОЛИЧЕСТВЕ МЕЛОДИЙ, КОТОРЫЕ МОЖНО СОЗДАТЬ ИЗ ДАННОГО НАБОРА НОТ;
ДЛЯ ЭТОГО ОН ПРИДУМАЛ ТО, ЧТО НАЗЫВАЛ "МУЗАРИФМЕТИКОЙ". нА СТР. 18--21 
СВОЕГО ТРУДА ОН ДАЕТ ВЕРНОЕ ЗНАЧЕНИЕ ЧИСЛА ПЕРЕСТАНОВОК МУЛЬТИМНОЖЕСТВА 
$\{m\cdot C, n\cdot D\}$ ПРИ НЕСКОЛЬКИХ ЗНАЧЕНИЯХ $m$ И $n$, ХОТЯ ОПИСАЛ 
ОН СВОЙ МЕТОД ВЫЧИСЛЕНИЙ ЛИШЬ ДЛЯ СЛУЧАЯ $n= 1$.

оБЩЕЕ ПРАВИЛО (3) ПОЯВИЛОСЬ ПОЗЖЕ В КНИГЕ жАНА пРЕСТЭ El\'emens de 
Math\'ematiques (Paris, 1675), СТР. 351--352, КОТОРАЯ СОДЕРЖИТ ОДНО ИЗ 
ПЕРВЫХ ИЗЛОЖЕНИЙ КОМБИНАТОРНОЙ МАТЕМАТИКИ, НАПИСАННЫХ В ЗАПАДНОЙ еВРОПЕ. 
пРЕСТЭ ВЕРНО СФОРМУЛИРОВАЛ ПРАВИЛО ДЛЯ СЛУЧАЯ ПРОИЗВОЛЬНОГО 
МУЛЬТИМНОЖЕСТВА, НО ПРОИЛЛЮСТРИРОВАЛ ЕГО ЛИШЬ ПРОСТЫМ ПРИМЕРОМ $\{a, a, 
b, b, c, c\}$. оН ОСОБО ОТМЕТИЛ, ЧТО ДЕЛЕНИЕ НА \emph{СУММУ} ФАКТОРИАЛОВ, 
КОТОРОЕ ОН СЧИТАЛ ЕСТЕСТВЕННЫМ ОБОБЩЕНИЕМ ПРАВИЛА кИРХЕРА, БЫЛО БЫ ОШИБКОЙ.
 нЕСКОЛЬКО ЛЕТ СПУСТЯ дЖОН вАЛЛИС В СВОЕЙ КНИГЕ Treatise of Algebra 
(Oxford, 1685), ТОМ 2, СТР. 117--118, ОБСУДИЛ ЭТО ПРАВИЛО НЕСКОЛЬКО БОЛЕЕ ПОДРОБНО.

в 1965~Г. дОМИНИК фОАТА ВВЕЛ ОДНО ИНТЕРЕСНОЕ ПОНЯТИЕ, ТАК НАЗЫВАЕМОЕ 
"СОЕДИНИТЕЛЬНОЕ ПРОИЗВЕДЕНИЕ"%
\note{1}{в ОРИГИНАЛЕ---"intercalation product".---{\sl пРИМ. ПЕРЕВ.\/}}, 
КОТОРОЕ ПОЗВОЛИЛО РАСПРОСТРАНИТЬ МНОГИЕ ИЗВЕСТНЫЕ РЕЗУЛЬТАТЫ, КАСАЮЩИЕСЯ 
ОБЫЧНЫХ ПЕРЕСТАНОВОК, НА ОБЩИЙ СЛУЧАИ ПЕРЕСТАНОВОК МУЛЬТИМНОЖЕСТВА. 
[сМ. Publ. Inst. Statistique, Univ. Paris, {\bf 14} (1965), 81--241. А 
ТАКЖЕ Lecture Notes in Math., {\bf 85} (Springer, 1969).] пРЕДПОЛАГАЯ, ЧТО 
ЭЛЕМЕНТЫ МУЛЬТИМНОЖЕСТВА КАКИМ-ТО СПОСОБОМ ЛИНЕЙНО УПОРЯДОЧЕНЫ, МОЖНО 
РАССМОТРЕТЬ \dfn{ДВУСТРОЧНОЕ ОБОЗНАЧЕНИЕ}, НАПРИМЕР
$$
\pmatrix{
 a & a & a & b & b & c & d & d & d & d\cr
 c & a & b & d & d & a & b & d & a & d\cr
}.
$$
зДЕСЬ ВЕРХНЯЯ СТРОКА СОДЕРЖИТ ЭЛЕМЕНТЫ $M$ В НЕУБЫВАЮЩЕМ ПОРЯДКЕ, И 
НИЖНЯЯ---ЭТО САМА ПЕРЕСТАНОВКА. \dfn{сОЕДИНИТЕЛЬНОЕ
%%39
ПРОИЗВЕДЕНИЕ} $\alpha\T\beta$  ДВУХ ПЕРЕСТАНОВОК МУЛЬТИМНОЖЕСТВ $\alpha$  
И $\beta$---ЭТО ПЕРЕСТАНОВКА, КОТОРАЯ ПОЛУЧАЕТСЯ, ЕСЛИ (a) ВЗЯТЬ 
ДВУСТРОЧНЫЕ ОБОЗНАЧЕНИЯ ДЛЯ $\alpha$ И~$\beta$, (b) ЗАПИСАТЬ 
СООТВЕТСТВУЮЩИЕ СТРОКИ В ОДНУ И (c) ОТСОРТИРОВАТЬ СТОЛБЦЫ ТАК, ЧТОБЫ 
ЭЛЕМЕНТЫ ВЕРХНЕЙ СТРОКИ РАСПОЛОЖИЛИСЬ В НЕУБЫВАЮЩЕМ ПОРЯДКЕ. 
сОРТИРОВКА ДОЛЖНА БЫТЬ УСТОЙЧИВОЙ В ТОМ СМЫСЛЕ, ЧТО ВЗАИМНОЕ 
РАСПОЛОЖЕНИЕ ЭЛЕМЕНТОВ НИЖНЕЙ СТРОКИ СОХРАНЯЕТСЯ, ЕСЛИ СООТВЕТСТВУЮЩИЕ 
ЭЛЕМЕНТЫ ВЕРХНЕЙ СТРОКИ РАВНЫ. нАПРИМЕР, 
$c\ a\ d\ a\ b \T b\ d\ d\ a\ d=c\ a\ b \ d\ d\ a\ b\ d\ a\ d$, ТАК КАК
$$
\pmatrix{
a & a & b & c & d \cr
c & a & d & a & b\cr
}\T
\pmatrix{
a & b & d & d & d \cr
b & d & d & a & d\cr
}=
\pmatrix{
a & a & a & b & b & c & d & d & d & d\cr
c & a & b & d & d & a & b & d & a & d\cr
}.
\eqno(5)
$$

нЕТРУДНО ВИДЕТЬ, ЧТО ОПЕРАЦИЯ СОЕДИНИТЕЛЬНОГО ПРОИЗВЕДЕНИЯ АССОЦИАТИВНА, 
Т.~Е.
$$
\alpha\T\beta\T\gamma=\alpha\T(\beta\T\gamma),
\eqno(6)
$$
И ЧТО ОНА ПОДЧИНЯЕТСЯ ЗАКОНАМ СОКРАЩЕНИЯ
$$
\eqalign{
&\hbox{ЕСЛИ $\pi\T\alpha=\pi\T\beta$, ТО $\alpha=\beta$,}\cr
&\hbox{ЕСЛИ $\alpha\T\pi=\beta\T\pi$, ТО $\alpha=\beta$.}\cr
}
$$
сУЩЕСТВУЕТ "ЕДИНИЧНЫЙ ЭЛЕМЕНТ"
$$
\alpha\T\varepsilon=\varepsilon\T\alpha=\alpha,
\eqno(8)
$$
ГДЕ $\varepsilon$---ПУСТАЯ ПЕРЕСТАНОВКА, "РАСПОЛОЖЕНИЕ В РЯД" 
ЭЛЕМЕНТОВ ПУСТОГО МНОЖЕСТВА. зАКОН КОММУТАТИВНОСТИ, ВООБЩЕ ГОВОРЯ, 
НЕ ВЫПОЛНЯЕТСЯ (СМ. УПР.~2), ТЕМ НЕ МЕНЕЕ
$$
\alpha\T\beta=\beta\T\alpha,
\rem{ЕСЛИ $\alpha$ И~$\beta$ НЕ СОДЕРЖАТ ОБЩИХ БУКВ.}
\eqno (9)
$$

аНАЛОГИЧНЫМ СПОСОБОМ И ПОНЯТИЕ \emph{ЦИКЛА} МОЖНО РАСПРОСТРАНИТЬ НА СЛУЧАЙ,
КОГДА ЭЛЕМЕНТЫ МОГУТ ПОВТОРЯТЬСЯ. бУДЕМ ЗАПИСЫВАТЬ В ВИДЕ
$$
(x_1\  x_2\ \dots\ x_n) 
\eqno (10)
$$
ПЕРЕСТАНОВКУ, ДВУСТРОЧНОЕ ПРЕДСТАВЛЕНИЕ КОТОРОЙ ПОЛУЧАЕТСЯ ПУТЕМ 
УСТОЙЧИВОЙ СОРТИРОВКИ СТОЛБЦОВ
$$
\pmatrix{
x_1 & x_2 & \ldots & x_n\cr
x_2 & x_3 & \ldots & x_1\cr
}
\eqno(11)
$$
ПО ВЕРХНИМ ЭЛЕМЕНТАМ. нАПРИМЕР,
$$
\pmatrix{
d & b & d & d & a & c & a & a & b & d \cr
}=
\pmatrix{
d & b & d & d & a & c & a & a & b & d \cr
b & d & d & a & c & a & a & b & d & d\cr
}=
\pmatrix{
a & a & a & b & b & c & d & d & d & d \cr
c & a & b & d & d & a & b & d & a & d\cr
}
$$
%%40
ТАК ЧТО ПЕРЕСТАНОВКА (4) ФАКТИЧЕСКИ ЯВЛЯЕТСЯ ЦИКЛОМ. мЫ МОГЛИ БЫ ОПИСАТЬ 
ЭТОТ ЦИКЛ СЛОВЕСНО, СКАЗАВ ЧТО-НИБУДЬ ВРОДЕ "$d$ ПЕРЕХОДИТ В $b$, 
ПЕРЕХОДИТ В $d$, ПЕРЕХОДИТ В $d$, ПЕРЕХОДИТ В \dots ПЕРЕХОДИТ В $d$ И 
ВОЗВРАЩАЕТСЯ ОБРАТНО". зАМЕТИМ, ЧТО ЭТИ ОБОБЩЕННЫЕ ЦИКЛЫ НЕ ОБЛАДАЮТ 
ВСЕМИ СВОЙСТВАМИ ОБЫЧНЫХ ЦИКЛОВ;
$(x_1\ x_2\ \ldots\ x_n)$ НЕ ОБЯЗАТЕЛЬНО ТО ЖЕ САМОЕ, ЧТО И 
$(x_2\ \ldots\ x_n\ x_1)$ .

в П.~1.3.3 МЫ ВЫЯСНИЛИ, ЧТО КАЖДУЮ ПЕРЕСТАНОВКУ МНОЖЕСТВА МОЖНО 
ЕДИНСТВЕННЫМ С ТОЧНОСТЬЮ ДО ПОРЯДКА СОМНОЖИТЕЛЕЙ ОБРАЗОМ ПРЕДСТАВИТЬ В 
ВИДЕ ПРОИЗВЕДЕНИЯ НЕПЕРЕСЕКАЮЩИХСЯ ЦИКЛОВ, ГДЕ ПРОИЗВЕДЕНИЕ ПЕРЕСТАНОВОК 
ОПРЕДЕЛЯЕТСЯ ЗАКОНОМ КОМПОЗИЦИИ. лЕГКО ВИДЕТЬ, ЧТО \dfn{ПРОИЗВЕДЕНИЕ 
НЕПЕРЕСЕКАЮЩИХСЯ ЦИКЛОВ---ТО ЖЕ САМОЕ, ЧТО ИХ СОЕДИНИТЕЛЬНОЕ ПРОИЗВЕДЕНИЕ;} 
ЭТО НАВОДИТ НА МЫСЛЬ О ТОМ, ЧТО МОЖНО БУДЕТ ОБОБЩИТЬ ПОЛУЧЕННЫЕ РАНЕЕ 
РЕЗУЛЬТАТЫ, ЕСЛИ НАЙТИ ЕДИНСТВЕННОЕ (В КАКОМ-ТО СМЫСЛЕ) ПРЕДСТАВЛЕНИЕ И 
ДЛЯ ПРОИЗВОЛЬНОЙ ПЕРЕСТАНОВКИ МУЛЬТИМНОЖЕСТВА В ВИДЕ СОЕДИНИТЕЛЬНОГО 
ПРОИЗВЕДЕНИЯ ЦИКЛОВ. в ДЕЙСТВИТЕЛЬНОСТИ СУЩЕСТВУЮТ ПО КРАЙНЕЙ МЕРЕ ДВА 
ЕСТЕСТВЕННЫХ СПОСОБА СДЕЛАТЬ ЭТО, И КАЖДЫЙ ИЗ НИХ ИМЕЕТ ВАЖНЫЕ ПРИЛОЖЕНИЯ.

рАВЕНСТВО (5) ДАЕТ ОДИН СПОСОБ ПРЕДСТАВЛЕНИЯ 
$c\ a\ b\ d\ d\ a\ b\ d\ a\ \ d$ В ВИДЕ СОЕДИНИТЕЛЬНОГО ПРОИЗВЕДЕНИЯ БОЛЕЕ 
КОРОТКИХ ПЕРЕСТАНОВОК; 
РАССМОТРИМ ОБЩУЮ ЗАДАЧУ О НАХОЖДЕНИИ ВСЕХ РАЗЛОЖЕНИЙ $\pi=\alpha\T\beta$ 
ДАННОЙ ПЕРЕСТАНОВКИ $\pi$. дЛЯ ИССЛЕДОВАНИЯ ЭТОГО ВОПРОСА  ПОЛЕЗНО 
РАССМОТРЕТЬ КОНКРЕТНУЮ ПЕРЕСТАНОВКУ, СКАЖЕМ
$$
\pi=\pmatrix{
a & a & b & b & b & b & b & c & c & c & d & d & d & d &d\cr
d & b & c & b &c & a & c & d & a & d & d & b & b & b & d\cr
},
\eqno(12)
$$

еСЛИ МОЖНО ЗАПИСАТЬ $\pi$ В ВИДЕ $\alpha\T\beta$, ГДЕ $\alpha$ СОДЕРЖИТ ПО 
КРАЙНЕЙ МЕРЕ ОДНУ БУКВУ $a$, ТО САМОЕ ЛЕВОЕ $a$ В ВЕРХНЕЙ СТРОКЕ 
ДВУСТРОЧНОГО ПРЕДСТАВЛЕНИЯ $\alpha$ ДОЛЖНО ОКАЗАТЬСЯ НАД $d$, ЗНАЧИТ, 
ПЕРЕСТАНОВКА $\alpha$ ДОЛЖНА СОДЕРЖАТЬ ПО КРАЙНЕЙ МЕРЕ ОДНУ БУКВУ 
$\d$. еСЛИ ВЗГЛЯНУТЬ ТЕПЕРЬ НА САМОЕ ЛЕВОЕ $d$ В ВЕРХНЕЙ СТРОКЕ $\alpha$, 
ТО УВИДИМ ТОЧНО ТАК ЖЕ, ЧТО ОНО ДОЛЖНО ОКАЗАТЬСЯ НАД $d$, ЗНАЧИТ, В 
$\alpha$ ДОЛЖНЫ СОДЕРЖАТЬСЯ ПО МЕНЬШЕЙ МЕРЕ \emph{ДВЕ} БУКВЫ $d$. 
пОСМОТРЕВ НА ВТОРОЕ $d$, ВИДИМ, ЧТО $\alpha$ СОДЕРЖИТ ТАКЖЕ $b$. 
оДНО-ЕДИНСТВЕННОЕ ПРЕДПОЛОЖЕНИЕ О ТОМ, ЧТО $\alpha$ ЕСТЬ ЛЕВЫЙ СОМНОЖИТЕЛЬ 
$\pi$, СОДЕРЖАЩИЙ БУКВУ $a$, ПРИВОДИТ К ТАКОМУ ПРОМЕЖУТОЧНОМУ РЕЗУЛЬТАТУ:
$$
\pmatrix{
a &           & b &          & d & d \cr
   &\ldots &    &\ldots&   &  & \ldots\cr
d &           &    &          & d & b \cr
}.
\eqno(13)
$$

пРОДОЛЖАЯ РАССУЖДАТЬ ТОЧНО ТАК ЖЕ И ДАЛЕЕ, ОБНАРУЖИМ, ЧТО БУКВА $b$ В 
ВЕРХНЕЙ СТРОКЕ (13) ДОЛЖНА ОКАЗАТЬСЯ НАД $c$ И Т.~Д. в КОНЦЕ КОНЦОВ ЭТОТ 
ПРОЦЕСС ВНОВЬ ПРИВЕДЕТ НАС К БУКВЕ $a$, И МЫ СМОЖЕМ, ЕСЛИ ЗАХОТИМ, 
ОТОЖДЕСТВИТЬ ЕЕ С ПЕРВОЙ БУКВОЙ $a$. тОЛЬКО ЧТО ПРОВЕДЕННОЕ РАССУЖДЕНИЕ, 
ПО СУЩЕСТВУ, ДОКАЗЫВАЕТ,
%% 41
\bye