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

%%34

\ex[m23] iZVESTNO, CHTO V RAZLOZHENII OPREDELITELYA POLOVINA 
CHLENOV VYPISYVAETSYA SO ZNAKOM~$+$, A POLOVINA---SO ZNAKOM~$-$. dRUGIMI 
SLOVAMI, PRI $n\ge 2$ PERESTANOVOK S \emph{CHETNYM} CHISLOM INVERSIJ ROVNO 
STOLXKO ZHE, SKOLXKO S \emph{NECHETNYM}. pOKAZHITE, CHTO VOOBSHCHE PRI $n\ge m$ 
KOLICHESTVO PERESTANOVOK S CHISLOM INVERSIJ, KONGRU|NTNYM $t \bmod m$, RAVNO 
$n!/m$, NEZAVISIMO OT TOGO, KAKOVO CELOE CHISLO~$t$.

\ex[m24] \exhead(f. fRANKLIN.) rAZBIENIE CHISLA~$n$ NA $k$~RAZLICHNYH 
CHASTEJ--- |TO PREDSTAVLENIE~$n$ V VIDE SUMMY $n=p_1+p_2+\cdots+p_k$, GDE 
$p_1>p_2>\ldots>p_k>0$. nAPRIMER, RAZBIENIYA CHISLA~7 NA RAZLICHNYE CHASTI 
TAKOVY: $7$, $6+1$, $5+2$,
\picture{rIS. 2. sOOTVETSTVIE fRANKLINA MEZHDU RAZBIENIYAMI NA RAZLICHNYE CHASTI.}
$4+3$, $4+2+1$. pUSTX $f_k(n)$---CHISLO RAZBIENIJ $n$ NA $k$~RAZLICHNYH CHASTEJ.
 dOKAZHITE, CHTO $\sum_k (-1)^k f_k(n)=0$, ESLI TOLXKO $n$ NE 
PREDSTAVLYAETSYA V 
VIDE~$(3j^2\pm j)/2$ PRI NEKOTOROM NEOTRICATELXNOM CELOM~$j$; V |TOM 
SLUCHAE SUMMA RAVNA $(-1)^j$. nAPRIMER, DLYA $n=7$ SUMMA RAVNA~$-1+3-1=1$, 
POTOMU CHTO $7=(3\cdot2^2+2)/2$. [\emph{uKAZANIE.} pREDSTAVXTE RAZBIENIYA V 
VIDE MASSIVA TOCHEK, V $i\hbox{-J}$ STROKE KOTOROGO IMEETSYA $p_i$~TOCHEK, 
$1\le i\le k$. nAJDITE NAIMENXSHEE~$j$, TAKOE, CHTO $p_{j+1}<p_j-1$, I 
OBVEDITE KRAJNIE PRAVYE TOCHKI PERVYH $j$~STROK. eSLI $j<p_k$, TO |TI 
$j$~TOCHEK MOZHNO, KAK PRAVILO IZ®YATX IZ MASSIVA, POVERNUTX NA $45^\circ$ I 
POMESTITX V NOVUYU, $(k+1)\hbox{-YU}$ STROKU. s DRUGOJ STORONY, ESLI $j\ge 
p_k$, TO OBYCHNO MOZHNO IZ®YATX IZ MASSIVA $k\hbox{-YU}$ STROKU TOCHEK, 
POVERNUTX EE NA $45^\circ$ I POMESTITX SPRAVA OT OBVEDENNYH TOCHEK (RIS.~2).
 v REZULXTATE |TOGO PROCESSA V BOLXSHINSTVE SLUCHAEV RAZBIENIYA S CHETNYM 
CHISLOM STROK I RAZBIENIYA S NECHETNYM CHISLOM STROK GRUPPIRUYUTSYA V PARY, 
TAKIM OBRAZOM, V SUMME NADO UCHITYVATX TOLXKO NEPARNYE RAZBIENIYA.]

\emph{zAMECHANIE.} v KACHESTVE SLEDSTVIYA POLUCHAEM FORMULU eJLERA
$$
\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
}
$$
tAK KAK PROIZVODYASHCHAYA FUNKCIYA DLYA OBYCHNYH RAZBIENIJ (NE OBYAZATELXNO 
NA RAZLICHNYE CHASTI) RAVNA $\sum p(n) z^n=1/(1-z)(1-z^2)(1-z^3)\ldots$, TO 
POLUCHAEM NEOCHEVIDNOE REKURRENTNOE SOOTNOSHENIE DLYA CHISLA RAZBIENIJ
$p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n+12)+p(n+15)-\cdots$.

