\input style
\noindent
%% 41
ЧТО ЛЮБОЙ ЛЕВЫЙ СОМНОЖИТЕЛЬ В РАЗЛОЖЕНИИ ПЕРЕСТАНОВКИ (12), СОДЕРЖАЩИЙ $a$,
 ИМЕЕТ ВИД $(d\ d\ b\ c\ d\ b\ b\ c\ a)\T \alpha'$, ГДЕ $\alpha'$--- 
НЕКОТОРАЯ ПЕРЕСТАНОВКА. (уДОБНО ЗАПИСЫВАТЬ $a$ НЕ В НАЧАЛЕ, А В 
КОНЦЕ ЦИКЛА; ЭТО ДОПУСТИМО, ПОСКОЛЬКУ БУКВА $a$ ТОЛЬКО ОДНА.) аНАЛОГИЧНО,
 ЕСЛИ БЫ МЫ ПРЕДПОЛОЖИЛИ, ЧТО $\alpha$ СОДЕРЖИТ БУКВУ $b$, ТО ВЫВЕЛИ БЫ, 
ЧТО $\alpha=(c\ d\ d\ b) \T \alpha''$, ГДЕ $\alpha''$---НЕКОТОРАЯ ПЕРЕСТАНОВКА.

в ОБЩЕМ СЛУЧАЕ ЭТИ РАССУЖДЕНИЯ ПОКАЗЫВАЮТ, ЧТО \emph{ЕСЛИ 
ЕСТЬ КАКОЕ-НИБУДЬ РАЗЛОЖЕНИЕ $\alpha\T\beta=\pi$, ГДЕ $\alpha$ СОДЕРЖИТ 
ДАННУЮ БУКВУ $y$, ТО СУЩЕСТВУЕТ ЕДИНСТВЕННЫЙ ЦИКЛ ВИДА
$$
(x_1\ \ldots\ x_n\ y), \qquad n\ge 0, x_1, \ldots, x_n\ne y,
\eqno(14)
$$
КОТОРЫЙ ЯВЛЯЕТСЯ ЛЕВЫМ СОМНОЖИТЕЛЕМ В РАЗЛОЖЕНИИ ПЕРЕСТАНОВКИ $\alpha$.} 
тАКОЙ ЦИКЛ ЛЕГКО ОТЫСКАТЬ, ЗНАЯ $\pi$ И $y$; ЭТО САМЫЙ КОРОТКИЙ ЛЕВЫЙ 
СОМНОЖИТЕЛЬ В РАЗЛОЖЕНИИ ПЕРЕСТАНОВКИ $\pi$, СОДЕРЖАЩИЙ БУКВУ $y$. оДНО ИЗ 
СЛЕДСТВИЙ ЭТОГО НАБЛЮДЕНИЯ ДАЕТ

\proclaim тЕОРЕМА A. пУСТЬ ЭЛЕМЕНТЫ МУЛЬТИМНОЖЕСТВА $M$ ЛИНЕЙНО 
УПОРЯДОЧЕНЫ ОТНОШЕНИЕМ "$<$". кАЖДАЯ ПЕРЕСТАНОВКА $\pi$ МУЛЬТИМНОЖЕСТВА 
$M$ ИМЕЕТ ЕДИНСТВЕННОЕ ПРЕДСТАВЛЕНИЕ В ВИДЕ СОЕДИНИТЕЛЬНОГО ПРОИЗВЕДЕНИЯ
$$
\pi=(x_{11}\ldots x_{1n_1}y_1)\T(x_{21}\ldots x_{2n_2}y_2)\T \ldots
(x_{t1}\ldots x_{tn_t}y_t), \quad t\ge 0,
\eqno(15)
$$
УДОВЛЕТВОРЯЮЩЕЕ СЛЕДУЮЩИМ ДВУМ УСЛОВИЯМ:
$$
\displaylines{
y_1\le y_2 \le \ldots \le y_t;\cr
\hfill y_i<x_{ij}\hbox{ ПРИ $1\le j\le n_i$, $1\le i\le t$.}\hfill\llap{\rm(16)}\cr
}
$$
(иНЫМИ СЛОВАМИ, В КАЖДОМ ЦИКЛЕ ПОСЛЕДНИЙ ЭЛЕМЕНТ МЕНЬШЕ ЛЮБОГО ДРУГОГО, И 
ПОСЛЕДНИЕ ЭЛЕМЕНТЫ ЦИКЛОВ ОБРАЗУЮТ НЕУБЫВАЮЩУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ.)

