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

%%34

\ex[м23] иЗВЕСТНО, ЧТО В РАЗЛОЖЕНИИ ОПРЕДЕЛИТЕЛЯ ПОЛОВИНА 
ЧЛЕНОВ ВЫПИСЫВАЕТСЯ СО ЗНАКОМ~$+$, А ПОЛОВИНА---СО ЗНАКОМ~$-$. дРУГИМИ 
СЛОВАМИ, ПРИ $n\ge 2$ ПЕРЕСТАНОВОК С \emph{ЧЕТНЫМ} ЧИСЛОМ ИНВЕРСИЙ РОВНО 
СТОЛЬКО ЖЕ, СКОЛЬКО С \emph{НЕЧЕТНЫМ}. пОКАЖИТЕ, ЧТО ВООБЩЕ ПРИ $n\ge m$ 
КОЛИЧЕСТВО ПЕРЕСТАНОВОК С ЧИСЛОМ ИНВЕРСИЙ, КОНГРУЭНТНЫМ $t \bmod m$, РАВНО 
$n!/m$, НЕЗАВИСИМО ОТ ТОГО, КАКОВО ЦЕЛОЕ ЧИСЛО~$t$.

\ex[м24] \exhead(ф. фРАНКЛИН.) рАЗБИЕНИЕ ЧИСЛА~$n$ НА $k$~РАЗЛИЧНЫХ 
ЧАСТЕЙ--- ЭТО ПРЕДСТАВЛЕНИЕ~$n$ В ВИДЕ СУММЫ $n=p_1+p_2+\cdots+p_k$, ГДЕ 
$p_1>p_2>\ldots>p_k>0$. нАПРИМЕР, РАЗБИЕНИЯ ЧИСЛА~7 НА РАЗЛИЧНЫЕ ЧАСТИ 
ТАКОВЫ: $7$, $6+1$, $5+2$,
\picture{рИС. 2. сООТВЕТСТВИЕ фРАНКЛИНА МЕЖДУ РАЗБИЕНИЯМИ НА РАЗЛИЧНЫЕ ЧАСТИ.}
$4+3$, $4+2+1$. пУСТЬ $f_k(n)$---ЧИСЛО РАЗБИЕНИЙ $n$ НА $k$~РАЗЛИЧНЫХ ЧАСТЕЙ.
 дОКАЖИТЕ, ЧТО $\sum_k (-1)^k f_k(n)=0$, ЕСЛИ ТОЛЬКО $n$ НЕ 
ПРЕДСТАВЛЯЕТСЯ В 
ВИДЕ~$(3j^2\pm j)/2$ ПРИ НЕКОТОРОМ НЕОТРИЦАТЕЛЬНОМ ЦЕЛОМ~$j$; В ЭТОМ 
СЛУЧАЕ СУММА РАВНА $(-1)^j$. нАПРИМЕР, ДЛЯ $n=7$ СУММА РАВНА~$-1+3-1=1$, 
ПОТОМУ ЧТО $7=(3\cdot2^2+2)/2$. [\emph{уКАЗАНИЕ.} пРЕДСТАВЬТЕ РАЗБИЕНИЯ В 
ВИДЕ МАССИВА ТОЧЕК, В $i\hbox{-Й}$ СТРОКЕ КОТОРОГО ИМЕЕТСЯ $p_i$~ТОЧЕК, 
$1\le i\le k$. нАЙДИТЕ НАИМЕНЬШЕЕ~$j$, ТАКОЕ, ЧТО $p_{j+1}<p_j-1$, И 
ОБВЕДИТЕ КРАЙНИЕ ПРАВЫЕ ТОЧКИ ПЕРВЫХ $j$~СТРОК. еСЛИ $j<p_k$, ТО ЭТИ 
$j$~ТОЧЕК МОЖНО, КАК ПРАВИЛО ИЗRЯТЬ ИЗ МАССИВА, ПОВЕРНУТЬ НА $45^\circ$ И 
ПОМЕСТИТЬ В НОВУЮ, $(k+1)\hbox{-Ю}$ СТРОКУ. с ДРУГОЙ СТОРОНЫ, ЕСЛИ $j\ge 
p_k$, ТО ОБЫЧНО МОЖНО ИЗRЯТЬ ИЗ МАССИВА $k\hbox{-Ю}$ СТРОКУ ТОЧЕК, 
ПОВЕРНУТЬ ЕЕ НА $45^\circ$ И ПОМЕСТИТЬ СПРАВА ОТ ОБВЕДЕННЫХ ТОЧЕК (РИС.~2).
 в РЕЗУЛЬТАТЕ ЭТОГО ПРОЦЕССА В БОЛЬШИНСТВЕ СЛУЧАЕВ РАЗБИЕНИЯ С ЧЕТНЫМ 
ЧИСЛОМ СТРОК И РАЗБИЕНИЯ С НЕЧЕТНЫМ ЧИСЛОМ СТРОК ГРУППИРУЮТСЯ В ПАРЫ, 
ТАКИМ ОБРАЗОМ, В СУММЕ НАДО УЧИТЫВАТЬ ТОЛЬКО НЕПАРНЫЕ РАЗБИЕНИЯ.]