\ex[m29] dOKAZHITE, CHTO (16)---PROIZVODYASHCHAYA FUNKCIYA DLYA CHISLA RAZBIENIJ NA 
NE BOLEE CHEM $n$~CHASTEJ, T.~E.~DOKAZHITE, CHTO KO|FFICIENT PRI $z^m$ V 
$1/(1-z)(1-z^2)\ldots(1-z^n)$ RAVEN CHISLU SPOSOBOV PREDSTAVITX~$m$ V VIDE 
SUMMY $p_1+p_2+\cdots+p_n$, GDE $p_1\ge p_2\ge\ldots p_n\ge0$. 
[\emph{uKAZANIE.} nARISUJTE TOCHKI, KAK V UPR.~14, I POKAZHITE, CHTO 
SUSHCHESTVUET VZAIMNO ODNOZNACHNOE SOOTVETSTVIE MEZHDU $n\hbox{-KAMI}$ CHISEL 
$(p_1, p_2,~\ldots, p_n)$, TAKIMI, CHTO 
$p_1\ge p_2\ge\ldots\ge p_n\ge0$, I POSLEDOVATELXNOSTYAMI 
$(P_1, P_2, P_3,\ldots)$, TAKIMI, 
CHTO $n\ge P_1\ge P_2\ge P_3\ge\ldots\ge0$, OBLADAYUSHCHEE 
TEM SVOJSTVOM, CHTO $p_1+p_2+\cdots+p_n=P_1+P_2+P_3+\cdots$. iNYMI SLOVAMI, 
RAZBIENIYAM NA NE BOLEE CHEM $n$~CHASTEJ SOOTVETSTVUYUT RAZBIENIYA NA CHASTI, NE 
PREVOSHODYASHCHIE~$n$.]

%% 35

\ex[m25](l. eJLER.) dOKAZHITE SLEDUYUSHCHIE TOZHDESTVA, 
INTERPRETIRUYA OBE CHASTI SOOTNOSHENIJ V TERMINAH RAZBIENIJ:

$$
\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] kAKOVY 24 CHETVERKI $(q_1, q_2, q_3, q_4)$, DLYA KOTORYH V 
SOOTVETSTVII mAK-mAGONA, OPREDELENNOM V KONCE |TOGO PUNKTA,  $(p_1, p_2,  
p_3, p_4)=(0,0, 0, 0)$?

\ex[m30] (t.~hIBBARD, {\sl CACM\/}, {\bf 6} (1963), 210.) pUSTX $n>0$, I 
PREDPOLOZHIM, CHTO POSLEDOVATELXNOSTX  $n\hbox{-BITOVYH}$ CELYH CHISEL 
$X_0$,~\dots, $X_{2^n-1}$   DLINY~$2^n$ POLUCHENA SLUCHAJNYM OBRAZOM, PRICHEM 
KAZHDYJ BIT KAZHDOGO CHISLA NEZAVISIMO PRINIMAET ZNACHENIE~1 S 
VEROYATNOSTXYU~$p$. rASSMOTRIM POSLEDOVATELXNOSTX $X_0\oplus0$, $X_1\oplus1$,
~\dots, $X_{2^n-1}\oplus(2^n-1)$, GDE $\oplus$---OPERACIYA "ISKLYUCHAYUSHCHEE ILI"
NAD BINARNYMI PREDSTAVLENIYAMI. tAK, ESLI $p=0$, TO POSLEDOVATELXNOSTX 
BUDET $0$, $1$,~\dots,  $2^n-1$, A ESLI $p= 1$, TO ONA BUDET $2^n- 1$,
~\dots, $1$, $0$; ESLI ZHE $p={1\over2}$,
TO KAZHDYJ |LEMENT POSLEDOVATELXNOSTI---SLUCHAJNOE CHISLO MEZHDU~$0$ 
I~$2^n-1$. vOOBSHCHE ZHE PRI RAZNYH~$p$ |TO HOROSHIJ SPOSOB POLUCHENIYA 
POSLEDOVATELXNOSTI SLUCHAJNYH CELYH CHISEL SO SMESHCHENNYM CHISLOM INVERSIJ, V 
TO VREMYA KAK RASPREDELENIE |LEMENTOV POSLEDOVATELXNOSTI, RASSMATRIVAEMOJ 
KAK EDINOE CELOE, RAVNOMERNO.