\proof пРИ $\pi=\varepsilon$ ПОЛУЧИМ ТРЕБУЕМОЕ РАЗЛОЖЕНИЕ, ПОЛОЖИВ $t=0$.
 в ПРОТИВНОМ СЛУЧАЕ ПУСТЬ $y_1$---МИНИМАЛЬНЫЙ ЭЛЕМЕНТ $\pi$;
ОПРЕДЕЛИМ $(x_{11}\ldots x_{1n_1}y_1)$---САМЫЙ КОРОТКИЙ ЛЕВЫЙ 
СОМНОЖИТЕЛЬ РАЗЛОЖЕНИЯ $\pi$, СОДЕРЖАЩИЙ $y_1$, КАК В РАССМОТРЕННОМ 
ПРИМЕРЕ. тЕПЕРЬ $\pi=(x_{11}\ldots x_{1n_1} y_1)\T\rho$, ГДЕ 
$\rho$---НЕКОТОРАЯ ПЕРЕСТАНОВКА;
ПРИМЕНИВ ИНДУКЦИЮ ПО ДЛИНЕ ПЕРЕСТАНОВКИ, МОЖЕМ НАПИСАТЬ
$$
\rho=(x_{21}\ldots x_{2n_2}y_2)\T\ldots\T(x_{t1}\ldots x_{tn_t}y_t), t\ge1,
$$
ГДЕ УСЛОВИЯ (16) ВЫПОЛНЕНЫ. тЕМ САМЫМ ДОКАЗАНО СУЩЕСТВОВАНИЕ ТАКОГО РАЗЛОЖЕНИЯ.