\emph{зАМЕЧАНИЕ.} в КАЧЕСТВЕ СЛЕДСТВИЯ ПОЛУЧАЕМ ФОРМУЛУ эЙЛЕРА
$$
\eqalign{
(1-z)(1-z^2)(1-z^3)\ldots&=1-z-z^2+z^5+z^7-z^{12}-z^{15}+\cdots=\cr
&=\sum_{-\infty<j<\infty} (-1)^j z^{(3j^2+j)/2}.\cr
}
$$
тАК КАК ПРОИЗВОДЯЩАЯ ФУНКЦИЯ ДЛЯ ОБЫЧНЫХ РАЗБИЕНИЙ (НЕ ОБЯЗАТЕЛЬНО 
НА РАЗЛИЧНЫЕ ЧАСТИ) РАВНА $\sum p(n) z^n=1/(1-z)(1-z^2)(1-z^3)\ldots$, ТО 
ПОЛУЧАЕМ НЕОЧЕВИДНОЕ РЕКУРРЕНТНОЕ СООТНОШЕНИЕ ДЛЯ ЧИСЛА РАЗБИЕНИЙ
$p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n+12)+p(n+15)-\cdots$.

\ex[м29] дОКАЖИТЕ, ЧТО (16)---ПРОИЗВОДЯЩАЯ ФУНКЦИЯ ДЛЯ ЧИСЛА РАЗБИЕНИЙ НА 
НЕ БОЛЕЕ ЧЕМ $n$~ЧАСТЕЙ, Т.~Е.~ДОКАЖИТЕ, ЧТО КОЭФФИЦИЕНТ ПРИ $z^m$ В 
$1/(1-z)(1-z^2)\ldots(1-z^n)$ РАВЕН ЧИСЛУ СПОСОБОВ ПРЕДСТАВИТЬ~$m$ В ВИДЕ 
СУММЫ $p_1+p_2+\cdots+p_n$, ГДЕ $p_1\ge p_2\ge\ldots p_n\ge0$. 
[\emph{уКАЗАНИЕ.} нАРИСУЙТЕ ТОЧКИ, КАК В УПР.~14, И ПОКАЖИТЕ, ЧТО 
СУЩЕСТВУЕТ ВЗАИМНО ОДНОЗНАЧНОЕ СООТВЕТСТВИЕ МЕЖДУ $n\hbox{-КАМИ}$ ЧИСЕЛ 
$(p_1, p_2,~\ldots, p_n)$, ТАКИМИ, ЧТО 
$p_1\ge p_2\ge\ldots\ge p_n\ge0$, И ПОСЛЕДОВАТЕЛЬНОСТЯМИ 
$(P_1, P_2, P_3,\ldots)$, ТАКИМИ, 
ЧТО $n\ge P_1\ge P_2\ge P_3\ge\ldots\ge0$, ОБЛАДАЮЩЕЕ 
ТЕМ СВОЙСТВОМ, ЧТО $p_1+p_2+\cdots+p_n=P_1+P_2+P_3+\cdots$. иНЫМИ СЛОВАМИ, 
РАЗБИЕНИЯМ НА НЕ БОЛЕЕ ЧЕМ $n$~ЧАСТЕЙ СООТВЕТСТВУЮТ РАЗБИЕНИЯ НА ЧАСТИ, НЕ 
ПРЕВОСХОДЯЩИЕ~$n$.]