oPREDELITE SREDNEE CHISLO INVERSIJ V TAKOJ POSLEDOVATELXNOSTI KAK FUNKCIYU 
OT VEROYATNOSTI~$p$.

\ex [M36]  (d. fOATA.) dAJTE PRYAMOE DOKAZATELXSTVO TEOREMY mAK-mAGONA OB 
INDEKSAH: NAJDITE TOCHNOE VZAIMNO ODNOZNACHNOE SOOTVETSTVIE, KOTOROE 
PEREVODIT PERESTANOVKU $n$~|LEMENTOV, IMEYUSHCHUYU INDEKS~$k$, V PERESTANOVKU,
 IMEYUSHCHUYU $k$~INVERSIJ I TOT ZHE SAMYJ KRAJNIJ PRAVYJ |LEMENT.

\ex[M43] sLEDUYUSHCHEE ZNAMENITOE TOZHDESTVO, PRINADLEZHASHCHEE yaKOBI 
[Fundamenta Nova Theori\ae{} Functionum Ellipticorum (1829), \S~64], LEZHIT 
V OSNOVE MNOGIH ZAMECHATELXNYH SOOTNOSHENIJ, SODERZHASHCHIH |LLIPTICHESKIE FUNKCII:
$$
\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
}
$$
eSLI, NAPRIMER, POLOZHITX $u=z$, $v=z^2$, TO POLUCHITSYA FORMULA eJLERA 
IZ UPR.~14. eSLI POLOZHITX $z=\sqrt{u/v}$, $q=\sqrt{uv}$, TO POLUCHIM
$$
\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

sUSHCHESTVUET LI KOMBINATORNOE DOKAZATELXSTVO TOZHDESTVA yaKOBI, ANALOGICHNOE 
DOKAZATELXSTVU fRANKLINA DLYA CHASTNOGO SLUCHAYA UPR.~14? (tAKIM OBRAZOM,
 NUZHNO RASSMOTRETX "KOMPLEKSNYE RAZBIENIYA"
$$
m+ni=(p_1+q_1i)+(p_2+q_2i)+\cdots+(p_k+q_ki),
$$
GDE $p_j+q_ji$---RAZLICHNYE NENULEVYE KOMPLEKSNYE CHISLA; $p_j$, 
$q_j$---NEOTRICATELXNYE CELYE CHISLA, PRICHEM $\abs{p_j-q_j}\le 1$. sOGLASNO 
TOZHDESTVU yaKOBI, CHISLO TAKIH PREDSTAVLENIJ S CHETNYMI $k$ RAVNO CHISLU 
PREDSTAVLENIJ S NECHETNYMI $k$, ESLI TOLXKO $m$ I~$n$ NE YAVLYAYUTSYA SOSEDNIMI 
TREUGOLXNYMI CHISLAMI!) kAKIMI ESHCHE ZAMECHATELXNYMI SVOJSTVAMI OBLADAYUT 
KOMPLEKSNYE RAZBIENIYA?

\rex[m25] (g. d. kNOTT.) pOKAZHITE, CHTO PERESTANOVKU $a_1$ \dots $a_n$ 
MOZHNO POLUCHITX S POMOSHCHXYU STEKA V SMYSLE UPR. 2.2.1--5 ILI~2.3.1--6 TOGDA I 
TOLXKO TOGDA, KOGDA $C_j\le C_{j+1}+1$  PRI $1\le j<n$ (SM. OBOZNACHENIYA V UPR.~7).

\ex[m28] (k. mEJER.) mY ZNAEM, CHTO ESLI $m$ I~$n$---VZAIMNO PROSTYE CHISLA,
 TO POSLEDOVATELXNOSTX $(m \bmod n)$ $(2m \bmod n)$ \dots $((n-1) m\bmod 
n)$ PREDSTAVLYAET SOBOJ PERESTANOVKU MNOZHESTVA $\{1, 2, \ldots, n-1\}$. 
pOKAZHITE, CHTO CHISLO INVERSIJ V |TOJ PERESTANOVKE MOZHNO VYRAZITX CHEREZ 
SUMMY dEDEKINDA (SR. S P.~3.3.3).