дОКАЖЕМ ЕДИНСТВЕННОСТЬ РАЗЛОЖЕНИЯ (15), УДОВЛЕТВОРЯЮЩЕГО УСЛОВИЯМ (16). 
яСНО, ЧТО $t=0$ ТОГДА И ТОЛЬКО ТОГДА, КОГДА $\pi$--- ПУСТАЯ ПЕРЕСТАНОВКА 
$\varepsilon$. пРИ $t>0$ ИЗ (16) СЛЕДУЕТ, ЧТО $y_1$---МИНИМАЛЬНЫЙ ЭЛЕМЕНТ 
ПЕРЕСТАНОВКИ $\pi$ И ЧТО $(x_{11}\ldots x_{1n_1}y_1$---САМЫЙ КОРОТКИЙ
%%42
ЛЕВЫЙ СОМНОЖИТЕЛЬ, СОДЕРЖАЩИЙ $y_1$. пОЭТОМУ 
$(x_{11}\ldots x_{1n_1} y_1)$
ОПРЕДЕЛЯЕТСЯ ОДНОЗНАЧНО; ДОКАЗАТЕЛЬСТВО ЕДИНСТВЕННОСТИ 
ТАКОГО ПРЕДСТАВЛЕНИЯ ЗАВЕРШАЕТСЯ ПРИМЕНЕНИЕМ ИНДУКЦИИ И ЗАКОНОВ СОКРАЩЕНИЯ 
(7). 
\proofend

нАПРИМЕР, "КАНОНИЧЕСКОЕ" РАЗЛОЖЕНИЕ ПЕРЕСТАНОВКИ (12), УДОВЛЕТВОРЯЮЩЕЕ 
ДАННЫМ УСЛОВИЯМ, ТАКОВО:
$$
(d\ d\ b\ c\ d\ b\ b\ c\ a)\T(b\ a)\T(c\ d\ b)\T(d),
\eqno(17)
$$
ЕСЛИ $a<b<c<d$.

вАЖНО ОТМЕТИТЬ, ЧТО НА САМОМ ДЕЛЕ В ЭТОМ ОПРЕДЕЛЕНИИ МОЖНО ОТБРОСИТЬ 
СКОБКИ И ЗНАКИ ОПЕРАЦИИ $\T$, И ЭТО НЕ ПРИВЕДЕТ К НЕОДНОЗНАЧНОСТИ! 
кАЖДЫЙ ЦИКЛ ЗАКАНЧИВАЕТСЯ ПОЯВЛЕНИЕМ НАИМЕНЬШЕГО ИЗ ОСТАВШИХСЯ ЭЛЕМЕНТОВ.
 тАКИМ ОБРАЗОМ, НАШЕ ПОСТРОЕНИЕ СВЯЗЫВАЕТ С ИСХОДНОЙ ПЕРЕСТАНОВКОЙ
$$
\pi'=d\ d\ b\ c\ d\ b\ b\ c\ a\ b\ a\ c\ d\ b\ d
$$
ПЕРЕСТАНОВКУ
$$
\pi=d\ b\ c\ b\ c\ a\ c\ d\ a\ d\ d\ b\ b\ b\ d.
$$
еСЛИ В ДВУСТРОЧНОМ ПРЕДСТАВЛЕНИИ $\pi$ СОДЕРЖИТСЯ СТОЛБЕЦ ВИДА 
$y\atop x$, ГДЕ $x<y$, ТО В СВЯЗАННОЙ С $\pi$ ПЕРЕСТАНОВКЕ ПРИСУТСТВУЕТ 
СООТВЕТСТВУЮЩАЯ ПАРА СОСЕДНИХ ЭЛЕМЕНТОВ $\ldots y\ x\ldots$. тАК, В 
НАШЕМ ПРИМЕРЕ $\pi$ СОДЕРЖИТ ТРИ СТОЛБЦА ВИДА $d\atop b$, А В $\pi'$ ТРИЖДЫ
ВСТРЕЧАЕТСЯ ПАРА $d\ b$. вООБЩЕ ИЗ ЭТОГО ПОСТРОЕНИЯ ВЫТЕКАЕТ ЗАМЕЧАТЕЛЬНАЯ

\proclaim тЕОРЕМА B. {пУСТЬ $M$---МУЛЬТИМНОЖЕСТВО. сУЩЕСТВУЕТ ВЗАИМНО 
ОДНОЗНАЧНОЕ СООТВЕТСТВИЕ МЕЖДУ ПЕРЕСТАНОВКАМИ $M$, ТАКОЕ, ЧТО ЕСЛИ $\pi$ 
СООТВЕТСТВУЕТ $\pi'$, ТО ВЫПОЛНЯЮТСЯ СЛЕДУЮЩИЕ УСЛОВИЯ:
\medskip
\item{a)} КРАЙНИЙ ЛЕВЫЙ ЭЛЕМЕНТ $\pi'$ РАВЕН КРАЙНЕМУ ЛЕВОМУ 
ЭЛЕМЕНТУ~$\pi$;
\item{b)} ДЛЯ ВСЕХ ПАР УЧАСТВУЮЩИХ В ПЕРЕСТАНОВКЕ ЭЛЕМЕНТОВ $(x, y)$,
\medskip
\noindent ТАКИХ, ЧТО $x<y$, ЧИСЛО ВХОЖДЕНИЙ СТОЛБЦА $y\atop x$ В 
ДВУСТРОЧНОЕ ПРЕДСТАВЛЕНИЕ ПЕРЕСТАНОВКИ $\pi$ РАВНО ЧИСЛУ СЛУЧАЕВ, КОГДА В 
ПЕРЕСТАНОВКЕ $\pi'$ ЭЛЕМЕНТ $x$ СЛЕДУЕТ НЕПОСРЕДСТВЕННО ЗА $y$.}

еСЛИ $M$---МНОЖЕСТВО, ТО ЭТО, ПО СУЩЕСТВУ, "НЕСТАНДАРТНОЕ СООТВЕТСТВИЕ", 
ОБСУЖДАВШЕЕСЯ В КОНЦЕ П.~1.3.3, С НЕЗНАЧИТЕЛЬНЫМИ ИЗМЕНЕНИЯМИ. бОЛЕЕ 
ОБЩИЙ РЕЗУЛЬТАТ ТЕОРЕМЫ B ПОЛЕЗЕН ПРИ ПОДСЧЕТЕ ЧИСЛА ПЕРЕСТАНОВОК 
СПЕЦИАЛЬНЫХ ТИПОВ, ПОСКОЛЬКУ ЧАСТО ПРОЩЕ РЕШИТЬ ЗАДАЧУ С ОГРАНИЧЕНИЯМИ, 
НАЛОЖЕННЫМИ НА ДВУСТРОЧНОЕ ПРЕДСТАВЛЕНИЕ, ЧЕМ ЭКВИВАЛЕНТНУЮ ЗАДАЧУ С 
ОГРАНИЧЕНИЯМИ НА ПАРЫ СОСЕДНИХ ЭЛЕМЕНТОВ.
%% 43