%% 35

\ex[м25](л. эЙЛЕР.) дОКАЖИТЕ СЛЕДУЮЩИЕ ТОЖДЕСТВА, 
ИНТЕРПРЕТИРУЯ ОБЕ ЧАСТИ СООТНОШЕНИЙ В ТЕРМИНАХ РАЗБИЕНИЙ:

$$
\eqalign{
\prod_{k\ge0} {1\over (1-q^kz)} &= {1\over (1-z)(1-qz)(1-q^2z)\ldots}=\cr
&=1+{z\over 1-q}+{z^2\over (1-q)(1-q^2)}+\cdots=\sum_{n\ge0}z^n/
\prod_{1\le k\le n} (1-q^k).\cr
\prod_{k\ge0}(1+q^kz)&=(1+z)(1+qz)(1+q^2z)\ldots=\cr
&=1+{z\over 1-q}+{z^2q\over (1-q)(1-q^2)}+\cdots=\cr
&=\sum_{n\ge 0} z^nq^{n(n-1)/2}/\prod_{1\le k\le n} (1-q^k).\cr
}
$$

\ex[20] кАКОВЫ 24 ЧЕТВЕРКИ $(q_1, q_2, q_3, q_4)$, ДЛЯ КОТОРЫХ В 
СООТВЕТСТВИИ мАК-мАГОНА, ОПРЕДЕЛЕННОМ В КОНЦЕ ЭТОГО ПУНКТА,  $(p_1, p_2,  
p_3, p_4)=(0,0, 0, 0)$?

\ex[м30] (т.~хИББАРД, {\sl CACM\/}, {\bf 6} (1963), 210.) пУСТЬ $n>0$, И 
ПРЕДПОЛОЖИМ, ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ  $n\hbox{-БИТОВЫХ}$ ЦЕЛЫХ ЧИСЕЛ 
$X_0$,~\dots, $X_{2^n-1}$   ДЛИНЫ~$2^n$ ПОЛУЧЕНА СЛУЧАЙНЫМ ОБРАЗОМ, ПРИЧЕМ 
КАЖДЫЙ БИТ КАЖДОГО ЧИСЛА НЕЗАВИСИМО ПРИНИМАЕТ ЗНАЧЕНИЕ~1 С 
ВЕРОЯТНОСТЬЮ~$p$. рАССМОТРИМ ПОСЛЕДОВАТЕЛЬНОСТЬ $X_0\oplus0$, $X_1\oplus1$,
~\dots, $X_{2^n-1}\oplus(2^n-1)$, ГДЕ $\oplus$---ОПЕРАЦИЯ "ИСКЛЮЧАЮЩЕЕ ИЛИ"
НАД БИНАРНЫМИ ПРЕДСТАВЛЕНИЯМИ. тАК, ЕСЛИ $p=0$, ТО ПОСЛЕДОВАТЕЛЬНОСТЬ 
БУДЕТ $0$, $1$,~\dots,  $2^n-1$, А ЕСЛИ $p= 1$, ТО ОНА БУДЕТ $2^n- 1$,
~\dots, $1$, $0$; ЕСЛИ ЖЕ $p={1\over2}$,
ТО КАЖДЫЙ ЭЛЕМЕНТ ПОСЛЕДОВАТЕЛЬНОСТИ---СЛУЧАЙНОЕ ЧИСЛО МЕЖДУ~$0$ 
И~$2^n-1$. вООБЩЕ ЖЕ ПРИ РАЗНЫХ~$p$ ЭТО ХОРОШИЙ СПОСОБ ПОЛУЧЕНИЯ 
ПОСЛЕДОВАТЕЛЬНОСТИ СЛУЧАЙНЫХ ЦЕЛЫХ ЧИСЕЛ СО СМЕЩЕННЫМ ЧИСЛОМ ИНВЕРСИЙ, В 
ТО ВРЕМЯ КАК РАСПРЕДЕЛЕНИЕ ЭЛЕМЕНТОВ ПОСЛЕДОВАТЕЛЬНОСТИ, РАССМАТРИВАЕМОЙ 
КАК ЕДИНОЕ ЦЕЛОЕ, РАВНОМЕРНО.