\subsubchap{*pERESTANOVKI MULXTIMNOZHESTVA}
dO SIH POR MY RASSMATRIVALI PERESTANOVKI \emph{MNOZHESTVA} |LEMENTOV; |TO 
CHASTNYJ SLUCHAJ PERESTANOVOK \dfn{MULXTIMNOZHESTVA}. (mULXTIMNOZHESTVO---|TO TO 
ZHE SAMOE, CHTO I MNOZHESTVO, NO V NEM MOGUT SODERZHATXSYA ODINAKOVYE |LEMENTY. 
nEKOTORYE OSNOVNYE SVOJSTVA MULXTIMNOZHESTV OBSUZHDALISX V P.~4.6.3.)

rASSMOTRIM, NAPRIMER, MULXTIMNOZHESTVO
$$
M=\{a, a, a, b, b, c, d, d, d, d\},
\eqno(1)
$$
V KOTOROM SODERZHITSYA 3 |LEMENTA $a$, 2 |LEMENTA $b$, 1 |LEMENT $c$ I 4 
|LEMENTA $d$. pOVTORENIYA |LEMENTOV MOZHNO UKAZATX I DRUGIM SPOSOBOM:
$$
M=\{3\cdot a, 2\cdot b, c, 4\cdot d\}.
\eqno(2)
$$
pERESTANOVKA MULXTIMNOZHESTVA --- |TO NEKOTOROE RASPOLOZHENIE EGO |LEMENTOV V 
RYAD, NAPRIMER
$$
c\ a\ b\ d\ d\ a\ b\ d\ a\ d.
$$
s DRUGOJ STORONY, TAKUYU POSLEDOVATELXNOSTX MOZHNO NAZVATX CEPOCHKOJ BUKV, 
SODERZHASHCHEJ 3 BUKVY $a$, 2 BUKVY $b$, 1 BUKVU $c$ I 4 BUKVY $d$.

sKOLXKO SUSHCHESTVUET PERESTANOVOK MULXTIMNOZHESTVA $M$? eSLI BY MY 
RASSMATRIVALI VSE |LEMENTY $M$ KAK RAZLICHNYE, OBOZNACHIV IH $a_1$, $a_2$, 
$a_3$, $b_1$, $b_2$, $c_1$, $d_1$, $d_2$, $d_3$, $d_4$, TO POLUCHILI BY 
$10!=3\ 628\ 800$ PERESTANOVOK, NO POSLE OTBRASYVANIYA INDEKSOV MNOGIE IZ 
NIH OKAZALISX BY ODINAKOVYMI. fAKTICHESKI KAZHDAYA PERESTANOVKA $M$ 
VSTRETILASX BY ROVNO $3!2!1!4!=288$ RAZ, POSKOLXKU V LYUBOJ PERESTANOVKE 
$M$ INDEKSY PRI BUKVAH $a$ MOZHNO RASSTAVITX 31 SPOSOBAMI,
%% 37
PRI $b$ (NEZAVISIMO)---2! SPOSOBAMI, PRI $c$---ODNIM SPOSOBOM, A PRI 
$d$---SOOTVETSTVENNO 4! SPOSOBAMI. pO|TOMU CHISLO PERESTANOVOK $M$ RAVNO
$$
{10!\over 3!2!1!4!}=12\ 600.
$$
v PRIMENENII K OBSHCHEMU SLUCHAYU TE ZHE RASSUZHDENIYA DOKAZYVAYUT, CHTO CHISLO 
PERESTANOVOK LYUBOGO MULXTIMNOZHESTVA RAVNO MULXTINOMIALXNOMU KO|FFICIENTU
$$
\perm{n}{n_1, n_2, \ldots}={n!\over n_1!n_2!\ldots},
$$
GDE $n_1$---CHISLO |LEMENTOV PERVOGO TIPA, $n_2$---CHISLO |LEMENTOV VTOROGO TIPA 
I T. D., A $n=n_1+n_2+\cdots$---OBSHCHEE CHISLO |LEMENTOV.