п.~а.~мАК-мАГОН РАССМОТРЕЛ ЗАДАЧИ ЭТОГО ТИПА В СВОЕЙ ВЫДАЮЩЕЕСЯ КНИГЕ 
Combinatory Analysis (Cambridge Univ. Press, 1915), ТОМ~1, СТР. 168--186. 
оН ДАЛ КОНСТРУКТИВНОЕ ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ~B В ЧАСТНОМ СЛУЧАЕ, КОГДА M 
СОДЕРЖИТ ЭЛЕМЕНТЫ ЛИШЬ ДВУХ РАЗЛИЧНЫХ ТИПОВ, СКАЖЕМ $a$ И~$b$, ЕГО 
ПОСТРОЕНИЕ ДЛЯ ЭТОГО СЛУЧАЯ, ПО СУЩЕСТВУ, СОВПАДАЕТ С ПРИВЕДЕННЫМ ЗДЕСЬ, 
НО ПРЕДСТАВЛЕНО В СОВЕРШЕННО ИНОМ ВИДЕ. дЛЯ СЛУЧАЯ ТРЕХ РАЗЛИЧНЫХ 
ЭЛЕМЕНТОВ $a$, $b$, $c$ мАК-мАГОН ДАЛ СЛОЖНОЕ НЕКОНСТРУКТИВНОЕ 
ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ~B; ОБЩИЙ СЛУЧАЙ ВПЕРВЫЕ ДОКАЗАЛ фОАТА В 1965~Г.

в КАЧЕСТВЕ НЕТРИВИАЛЬНОГО ПРИМЕРА ПРИМЕНЕНИЯ ТЕОРЕМЫ~B НАЙДЕМ ЧИСЛО 
ЦЕПОЧЕК БУКВ $a$, $b$, $c$, СОДЕРЖАЩИХ РОВНО
$$
\eqalign{
A&\hbox{ ВХОЖДЕНИЙ БУКВЫ $a$;}\cr
B&\hbox{ ВХОЖДЕНИЙ БУКВЫ $b$;}\cr
C&\hbox{ ВХОЖДЕНИЙ БУКВЫ $c$;}\cr
k&\hbox{ ВХОЖДЕНИЙ ПАРЫ СТОЯЩИХ РЯДОМ БУКВ $c\ a$;}\cr
l&\hbox{ ВХОЖДЕНИЙ ПАРЫ СТОЯЩИХ РЯДОМ БУКВ $c\ b$;}\cr
m&\hbox{ ВХОЖДЕНИЙ ПАРЫ СТОЯЩИХ РЯДОМ БУКВ $b\ a$;}\cr
}
\eqno(18)
$$
иЗ ТЕОРЕМЫ СЛЕДУЕТ, ЧТО ЭТО ТО ЖЕ САМОЕ, ЧТО НАЙТИ ЧИСЛО ДВУСТРОЧНЫХ 
МАССИВОВ ВИДА
{
\newbox\Abox\newbox\Bbox\newbox\Cbox
\setbox\Abox\hbox{$\displaystyle
\underbrace{
\hbox to 0pt{\hss$\displaystyle\Bigl($}
  \overbrace{
    \matrix{
      a & \ldots & a \cr
      \]& \ldots & \]\cr
    }
  }^A 
}_{A-k-m\hbox{ БУКВ $a$}}
$}
\setbox\Bbox\hbox{$\displaystyle
\underbrace{
  \overbrace{
    \matrix{
      b & \ldots & b\cr
     \] & \ldots &\]\cr
    }
  }^B
}_{m\hbox{ БУКВ $a$}}
$}
\setbox\Cbox\hbox{$\displaystyle
\underbrace{
\overbrace{
 \matrix{
   c & \ldots & c \cr
  \] & \ldots &\] \cr
 }
}^C
\hbox to 0pt{$\displaystyle\Bigr)\hss$}
}_{k\hbox{ БУКВ $a$}}
$}
$$
\underbrace{
 \underbrace{\copy\Abox \copy\Bbox}_{\hbox{$B-l$ БУКВ $b$}}\;\;
 \underbrace{\copy\Cbox}_{\hbox{$l$ БУКВ $b$}}
}_{\hbox{$C$ БУКВ $c$}}
\eqno (19)
$$
}
бУКВЫ $a$ МОЖНО РАСПОЛОЖИТЬ ВО ВТОРОЙ СТРОКЕ
$$
\perm{A}{A-k-m}\perm{B}{m}\perm{C}{k}
\rem{СПОСОБАМИ;}
$$
ПОСЛЕ ЭТОГО БУКВЫ $b$ МОЖНО РАЗМЕСТИТЬ В ОСТАВШИХСЯ ПОЗИЦИЯХ
$$
\perm{B+k}{B-l}\perm{C-k}{l}\rem{СПОСОБАМИ.}
$$
оСТАЛЬНЫЕ СВОБОДНЫЕ МЕСТА НУЖНО ЗАПОЛНИТЬ БУКВАМИ $c$; СЛЕДОВАТЕЛЬНО, 
ИСКОМОЕ ЧИСЛО РАВНО
$$
\perm{A}{A-k-m}\perm{B}{m}\perm{C}{k}\perm{B+k}{B-l}\perm{C-k}{l}.
\eqno(20)
$$

