\input style
\noindent
%% 41
CHTO LYUBOJ LEVYJ SOMNOZHITELX V RAZLOZHENII PERESTANOVKI (12), SODERZHASHCHIJ $a$,
 IMEET VID $(d\ d\ b\ c\ d\ b\ b\ c\ a)\T \alpha'$, GDE $\alpha'$--- 
NEKOTORAYA PERESTANOVKA. (uDOBNO ZAPISYVATX $a$ NE V NACHALE, A V 
KONCE CIKLA; |TO DOPUSTIMO, POSKOLXKU BUKVA $a$ TOLXKO ODNA.) aNALOGICHNO,
 ESLI BY MY PREDPOLOZHILI, CHTO $\alpha$ SODERZHIT BUKVU $b$, TO VYVELI BY, 
CHTO $\alpha=(c\ d\ d\ b) \T \alpha''$, GDE $\alpha''$---NEKOTORAYA PERESTANOVKA.

v OBSHCHEM SLUCHAE |TI RASSUZHDENIYA POKAZYVAYUT, CHTO \emph{ESLI 
ESTX KAKOE-NIBUDX RAZLOZHENIE $\alpha\T\beta=\pi$, GDE $\alpha$ SODERZHIT 
DANNUYU BUKVU $y$, TO SUSHCHESTVUET EDINSTVENNYJ CIKL VIDA
$$
(x_1\ \ldots\ x_n\ y), \qquad n\ge 0, x_1, \ldots, x_n\ne y,
\eqno(14)
$$
KOTORYJ YAVLYAETSYA LEVYM SOMNOZHITELEM V RAZLOZHENII PERESTANOVKI $\alpha$.} 
tAKOJ CIKL LEGKO OTYSKATX, ZNAYA $\pi$ I $y$; |TO SAMYJ KOROTKIJ LEVYJ 
SOMNOZHITELX V RAZLOZHENII PERESTANOVKI $\pi$, SODERZHASHCHIJ BUKVU $y$. oDNO IZ 
SLEDSTVIJ |TOGO NABLYUDENIYA DAET

\proclaim tEOREMA A. pUSTX |LEMENTY MULXTIMNOZHESTVA $M$ LINEJNO 
UPORYADOCHENY OTNOSHENIEM "$<$". kAZHDAYA PERESTANOVKA $\pi$ MULXTIMNOZHESTVA 
$M$ IMEET EDINSTVENNOE PREDSTAVLENIE V VIDE SOEDINITELXNOGO PROIZVEDENIYA
$$
\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)
$$
UDOVLETVORYAYUSHCHEE SLEDUYUSHCHIM DVUM USLOVIYAM:
$$
\displaylines{
y_1\le y_2 \le \ldots \le y_t;\cr
\hfill y_i<x_{ij}\hbox{ PRI $1\le j\le n_i$, $1\le i\le t$.}\hfill\llap{\rm(16)}\cr
}
$$
(iNYMI SLOVAMI, V KAZHDOM CIKLE POSLEDNIJ |LEMENT MENXSHE LYUBOGO DRUGOGO, I 
POSLEDNIE |LEMENTY CIKLOV OBRAZUYUT NEUBYVAYUSHCHUYU POSLEDOVATELXNOSTX.)

\proof pRI $\pi=\varepsilon$ POLUCHIM TREBUEMOE RAZLOZHENIE, POLOZHIV $t=0$.
 v PROTIVNOM SLUCHAE PUSTX $y_1$---MINIMALXNYJ |LEMENT $\pi$;
OPREDELIM $(x_{11}\ldots x_{1n_1}y_1)$---SAMYJ KOROTKIJ LEVYJ 
SOMNOZHITELX RAZLOZHENIYA $\pi$, SODERZHASHCHIJ $y_1$, KAK V RASSMOTRENNOM 
PRIMERE. tEPERX $\pi=(x_{11}\ldots x_{1n_1} y_1)\T\rho$, GDE 
$\rho$---NEKOTORAYA PERESTANOVKA;
PRIMENIV INDUKCIYU PO DLINE PERESTANOVKI, MOZHEM NAPISATX
$$
\rho=(x_{21}\ldots x_{2n_2}y_2)\T\ldots\T(x_{t1}\ldots x_{tn_t}y_t), t\ge1,
$$
GDE USLOVIYA (16) VYPOLNENY. tEM SAMYM DOKAZANO SUSHCHESTVOVANIE TAKOGO RAZLOZHENIYA.