kOLICHESTVO PERESTANOVOK MNOZHESTVA BYLO IZVESTNO ESHCHE V DREVNIE VREMENA. v 
DREVNEEVREJSKOJ 
kNIGE tVORENIYA (OKOLO 100 G. N. |.)%
\note{1}{kNIGA tVORENIYA (jOCIRA)---ODNA IZ OSNOVOPOLAGAYUSHCHIH KNIG 
KABBALISTIKI.--- {\sl pRIM. PEREV.\/}}, NAIBOLEE RANNEM LITERATURNOM 
PROIZVEDENII IUDEJSKOGO FILOSOFSKOGO MISTICIZMA, DANY VERNYE ZNACHENIYA 
PERVYH SEMI FAKTORIALOV, POSLE CHEGO GOVORITSYA: "pRODOLZHAJ I POLUCHISHX CHISLA,
 KOTORYE USTA NE MOGUT PROIZNESTI, A UHO NE MOZHET VOSPRINYATX." [Sefer 
Yezirah, ed. by R. Mordecai Atia (Jerusalem:
Sh. Monson, 1962), STIH 52 (STR. 107--108); SR. TAKZHE S Solomon Gandz, 
Studies in Hebrew Astronomy and Mathematics (New York:
Ktav, 1970), 494--496. kNIGA tVORENIYA BYLA OSNOVANA NA SCHITAVSHIHSYA VAZHNYMI 
OTNOSHENIYAH MEZHDU SEMXYU PLANETAMI, SEMXYU SOGLASNYMI ZVUKAMI S DVOJNYM 
PROIZNOSHENIEM, SEMXYU OTVERSTIYAMI V GOLOVE CHELOVEKA I SEMXYU DNYAMI 
SOTVORENIYA MIRA.] eTO PERVYJ IZVESTNYJ V ISTORII PODSCHET CHISLA 
PERESTANOVOK. vTOROJ VSTRECHAETSYA V INDIJSKOM KLASSICHESKOM PROIZVEDENII 
aNUJOGADVARA-SUTRA (OKOLO 500~G.~N.~|.), PRAVILO 97, GDE 
PRIVODITSYA FORMULA CHISLA PERESTANOVOK SHESTI |LEMENTOV, KOTORYE NE 
RASPOLOZHENY NI V VOZRASTAYUSHCHEM, NI V UBYVAYUSHCHEM PORYADKE:
$$
6\times5\times4\times3\times2\times1-2.
$$
[sM. G. Chakravarti, {\sl Bull. Calcutta Math. Soc.\/}, {\bf 24} (1932), 
79--88. aNUJOGADVARA-SUTRA---ODNA IZ KNIG KANONOV DZHAJNIZMA, RELIGIOZNOJ 
SEKTY, RASPROSTRANENNOJ V iNDII.]

sOOTVETSTVUYUSHCHEE PRAVILO DLYA MULXTIMNOZHESTV VPERVYE, PO- VIDIMOMU, 
VSTRECHAETSYA V KNIGE lILAVATI, NAPISANNOJ bHASKAROJ aHARXEJ (OK. 1150~G.), 
RAZD.~270--271. u bHASZHARY |TO PRAVILO SFORMULIROVANO VESXMA SZHATO I 
PROILLYUSTRIROVANO LISHX DVUMYA PROSTYMI PRIMERAMI $\{2, 2, 1, 1\}$ I~$\{4, 8,
 5, 5, 5\}$. v REZULXTATE V ANGLIJSKOM PEREVODE |TO PRAVILO NE SFORMULIROVANO
%% 38
KORREKTNO, VPROCHEM, IMEYUTSYA NEKOTORYE SOMNENIYA OTNOSITELXNO TOGO, PONIMAL 
LI SAM bHASKARA, O CHEM ON GOVORIL. vSLED ZA |TIM PRAVILOM bHASKARA 
PRIVODIT INTERESNUYU FORMULU
$$
(4+8+5+5+5)\times 120\times 11111 \over 5\times 6
$$
DLYA SUMMY 20 CHISEL $48\ 555 + 45 855 + \cdots$.