%% 44

вЕРНЕМСЯ К ВОПРОСУ О НАХОЖДЕНИИ ВСЕХ РАЗЛОЖЕНИЙ ДАННОЙ ПЕРЕСТАНОВКИ. 
сУЩЕСТВУЕТ ЛИ ТАКОЙ ОБ®ЕКТ, КАК "ПРОСТАЯ" ПЕРЕСТАНОВКА, КОТОРАЯ НЕ 
РАЗЛАГАЕТСЯ НА МНОЖИТЕЛИ, ОТЛИЧНЫЕ ОТ НЕЕ САМОЙ И $\varepsilon$? 
оБСУЖДЕНИЕ, ПРЕДШЕСТВУЮЩЕЕ ТЕОРЕМЕ A, НЕМЕДЛЕННО ПРИВОДИТ К ВЫВОДУ О ТОМ, 
ЧТО \emph{ПЕРЕСТАНОВКА БУДЕТ ПРОСТОЙ ТОГДА И ТОЛЬКО ТОГДА, КОГДА ОНА ЕСТЬ 
ЦИКЛ БЕЗ ПОВТОРЯЮЩИХСЯ ЭЛЕМЕНТОВ,} ТАК КАК, ЕСЛИ ПЕРЕСТАНОВКА ЯВЛЯЕТСЯ 
ТАКИМ ЦИКЛОМ, НАШЕ РАССУЖДЕНИЕ ДОКАЗЫВАЕТ, ЧТО НЕ СУЩЕСТВУЕТ ЛЕВЫХ 
МНОЖИТЕЛЕЙ, КРОМЕ $\varepsilon$ И САМОГО ЦИКЛА. еСЛИ ЖЕ ПЕРЕСТАНОВКА 
СОДЕРЖИТ ПОВТОРЯЮЩИЙСЯ ЭЛЕМЕНТ $y$, ТО ВСЕГДА МОЖНО ВЫДЕЛИТЬ 
НЕТРИВИАЛЬНЫЙ ЦИКЛ В КАЧЕСТВЕ ЛЕВОГО СОМНОЖИТЕЛЯ, В КОТОРОМ ЭЛЕМЕНТ 
У ВСТРЕЧАЕТСЯ ВСЕГО ОДНАЖДЫ.

еСЛИ ПЕРЕСТАНОВКА НЕ ПРОСТАЯ, ТО ЕЕ МОЖНО РАЗЛАГАТЬ НА ВСЕ МЕНЬШИЕ И 
МЕНЬШИЕ ЧАСТИ, ПОКА НЕ БУДЕТ ПОЛУЧЕНО ПРОИЗВЕДЕНИЕ ПРОСТЫХ ПЕРЕСТАНОВОК. 
мОЖНО ДАЖЕ ПОКАЗАТЬ, ЧТО ТАКОЕ РАЗЛОЖЕНИЕ ЕДИНСТВЕННО С ТОЧНОСТЬЮ ДО 
ПОРЯДКА ЗАПИСИ КОММУТИРУЮЩИХ СОМНОЖИТЕЛЕЙ.