dOKAZHEM EDINSTVENNOSTX RAZLOZHENIYA (15), UDOVLETVORYAYUSHCHEGO USLOVIYAM (16). 
yaSNO, CHTO $t=0$ TOGDA I TOLXKO TOGDA, KOGDA $\pi$--- PUSTAYA PERESTANOVKA 
$\varepsilon$. pRI $t>0$ IZ (16) SLEDUET, CHTO $y_1$---MINIMALXNYJ |LEMENT 
PERESTANOVKI $\pi$ I CHTO $(x_{11}\ldots x_{1n_1}y_1$---SAMYJ KOROTKIJ
%%42
LEVYJ SOMNOZHITELX, SODERZHASHCHIJ $y_1$. pO|TOMU 
$(x_{11}\ldots x_{1n_1} y_1)$
OPREDELYAETSYA ODNOZNACHNO; DOKAZATELXSTVO EDINSTVENNOSTI 
TAKOGO PREDSTAVLENIYA ZAVERSHAETSYA PRIMENENIEM INDUKCII I ZAKONOV SOKRASHCHENIYA 
(7). 
\proofend

nAPRIMER, "KANONICHESKOE" RAZLOZHENIE PERESTANOVKI (12), UDOVLETVORYAYUSHCHEE 
DANNYM USLOVIYAM, TAKOVO:
$$
(d\ d\ b\ c\ d\ b\ b\ c\ a)\T(b\ a)\T(c\ d\ b)\T(d),
\eqno(17)
$$
ESLI $a<b<c<d$.

vAZHNO OTMETITX, CHTO NA SAMOM DELE V |TOM OPREDELENII MOZHNO OTBROSITX 
SKOBKI I ZNAKI OPERACII $\T$, I |TO NE PRIVEDET K NEODNOZNACHNOSTI! 
kAZHDYJ CIKL ZAKANCHIVAETSYA POYAVLENIEM NAIMENXSHEGO IZ OSTAVSHIHSYA |LEMENTOV.
 tAKIM OBRAZOM, NASHE POSTROENIE SVYAZYVAET S ISHODNOJ PERESTANOVKOJ
$$
\pi'=d\ d\ b\ c\ d\ b\ b\ c\ a\ b\ a\ c\ d\ b\ d
$$
PERESTANOVKU
$$
\pi=d\ b\ c\ b\ c\ a\ c\ d\ a\ d\ d\ b\ b\ b\ d.
$$
eSLI V DVUSTROCHNOM PREDSTAVLENII $\pi$ SODERZHITSYA STOLBEC VIDA 
$y\atop x$, GDE $x<y$, TO V SVYAZANNOJ S $\pi$ PERESTANOVKE PRISUTSTVUET 
SOOTVETSTVUYUSHCHAYA PARA SOSEDNIH |LEMENTOV $\ldots y\ x\ldots$. tAK, V 
NASHEM PRIMERE $\pi$ SODERZHIT TRI STOLBCA VIDA $d\atop b$, A V $\pi'$ TRIZHDY
VSTRECHAETSYA PARA $d\ b$. vOOBSHCHE IZ |TOGO POSTROENIYA VYTEKAET ZAMECHATELXNAYA

\proclaim tEOREMA B. {pUSTX $M$---MULXTIMNOZHESTVO. sUSHCHESTVUET VZAIMNO 
ODNOZNACHNOE SOOTVETSTVIE MEZHDU PERESTANOVKAMI $M$, TAKOE, CHTO ESLI $\pi$ 
SOOTVETSTVUET $\pi'$, TO VYPOLNYAYUTSYA SLEDUYUSHCHIE USLOVIYA:
\medskip
\item{a)} KRAJNIJ LEVYJ |LEMENT $\pi'$ RAVEN KRAJNEMU LEVOMU 
|LEMENTU~$\pi$;
\item{b)} DLYA VSEH PAR UCHASTVUYUSHCHIH V PERESTANOVKE |LEMENTOV $(x, y)$,
\medskip
\noindent TAKIH, CHTO $x<y$, CHISLO VHOZHDENIJ STOLBCA $y\atop x$ V 
DVUSTROCHNOE PREDSTAVLENIE PERESTANOVKI $\pi$ RAVNO CHISLU SLUCHAEV, KOGDA V 
PERESTANOVKE $\pi'$ |LEMENT $x$ SLEDUET NEPOSREDSTVENNO ZA $y$.}