vERNOE PRAVILO DLYA NAHOZHDENIYA CHISLA PERESTANOVOK V SLUCHAE, KOGDA TOLXKO 
ODIN |LEMENT MOZHET POVTORYATXSYA, NAJDENO NEZAVISIMO NEMECKIM UCHENYM 
IEZUITOM aTANASIUSOM kIRHEROM V EGO MNOGOTOMNOM TRUDE O MUZYKE Musurgia 
Universalis (Rome, 1650), TOM~2, STR.~5--7. kIRHERA INTERESOVAL VOPROS O 
KOLICHESTVE MELODIJ, KOTORYE MOZHNO SOZDATX IZ DANNOGO NABORA NOT;
DLYA |TOGO ON PRIDUMAL TO, CHTO NAZYVAL "MUZARIFMETIKOJ". nA STR. 18--21 
SVOEGO TRUDA ON DAET VERNOE ZNACHENIE CHISLA PERESTANOVOK MULXTIMNOZHESTVA 
$\{m\cdot C, n\cdot D\}$ PRI NESKOLXKIH ZNACHENIYAH $m$ I $n$, HOTYA OPISAL 
ON SVOJ METOD VYCHISLENIJ LISHX DLYA SLUCHAYA $n= 1$.

oBSHCHEE PRAVILO (3) POYAVILOSX POZZHE V KNIGE zhANA pREST| El\'emens de 
Math\'ematiques (Paris, 1675), STR. 351--352, KOTORAYA SODERZHIT ODNO IZ 
PERVYH IZLOZHENIJ KOMBINATORNOJ MATEMATIKI, NAPISANNYH V ZAPADNOJ eVROPE. 
pREST| VERNO SFORMULIROVAL PRAVILO DLYA SLUCHAYA PROIZVOLXNOGO 
MULXTIMNOZHESTVA, NO PROILLYUSTRIROVAL EGO LISHX PROSTYM PRIMEROM $\{a, a, 
b, b, c, c\}$. oN OSOBO OTMETIL, CHTO DELENIE NA \emph{SUMMU} FAKTORIALOV, 
KOTOROE ON SCHITAL ESTESTVENNYM OBOBSHCHENIEM PRAVILA kIRHERA, BYLO BY OSHIBKOJ.
 nESKOLXKO LET SPUSTYA dZHON vALLIS V SVOEJ KNIGE Treatise of Algebra 
(Oxford, 1685), TOM 2, STR. 117--118, OBSUDIL |TO PRAVILO NESKOLXKO BOLEE PODROBNO.

v 1965~G. dOMINIK fOATA VVEL ODNO INTERESNOE PONYATIE, TAK NAZYVAEMOE 
"SOEDINITELXNOE PROIZVEDENIE"%
\note{1}{v ORIGINALE---"intercalation product".---{\sl pRIM. PEREV.\/}}, 
KOTOROE POZVOLILO RASPROSTRANITX MNOGIE IZVESTNYE REZULXTATY, KASAYUSHCHIESYA 
OBYCHNYH PERESTANOVOK, NA OBSHCHIJ SLUCHAI PERESTANOVOK MULXTIMNOZHESTVA. 
[sM. Publ. Inst. Statistique, Univ. Paris, {\bf 14} (1965), 81--241. A 
TAKZHE Lecture Notes in Math., {\bf 85} (Springer, 1969).] pREDPOLAGAYA, CHTO 
|LEMENTY MULXTIMNOZHESTVA KAKIM-TO SPOSOBOM LINEJNO UPORYADOCHENY, MOZHNO 
RASSMOTRETX \dfn{DVUSTROCHNOE OBOZNACHENIE}, NAPRIMER
$$
\pmatrix{
 a & a & a & b & b & c & d & d & d & d\cr
 c & a & b & d & d & a & b & d & a & d\cr
}.
$$
zDESX VERHNYAYA STROKA SODERZHIT |LEMENTY $M$ V NEUBYVAYUSHCHEM PORYADKE, I 
NIZHNYAYA---|TO SAMA PERESTANOVKA. \dfn{sOEDINITELXNOE
%%39
PROIZVEDENIE} $\alpha\T\beta$  DVUH PERESTANOVOK MULXTIMNOZHESTV $\alpha$  
I $\beta$---|TO PERESTANOVKA, KOTORAYA POLUCHAETSYA, ESLI (a) VZYATX 
DVUSTROCHNYE OBOZNACHENIYA DLYA $\alpha$ I~$\beta$, (b) ZAPISATX 
SOOTVETSTVUYUSHCHIE STROKI V ODNU I (c) OTSORTIROVATX STOLBCY TAK, CHTOBY 
|LEMENTY VERHNEJ STROKI RASPOLOZHILISX V NEUBYVAYUSHCHEM PORYADKE. 
sORTIROVKA DOLZHNA BYTX USTOJCHIVOJ V TOM SMYSLE, CHTO VZAIMNOE 
RASPOLOZHENIE |LEMENTOV NIZHNEJ STROKI SOHRANYAETSYA, ESLI SOOTVETSTVUYUSHCHIE 
|LEMENTY VERHNEJ STROKI RAVNY. nAPRIMER, 
$c\ a\ d\ a\ b \T b\ d\ d\ a\ d=c\ a\ b \ d\ d\ a\ b\ d\ a\ d$, TAK KAK
$$
\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)
$$