\proclaim тЕОРЕМА C. кАЖДУЮ ПЕРЕСТАНОВКУ МУЛЬТИМНОЖЕСТВА МОЖНО ЗАПИСАТЬ 
В ВИДЕ ПРОИЗВЕДЕНИЯ
$$
\sigma_1\T\sigma_2\T\ldots\T\sigma_t, \quad t\ge 0,
\eqno(21)
$$
ГДЕ $\sigma_j$---ЦИКЛЫ, НЕ СОДЕРЖАЩИЕ ПОВТОРЯЮЩИХСЯ ЭЛЕМЕНТОВ. 
эТО ПРЕДСТАВЛЕНИЕ ЕДИНСТВЕННО В ТОМ СМЫСЛЕ, ЧТО ЛЮБЫЕ ДВА 
ТАКИХ ПРЕДСТАВЛЕНИЯ ОДНОЙ И ТОЙ ЖЕ ПЕРЕСТАНОВКИ МОЖНО ПРЕОБРАЗОВАТЬ ОДНО 
В ДРУГОЕ, ПОСЛЕДОВАТЕЛЬНО МЕНЯЯ МЕСТАМИ СОСЕДНИЕ НЕПЕРЕСЕКАЮЩИЕСЯ ЦИКЛЫ.

тЕРМИН "НЕПЕРЕСЕКАЮЩИЕСЯ ЦИКЛЫ" ОТНОСИТСЯ К ЦИКЛАМ, НЕ ИМЕЮЩИМ ОБЩИХ 
ЭЛЕМЕНТОВ. в КАЧЕСТВЕ ПРИМЕРА МОЖНО ПРОВЕРИТЬ, ЧТО ПЕРЕСТАНОВКА
$$
\pmatrix{
a & a & b & b & c & c & d\cr
b & a & a & c & d & b & c\cr
}
$$ 
РАЗЛАГАЕТСЯ НА МНОЖИТЕЛИ РОВНО ПЯТЬЮ СПОСОБАМИ:
$$
\eqalign{
(a\ b)\T(a)\T(c\ d)\T(b\ c) 
&=  (a\ b)\T(c\ d)\T(a)\T(b\ c)=\cr
&=(a\ b)\T(c\ d)\T(b\ c)\T(a)=\cr
&=(c\ d)\T(a\ b)\T(a)\T(b\ c)=\cr
&=(c\ d)\T(a\ b)\T(b\ c)\T(a).\cr
}
\eqno(22)
$$

\proof нУЖНО УСТАНОВИТЬ, ЧТО ВЫПОЛНЯЕТСЯ СФОРМУЛИРОВАННОЕ В ТЕОРЕМЕ 
СВОЙСТВО ЕДИНСТВЕННОСТИ. пРИМЕНИМ ИНДУКЦИЮ ПО ДЛИНЕ ПЕРЕСТАНОВКИ; ТОГДА 
ДОСТАТОЧНО ДОКАЗАТЬ, ЧТО ЕСЛИ $\rho$ И~$\sigma$---ДВА РАЗЛИЧНЫХ ЦИКЛА, НЕ 
СОДЕРЖАЩИЕ ПОВТОРЯЮЩИХСЯ ЭЛЕМЕНТОВ,
%%45
И
$$
\rho\T\alpha=\sigma\T\beta,
$$
ТО $\rho$ И~$\sigma$---НЕПЕРЕСЕКАЮЩИЕСЯ ЦИКЛЫ,  И
$$
\alpha=\sigma\T\theta,\quad \beta=\rho\T\theta,
$$
ГДЕ $\theta$---НЕКОТОРАЯ ПЕРЕСТАНОВКА.

пУСТЬ $y$---ПРОИЗВОЛЬНЫЙ ЭЛЕМЕНТ ЦИКЛА $\rho$, ТОГДА У ЛЮБОГО ЛЕВОГО 
СОМНОЖИТЕЛЯ В РАЗЛОЖЕНИИ $\sigma\T\beta$, СОДЕРЖАЩЕГО ЭТОТ ЭЛЕМЕНТ $y$, 
БУДЕТ ЛЕВЫЙ СОМНОЖИТЕЛЬ $\rho$. зНАЧИТ, ЕСЛИ $\rho$ И~$\sigma$ ИМЕЮТ ОБЩИЙ 
ЭЛЕМЕНТ, ТО ЦИКЛ $\sigma$ ДОЛЖЕН БЫТЬ КРАТЕН $\rho$; СЛЕДОВАТЕЛЬНО,
 $\sigma=\rho$ (ТАК КАК ОНИ ПРОСТЫЕ), ЧТО ПРОТИВОРЕЧИТ НАШЕМУ 
