\input style
\chapno=5
\subchno=1
\subsubchno=1
\chapnotrue
\excercises
%% 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