оПРЕДЕЛИТЕ СРЕДНЕЕ ЧИСЛО ИНВЕРСИЙ В ТАКОЙ ПОСЛЕДОВАТЕЛЬНОСТИ КАК ФУНКЦИЮ 
ОТ ВЕРОЯТНОСТИ~$p$.

\ex [M36]  (д. фОАТА.) дАЙТЕ ПРЯМОЕ ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ мАК-мАГОНА ОБ 
ИНДЕКСАХ: НАЙДИТЕ ТОЧНОЕ ВЗАИМНО ОДНОЗНАЧНОЕ СООТВЕТСТВИЕ, КОТОРОЕ 
ПЕРЕВОДИТ ПЕРЕСТАНОВКУ $n$~ЭЛЕМЕНТОВ, ИМЕЮЩУЮ ИНДЕКС~$k$, В ПЕРЕСТАНОВКУ,
 ИМЕЮЩУЮ $k$~ИНВЕРСИЙ И ТОТ ЖЕ САМЫЙ КРАЙНИЙ ПРАВЫЙ ЭЛЕМЕНТ.

\ex[M43] сЛЕДУЮЩЕЕ ЗНАМЕНИТОЕ ТОЖДЕСТВО, ПРИНАДЛЕЖАЩЕЕ яКОБИ 
[Fundamenta Nova Theori\ae{} Functionum Ellipticorum (1829), \S~64], ЛЕЖИТ 
В ОСНОВЕ МНОГИХ ЗАМЕЧАТЕЛЬНЫХ СООТНОШЕНИЙ, СОДЕРЖАЩИХ ЭЛЛИПТИЧЕСКИЕ ФУНКЦИИ:
$$
\eqalign{
\prod_{k\ge1}(1-u^kv^{k-1})&(1-u^{k-1}v^k)(1-u^kv^k)=\cr
&=(1-u)(1-v)(1-uv)(1-u^2v)(1-uv^2)(1-u^2v^2)\ldots=\cr
&=1-(u+v)+(u^3v+uv^3)-(u^6v^3+u^3v^6)+\cdots=\cr
&=1+\sum_{n\ge1}(-1)^n(u^{(n+1)n/2}v^{(n-1)n/2}+u^{(n-1)n/2}v^{(n+1)n/2}).\cr
}
$$
еСЛИ, НАПРИМЕР, ПОЛОЖИТЬ $u=z$, $v=z^2$, ТО ПОЛУЧИТСЯ ФОРМУЛА эЙЛЕРА 
ИЗ УПР.~14. еСЛИ ПОЛОЖИТЬ $z=\sqrt{u/v}$, $q=\sqrt{uv}$, ТО ПОЛУЧИМ
$$
\prod_{k\ge1}(1-q^{2k-1}z)(1-q^{2k-1}z^{-1}(1-q^{2k})=\sum_{-\infty<n<\infty} (-1)^nz^nq^{n^2}.
$$

%% 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