nETRUDNO VIDETX, CHTO OPERACIYA SOEDINITELXNOGO PROIZVEDENIYA ASSOCIATIVNA, 
T.~E.
$$
\alpha\T\beta\T\gamma=\alpha\T(\beta\T\gamma),
\eqno(6)
$$
I CHTO ONA PODCHINYAETSYA ZAKONAM SOKRASHCHENIYA
$$
\eqalign{
&\hbox{ESLI $\pi\T\alpha=\pi\T\beta$, TO $\alpha=\beta$,}\cr
&\hbox{ESLI $\alpha\T\pi=\beta\T\pi$, TO $\alpha=\beta$.}\cr
}
$$
sUSHCHESTVUET "EDINICHNYJ |LEMENT"
$$
\alpha\T\varepsilon=\varepsilon\T\alpha=\alpha,
\eqno(8)
$$
GDE $\varepsilon$---PUSTAYA PERESTANOVKA, "RASPOLOZHENIE V RYAD" 
|LEMENTOV PUSTOGO MNOZHESTVA. zAKON KOMMUTATIVNOSTI, VOOBSHCHE GOVORYA, 
NE VYPOLNYAETSYA (SM. UPR.~2), TEM NE MENEE
$$
\alpha\T\beta=\beta\T\alpha,
\rem{ESLI $\alpha$ I~$\beta$ NE SODERZHAT OBSHCHIH BUKV.}
\eqno (9)
$$

aNALOGICHNYM SPOSOBOM I PONYATIE \emph{CIKLA} MOZHNO RASPROSTRANITX NA SLUCHAJ,
KOGDA |LEMENTY MOGUT POVTORYATXSYA. bUDEM ZAPISYVATX V VIDE
$$
(x_1\  x_2\ \dots\ x_n) 
\eqno (10)
$$
PERESTANOVKU, DVUSTROCHNOE PREDSTAVLENIE KOTOROJ POLUCHAETSYA PUTEM 
USTOJCHIVOJ SORTIROVKI STOLBCOV
$$
\pmatrix{
x_1 & x_2 & \ldots & x_n\cr
x_2 & x_3 & \ldots & x_1\cr
}
\eqno(11)
$$
PO VERHNIM |LEMENTAM. nAPRIMER,
$$
\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
TAK CHTO PERESTANOVKA (4) FAKTICHESKI YAVLYAETSYA CIKLOM. mY MOGLI BY OPISATX 
|TOT CIKL SLOVESNO, SKAZAV CHTO-NIBUDX VRODE "$d$ PEREHODIT V $b$, 
PEREHODIT V $d$, PEREHODIT V $d$, PEREHODIT V \dots PEREHODIT V $d$ I 
VOZVRASHCHAETSYA OBRATNO". zAMETIM, CHTO |TI OBOBSHCHENNYE CIKLY NE OBLADAYUT 
VSEMI SVOJSTVAMI OBYCHNYH CIKLOV;
$(x_1\ x_2\ \ldots\ x_n)$ NE OBYAZATELXNO TO ZHE SAMOE, CHTO I 
$(x_2\ \ldots\ x_n\ x_1)$ .