eSLI $M$---MNOZHESTVO, TO |TO, PO SUSHCHESTVU, "NESTANDARTNOE SOOTVETSTVIE", 
OBSUZHDAVSHEESYA V KONCE P.~1.3.3, S NEZNACHITELXNYMI IZMENENIYAMI. bOLEE 
OBSHCHIJ REZULXTAT TEOREMY B POLEZEN PRI PODSCHETE CHISLA PERESTANOVOK 
SPECIALXNYH TIPOV, POSKOLXKU CHASTO PROSHCHE RESHITX ZADACHU S OGRANICHENIYAMI, 
NALOZHENNYMI NA DVUSTROCHNOE PREDSTAVLENIE, CHEM |KVIVALENTNUYU ZADACHU S 
OGRANICHENIYAMI NA PARY SOSEDNIH |LEMENTOV.
%% 43

p.~a.~mAK-mAGON RASSMOTREL ZADACHI |TOGO TIPA V SVOEJ VYDAYUSHCHEESYA KNIGE 
Combinatory Analysis (Cambridge Univ. Press, 1915), TOM~1, STR. 168--186. 
oN DAL KONSTRUKTIVNOE DOKAZATELXSTVO TEOREMY~B V CHASTNOM SLUCHAE, KOGDA M 
SODERZHIT |LEMENTY LISHX DVUH RAZLICHNYH TIPOV, SKAZHEM $a$ I~$b$, EGO 
POSTROENIE DLYA |TOGO SLUCHAYA, PO SUSHCHESTVU, SOVPADAET S PRIVEDENNYM ZDESX, 
NO PREDSTAVLENO V SOVERSHENNO INOM VIDE. dLYA SLUCHAYA TREH RAZLICHNYH 
|LEMENTOV $a$, $b$, $c$ mAK-mAGON DAL SLOZHNOE NEKONSTRUKTIVNOE 
DOKAZATELXSTVO TEOREMY~B; OBSHCHIJ SLUCHAJ VPERVYE DOKAZAL fOATA V 1965~G.

v KACHESTVE NETRIVIALXNOGO PRIMERA PRIMENENIYA TEOREMY~B NAJDEM CHISLO 
CEPOCHEK BUKV $a$, $b$, $c$, SODERZHASHCHIH ROVNO
$$
\eqalign{
A&\hbox{ VHOZHDENIJ BUKVY $a$;}\cr
B&\hbox{ VHOZHDENIJ BUKVY $b$;}\cr
C&\hbox{ VHOZHDENIJ BUKVY $c$;}\cr
k&\hbox{ VHOZHDENIJ PARY STOYASHCHIH RYADOM BUKV $c\ a$;}\cr
l&\hbox{ VHOZHDENIJ PARY STOYASHCHIH RYADOM BUKV $c\ b$;}\cr
m&\hbox{ VHOZHDENIJ PARY STOYASHCHIH RYADOM BUKV $b\ a$;}\cr
}
\eqno(18)
$$
iZ TEOREMY SLEDUET, CHTO |TO TO ZHE SAMOE, CHTO NAJTI CHISLO DVUSTROCHNYH 
MASSIVOV VIDA
{
\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{ BUKV $a$}}
$}
\setbox\Bbox\hbox{$\displaystyle
\underbrace{
  \overbrace{
    \matrix{
      b & \ldots & b\cr
     \] & \ldots &\]\cr
    }
  }^B
}_{m\hbox{ BUKV $a$}}
$}
\setbox\Cbox\hbox{$\displaystyle
\underbrace{
\overbrace{
 \matrix{
   c & \ldots & c \cr
  \] & \ldots &\] \cr
 }
}^C
\hbox to 0pt{$\displaystyle\Bigr)\hss$}
}_{k\hbox{ BUKV $a$}}
$}
$$
\underbrace{
 \underbrace{\copy\Abox \copy\Bbox}_{\hbox{$B-l$ BUKV $b$}}\;\;
 \underbrace{\copy\Cbox}_{\hbox{$l$ BUKV $b$}}
}_{\hbox{$C$ BUKV $c$}}
\eqno (19)
$$
}
bUKVY $a$ MOZHNO RASPOLOZHITX VO VTOROJ STROKE
$$
\perm{A}{A-k-m}\perm{B}{m}\perm{C}{k}
\rem{SPOSOBAMI;}
$$
POSLE |TOGO BUKVY $b$ MOZHNO RAZMESTITX V OSTAVSHIHSYA POZICIYAH
$$
\perm{B+k}{B-l}\perm{C-k}{l}\rem{SPOSOBAMI.}
$$
oSTALXNYE SVOBODNYE MESTA NUZHNO ZAPOLNITX BUKVAMI $c$; SLEDOVATELXNO, 
ISKOMOE CHISLO RAVNO
$$
\perm{A}{A-k-m}\perm{B}{m}\perm{C}{k}\perm{B+k}{B-l}\perm{C-k}{l}.
\eqno(20)
$$