ПРЕДПОЛОЖЕНИЮ. сЛЕДОВАТЕЛЬНО, ЦИКЛ, СОДЕРЖАЩИЙ $y$ И НЕ ИМЕЮЩИЙ ОБЩИХ 
ЭЛЕМЕНТОВ С $\sigma$, ДОЛЖЕН БЫТЬ ЛЕВЫМ СОМНОЖИТЕЛЕМ В РАЗЛОЖЕНИИ $\beta$. 
пРИМЕНИВ ЗАКОНЫ СОКРАЩЕНИЯ (7), ЗАВЕРШИМ ДОКАЗАТЕЛЬСТВО.
\proofend

в КАЧЕСТВЕ ИЛЛЮСТРАЦИИ ТЕОРЕМЫ C РАССМОТРИМ ПЕРЕСТАНОВКИ МУЛЬТИМНОЖЕСТВА 
$M=\{A\cdot a, B\cdot b, C\cdot c\}$, СОСТОЯЩЕГО ИЗ $A$ ЭЛЕМЕНТОВ~$a$, 
$B$ ЭЛЕМЕНТОВ~$b$ И~$C$ ЭЛЕМЕНТОВ~$c$. пУСТЬ $N(A, B, C, m)$--- ЧИСЛО 
ПЕРЕСТАНОВОК МУЛЬТИМНОЖЕСТВА~$M$, ДВУСТРОЧНОЕ ПРЕДСТАВЛЕНИЕ КОТОРЫХ 
\emph{НЕ СОДЕРЖИТ} СТОЛБЦОВ ВИДА $a\atop a$, $b\atop b$, $c\atop c$  И СОДЕРЖИТ
РОВНО $m$ СТОЛБЦОВ ВИДА~$a\atop b$. оТСЮДА СЛЕДУЕТ, ЧТО ИМЕЕТСЯ 
РОВНО $A-m$~СТОЛБЦОВ ВИДА~$a\atop c$, $B-m$~СТОЛБЦОВ ВИДА~$c\atop b$, 
$C-B+m$ СТОЛБЦОВ ВИДА~$c\atop a$, $C-A+m$~СТОЛБЦОВ ВИДА$b\atop c$   
И~$A+B-C-m$ СТОЛБЦОВ ВИДА~$b\atop a$ ; СЛЕДОВАТЕЛЬНО,
$$
N(A, B, C, m)=\perm{A}{m}\perm{B}{C-A+m}\perm{C}{B-m}.
\eqno(23)
$$

тЕОРЕМА~C ПРЕДЛАГАЕТ ДРУГОЙ СПОСОБ ДЛЯ ПОДСЧЕТА ЭТИХ ПЕРЕСТАНОВОК: КОЛЬ 
СКОРО СТОЛБЦЫ $a\atop a$, $b\atop b$, $c\atop c$ ИСКЛЮЧЕНЫ, ТО В 
РАЗЛОЖЕНИИ ПЕРЕСТАНОВКИ ЕДИНСТВЕННО ВОЗМОЖНЫ ТАКИЕ ПРОСТЫЕ МНОЖИТЕЛИ:
$$
(a\ b), (a\ c), (b\ c), (a\ b\ c), (a\ c\ b).
\eqno(24)
$$ 
кАЖДАЯ ПАРА ЭТИХ ЦИКЛОВ ИМЕЕТ ХОТЯ БЫ ОДНУ ОБЩУЮ БУКВУ, ЗНАЧИТ, РАЗЛОЖЕНИЕ 
ЕДИНСТВЕННО. еСЛИ ЦИКЛ $(a\ b\ c)$ ВСТРЕЧАЕТСЯ В РАЗЛОЖЕНИИ $k$ РАЗ, ТО ИЗ 
НАШЕГО ПРЕДЫДУЩЕГО ПРЕДПОЛОЖЕНИЯ СЛЕДУЕТ, ЧТО $(a\ b)$ ВСТРЕЧАЕТСЯ 
$m-k$~РАЗ, $(b\ c)$ ВСТРЕЧАЕТСЯ $C-A+m-k$~РАЗ, $(a\ c)$ ВСТРЕЧАЕТСЯ 
$C-B+m-k$~РАЗ И~$(a\ c\ b)$ ВСТРЕЧАЕТСЯ $A+B-C-2m+k$~РАЗ. сЛЕДОВАТЕЛЬНО, 
$N (A, B, C, m)$
%% 46
\bye