v P.~1.3.3 MY VYYASNILI, CHTO KAZHDUYU PERESTANOVKU MNOZHESTVA MOZHNO 
EDINSTVENNYM S TOCHNOSTXYU DO PORYADKA SOMNOZHITELEJ OBRAZOM PREDSTAVITX V 
VIDE PROIZVEDENIYA NEPERESEKAYUSHCHIHSYA CIKLOV, GDE PROIZVEDENIE PERESTANOVOK 
OPREDELYAETSYA ZAKONOM KOMPOZICII. lEGKO VIDETX, CHTO \dfn{PROIZVEDENIE 
NEPERESEKAYUSHCHIHSYA CIKLOV---TO ZHE SAMOE, CHTO IH SOEDINITELXNOE PROIZVEDENIE;} 
|TO NAVODIT NA MYSLX O TOM, CHTO MOZHNO BUDET OBOBSHCHITX POLUCHENNYE RANEE 
REZULXTATY, ESLI NAJTI EDINSTVENNOE (V KAKOM-TO SMYSLE) PREDSTAVLENIE I 
DLYA PROIZVOLXNOJ PERESTANOVKI MULXTIMNOZHESTVA V VIDE SOEDINITELXNOGO 
PROIZVEDENIYA CIKLOV. v DEJSTVITELXNOSTI SUSHCHESTVUYUT PO KRAJNEJ MERE DVA 
ESTESTVENNYH SPOSOBA SDELATX |TO, I KAZHDYJ IZ NIH IMEET VAZHNYE PRILOZHENIYA.

rAVENSTVO (5) DAET ODIN SPOSOB PREDSTAVLENIYA 
$c\ a\ b\ d\ d\ a\ b\ d\ a\ \ d$ V VIDE SOEDINITELXNOGO PROIZVEDENIYA BOLEE 
KOROTKIH PERESTANOVOK; 
RASSMOTRIM OBSHCHUYU ZADACHU O NAHOZHDENII VSEH RAZLOZHENIJ $\pi=\alpha\T\beta$ 
DANNOJ PERESTANOVKI $\pi$. dLYA ISSLEDOVANIYA |TOGO VOPROSA  POLEZNO 
RASSMOTRETX KONKRETNUYU PERESTANOVKU, SKAZHEM
$$
\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)
$$

eSLI MOZHNO ZAPISATX $\pi$ V VIDE $\alpha\T\beta$, GDE $\alpha$ SODERZHIT PO 
KRAJNEJ MERE ODNU BUKVU $a$, TO SAMOE LEVOE $a$ V VERHNEJ STROKE 
DVUSTROCHNOGO PREDSTAVLENIYA $\alpha$ DOLZHNO OKAZATXSYA NAD $d$, ZNACHIT, 
PERESTANOVKA $\alpha$ DOLZHNA SODERZHATX PO KRAJNEJ MERE ODNU BUKVU 
$d$. eSLI VZGLYANUTX TEPERX NA SAMOE LEVOE $d$ V VERHNEJ STROKE $\alpha$, 
TO UVIDIM TOCHNO TAK ZHE, CHTO ONO DOLZHNO OKAZATXSYA NAD $d$, ZNACHIT, V 
$\alpha$ DOLZHNY SODERZHATXSYA PO MENXSHEJ MERE \emph{DVE} BUKVY $d$. 
pOSMOTREV NA VTOROE $d$, VIDIM, CHTO $\alpha$ SODERZHIT TAKZHE $b$. 
oDNO-EDINSTVENNOE PREDPOLOZHENIE O TOM, CHTO $\alpha$ ESTX LEVYJ SOMNOZHITELX 
$\pi$, SODERZHASHCHIJ BUKVU $a$, PRIVODIT K TAKOMU PROMEZHUTOCHNOMU REZULXTATU:
$$
\pmatrix{
a &           & b &          & d & d \cr
   &\ldots &    &\ldots&   &  & \ldots\cr
d &           &    &          & d & b \cr
}.
\eqno(13)
$$

pRODOLZHAYA RASSUZHDATX TOCHNO TAK ZHE I DALEE, OBNARUZHIM, CHTO BUKVA $b$ V 
VERHNEJ STROKE (13) DOLZHNA OKAZATXSYA NAD $c$ I T.~D. v KONCE KONCOV |TOT 
PROCESS VNOVX PRIVEDET NAS K BUKVE $a$, I MY SMOZHEM, ESLI ZAHOTIM, 
OTOZHDESTVITX EE S PERVOJ BUKVOJ $a$. tOLXKO CHTO PROVEDENNOE RASSUZHDENIE, 
PO SUSHCHESTVU, DOKAZYVAET,
%% 41
\bye