%% 44

vERNEMSYA K VOPROSU O NAHOZHDENII VSEH RAZLOZHENIJ DANNOJ PERESTANOVKI. 
sUSHCHESTVUET LI TAKOJ OB®EKT, KAK "PROSTAYA" PERESTANOVKA, KOTORAYA NE 
RAZLAGAETSYA NA MNOZHITELI, OTLICHNYE OT NEE SAMOJ I $\varepsilon$? 
oBSUZHDENIE, PREDSHESTVUYUSHCHEE TEOREME A, NEMEDLENNO PRIVODIT K VYVODU O TOM, 
CHTO \emph{PERESTANOVKA BUDET PROSTOJ TOGDA I TOLXKO TOGDA, KOGDA ONA ESTX 
CIKL BEZ POVTORYAYUSHCHIHSYA |LEMENTOV,} TAK KAK, ESLI PERESTANOVKA YAVLYAETSYA 
TAKIM CIKLOM, NASHE RASSUZHDENIE DOKAZYVAET, CHTO NE SUSHCHESTVUET LEVYH 
MNOZHITELEJ, KROME $\varepsilon$ I SAMOGO CIKLA. eSLI ZHE PERESTANOVKA 
SODERZHIT POVTORYAYUSHCHIJSYA |LEMENT $y$, TO VSEGDA MOZHNO VYDELITX 
NETRIVIALXNYJ CIKL V KACHESTVE LEVOGO SOMNOZHITELYA, V KOTOROM |LEMENT 
U VSTRECHAETSYA VSEGO ODNAZHDY.

eSLI PERESTANOVKA NE PROSTAYA, TO EE MOZHNO RAZLAGATX NA VSE MENXSHIE I 
MENXSHIE CHASTI, POKA NE BUDET POLUCHENO PROIZVEDENIE PROSTYH PERESTANOVOK. 
mOZHNO DAZHE POKAZATX, CHTO TAKOE RAZLOZHENIE EDINSTVENNO S TOCHNOSTXYU DO 
PORYADKA ZAPISI KOMMUTIRUYUSHCHIH SOMNOZHITELEJ.

\proclaim tEOREMA C. kAZHDUYU PERESTANOVKU MULXTIMNOZHESTVA MOZHNO ZAPISATX 
V VIDE PROIZVEDENIYA
$$
\sigma_1\T\sigma_2\T\ldots\T\sigma_t, \quad t\ge 0,
\eqno(21)
$$
GDE $\sigma_j$---CIKLY, NE SODERZHASHCHIE POVTORYAYUSHCHIHSYA |LEMENTOV. 
eTO PREDSTAVLENIE EDINSTVENNO V TOM SMYSLE, CHTO LYUBYE DVA 
TAKIH PREDSTAVLENIYA ODNOJ I TOJ ZHE PERESTANOVKI MOZHNO PREOBRAZOVATX ODNO 
V DRUGOE, POSLEDOVATELXNO MENYAYA MESTAMI SOSEDNIE NEPERESEKAYUSHCHIESYA CIKLY.

tERMIN "NEPERESEKAYUSHCHIESYA CIKLY" OTNOSITSYA K CIKLAM, NE IMEYUSHCHIM OBSHCHIH 
|LEMENTOV. v KACHESTVE PRIMERA MOZHNO PROVERITX, CHTO PERESTANOVKA
$$
\pmatrix{
a & a & b & b & c & c & d\cr
b & a & a & c & d & b & c\cr
}
$$ 
RAZLAGAETSYA NA MNOZHITELI ROVNO PYATXYU SPOSOBAMI:
$$
\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 nUZHNO USTANOVITX, CHTO VYPOLNYAETSYA SFORMULIROVANNOE V TEOREME 
SVOJSTVO EDINSTVENNOSTI. pRIMENIM INDUKCIYU PO DLINE PERESTANOVKI; TOGDA 
DOSTATOCHNO DOKAZATX, CHTO ESLI $\rho$ I~$\sigma$---DVA RAZLICHNYH CIKLA, NE 
SODERZHASHCHIE POVTORYAYUSHCHIHSYA |LEMENTOV,
%%45
I
$$
\rho\T\alpha=\sigma\T\beta,
$$
TO $\rho$ I~$\sigma$---NEPERESEKAYUSHCHIESYA CIKLY,  I
$$
\alpha=\sigma\T\theta,\quad \beta=\rho\T\theta,
$$
GDE $\theta$---NEKOTORAYA PERESTANOVKA.

pUSTX $y$---PROIZVOLXNYJ |LEMENT CIKLA $\rho$, TOGDA U LYUBOGO LEVOGO 
SOMNOZHITELYA V RAZLOZHENII $\sigma\T\beta$, SODERZHASHCHEGO |TOT |LEMENT $y$, 
BUDET LEVYJ SOMNOZHITELX $\rho$. zNACHIT, ESLI $\rho$ I~$\sigma$ IMEYUT OBSHCHIJ 
|LEMENT, TO CIKL $\sigma$ DOLZHEN BYTX KRATEN $\rho$; SLEDOVATELXNO,
 $\sigma=\rho$ (TAK KAK ONI PROSTYE), CHTO PROTIVORECHIT NASHEMU 
PREDPOLOZHENIYU. sLEDOVATELXNO, CIKL, SODERZHASHCHIJ $y$ I NE IMEYUSHCHIJ OBSHCHIH 
|LEMENTOV S $\sigma$, DOLZHEN BYTX LEVYM SOMNOZHITELEM V RAZLOZHENII $\beta$. 
pRIMENIV ZAKONY SOKRASHCHENIYA (7), ZAVERSHIM DOKAZATELXSTVO.
\proofend

v KACHESTVE ILLYUSTRACII TEOREMY C RASSMOTRIM PERESTANOVKI MULXTIMNOZHESTVA 
$M=\{A\cdot a, B\cdot b, C\cdot c\}$, SOSTOYASHCHEGO IZ $A$ |LEMENTOV~$a$, 
$B$ |LEMENTOV~$b$ I~$C$ |LEMENTOV~$c$. pUSTX $N(A, B, C, m)$--- CHISLO 
PERESTANOVOK MULXTIMNOZHESTVA~$M$, DVUSTROCHNOE PREDSTAVLENIE KOTORYH 
\emph{NE SODERZHIT} STOLBCOV VIDA $a\atop a$, $b\atop b$, $c\atop c$  I SODERZHIT
ROVNO $m$ STOLBCOV VIDA~$a\atop b$. oTSYUDA SLEDUET, CHTO IMEETSYA 
ROVNO $A-m$~STOLBCOV VIDA~$a\atop c$, $B-m$~STOLBCOV VIDA~$c\atop b$, 
$C-B+m$ STOLBCOV VIDA~$c\atop a$, $C-A+m$~STOLBCOV VIDA$b\atop c$   
I~$A+B-C-m$ STOLBCOV VIDA~$b\atop a$ ; SLEDOVATELXNO,
$$
N(A, B, C, m)=\perm{A}{m}\perm{B}{C-A+m}\perm{C}{B-m}.
\eqno(23)
$$

tEOREMA~C PREDLAGAET DRUGOJ SPOSOB DLYA PODSCHETA |TIH PERESTANOVOK: KOLX 
SKORO STOLBCY $a\atop a$, $b\atop b$, $c\atop c$ ISKLYUCHENY, TO V 
RAZLOZHENII PERESTANOVKI EDINSTVENNO VOZMOZHNY TAKIE PROSTYE MNOZHITELI:
$$
(a\ b), (a\ c), (b\ c), (a\ b\ c), (a\ c\ b).
\eqno(24)
$$ 
kAZHDAYA PARA |TIH CIKLOV IMEET HOTYA BY ODNU OBSHCHUYU BUKVU, ZNACHIT, RAZLOZHENIE 
EDINSTVENNO. eSLI CIKL $(a\ b\ c)$ VSTRECHAETSYA V RAZLOZHENII $k$ RAZ, TO IZ 
NASHEGO PREDYDUSHCHEGO PREDPOLOZHENIYA SLEDUET, CHTO $(a\ b)$ VSTRECHAETSYA 
$m-k$~RAZ, $(b\ c)$ VSTRECHAETSYA $C-A+m-k$~RAZ, $(a\ c)$ VSTRECHAETSYA 
$C-B+m-k$~RAZ I~$(a\ c\ b)$ VSTRECHAETSYA $A+B-C-2m+k$~RAZ. sLEDOVATELXNO, 
$N (A, B, C, m)$
%% 46
\bye