\input style
\chapnotrue\chapno=5\subchno=1\subsubchno=3
sOPOSTAVIM S NEJ DRUGUYU PERESTANOVKU TOGO ZHE MULXTIMNOZHESTVA:
$$
\pmatrix{
1       & \ldots & 1       & 2       & \ldots & 2       & \ldots & m       & \ldots & m \cr
x'_{11} & \ldots & x'_{1p} & x'_{m1} & \ldots & x'_{mp} & \ldots & x'_{21} & \ldots & x'_{2p} \cr
},
\eqno(33)
$$
GDE~$x'=m+1-x$. eSLI PERESTANOVKA~(32) SODERZHIT $k$~STOLBCOV VIDA~$y \atop x$, 
TAKIH, CHTO~$x<y$, TO~(33) SODERZHIT~$(m-1)p-k$ TAKIH
STOLBCOV, POTOMU CHTO NEOBHODIMO RASSMOTRETX LISHX SLUCHAJ~$y>1$, A 
NERAVENSTVO~$x<y$ |KVIVALENTNO~$x' \ge m+2-y$. 
pOSKOLXKU~(32) SOOTVETSTVUET PERESTANOVKE S $k+1$~OTREZKAMI, 
A~(33)---PERESTANOVKE S $mp-p-k+1$~OTREZKAMI I PREOBRAZOVANIE, 
PEREVODYASHCHEE~(32) V~(33), OBRATIMO (ONO ZHE PEREVODIT~(33) V~(32)), TO TEM 
SAMYM DOKAZANO USLOVIE SIMMETRII mAK-mAGONA. pRIMER |TOGO POSTROENIYA 
SODERZHITSYA V UPR.~14.

v SILU SVOJSTVA SIMMETRII SREDNEE CHISLO OTREZKOV V SLUCHAJNOJ 
PERESTANOVKE DOLZHNO 
RAVNYATXSYA~${1\over2}(( k+1)+(mp-p-k+1))=1+{1\over2}p(m-1)$. nAPRIMER, DLYA 
STANDARTNOJ KOLODY SREDNEE
CHISLO STOPOK V PASXYANSE nXYUKOMBA RAVNO~$25$ (TAK CHTO RASKLADYVANIE |TOGO 
PASXYANSA VRYAD LI POKAZHETSYA STOLX UZH UVLEKATELXNYM ZANYATIEM).

nA SAMOM DELE, ISPOLXZUYA VESXMA PROSTOE RASSUZHDENIE, MOZHNO OPREDELITX 
SREDNEE CHISLO OTREZKOV V OBSHCHEM SLUCHAE DLYA \emph{LYUBOGO} DANNOGO 
MULXTIMNOZHESTVA~$\set{n_1\cdot x_1, n_2\cdot x_2,~\ldots, n_m\cdot x_m}$, 
GDE VSE~$x$ RAZLICHNY. pUSTX~$n=n_1+n_2+\cdots+n_m$, I PREDSTAVIM SEBE, 
CHTO VSE PERESTANOVKI~$a_1\,a_2\,\ldots\,a_n$ |TOGO MULXTIMNOZHESTVA 
ZAPISANY V YAVNOM VIDE; POSMOTRIM, KAK CHASTO $a_i$ OKAZYVAETSYA 
BOLXSHE~$a_{i+1}$ PRI KAZHDOM FIKSIROVANNOM ZNACHENII~$i$, $1 \le i < n$. 
chISLO SLUCHAEV, KOGDA~$a_i>a_{i+1}$, RAVNO V TOCHNOSTI POLOVINE CHISLA 
SLUCHAEV, KOGDA~$a_i \ne a_{i+1}$, I NETRUDNO VIDETX, CHTO~$a_i=a_{i+1}=x_j$ 
ROVNO V $N n_j(n_j-1)/n(n-1)$~SLUCHAYAH, GDE~$N$---OBSHCHEE CHISLO PERESTANOVOK. 
sLEDOVATELXNO, $a_i=a_{i+1}$ ROVNO V
$$
{N\over n(n-1)}(n_1(n_1-1)+\cdots+n_m(n_m-1))={N\over n(n-1)}(n_1^2+\cdots+n_m^2-n)
$$
SLUCHAYAH, a~$a_i>a_{i+1}$ ROVNO V
$$
{N\over 2n(n-1)}(n^2-(n_1^2+\cdots+n_m^2))
$$
SLUCHAYAH. sUMMIRUYA PO~$i$ I PRIBAVLYAYA~$N$, POTOMU CHTO V KAZHDOJ PERESTANOVKE 
ODIN OTREZOK KONCHAETSYA |LEMENTOM~$a_n$, POLUCHIM OBSHCHEE CHISLO OTREZKOV VO 
VSEH~$N$ PERESTANOVKAH:
$$
N\left({n\over2}-{1\over 2n}(n_1^2+\cdots+n_m^2)+1\right).
\eqno(34)
$$
pODELIV NA~$N$, POLUCHIM ISKOMOE SREDNEE CHISLO OTREZKOV. 
%%62

tAK KAK OTREZKI VAZHNY PRI IZUCHENII "PORYADKOVYH STATISTIK", IMEETSYA VESXMA 
OBSHIRNAYA LITERATURA, POSVYASHCHENNAYA IM, V TOM CHISLE I NEKOTORYM DRUGIM TIPAM 
OTREZKOV, NE RASSMOTRENNYM ZDESX. dOPOLNITELXNUYU INFORMACIYU MOZHNO NAJTI V 
KNIGE f.~n.~d|VID I~d.~e.~bARTONA Combinatorial Chance (London: Griffin, 1962), 
GL.~10, I V OBZORNOJ STATXE d.~e.~bARTONA I~k.~l.~m|LLOUZA 
[{\sl Annals of Math. Statistics,\/} {\bf 36} (1965), 236--260]. 
dALXNEJSHIE SVYAZI MEZHDU CHISLAMI eJLERA I PERESTANOVKAMI RASSMATRIVAYUTSYA V 
RABOTE d.~fOATY I~m.~p.~shYUCENBERZHE Th\'eorie G\'eom\'etrique des Polyn\^omes 
Eul\'eriens (Lecture Notes in Math., 138 (Berlin: Springer, 1970), 94~STR.).

\excercises
\ex[m26] vYVEDITE FORMULU eJLERA~(13).

\rex[m22] (A)~pOPYTAJTESX DALXSHE RAZVITX IDEYU, ISPOLXZOVANNUYU V TEKSTE PRI 
DOKAZATELXSTVE TOZHDESTVA~(8): RASSMOTRITE POSLEDOVATELXNOSTI~$a_1\,a_2\,
\ldots\,a_n$, SODERZHASHCHIE ROVNO~$q$ RAZLICHNYH |LEMENTOV, I DOKAZHITE, CHTO
$$
\sum_k \eul{n}{k} \perm{k-1}{n-q}=\Stir{n}{q}q!.
$$
(b)~iSPOLXZUYA |TO TOZHDESTVO, DOKAZHITE, CHTO
$$
\sum_k \eul{n}{k}\perm{k}{m}=\Stir{n+1}{n+1-m}(n-m)!
\rem{PRI~$n\ge m$.}
$$

\ex[vm25] vYCHISLITE SUMMU~$\sum_k \eul{n}{k}(-1)^k$.

\ex[m21] chEMU RAVNA SUMMA
$$
\sum_k (-1)^k\Stir{n}{k}k!\perm{n-k}{m}?
$$

\ex[m20] nAJDITE ZNACHENIE~$\eul{p}{k}\bmod p$, ESLI~$p$---PROSTOE CHISLO. 

\rex[m21] mISTER tUPICA ZAMETIL, CHTO IZ FORMUL~(4) I~(13) MOZHNO POLUCHITX
$$
n!=\sum_{k\ge0} \eul{n}{k}=\sum_{k\ge0}\sum_{j\ge0} (-1)^{k-j}\perm{n+1}{k-j}j^n.
$$
pROIZVEDYA SUMMIROVANIE SNACHALA PO~$k$, ZATEM PO~$j$, ON OBNARUZHIL, 
CHTO~$\sum_{k\ge0} (-1)^{k-j}\perm{n+1}{k-j}=0$ PRI VSEH~$j\ge0$, 
OTSYUDA~$n!=0$ PRI LYUBOM~$n\ge0$. nE DOPUSTIL LI ON KAKOJ-NIBUDX OSHIBKI?

\ex[vm40] yaVLYAETSYA LI RASPREDELENIE VEROYATNOSTEJ DLYA OTREZKOV, 
ZADAVAEMOE FORMULOJ~(14), ASIMPTOTICHESKI NORMALXNYM? (sR.~S~UPR.~1.2.10-13.)

\ex[m24] (p.~a.~mAK-mAGON ) pOKAZHITE, CHTO VEROYATNOSTX TOGO, CHTO 
DLINA PERVOGO OTREZKA DOSTATOCHNO DLINNOJ PERESTANOVKI ESTX~$l_1$, DLINA 
VTOROGO 
%%63
ESTX~$l_2$,~\dots, A DLINA $k\hbox{-GO OTREZKA}\ge l_k$, RAVNA
$$
\det\pmatrix{
1/l_1! & 1/(l_1+l_2)! & 1/(l_1+l_2+l_3)! & \ldots & 1/(l_1+l_2+l_3+\cdots+l_k)!\cr
1      & 1/l_2!       & 1/(l_2+l_3)!     & \ldots & 1/(l_2+l_3+\cdots+l_k)! \cr
0      & 1            & 1/l_3!           & \ldots & 1/(l_3+\cdots+l_k)!\cr
\vdots &              &                  &        & \vdots\cr
0      & 0            & \ldots           & 1      & 1/l_k! \cr
}.
$$

\ex[M30] pUSTX~$h_k(z)=\sum p_{km} z^m$, GDE~$p_{km}$---VEROYATNOSTX TOGO, 
CHTO OBSHCHAYA DLINA PERVYH $k$~OTREZKOV (BESKONECHNOJ) SLUCHAJNOJ 
POSLEDOVATELXNOSTI RAVNA~$m$. nAJDITE "PROSTYE" VYRAZHENIYA DLYA~$h_1(z)$, 
$h_2(z)$ I DLYA PROIZVODYASHCHIH FUNKCIJ~$h(z, x)=\sum_k h_k(z) x^k$ OT DVUH PEREMENNYH.

\ex[BM30] oPREDELITE ASIMPTOTICHESKOE POVEDENIE SREDNEGO ZNACHENIYA 
I DISPERSII RASPREDELENIYA~$h_k(z)$ IZ PREDYDUSHCHEGO UPRAZHNENIYA PRI BOLXSHIH~$k$.

\ex[m40] pUSTX~$H_k(z)=\sum p_{km} z^m$,  GDE~$p_{km}$---VEROYATNOSTX TOGO, 
CHTO DLINA $k\hbox{-GO}$~OTREZKA V SLUCHAJNOJ (BESKONECHNOJ) 
POSLEDOVATELXNOSTI RAVNA~$m$. vYRAZITE~$H_1(z)$, $H_2(z)$ I PROIZVODYASHCHUYU 
FUNKCIYU~$H(z, x)=\sum_k H_k(z) x^k$ OT DVUH PEREMENNYH CHEREZ IZVESTNYE FUNKCII.

\ex[M33] (p.a.~mAK-mAGON.) oBOBSHCHITE FORMULU~(13) NA SLUCHAJ PERESTANOVOK 
MULXTIMNOZHESTVA, DOKAZAV, CHTO CHISLO PERESTANOVOK 
MULXTIMNOZHESTVA~$\set{n_1\cdot 1, n_2\cdot 2,~\ldots, n_m\cdot m}$, 
IMEYUSHCHIH ROVNO $k$~OTREZKOV, RAVNO
$$
\sum_{0\le j \le k} (-1)^i \perm{n+1}{j} \perm{n_1-1+k-j}{n_1} 
\perm{n_2-1+k-j}{n_2} \cdots \perm{n_m-1+k-j}{n_m},
$$
GDE~$n=n_1+n_2+\cdots+n_m$.

\ex[05] kAKIM BUDET SREDNEE CHISLO STOPOK V PASXYANSE nXYUKOMBA, 
ESLI POLXZOVATXSYA OBYCHNOJ KOLODOJ DLYA BRIDZHA (IZ 52~KART), IGNORIRUYA 
STARSHINSTVO KART, NO SCHITAYA, CHTO
$$
\clubsuit < \diamondsuit < \heartsuit < \spadesuit?
$$

\ex[M17]  pERESTANOVKA~$3\,1\,1\,1\,2\,3\,1\,4\,2\,3\,3\,4\,2\,2\,4\,4$ 
SODERZHIT $5$~OTREZKOV; NAJDITE S POMOSHCHXYU PRIVEDENNOGO V TEKSTE POSTROENIYA 
DLYA USLOVIYA SIMMETRII mAK-mAGONA SOOTVETSTVUYUSHCHUYU PERESTANOVKU S $9\hbox{-YU}$~OTREZKAMI.

\rex[m21] \exhead(pEREMEZHAYUSHCHIESYA OTREZKI.) v KLASSICHESKOJ LITERATURE 
$19\hbox{-GO}$~VEKA PO KOMBINATORNOMU ANALIZU NE IZUCHALSYA VOPROS OB 
OTREZKAH V PERESTANOVKAH, KOTORYE RASSMATRIVAEM MY, NO BYLO NESKOLXKO 
STATEJ, POSVYASHCHENNYH POPEREMENNO VOZRASTAYUSHCHIM I UBYVAYUSHCHIM "OTREZKAM". tAK, 
SCHITALOSX, CHTO PERESTANOVKA~$5\,3\,2\,4\,7\,6\,1\,8$ SODERZHIT $4$~OTREZKA
$$
5\,3\, 2, \quad     2\,4\,7,\quad    7\,6\,1,\quad    1\,8.
$$
(pERVYJ OTREZOK BUDET VOZRASTAYUSHCHIM ILI UBYVAYUSHCHIM V ZAVISIMOSTI OT TOGO,
$a_1<a_2$ ILI~$a_1>a_2$; TAKIM OBRAZOM, PERESTANOVKI~$a_1\,a_2\ldots\, a_n$, 
$a_n\,\ldots\,a_2\,a_1$ I~$(n+1-a_1)\,(n+1-a_2)\ldots (n+1-a_n)$ VSE 
SODERZHAT ODINAKOVOE CHISLO PEREMEZHAYUSHCHIHSYA OTREZKOV.) mAKSIMALXNOE CHISLO 
OTREZKOV |TOGO TIPA V PERESTANOVKE $n$~|LEMENTOV RAVNO~$n-1$.

nAJDITE SREDNEE CHISLO PEREMEZHAYUSHCHIHSYA OTREZKOV V SLUCHAJNOJ 
PERESTANOVKE MNOZHESTVA~$\set{1, 2,~\ldots, n}$. 
[\emph{uKAZANIE:} RAZBERITE VYVOD FORMULY~(34).]

\ex[M30] pRODOLZHIM PREDYDUSHCHEE UPRAZHNENIE. pUSTX~$\Eul{n}{k}$---CHISLO PERESTANOVOK
%%64
MNOZHESTVA~$\set{1, 2,~\ldots, n}$, KOTORYE IMEYUT ROVNO 
$k$~PEREMEZHAYUSHCHIHSYA OTREZKOV. nAJDITE REKURRENTNOE SOOTNOSHENIE, S POMOSHCHXYU 
KOTOROGO MOZHNO
VYCHISLITX TABLICU ZNACHENIJ~$\Eul{n}{k}$; NAJDITE TAKZHE SOOTVETSTVUYUSHCHEE 
REKURRENTNOE SOOTNOSHENIE DLYA PROIZVODYASHCHEJ 
FUNKCII~$G_n(z)=\sum_k \Eul{n}{k} z^k \big / n!$. iSPOLXZUYA |TO POSLEDNEE 
REKURRENTNOE SOOTNOSHENIE, NAJDITE PROSTUYU FORMULU DLYA \emph{DISPERSII} CHISLA 
PEREMEZHAYUSHCHIHSYA OTREZKOV V SLUCHAJNOJ PERESTANOVKE MNOZHESTVA~$\set{1,2,
~\ldots, n}$.

\ex[M25] sUSHCHESTVUET VSEGO~$2^n$ POSLEDOVATELXNOSTEJ $a_1\,a_2\,a_n$, GDE 
KAZHDYJ |LEMENT~$a_j$---LIBO~$0$, LIBO~$1$. sKOLXKO SREDI NIH 
POSLEDOVATELXNOSTEJ, SODERZHASHCHIH ROVNO $k$~OTREZKOV (T.~E.~SODERZHASHCHIH 
ROVNO~$k-1$  |LEMENTOV~$a_j$, TAKIH, CHTO~$a_j>a_{j+1}$)?

\ex[M27] sUSHCHESTVUET VSEGO~$n!$ POSLEDOVATELXNOSTEJ~$a_1\,a_2\,\ldots\,a_n$,
GDE KAZHDYJ |LEMENT~$a_j$---CELOE CHISLO, LEZHASHCHEE V 
DIAPAZONE~$0 \le a_j \le n-j$; SKOLXKO SREDI NIH POSLEDOVATELXNOSTEJ, 
SODERZHASHCHIH ROVNO 
$k$~OTREZKOV (T.~E.~SODERZHASHCHIH ROVNO~$k-1$ |LEMENTOV~$a_j$, TAKIH, CHTO~$a_j>a_{j+1}$)?

\rex[M26] (dZH.~rIORDAN.) (A)~sKOLXKIMI SPOSOBAMI MOZHNO RASPOLOZHITX 
$n$~NEATAKUYUSHCHIH LADEJ (T.~E.~NIKAKIE DVE NE DOLZHNY NAHODITXSYA NA ODNOJ VERTIKALI
\picture{
 rIS.~4. nEATAKUYUSHCHIE LADXI NA SHAHMATNOJ DOSKE PRI ZADANNOM CHISLE 
 LADEJ NIZHE GLAVNOJ DIAGONALI.
}
ILI GORIZONTALI) NA SHAHMATNOJ DOSKE RAZMERA~$n\times n$ TAK, CHTOBY 
ROVNO~$k$ IZ NIH NAHODILISX NA ZADANNOJ STORONE OT GLAVNOJ DIAGONALI? 
(b)~sKOLXKIMI SPOSOBAMI MOZHNO RASPOLOZHITX $k$~NEATAKUYUSHCHIH LADEJ NA 
ZADANNOJ STORONE OT GLAVNOJ DIAGONALI SHAHMATNOJ DOSKI RAZMERA~$n\times n$?

nAPRIMER, NA RIS.~4 POKAZAN ODIN IZ $15619$~SPOSOBOV RASPOLOZHITX 
VOSEMX NEATAKUYUSHCHIH LADEJ NA OBYCHNOJ SHAHMATNOJ DOSKE S TREMYA LADXYAMI NA 
NEZASHTRIHOVANNOM UCHASTKE NIZHE GLAVNOJ DIAGONALI, A TAKZHE ODIN IZ 
$1050$~SPOSOBOV RASPOLOZHITX TRI NEATAKUYUSHCHIE LADXI NA TREUGOLXNOJ DOSKE.

\rex[m21] gOVORYAT, CHTO PERESTANOVKA TREBUET $k$~\emph{CHTENIJ,} ESLI EE 
NUZHNO PROSMOTRETX $k$~RAZ, SLEVA NAPRAVO, CHTOBY PROCHITATX VSE |LEMENTY V 
NEUBYVAYUSHCHEM PORYADKE. nAPRIMER, PERESTANOVKA
$$
4\,9\,1\,8\,2\,5\,3\,6\,7
$$
%%65
TREBUET CHETYREH CHTENIJ: PRI PERVOM CHTENII POLUCHAEM~$1,2,3$; PRI 
VTOROM---$4, 5, 6, 7$; ZATEM~$8$; ZATEM~$9$. nAJDITE SVYAZX MEZHDU OTREZKAMI 
I CHTENIYAMI.

\ex[M22] eSLI PERESTANOVKA~$a_1\,a_2\,\ldots\,a_n$ 
MNOZHESTVA~$\set{1, 2, ~\ldots, n}$ SODERZHIT $k$~OTREZKOV I TREBUET $j$~CHTENIJ 
V SMYSLE UPR.~20, TO CHTO MOZHNO SKAZATX O PERESTANOVKE~$a_n\,\ldots\,a_2\,a_1$?

\ex[M26] (l.~kARLIC, d.~p.~rOZELX I~r.~a.~sKOUVILL.) pOKAZHITE, CHTO NE 
SUSHCHESTVUET PERESTANOVKI MNOZHESTVA~$\set{1, 2,~\ldots, n}$ S 
$n+1-r$~OTREZKAMI, TREBUYUSHCHEJ $s$~CHTENIJ, ESLI~$rs<n$, ODNAKO TAKAYA 
PERESTANOVKA SUSHCHESTVUET, ESLI~$n\ge n+1-r\ge s \ge 1$, $rs\ge n$.

\ex[BM42] (vALXTER vEJSSBLYUM.) "uDLINENNYE OTREZKI" 
PERESTANOVKI~$a_1\,a_2\,\ldots\,a_n$ POLUCHAYUTSYA, ESLI VSTAVLYATX VERTIKALXNYE 
CHERTOCHKI V TEH MESTAH, GDE NARUSHAETSYA USTANOVIVSHAYASYA MONOTONNOSTX; UDLINENNYE 
OTREZKI BYVAYUT KAK VOZRASTAYUSHCHIMI, TAK I UBYVAYUSHCHIMI V ZAVISIMOSTI OT TOGO, V 
KAKOM PORYADKE RASPOLOZHENY PERVYE DVA |LEMENTA, TAK CHTO DLINA KAZHDOGO UDLINENNOGO 
OTREZKA (KROME, VOZMOZHNO, POSLEDNEGO)${}\ge2$. nAPRIMER, 
PERESTANOVKA~$7\,5\vert6\,2\vert3\,8\,9\vert1\,4$ SODERZHIT CHETYRE UDLINENNYH 
OTREZKA. nAJDITE SREDNIE DLINY PERVYH DVUH UDLINENNYH OTREZKOV BESKONECHNOJ 
PERESTANOVKI I DOKAZHITE, CHTO V PREDELE DLINA UDLINENNOGO OTREZKA RAVNA
$$
\left(1+\ctg{1\over2}\right)\Big/\left(3-\ctg{1\over2}\right)\approx 2.4202.
$$

\ex[M30] vYRAZITE V VIDE FUNKCII OT~$p$ SREDNEE CHISLO OTREZKOV V 
POSLEDOVATELXNOSTYAH, POLUCHENNYH METODOM, KOTORYJ OPISAN V UPR.~5.1.1-18.

\subsubchap{*tABLO I INVOLYUCII} %5.1.4.
v ZAKLYUCHENIE NASHEGO OBZORA KOMBINATORNYH SVOJSTV PERESTANOVOK OBSUDIM 
NEKOTORYE ZAMECHATELXNYE OTNOSHENIYA, SVYAZYVAYUSHCHIE PERESTANOVKI S MASSIVAMI 
CELYH CHISEL, NAZYVAEMYMI TABLO. \dfn{tABLO yaNGA FORMY~$(n_1, n_2,~\ldots, n_m)$,}  
GDE~$n_1\ge n_2 \ge \ldots \ge n_m \ge 0$, |TO RASPOLOZHENIE 
$n_1+n_2+\cdots+n_m$~RAZLICHNYH CELYH CHISEL V MASSIV STROK, VYROVNENNYH 
PO LEVOMU KRAYU, GDE V $i\hbox{-J}$~STROKE SODERZHITSYA $n_i$~|LEMENTOV; 
PRI |TOM V KAZHDOJ STROKE |LEMENTY VOZRASTAYUT SLEVA NAPRAVO, A |LEMENTY 
KAZHDOGO STOLBCA VOZRASTAYUT SVERHU VNIZ. nAPRIMER,
$$
\tableau{
1 & 2 & 5 & 9 & 10 & 15 \cr
3 & 6 & 7 & 13 \cr
4 & 8 & 12 & 14 \cr
11 \cr
}
\eqno(1)
$$
---TABLO yaNGA FORMY~$(6, 4, 4, 1)$. tAKIE RASPOLOZHENIYA VVEL aLXFRED yaNG 
V~1900~G. V KACHESTVE VSPOMOGATELXNOGO SREDSTVA PRI IZUCHENII MATRICHNOGO 
PREDSTAVLENIYA PERESTANOVOK. 
[sM., NAPRIMER, D.~e.~Rutherford, Substitutional Analysis (New York: Hafiier,
%%66
1968)]. dLYA KRATKOSTI MY BUDEM VMESTO "TABLO yaNGA" GOVORITX PROSTO "TABLO".

\dfn{iNVOLYUCIYA}---|TO PERESTANOVKA, OBRATNAYA SAMOJ SEBE. nAPRIMER, 
SUSHCHESTVUET 10 INVOLYUCIJ MNOZHESTVA~$\set{1, 2, 3, 4}$:
$$
\displaynarrow{
\pmatrix{
1 & 2 & 3 & 4 \cr
1 & 2 & 3 & 4 \cr
}
\pmatrix{
1 & 2 & 3 & 4 \cr
2 & 1 & 3 & 4 \cr
}
\pmatrix{
1 & 2 & 3 & 4 \cr
3 & 2 & 1 & 4 \cr
}
\pmatrix{
1 & 2 & 3 & 4 \cr
4 & 2 & 3 & 1 \cr
}
\pmatrix{
1 & 2 & 3 & 4 \cr
1 & 3 & 2 & 4 \cr
}
\cr
\pmatrix{
1 & 2 & 3 & 4 \cr
1 & 4 & 3 &  2\cr
}
\pmatrix{
1 & 2 & 3 & 4 \cr
1 & 2 & 4 & 3 \cr
}
\pmatrix{
1 & 2 & 3 & 4 \cr
2 & 1 & 4 & 3 \cr
}
\pmatrix{
1 & 2 & 3 & 4 \cr
3 & 4 & 1 & 2 \cr
}
\pmatrix{
1 & 2 & 3 & 4 \cr
4 & 3 & 2 & 1 \cr
}
}
\eqno(2)
$$
tERMIN "INVOLYUCIYA" PERVONACHALXNO ISPOLXZOVALSYA V KLASSICHESKIH ZADACHAH 
GEOMETRII; INVOLYUCII V OBSHCHEM SMYSLE, RASSMATRIVAEMYE ZDESX, BYLI VPERVYE 
IZUCHENY X.~a.~rOTE, KOGDA ON VVEL PONYATIE OBRATNOJ PERESTANOVKI (SM.~P.~5.1.1).

mOZHET POKAZATXSYA STRANNYM, CHTO MY RASSMATRIVAEM TABLO I INVOLYUCII VMESTE, 
NO SUSHCHESTVUET UDIVITELXNAYA SVYAZX MEZHDU |TIMI PONYATIYAMI, NE IMEYUSHCHIMI, 
KAZALOSX BY, DRUG K DRUGU NIKAKOGO OTNOSHENIYA: \dfn{CHISLO INVOLYUCIJ 
MNOZHESTVA~$\set{1, 2,~\ldots, n}$ RAVNO CHISLU TABLO, KOTORYE MOZHNO 
SFORMIROVATX IZ |LEMENTOV~$\set{1,2,~\ldots, n}$.} nAPRIMER, 
IZ~$\set{1, 2, 3, 4}$ MOZHNO SFORMIROVATX ROVNO 10~TABLO
$$
\displaynarrow{
\tableau{1& 2 & 3 & 4 \cr}\quad
\tableau{
1 & 3 & 4 \cr
2 \cr
}\quad
\tableau{
1 & 4 \cr
2 \cr
3 \cr
}\quad
\tableau{
1 & 3 \cr
2 \cr
4 \cr
}\quad
\tableau{
1 & 2 & 4 \cr
3 \cr
}\quad
\cr
\tableau{ 
1 & 2 \cr
3 \cr
4 \cr
 }\quad
\tableau{
1 & 2 & 3 \cr
4 \cr
}\quad
\tableau{
1 & 3 \cr
2  & 4 \cr
}\quad
\tableau{
1 & 2 \cr
3 & 4 \cr
}\quad
\tableau{
1 \cr
2 \cr
3 \cr
4 \cr
}\quad
\cr
}
\eqno (3)
$$
CHTO SOOTVETSTVUET 10~INVOLYUCIYAM~(2).

eTA SVYAZX MEZHDU INVOLYUCIYAMI I TABLO OTNYUDX NE OCHEVIDNA, I, PO-VIDIMOMU, NE 
SUSHCHESTVUET PROSTOGO SPOSOBA EE DOKAZATX. dOKAZATELXSTVO, KOTOROE MY 
OBSUDIM, VKLYUCHAET INTERESNYJ ALGORITM POSTROENIYA TABLO, OBLADAYUSHCHIJ I 
NEKOTORYMI DRUGIMI NEOZHIDANNYMI SVOJSTVAMI; ON OSNOVAN NA OSOBOJ 
PROCEDURE VSTAVKI V TABLO NOVYH |LEMENTOV.

%% 67

pREDPOLOZHIM, NAPRIMER, CHTO NUZHNO VSTAVITX |LEMENT~8 V TABLO
$$
\tableau{
1 & 3 & 5 & 9 & 12 & 16 \cr
2 & 6 & 10 & 15 \cr
4 & 13 & 14 \cr
11 \cr
17 \cr
}
\eqno (4)
$$
mETOD, KOTORYM MY BUDEM POLXZOVATXSYA, SOSTOIT V TOM, CHTOBY SNACHALA 
POMESTITX~8 V $1\hbox{-YU}$~STROKU, V KLETKU, RANEE ZANIMAEMUYU~$9$,
POSKOLXKU~$9$---NAIMENXSHIJ IZ |LEMENTOV |TOJ STROKI, 
BOLXSHIH~$8$. eLEMENT~$9$ "VYTESNYAETSYA" VNIZ, V STROKU~$2$, GDE ON 
ZAMESHCHAET~$10$. zATEM~$10$ "VYTESNYAET"~$13$ IZ $3\hbox{-J}$~STROKI V 
$4\hbox{-YU}$ I, POSKOLXKU V $4\hbox{-J}$~STROKE NET |LEMENTA BOLXSHE~$13$, 
PROCESS ZAVERSHAETSYA DOBAVLENIEM~$13$ V PRAVYJ KONEC STROKI~$4$. nASHE TABLO 
PREOBRAZOVALOSX V
$$
\tableau{
1 & 3 & 5 & 8 & 12 & 16 \cr
2 & 6 & 9 & 15 \cr
4 & 10 & 14 \cr
11 & 13 \cr
17 \cr
}
\eqno (5)
$$

tOCHNOE OPISANIE |TOGO PROCESSA S DOKAZATELXSTVOM TOGO, CHTO ON VSEGDA 
SOHRANYAET SVOJSTVA TABLO, SODERZHITSYA V ALGORITME~I.

\alg I.(vSTAVKA V TABLO.) pUSTX~$P=(P_{ij})$---TABLO CELYH POLOZHITELXNYH 
CHISEL, A~$x$---CELOE POLOZHITELXNOE CHISLO, NE SODERZHASHCHEESYA V~$P$. eTOT 
ALGORITM PREOBRAZUET~$P$ V DRUGOE TABLO, SODERZHASHCHEE~$x$ NARYADU S ISHODNYMI 
|LEMENTAMI~$P$. nOVOE TABLO IMEET TU ZHE FORMU, CHTO I STAROE, S TOJ LISHX 
RAZNICEJ, CHTO NA PERESECHENII STROKI~$s$ I STOLBCA~$t$ POYAVILSYA NOVYJ 
|LEMENT, GDE~$s$ I~$t$---VELICHINY, OPREDELYAEMYE ALGORITMOM.

(v |TOM ALGORITME ZAMECHANIYA V KRUGLYH SKOBKAH PREDNAZNACHENY DLYA 
DOKAZATELXSTVA EGO PRAVILXNOSTI, POSKOLXKU PO INDUKCII LEGKO PROVERITX, 
CHTO |TI ZAMECHANIYA SPRAVEDLIVY I CHTO MASSIV~$P$ PRODOLZHAET OSTAVATXSYA 
TABLO NA PROTYAZHENII VSEGO PROCESSA. dLYA UDOBSTVA BUDEM PREDPOLAGATX, CHTO 
TABLO OGRANICHENO
%% 68
NULYAMI SVERHU I SLEVA I SIMVOLAMI~$\infty$ SPRAVA I SNIZU, TAK 
CHTO |LEMENT~$P_{ij}$ OPREDELEN PRI VSEH~$i$,~$j\ge 0$. eSLI VVESTI OTNOSHENIE
$$
a \simlt b \rem{TOGDA I TOLXKO TOGDA, KOGDA~$a<b$ ILI~$a=b=\infty$,}
\eqno (6)
$$
TO NERAVENSTVA DLYA TABLO MOZHNO VYRAZITX V UDOBNOJ FORME:
$$
\displaynarrow{
P_{ij}=0, \rem{ESLI~$i=0$ ILI~$j=0$;}\cr
P_{ij}\simlt P_{i(j+1)} \rand P_{ij} \simlt P_{(i+1)j} 
\rem{PRI VSEH~$i, j\ge 0$.}\cr
}
\eqno(7)
$$
uTVERZHDENIE "$x\notin P$" OZNACHAET, CHTO LIBO~$x=\infty$, LIBO~$x$ NE 
RAVNO~$P_{ij}$ NI PRI KAKIH~$i, j\ge 0$.)

\st[vVESTI~$x$.] uSTANOVITX~$i\asg 1$, $x_1\asg x$, A $j$~USTANOVITX 
RAVNYM NAIMENXSHEMU ZNACHENIYU, TAKOMU, CHTO~$P_{1j}=\infty$.

\st[nAJTI~$x_{i+1}$.] (v |TOT MOMENT~$P_{(i-1)j} < x_i < P_{ij}$ 
I~$x_i\notin P$.) eSLI ~$x_i<P_{i(j-1)}$, TO UMENXSHITX~$j$ NA~$1$ I 
POVTORITX |TOT SHAG. v PROTIVNOM SLUCHAE USTANOVITX~$x_{i+1}\asg P_{ij}$  
I~$r_i\asg j$.

\st[zAMENITX NA~$x_i$.] (tEPERX~$P_{i(j-1)}< x_i < x_{i+1}=P_{ij}\simlt P_{i(j+1)}$, 
$P_{(i-1) j} < x_i < x_{i+1} = P_{ij} \simlt P_{(i+1)j}$ 
I~$r_i=j$.) uSTANOVITX~$P_{ij}\asg x_i$.

\st[$x_{i+1}=\infty$?] 
(tEPERX~$P_{i(j-1)}<P_{ij}=x_i < x_{i+1} \simlt P_{i(j-1)}$, 
$P_{(i-1)j}<P_{ij}=x_i<x_{i+1}\simlt P_{(i+1)j}$, $r_i=j$ 
I~$x_{i+1}\notin P$.) eSLI~$x_{i+1}\ne \infty$, TO UVELICHITX~$i$ NA~$1$ I 
VERNUTXSYA K SHAGU~\stp{2}.

\st[oPREDELITX~$s$, $t$.] uSTANOVITX~$s\asg i$, $t\asg j$ I ZAKONCHITX 
RABOTU ALGORITMA. (k |TOMU MOMENTU VYPOLNYAYUTSYA USLOVIYA
$$
P_{st}\ne\infty, P_{(s+1)t}=P_{s(t+1)}=\infty.)
\eqno(8)
$$
\algend

zAMETIM, CHTO |TOT ALGORITM OPREDELYAET "POSLEDOVATELXNOSTX VYTESNENII"
$$
x=x_1<x_2<\ldots<x_s<x_{s+1}=\infty,
\eqno(9)
$$
A TAKZHE VSPOMOGATELXNUYU POSLEDOVATELXNOSTX INDEKSOV STOLBCOV
$$
r_1\ge r_2 \ge \ldots \ge r_s = t;
\eqno(10)
$$
PRI |TOM |LEMENT~$P_{ir_i}$ MENYAET SVOE ZNACHENIE S~$x_{i+1}$ NA~$x_i$, 
$1\le i \le s$. nAPRIMER, KOGDA V TABLO~(4) VSTAVLYALSYA |LEMENT~$8$, 
POSLEDOVATELXNOSTXYU VYTESNENIJ BYLA~$8$, $9$, $10$, $13$, $\infty$, A 
VSPOMOGATELXNOJ POSLEDOVATELXNOSTXYU---$4$, $3$, $2$, $2$. mY MOGLI BY 
PEREFORMULIROVATX ALGORITM TAK, CHTOBY ON RASHODOVAL MENXSHE 
VREMENNOJ PAMYATI (NEOBHODIMO HRANITX TOLXKO TEKUSHCHIE ZNACHENIYA~$j$, $x_i$, $x_{i+1}$);
POSLEDOVATELXNOSTI~(9) I~(10) BYLI VVEDENY S TOJ LISHX CELXYU, CHTOBY MOZHNO 
BYLO DOKAZATX NEKOTORYE INTERESNYE FAKTY, KASAYUSHCHIESYA |TOGO ALGORITMA.

oSNOVNOE SVOJSTVO ALGORITMA~I, KOTORYM MY NE PREMINEM VOSPOLXZOVATXSYA, 
SOSTOIT V TOM, CHTO ALGORITM MOZHNO "PROKRUTITX" V OBRATNOM NAPRAVLENII: 
PO ZADANNYM~$s$ I~$t$, OPREDELENNYM
%% 69
V SHAGE~I5, MOZHNO PREOBRAZOVATX~$P$ K ISHODNOMU VIDU, NAJDYA I UDALIV 
|LEMENT~$x$, KOTORYJ BYL VSTAVLEN. rASSMOTRIM, NAPRIMER, (5), I PUSTX 
NAM IZVESTNO, CHTO |LEMENT~$13$ ZANIMAET POZICIYU, KOTORAYA RANXSHE BYLA 
PUSTA. tOGDA |LEMENT~$13$, DOLZHNO BYTX, BYL VYTESNEN VNIZ IZ 3-J STROKI 
CHISLOM~$10$, POTOMU CHTO $10$---NAIBOLXSHIJ |LEMENT V |TOJ STROKE, 
MENXSHIJ~$13$; ANALOGICHNO, |LEMENT~$10$, PO-VIDIMOMU, BYL VYTESNEN IZ 2-J 
STROKI CHISLOM~$9$, KOTOROE V SVOYU OCHEREDX BYLO VYTESNENO IZ 1-J STROKI 
CHISLOM~$8$. tAKIM OBRAZOM, OT~(5) MOZHNO VERNUTXSYA OBRATNO K~(4). v 
SLEDUYUSHCHEM ALGORITME PODROBNO OPISAN |TOT PROCESS.

\alg D.(uDALENIE IZ TABLO.) pO ZADANNOMU TABLO~$P$ I CELYM POLOZHITELXNYM 
CHISLAM~$s$ I~$t$, UDOVLETVORYAYUSHCHIM USLOVIYAM~(8), |TOT ALGORITM 
PREOBRAZUET~$P$ V DRUGOE TABLO POCHTI TAKOJ ZHE FORMY, NO S~$\infty$ NA 
PERESECHENII STOLBCA~$t$ I STROKI~$s$. oPREDELENNYJ ALGORITMOM 
|LEMENT~$x$ UDALYAETSYA IZ TABLO~$P$.

(kAK I V ALGORITME~I, POYASNENIYA V KRUGLYH SKOBKAH VKLYUCHENY DLYA 
OBLEGCHENIYA DOKAZATELXSTVA TOGO, CHTO MASSIV~$P$ PRODOLZHAET OSTAVATXSYA 
TABLO NA PROTYAZHENII VSEGO PROCESSA.)

\st[vVESTI~$s$, $t$.] uSTANOVITX~$j\asg t$, $i\asg s$, $x_{s+1}\asg\infty$. 

\st[nAJTI~$x_i$.] (v |TOT MOMENT~$P_{ij}<x_{i+1}\simlt P_{(i+1)j}$ 
I~$x_{i+1}\notin P$.) eSLI~$P_{i(j+1)}<x_{i+1}$, TO UVELICHITX~$j$ NA~$1$ I 
POVTORITX |TOT SHAG. v PROTIVNOM SLUCHAE USTANOVITX~$x_i\asg P_{ij}$ 
I~$r_i\asg j$.

\st[zAMENITX NA~$x_{i+1}$.] (tEPERX~$P_{i(j-1)}<P_{ij}=x_i<x_{i+1}\simlt P_{i(j+1)}$,
$P_{(i-1)j}<P_{ij}=x_i<x_{i+1}\simlt P_{(i+1)j}$ I~$r_i=j$.)   
uSTANOVITX~$P_{ij}\asg x_{i+1}$.

\st[$i=1$?] (tEPERX~$P_{i(j-1)}<x_i<x_{i+1}=P_{ij}\simlt P_{i(j+1)}$,  
$P_{(i-1)j}<x_i<x_{i+1}=P_{ij}\simlt P_{(i+1)j}$ I~$r_i=j$.) eSLI~$i>1$, 
TO UMENXSHITX~$t$ NA~$1$ I VERNUTXSYA K SHAGU~\stp{2}.

\st[oPREDELITX~$x$.] uSTANOVITX~$x\asg x_1$ I ZAKONCHITX RABOTU ALGORITMA.
 (tEPERX~$0 < x < \infty$.)
\algend

pOYASNENIYA K ALGORITMAM~I I~D, ZAKLYUCHENNYE V KRUGLYE SKOBKI, NE TOLXKO 
POLEZNY DLYA DOKAZATELXSTVA TOGO FAKTA, CHTO |TI ALGORITMY SOHRANYAYUT 
STRUKTURU TABLO, NO ONI POZVOLYAYUT UBEDITXSYA, CHTO 
\emph{ALGORITMY~I I~D VZAIMNO OBRATNY.} eSLI SNACHALA VYPOLNITX ALGORITM~I 
S DANNYM TABLO~$P$ I 
NEKOTORYM CELYM POLOZHITELXNYM CHISLOM~$x\notin P$, TO ON VSTAVIT~$x$ V~$P$ 
I OPREDELIT CELYE POLOZHITELXNYE CHISLA~$s$, $t$, UDOVLETVORYAYUSHCHIE 
USLOVIYAM~(8). aLGORITM~D, PRIMENENNYJ K POLUCHENNOMU REZULXTATU, 
VOSSTANOVIT ZNACHENIYA~$x$ I PERVONACHALXNYJ VID~$P$. oBRATNO, ESLI 
SNACHALA VYPOLNITX ALGORITM~D S DANNYM TABLO~$P$ I NEKOTORYMI CELYMI 
POLOZHITELXNYMI CHISLAMI~$s$, $t$, UDOVLETVORYAYUSHCHIMI USLOVIYAM~(8), TO ON 
MODIFICIRUET~$P$, UDALIV NEKOTOROE CELOE POLOZHITELXNOE CHISLO~$x$. 
aLGORITM~I, PRIMENENNYJ K POLUCHENNOMU REZULXTATU, VOSSTANOVIT ZNACHENIYA~$s$,
 $t$ I PERVONACHALXNYJ VID~$P$.
%% 70
pRICHINA ZAKLYUCHAETSYA V TOM, CHTO SODERZHANIE POYASNENIJ K SHAGAM~I3 I~D4 
SOVPADAET TAK ZHE, KAK I K SHAGAM~I4 I~D3; ONI ODNOZNACHNO OPREDELYAYUT 
ZNACHENIE~$j$. sLEDOVATELXNO, VSPOMOGATELXNYE POSLEDOVATELXNOSTI~(9), 
(10) ODINAKOVY, V OBOIH SLUCHAYAH.

tEPERX MY PODGOTOVLENY K DOKAZATELXSTVU OSNOVNOGO SVOJSTVA TABLO.

\proclaim tEOREMA~A. sUSHCHESTVUET VZAIMNO ODNOZNACHNOE SOOTVETSTVIE MEZHDU 
MNOZHESTVOM VSEH PERESTANOVOK MNOZHESTVA~$\set{1, 2,~\ldots, n}$ I 
MNOZHESTVOM VSEH UPORYADOCHENNYH PAR TABLO~$(P, Q)$, GDE~$P$ 
I~$Q$---TABLO ODINAKOVOJ FORMY IZ |LEMENTOV~$\set{1, 2,~\ldots, n}$.

(pRIMER K |TOJ TEOREME SODERZHITSYA V PRIVEDENNOM NIZHE DOKAZATELXSTVE.)

\proof uDOBNEE DOKAZATX NESKOLXKO BOLEE OBSHCHIJ REZULXTAT. pO 
PROIZVOLXNOMU DVUSTROCHNOMU MASSIVU
$$
\pmatrix{
q_1 & q_2 & \ldots & q_n \cr
p_1 & p_2 & \ldots & p_n \cr
},\qquad
\matrix{q_1 < q_2 < \ldots < q_n,\hfill\cr
p_1, p_2, \ldots, p_n \hbox{ VSE RAZNYE},\hfill\cr
}
\eqno (11)
$$
POSTROIM SOOTVETSTVUYUSHCHIE DVA TABLO~$P$ I~$Q$, GDE $P$~SOSTOIT 
IZ |LEMENTOV~$\set{p_1, p_2,~\ldots, p_n}$, A~$Q$---IZ 
|LEMENTOV~$\set{q_1, q_2,~\ldots, q_n}$, PRICHEM~$P$ I~$Q$ IMEYUT ODINAKOVUYU FORMU.

pUSTX~$P$ I~$Q$ VNACHALE PUSTY. pRI~$i=1$, $2$,~\dots, $n$ (IMENNO V TAKOM 
PORYADKE) PRODELAEM SLEDUYUSHCHUYU OPERACIYU: VSTAVIM~$P_i$ V TABLO~$P$ PRI 
POMOSHCHI ALGORITMA~I; ZATEM USTANOVIM~$Q_{st}\asg q_l$, GDE~$s$ I~$t$ 
OPREDELYAYUT VNOVX ZAPOLNENNUYU POZICIYU V~$P$.

nAPRIMER, ESLI ZADANA PERESTANOVKA~$
\pmatrix{
1 & 3 & 5 & 6 & 8 \cr
7 & 2 & 9 & 5 & 3 \cr
}$, DEJSTVUEM SLEDUYUSHCHIM OBRAZOM:

{\tdim=\hsize \advance\tdim by -\parindent \divide\tdim by 3
\def\+#1\cr{\line{\indent\vbox{\halign{\hbox to \tdim{##\hfil}&\hbox to \tdim{##\hfil}&\hbox to \tdim{##\hfil}\cr#1\cr}}\hfill}\smallskip}
\vskip\abovedisplayskip
\+ &  $P$ \hfil & $Q$ \hfil \cr
\+ vSTAVKA~7: &
\tableau{
 7 \cr
} & 
\tableau{
1 \cr
}\cr
\+ vSTAVKA~2: &
\tableau{
2 \cr
7 \cr
} &
\tableau {
1 \cr
3 \cr
}
\cr
\+ vSTAVKA~9: &
\tableau{
2 & 9 \cr
7 \cr
} &
\tableau{
1 & 5 \cr
3 \cr
}
\cr
%% 71
\+ vSTAVKA~5: &
\tableau{
2 & 5 \cr
7 & 9 \cr
} &
\tableau{
1 & 5 \cr
3 & 6 \cr
} \cr
\rightline{(12)}
\+ vSTAVKA~3: &
\tableau{
2& 3 \cr
5 & 9 \cr
7\cr
} &
\tableau{
1 & 5 \cr
3 & 6 \cr
8 \cr
} \cr
\vskip\belowdisplayskip
}

sLEDOVATELXNO, PARA TABLO~$(P, Q)$, SOOTVETSTVUYUSHCHAYA PERESTANOVKE
$\pmatrix{
1 & 3 & 5 & 6 & 8 \cr
7 & 2 & 9 & 5 & 3 \cr
}$, TAKOVA:
$$
P=\tableau{
2 & 3 \cr
5 & 9 \cr
7 \cr
}\,, \qquad
Q=\tableau{
1 & 5 \cr
3 & 6 \cr
8 \cr
}\,.
\eqno(13)
$$

iZ POSTROENIYA YASNO, CHTO~$P$ I~$Q$ VSEGDA IMEYUT ODINAKOVUYU FORMU. kROME 
TOGO, POSKOLXKU |LEMENTY VSEGDA DOBAVLYAYUTSYA NA GRANICU~$Q$ I V 
VOZRASTAYUSHCHEM PORYADKE, TO~$Q$---TABLO.

oBRATNO, ESLI ZADANY DVA TABLO ODINAKOVOJ FORMY, TO SOOTVETSTVUYUSHCHIJ 
DVUSTROCHNYJ MASSIV~(11) MOZHNO POSTROITX TAK. pUSTX
$$
q_1 < q_2 < \ldots < q_n
$$%
---|LEMENTY~$Q$. pUSTX PRI~$i=n$,~\dots, $2$, $1$ (IMENNO V TAKOM PORYADKE) 
$p_i$---|LEMENT~$x$, KOTORYJ UDALYAETSYA IZ~$P$ PO ALGORITMU~D S 
ISPOLXZOVANIEM ZNACHENIJ~$s$, $t$, TAKIH, CHTO~$Q_{st}=q_i$.

nAPRIMER, ESLI PRIMENITX |TO POSTROENIE K TABLO~(13) I PROIZVODITX 
VYCHISLENIYA, OBRATNYE~(12), DO TEH POR, POKA~$P$ NE ISCHERPAETSYA, TO 
POLUCHITSYA MASSIV $\pmatrix{
1 & 3 & 5 & 6 & 8 \cr
7 & 2 & 9 & 5 & 3 \cr
}$.

pOSKOLXKU ALGORITMY~I I~D VZAIMNO OBRATNY, TO VZAIMNO OBRATNY I OPISANNYE 
ZDESX DVA POSTROENIYA; TAKIM OBRAZOM, TREBUEMOE VZAIMNO ODNOZNACHNOE 
SOOTVETSTVIE USTANOVLENO.
\proofend

sOOTVETSTVIE, OPREDELENNOE V DOKAZATELXSTVE TEOREMY~A, OBLADAET 
MNOZHESTVOM PORAZITELXNYH SVOJSTV, I TEPERX MY PRISTUPIM K VYVODU 
NEKOTORYH IZ NIH. uBEDITELXNAYA PROSXBA K CHITATELYU, PREZHDE CHEM DVIGATXSYA 
DALXSHE, ISPYTATX SEBYA NA PRIMERAH IZ UPR.~1, CHTOBY OSVOITXSYA S |TIMI POSTROENIYAMI.

%%72

kAK TOLXKO |LEMENT VYTESNEN IZ STROKI~1 V STROKU~2, ON UZHE BOLXSHE NE 
VLIYAET NA STROKU~1; KROME TOGO, STROKI~2, 3,~\dots{} STROYATSYA IZ 
POSLEDOVATELXNOSTI "VYTESNENNYH" |LEMENTOV TOCHNO TAK ZHE, KAK STROKI~1, 2,~\dots{} 
STROYATSYA IZ ISHODNOJ PERESTANOVKI. eTI FAKTY NAVODYAT NA MYSLX O 
TOM, CHTO NA POSTROENIE V TEOREME~A MOZHNO VZGLYANUTX INACHE, OBRASHCHAYA 
VNIMANIE LISHX NA PERVYE STROKI~$P$ I~$Q$. nAPRIMER, PERESTANOVKA 
$\pmatrix{
1 & 3 & 5 & 6 & 8\cr
7 & 2 & 9 & 5 & 3 \cr
}$
VYZYVAET SLEDUYUSHCHIE DEJSTVIYA NAD STROKOJ~1 [SR.~S~(12)]:
$$
\vcenter{\halign{
#\hfil\bskip&\bskip #\hfil\bskip&\bskip$#$\hfil\cr
1: vSTAVITX~$7$, & USTANOVITX & Q_{11}\asg 1. \cr
3: vSTAVITX~$2$, & VYTESNITX~$7$. \cr
5: vSTAVITX~$9$, & USTANOVITX & Q_{12}\asg 5. \cr
6: vSTAVITX~$5$, & VYTESNITX~$9$. \cr
8: vSTAVITX~$3$, & VYTESNITX~$5$.\cr
}}
\eqno(14)
$$
tAKIM OBRAZOM, PERVAYA STROKA~$P$---|TO~$2~3$, A PERVAYA STROKA~$Q$---|TO~$1~5$. 
kROME TOGO, OSTALXNYE STROKI~$P$ I~$Q$ SOSTAVLYAYUT TABLO, SOOTVETSTVUYUSHCHIE 
"VYTESNENNOMU" DVUSTROCHNOMU MASSIVU
$$
\pmatrix{
3 & 6 & 8 \cr
7 & 9 & 5 \cr
},
\eqno (15)
$$

chTOBY PONYATX, KAK STROITSYA STROKA~1, MOZHNO IZUCHITX |LEMENTY, POPADAYUSHCHIE 
V DANNYJ STOLBEC |TOJ STROKI. bUDEM GOVORITX, CHTO PARA~$(q_i, p_i)$ 
PRINADLEZHIT KLASSU~$t$ OTNOSITELXNO DVUSTROCHNOGO MASSIVA
$$
\pmatrix{
q_1 & q_2 & \ldots & q_n \cr
p_1 & p_2 & \ldots & p_n \cr
},
\qquad\matrix{
q_1<q_2<\ldots<q_n,\hfill\cr
p_1, p_2, \ldots, p_n \hbox{ VSE RAZNYE,}\hfill\cr
}
\eqno(16)
$$
ESLI~$p_i=P_{1t}$ POSLE PRIMENENIYA ALGORITMA~I POSLEDOVATELXNO K~$p_1$, 
$p_2$,~\dots, $p_i$, NACHINAYA S PUSTOGO TABLO~$P$. (nAPOMNIM, CHTO
ALGORITM~I VSEGDA VSTAVLYAET DANNYJ |LEMENT V 1-YU STROKU.)

lEGKO VIDETX, CHTO~$(q_i, p_i)$ PRINADLEZHIT KLASSU~1 TOGDA I TOLXKO TOGDA, 
KOGDA $p_i$~IMEET $(i-1)$~INVERSIJ, 
T.~E.~$p_i=\min\set{p_1, p_2,~\ldots, p_i}$---"LEVOSTORONNIJ MINIMUM". eSLI 
V MASSIVE~(16) VYCHERKNUTX STOLBCY KLASSA~1, TO POLUCHITSYA 
DRUGOJ DVUSTROCHNYJ MASSIV:
$$
\pmatrix{
q'_1 & q'_2 & \ldots & q'_m \cr
p'_1 & p'_2 & \ldots & p'_m \cr
}
\eqno(17)
$$
TAKOJ, CHTO PARA~$(q, p)$ PRINADLEZHIT KLASSU~$t$ OTNOSITELXNO~(17) TOGDA I 
TOLXKO TOGDA, KOGDA ONA PRINADLEZHIT KLASSU~$t+1$ OTNOSITELXNO 
MASSIVA~(16). oPERACIYA PEREHODA OT~(16) K~(17) SOOTVETSTVUET
%%73
UDALENIYU KRAJNEJ LEVOJ POZICII STROKI~1. eTO 
DAET SISTEMATICHESKIJ SPOSOB OPREDELENIYA KLASSOV. nAPRIMER, V PERESTANOVKE 
$\pmatrix{
1 & 3 & 5 & 6 & 8 \cr
7 & 2 & 9 & 5 & 3 \cr
}$ 
LEVOSTORONNIMI MINIMUMAMI YAVLYAYUTSYA |LEMENTY~$7$ I~$2$, TAK CHTO 
KLASS~1---|TO~$\set{(1, 7), (3, 2)}$; V OSTAVSHEMSYA MASSIVE
$\pmatrix{
5 & 6 & 8 \cr
9 & 5 & 3 \cr
}$
VSE |LEMENTY MINIMALXNY, TAK CHTO KLASS~2---|TO~$\set{(5, 9), (6, 5), (8, 3)}$. 
v "VYTESNENNOM" MASSIVE~(15) KLASS~1---|TO~$\set{(3, 7), (8, 5)}$, A 
KLASS~2---$\set{(6, 9)}$.

dLYA LYUBOGO FIKSIROVANNOGO~$t$ |LEMENTY KLASSA~$t$ MOZHNO POMETITX
$$
(q_{i_1}, p_{i_1}), \ldots, (q_{i_k}, p_{i_k}),
$$
TAK CHTOBY VYPOLNYALISX NERAVENSTVA
$$
\eqalign{
q_{i_1}<q_{i_2}<\ldots<q_{i_k},\cr
p_{i_1}>p_{i_2}>\ldots>p_{i_k},\cr
}
\eqno(18)
$$
POSKOLXKU PRI RABOTE ALGORITMA VSTAVKI POZICIYA TABLO~$P_{1t}$ PRINIMAET 
UBYVAYUSHCHUYU POSLEDOVATELXNOSTX ZNACHENIJ~$p_{i_1}$,~\dots, $p_{i_k}$. v KONCE POSTROENIYA
$$
p_{1t}=p_{i_k}, \quad Q_{1t}=q_{i_1},
\eqno(19)
$$
A VYTESNENNYJ DVUSTROCHNYJ MASSIV, KOTORYM OPREDELYAYUTSYA STROKI~2, 3,~\dots{} 
TABLO~$P$ I~$Q$, SODERZHIT STOLBCY
$$
\pmatrix{
q_{i_2} & q_{i_3} & \ldots & q_{i_k} \cr
p_{i_1} & p_{i_2} & \ldots & p_{i_k-1}\cr
},
\eqno(20)
$$
A TAKZHE DRUGIE STOLBCY, ANALOGICHNYM OBRAZOM POLUCHENNYE IZ DRUGIH KLASSOV.

eTI NABLYUDENIYA PRIVODYAT K PROSTOMU METODU VYCHISLENIYA~$P$ I~$Q$ VRUCHNUYU 
(SM.~UPR.~3), A TAKZHE PREDOSTAVLYAYUT SREDSTVA DLYA DOKAZATELXSTVA ODNOGO 
VESXMA NEOZHIDANNOGO REZULXTATA.

\proclaim tEOREMA~B. eSLI V POSTROENII IZ TEOREMY~A PERESTANOVKA
$$
\pmatrix{
1 & 2 & \ldots & n \cr
a_1 & a_2 & \ldots & a_n \cr
}
$$
SOOTVETSTVUET TABLO~$(P, Q)$, TO OBRATNAYA EJ PERESTANOVKA SOOTVETSTVUET 
TABLO~$(Q, P)$.

eTO DOVOLXNO UDIVITELXNYJ FAKT, POTOMU CHTO V TEOREME~A TABLO~$P$ I~$Q$ 
FORMIRUYUTSYA SOVERSHENNO RAZNYMI SPOSOBAMI, I OBRATNAYA PERESTANOVKA 
POLUCHAETSYA V REZULXTATE VESXMA PRICHUDLIVOJ PERETASOVKI STOLBCOV 
DVUSTROCHNOGO MASSIVA.

%% 74
\proof  pREDPOLOZHIM, U NAS ESTX DVUSTROCHNYJ MASSIV~(16);
POMENYAV MESTAMI EGO STROKI I OTSORTIROVAV STOLBCY TAK, CHTOBY |LEMENTY 
NOVOJ VERHNEJ STROKI RASPOLOZHILISX V NEUBYVAYUSHCHEM PORYADKE, POLUCHIM 
"OBRATNYJ" MASSIV
$$
\eqalign{
\pmatrix{
q_1 & q_2 & \ldots & q_n \cr
p_1 & p_2 & \ldots & p_n \cr
}^{-1}&=
\pmatrix{
p_1 & p_2 & \ldots & p_n \cr
q_1 & q_2 & \ldots & q_n \cr
}=\cr
&=\pmatrix{
p'_1 & p'_2 & \ldots & p'_n \cr
q'_1 & q'_2 & \ldots & q'_n \cr
},\qquad
\matrix{
p'_1 < p'_2 < \ldots < p'_n; \hfill\cr
q'_1, q'_2, \ldots, q'_n \hbox{ VSE RAZNYE.}\hfill\cr
}\cr
}
\eqno(21)
$$
pOKAZHEM, CHTO |TA OPERACIYA SOOTVETSTVUET ZAMENE~$(P, Q)$ NA~$(Q, P)$ V 
POSTROENII IZ TEOREMY~A.

v UPR.~2 NASHI ZAMECHANIYA OB OPREDELENII KLASSOV PEREFORMULIROVANY TAKIM 
OBRAZOM, CHTO KLASS, K KOTOROMU OTNOSITSYA PARA~$(q_i, p_i)$, NE ZAVISIT OT 
TOGO FAKTA, CHTO |LEMENTY~$q_1$, $q_2$,~\dots, $q_n$ RASPOLOZHENY V 
VOZRASTAYUSHCHEM PORYADKE. pOSKOLXKU REZULXTIRUYUSHCHIE USLOVIYA SIMMETRICHNY 
OTNOSITELXNO~$p$ I~$q$, TO OPERACIYA~(21) NE NARUSHAET STRUKTURU KLASSOV; 
ESLI~$(q, p)$ PRINADLEZHIT KLASSU~$t$ OTNOSITELXNO~(16), TO~$(p, q)$ 
PRINADLEZHIT KLASSU~$t$ OTNOSITELXNO~(21). pO|TOMU, ESLI RAZMESTITX 
|LEMENTY |TOGO POSLEDNEGO KLASSA~$t$ TAK, CHTOBY
$$
\eqalign{
p_{i_k}<\ldots< p_{i_2} < p_{i_1}, \cr
q_{i_k}>\ldots> q_{i_2} > q_{i_1}, \cr
}
\eqno(22)
$$
[SR.~S~(18)], TO POLUCHIM
$$
P_{1t}=q_{i_1}, Q_{1t}=p_{i_k},
\eqno (23)
$$
KAK V~(19), A STOLBCY
$$
\pmatrix{
p_{i_{k-1}} & \ldots & p_{i_2} & p_{i_1} \cr
q_{i_k} & \ldots & q_{i_3} & q_{i_2} \cr
}
\eqno(24)
$$
VOJDUT V VYTESNENNYJ MASSIV, KAK V~(20). sLEDOVATELXNO, PERVYE 
STROKI~$P$ I~$Q$ MENYAYUTSYA MESTAMI. kROME TOGO, VYTESNENNYJ DVUSTROCHNYJ 
MASSIV DLYA~(21) YAVLYAETSYA OBRATNYM PO OTNOSHENIYU K VYTESNENNOMU DVUSTROCHNOMU 
MASSIVU DLYA~(16), TAK CHTO DOKAZATELXSTVO ZAVERSHAETSYA PRIMENENIEM 
INDUKCII PO CHISLU STROK V TABLO.
\proofend

\proclaim sLEDSTVIE. kOLICHESTVO TABLO, KOTORYE MOZHNO SFORMIROVATX IZ 
|LEMENTOV~$\set{1, 2,~\ldots, n}$, RAVNO KOLICHESTVU INVOLYUCIJ 
MNOZHESTVA~$\set{1, 2,~\ldots, n}$.

\proof eSLI~$\pi$---INVOLYUCIYA, SOOTVETSTVUYUSHCHAYA PARE TABLO~$(P, Q)$, 
TO~$\pi=\pi^{-1}$ SOOTVETSTVUET PARE~$(Q, P)$. sLEDOVATELXNO,
%% 75
$P=Q$. oBRATNO, ESLI~$\pi$---KAKAYA-LIBO PERESTANOVKA, 
SOOTVETSTVUYUSHCHAYA PARE~$(P, P)$, TO~$\pi^{-1}$ TOZHE SOOTVETSTVUET PARE~$(P,P)$;
OTSYUDA~$\pi=\pi^{-1}$. tAKIM OBRAZOM, SUSHCHESTVUET VZAIMNO 
ODNOZNACHNOE SOOTVETSTVIE MEZHDU INVOLYUCIYAMI~$\pi$ I TABLO~$P$.
\proofend

yaSNO, CHTO |LEMENT V LEVOM VERHNEM UGLU TABLO VSEGDA NAIMENXSHIJ. eTO 
NAVODIT NA MYSLX O VOZMOZHNOM SPOSOBE SORTIROVKI MNOZHESTVA CHISEL. sNACHALA 
MOZHNO SOSTAVITX IZ NIH TABLO, MNOGOKRATNO PRIMENYAYA ALGORITM~I, V 
REZULXTATE NAIMENXSHIJ |LEMENT OKAZHETSYA V UGLU. zATEM |TOT NAIMENXSHIJ 
|LEMENT UDALYAETSYA, A OSTALXNYE |LEMENTY PERERAZMESHCHAYUTSYA TAK, CHTOBY 
OBRAZOVALOSX DRUGOE TABLO; POTOM UDALYAETSYA NOVYJ MINIMALXNYJ |LEMENT I T.D.

pO|TOMU DAVAJTE POSMOTRIM, CHTO PROISHODIT, KOGDA MY UDALYAEM UGLOVOJ 
|LEMENT IZ TABLO
$$
\tableau{
1 & 3 & 5 & 8 & 12 & 16\cr
2 & 6 & 9 & 15\cr
4 & 10 & 14 \cr
11 & 13 \cr
17\cr
}
\eqno (25)
$$
pOSLE UDALENIYA~$1$ NA OSVOBODIVSHEESYA MESTO NEOBHODIMO POSTAVITX~$2$. 
zATEM MOZHNO PODNYATX~$4$ NA MESTO DVOJKI, ODNAKO~$11$ NELXZYA PODNYATX NA 
MESTO~$4$, NO NA |TO MESTO MOZHNO PODVINUTX~$10$, A POTOM~$13$ NA 
MESTO~$10$. v OBSHCHEM SLUCHAE PRIHODIM K SLEDUYUSHCHEJ PROCEDURE.

\alg S.(uDALENIE UGLOVOGO |LEMENTA.) eTOT ALGORITM UDALYAET |LEMENT IZ 
LEVOGO VERHNEGO UGLA TABLO~$P$ I PEREMESHCHAET OSTALXNYE |LEMENTY TAK, CHTOBY 
SOHRANILISX SVOJSTVA TABLO. iSPOLXZUYUTSYA TE ZHE OBOZNACHENIYA, CHTO I V 
ALGORITMAH~I I~D.

\st[nACHALXNAYA USTANOVKA.] uSTANOVITX~$r\asg 1$, $s\asg 1$.

\st[kONEC?] eSLI~$P_{rs}=\infty$, TO PROCESS ZAVERSHEN.

\st[sRAVNITX.] eSLI~$P_{(r+1)s}\simlt P_{r(s+1)}$, TO PEREJTI K 
SHAGU~\stp{5}. (sRAVNIVAEM |LEMENTY SPRAVA I SNIZU OT SVOBODNOGO MESTA I 
PEREDVIGAEM MENXSHIJ IZ NIH.)

\st[pODVINUTX VLEVO.] uSTANOVITX~$P_{rs}\asg P_{r(s+1)}$, $s\asg s+1$  I 
VERNUTXSYA K~\stp{3}.

\st[pODVINUTX VVERH.] uSTANOVITX~$P_{rs}\asg P_{(r+1)s}$, $r\asg r+1$ I 
VERNUTXSYA K~\stp{2}.
\algend

lEGKO DOKAZATX, CHTO POSLE UDALENIYA UGLOVOGO |LEMENTA S POMOSHCHXYU 
ALGORITMA~S, $P$---PO-PREZHNEMU TABLO (SM.~UPR.~10). tAKIM
%%76
OBRAZOM, PRIMENYAYA ALGORITM~S DO TEH POR, POKA~$P$ NE ISCHERPAETSYA, MOZHNO 
PROCHITATX EGO |LEMENTY V VOZRASTAYUSHCHEM PORYADKE. k SOZHALENIYU, |TOT ALGORITM 
SORTIROVKI OKAZYVAETSYA NE STOLX |FFEKTIVNYM, KAK DRUGIE ALGORITMY, KOTORYE 
NAM ESHCHE PREDSTOIT RASSMOTRETX. mINIMALXNOE VREMYA EGO RABOTY PROPORCIONALXNO~$n^{1.5}$;
ANALOGICHNYE ALGORITMY, ISPOLXZUYUSHCHIE VMESTO TABLO DEREVXYA, ZATRACHIVAYUT 
VREMYA PORYADKA~$n\log n$.

aLGORITM~S, HOTYA I NE PRIVODIT K OSOBENNO |FFEKTIVNOMU ALGORITMU 
SORTIROVKI, OBLADAET NEKOTORYMI OCHENX INTERESNYMI SVOJSTVAMI.

\proclaim tEOREMA~C. (m.~p.~shYUCENBERZHE.) eSLI~$P$---TABLO, POSTROENNOE, KAK 
V TEOREME~A, IZ PERESTANOVKI~$a_1\,a_2,\ldots\,a_n$, 
I~$a_i=\min\set{a_1, a_2, \ldots, a_n}$, TO ALGORITM~S PREOBRAZUET~$P$ V 
TABLO, SOOTVETSTVUYUSHCHEE PERESTANOVKE~$a_1\,\ldots\,a_{i-1}\,a_{i+1}\,\ldots\,a_n$.

\proof sM. UPR. 13.
\proofend

dAVAJTE POSLE PRIMENENIYA ALGORITMA~S POMESTIM NA VNOVX OSVOBODIVSHEESYA 
MESTO UDALENNYJ |LEMENT V SKOBKAH, UKAZAV TAKIM OBRAZOM, CHTO NA SAMOM DELE 
ON NE YAVLYAETSYA CHASTXYU TABLO. pRIMENIV, NAPRIMER, |TU PROCEDURU K 
TABLO~(25), MY POLUCHILI BY
$$
\tableau{
2 & 3 & 5 & 8 & 12 & 16\cr
4 & 6 & 9 & 15\cr
10 & 13 & 14 \cr
11 & (1) \cr
17 \cr
}
$$
A ESHCHE DVA PRIMENENIYA PRIVODYAT K
$$
\tableau{
4 &  5 & 8 & 12 & 16 & (2)\cr
6 & 9 & 14 &15\cr
10 & 13 & (3) \cr
11 & (1) \cr
17\cr
}
$$
%% 77
pRODOLZHAYA DO TEH POR, POKA VSE |LEMENTY NE OKAZHUTSYA V SKOBKAH, I UBRAV 
SKOBKI, POLUCHIM KONFIGURACIYU
$$
\tableau{
17 & 15 & 14 & 13 & 11 & 2 \cr
16 & 10 & 6 & 4 \cr
12 & 5 & 3 \cr
9 & 1 \cr
8 \cr
}
\eqno(26)
$$
IMEYUSHCHUYU TU ZHE FORMU, CHTO I ISHODNOE TABLO~(25). eTU KONFIGURACIYU MOZHNO 
NAZVATX \dfn{DVOJSTVENNYM TABLO,} POTOMU CHTO ONA POHOZHA NA TABLO S TOJ 
LISHX RAZNICEJ, CHTO PRIMENYAETSYA "DVOJSTVENNOE OTNOSHENIE PORYADKA" ($<$ 
I~$>$ POMENYALISX ROLYAMI). oBOZNACHIM DVOJSTVENNOE TABLO, POLUCHENNOE IZ~$P$ 
TAKIM SPOSOBOM, CHEREZ~$P^S$.

tABLO~$P$ OPREDELYAETSYA IZ~$P^S$ EDINSTVENNYM OBRAZOM. v SAMOM DELE, 
ISHODNOE TABLO MOZHNO POLUCHITX IZ~$P^S$ PRI POMOSHCHI TOGO ZHE SAMOGO ALGORITMA 
(S OBRATNYM OTNOSHENIEM PORYADKA, POSKOLXKU $P^S$---DVOJSTVENNOE TABLO). 
nAPRIMER, PRIMENENIE K~(26) DVUH SHAGOV |TOGO ALGORITMA DAET
$$
\tableau{
15 & 14 & 13 & 11 & 2 & (16)\cr
12 & 10 & 6 & 4\cr
9 & 5 & 3 \cr
8 & 1 \cr
(17)\cr
}
$$
I V KONCE KONCOV OPYATX POLUCHAETSYA TABLO~(25). eTOT ZAMECHATELXNYJ 
REZULXTAT---ODNO IZ SLEDSTVIJ NASHEJ SLEDUYUSHCHEJ TEOREMY.

{\let\newpar=\par
\proclaim tEOREMA D. (k.~shENSTED, m.~p.~shYUCENBERZHE.) pUSTX
$$
\pmatrix{
q_1 & q_2 & \ldots & q_n \cr
p_1 & p_2 & \ldots & p_n \cr
}
\eqno(27)
$$
---DVUSTROCHNYJ MASSIV, SOOTVETSTVUYUSHCHIJ PARE TABLO~$(P, Q)$.
%% 78
{\medskip\narrower
\item{a)}eSLI POLXZOVATXSYA DVOJSTVENNYM (OBRATNYM) OTNOSHENIEM PORYADKA 
DLYA~$q$, NO NE DLYA~$p$, TO DVUSTROCHNYJ MASSIV
$$
\pmatrix{
q_n & \ldots & q_2 & q_1 \cr
p_n & \ldots & p_2 & p_1 \cr
}
\eqno(28)
$$
SOOTVETSTVUET PARE~$(P^T, (Q^S)^T)$.
\newpar
{\noindent \rm (kAK OBYCHNO, CHEREZ~$T$ OBOZNACHENA OPERACIYA TRANSPONIROVANIYA;
$P^T$---TABLO, a~$(Q^S)^T$---DVOJSTVENNOE TABLO, POSKOLXKU 
|LEMENTY~$q$ RASPOLOZHENY V OBRATNOM PORYADKE.)}
\newpar
\item{b)}eSLI POLXZOVATXSYA DVOJSTVENNYM OTNOSHENIEM PORYADKA DLYA~$p$, NO NE 
DLYA~$q$, TO DVUSTROCHNYJ MASSIV~(37) SOOTVETSTVUET PARE~$((P^S)^T, Q^T)$.
\newpar
\item{c)}eSLI POLXZOVATXSYA DVOJSTVENNYM OTNOSHENIEM PORYADKA KAK DLYA~$p$, 
TAK I DLYA~$q$, TO DVUSTROCHNYJ MASSIV~(28) SOOTVETSTVUET PARE~$(P^S, Q^S)$.
\newpar}
\par
}

\proof nE IZVESTNO PROSTOGO DOKAZATELXSTVA |TOJ TEOREMY. tO, CHTO 
SLUCHAJ~(a) SOOTVETSTVUET PARE~$(P^T, X)$, GDE~$X$---NEKOTOROE DVOJSTVENNOE 
TABLO, DOKAZANO V UPR.~6; SLEDOVATELXNO, PO TEOREME~B, SLUCHAJ~(b) 
SOOTVETSTVUET PARE~$(Y, Q^T)$, GDE~$Y$---NEKOTOROE DVOJSTVENNOE TABLO TOJ ZHE 
FORMY, CHTO I~$P^T$.

pUSTX~$p_i=\min\set{p_1,~\ldots, p_n}$; TAK KAK~$p_i$---"NAIBOLXSHIJ" 
|LEMENT PRI DVOJSTVENNOM OTNOSHENII PORYADKA, TO ON OKAZHETSYA 
NA GRANICE~$Y$ I NE VYTESNYAET NIKAKIH |LEMENTOV PRI POSTROENII IZ 
TEOREMY~A. tAKIM OBRAZOM, ESLI POSLEDOVATELXNO VSTAVLYATX 
|LEMENTY~$p_1$,~\dots, $p_{i-1}$, $p_{i+1}$,~\dots, $p_n$, PRIMENYAYA DVOJSTVENNOE 
OTNOSHENIE PORYADKA, TO POLUCHITSYA~$Y-\set{p_i}$, T.E.~$Y$, IZ KOTOROGO 
UDALEN |LEMENT~$p_i$. pO TEOREME~C, ESLI POSLEDOVATELXNO VSTAVLYATX 
|LEMENTY~$p_1$,~\dots, $p_{i-1}$, $p_{i+1}$,~\dots, $p_n$, PRIMENYAYA 
OBYCHNOE OTNOSHENIE PORYADKA, POSTROIM TABLO~$d(P)$, KOTOROE POLUCHAETSYA PUTEM 
PRIMENENIYA K~$P$ ALGORITMA~S. iNDUKCIYA PO~$n$ 
DAET~$Y-\set{p_i}=(d(P)^S)^T$. nO POSKOLXKU
$$
(P^S)^T-\set{p_i}=(d(P)^S)^T
\eqno (29)
$$
PO OPREDELENIYU OPERACII~$S$, A $Y$~IMEET TU ZHE FORMU, CHTO I~$(P^S)^T$, TO 
DOLZHNO IMETX MESTO RAVENSTVO~$Y=(P^S)^T$.

tEM SAMYM DOKAZANO UTVERZHDENIE~(b); (a)~POLUCHAETSYA PRIMENENIEM TEOREMY~B.
pOSLEDOVATELXNOE PRIMENENIE~(a) I~(b) POKAZYVAET, CHTO SLUCHAJ~(c) 
SOOTVETSTVUET PARE~$(((P^T)^S)^T, ((Q^S)^T)^T)$, a |TO RAVNO~$(P^S, Q^S)$, 
TAK KAK~$(P^S)^T=(P^T)^S$ VSLEDSTVIE SIMMETRII OPERACII~$S$ PO OTNOSHENIYU K 
STROKAM I STOLBCAM.
\proofend

eTA TEOREMA, V CHASTNOSTI, USTANAVLIVAET DVA UDIVITELXNYH FAKTA, KASAYUSHCHIHSYA 
ALGORITMA VSTAVKI V TABLO. eSLI V REZULXTATE POSLEDOVATELXNOJ VSTAVKI 
RAZLICHNYH |LEMENTOV~$p_1$,~\dots, $p_n$
%% 79
V PUSTOE TABLO POLUCHAETSYA TABLO~$P$, TO V REZULXTATE VSTAVKI |TIH 
|LEMENTOV V OBRATNOM PORYADKE---$p_n$,~\dots, $p_1$, 
POLUCHITSYA \dfn{TRANSPONIROVANNOE} TABLO~$P^T$. eSLI ZHE MY NE TOLXKO 
STANEM VSTAVLYATX |LEMENTY V PORYADKE~$p_n$,~\dots, $p_1$, NO I POMENYAEM 
ROLYAMI~$<$ I~$>$, A TAKZHE~$0$ I~$\infty$, TO POLUCHIM DVOJSTVENNOE 
TABLO~$P^S$. nASTOYATELXNO REKOMENDUEM CHITATELYU ISPYTATX |TI PROCESSY 
NA NESKOLXKIH PROSTYH PRIMERAH. nEOBYCHNAYA PRIRODA |TIH SOVPADENIJ MOZHET 
VYZVATX PODOZRENIE O VMESHATELXSTVE KAKIH-TO KOLDOVSKIH SIL. dO SIH POR 
NE IZVESTNO KAKOGO-LIBO PROSTOGO OB®YASNENIYA PODOBNYH YAVLENIJ; KAZHETSYA, NE 
SUSHCHESTVUET PROSTOGO SPOSOBA DOKAZATX DAZHE TO, CHTO SLUCHAJ~(c) SOOTVETSTVUET 
TABLO TOJ ZHE \emph{FORMY,} CHTO~$P$ I~$Q$.

sOOTVETSTVIE, USTANAVLIVAEMOE TEOREMOJ~A, NAJDENO zh.~rOBINSONOM 
[{\sl American J.\ Math.,\/} {\bf 60} (1938), 745--760, Sec.~5]
V NESKOLXKO INOJ I DOVOLXNO TUMANNOJ FORME KAK CHASTX RESHENIYA VESXMA 
SLOZHNOJ ZADACHI IZ TEORII GRUPP. nETRUDNO PROVERITX, CHTO EGO POSTROENIE V 
SUSHCHNOSTI IDENTICHNO PRIVEDENNOMU ZDESX. oN SFORMULIROVAL TEOREMU~B BEZ 
DOKAZATELXSTVA. mNOGO LET SPUSTYA k.~shENSTED NEZAVISIMO ZANOVO OTKRYL |TO 
SOOTVETSTVIE, KOTOROE ON SFORMULIROVAL PO SUSHCHESTVU V TOJ ZHE FORME, 
KAKUYU ISPOLXZOVALI MY 
[{\sl Canadian J.\ Math.,\/} {\bf 13} (1961), 179--191]. oN TAKZHE DOKAZAL 
"$P$"-CHASTX TEOREMY~D~(a). m.~p.~shYUCENBERZHE
[{\sl Math. Scand.,\/} {\bf 12} (1963), 117--128] DOKAZAL TEOREMU~B I 
"$Q$"-CHASTX TEOREMY~D~(a), IZ KOTOROJ SLEDUYUT~(b) I~(c). eTO 
SOOTVETSTVIE MOZHNO RASPROSTRANITX I NA PERESTANOVKI MULXTIMNOZHESTV;
SLUCHAJ, KOGDA~$p_1$,~\dots, $p_n$ NE OBYAZATELXNO RAZLICHNY, 
RASSMOTREL shENSTED, A "MAKSIMALXNOE" OBOBSHCHENIE NA SLUCHAJ, KOGDA I~$p$, 
I~$q$ MOGUT SODERZHATX POVTORYAYUSHCHIESYA |LEMENTY, ISSLEDOVANO kNUTOM
[{\sl Pacific J.\ Math.,\/} {\bf 34} (1970), 709--727].

oBRATIMSYA TEPERX K RODSTVENNOMU VOPROSU: \emph{SKOLXKO TABLO, SOSTAVLENNYH 
IZ |LEMENTOV~$\set{1, 2,~\ldots, n}$, IMEYUT DANNUYU 
FORMU~$(n_1, n_2,~\ldots, n_m)$, GDE~$n_1+n_2+\cdots+n_m=n$?} oBOZNACHIM |TO 
CHISLO CHEREZ~$f(n_1, n_2,~\ldots, n_m)$; ONO DOLZHNO UDOVLETVORYATX SOOTNOSHENIYAM
$$
\displaylines{
f(n_1, n_2, \ldots, n_m)=0, 
\rem{ESLI NE VYPOLNENO USLOVIE~$n_1\ge n_2\ge \ldots\ge n_m\ge 0$;} \hfill \llap{(30)}\cr
f(n_1, n_2, \ldots, n_m, 0)=f(n_1, n_2, \ldots, n_m); \hfill\llap{(31)}\cr
f(n_1, n_2, \ldots, n_m)=f(n_1-1, n_2, \ldots, n_m)
  +f(n_1, n_2-1, \ldots,  n_m)+\cdots+f(n_1, n_2, \ldots, n_m-1),\hfill\cr
\hfill \rem{ESLI $n_1\ge n_2 \ge \ldots \ge n_m \ge 1$.}\quad (32)\cr
}
$$
pOSLEDNEE REKURRENTNOE SOOTNOSHENIE VYTEKAET IZ TOGO FAKTA, CHTO PRI 
UDALENII NAIBOLXSHEGO |LEMENTA TABLO VSEGDA SNOVA POLUCHAETSYA TABLO; 
NAPRIMER, KOLICHESTVO TABLO FORMY~$(6, 4, 4, 1)$ 
RAVNO~$f(5, 4, 4, 1)+f(6, 3, 4, 1)+f(6, 4, 3, 1) + f(6, 4, 4, 0)=f(5, 4, 4, 1)
%%80
+f(6, 4, 3, 1)+f(6, 4, 4)$, POTOMU CHTO VSYAKOE TABLO FORMY~$(6, 4, 4, 1)$
IZ |LEMENTOV~$\set{1, 2,~\ldots, 15}$ POLUCHAETSYA V REZULXTATE VSTAVKI 
|LEMENTA~$15$ V PODHODYASHCHEE MESTO V TABLO FORMY~$(5, 4, 4, 1)$, $(6, 4, 3, 1)$
ILI~$(6, 4, 4)$. iZOBRAZIM |TO NA SHEME
\picture{p. 80, (33)}

fUNKCIYA~$f(n_1, n_2,~\ldots, n_m)$, UDOVLETVORYAYUSHCHAYA TAKIM SOOTNOSHENIYAM, 
IMEET DOVOLXNO PROSTOJ VID:
$$
f(n_1, n_2,~\ldots, n_m)=
{\Delta(n_1+m-1, n_2+m-2, \ldots, n_m) n! \over (n_1+m-1)! (n_2+m-2)! \ldots n_m!}
\rem{PRI~$n_1+m-1\ge n_2+m-2 \ge \ldots \ge n_m,$} 
\eqno (34)
$$ GDE CHEREZ~$\Delta$ OBOZNACHEN DETERMINANT
$$
\Delta(x_1, x_2, \ldots, x_m)=\det\pmatrix{
x_1^{m-1} & x_2^{m-1} & \ldots & x_m^{m-1}\cr
\vdots    &           &        & \vdots   \cr
x_1^2     & x_2^2     &        & x_m^2    \cr
x_1       & x_2       &        & x_m      \cr
1         & 1         & \ldots & 1        \cr
}=\prod_{1\le i < j \le m} (x_i-x_j)
\eqno(35)
$$
fORMULU~(34) VYVEL f.~fROBENIUS 
[Sitzungsberichte Preuss. Akad.\ der Wissenchaften (Berlin, 1900), 516--534, Sec.~3], 
IZUCHAYA |KVIVALENTNUYU ZADACHU TEORII GRUPP; ON 
ISPOLXZOVAL DOVOLXNO GLUBOKUYU ARGUMENTACIYU, OPIRAYUSHCHUYUSYA NA TEORIYU GRUPP. 
kOMBINATORNOE DOKAZATELXSTVO NEZAVISIMO NASHEL mAK-mAGON 
[{\sl Philosophical Trans.,\/} {\bf A-209} (London, 1909), 153--175]. eTU 
FORMULU MOZHNO DOKAZATX PO INDUKCII, TAK KAK~(30) I~(31) DOKAZYVAYUTSYA BEZ 
TRUDA, A FORMULA~(32) POLUCHAETSYA, ESLI POLOZHITX~$y=-1$ V TOZHDESTVE UPR.~17.

iZ TEOREMY~A V SVYAZI S |TOJ FORMULOJ DLYA CHISLA TABLO VYTEKAET 
ZAMECHATELXNOE TOZHDESTVO. vZYAV SUMMU PO VSEVOZMOZHNYM %%81
FORMAM TABLO, POLUCHIM
$$
\eqalign{
n! &= \sum_{\scriptstyle k_1\ge \ldots \ge k_n \ge 0 \atop \scriptstyle 
     k_1+\cdots+k_n=n} f(k_1, \ldots, k_n)^2=\cr
   &= n!^2 \sum_{\scriptstyle k_1\ge \ldots \ge k_n \ge 0 \atop \scriptstyle k_1+\cdots+k_n=n}
      {\Delta(k_1+n-1, \ldots, k_n)^2 \over (k_1+n-1)!^2\ldots k_n!^2}=\cr
   &= n!^2 \sum_{\scriptstyle q_1>q_2>\ldots>q_n\ge 0 \atop \scriptstyle 
      q_1+\cdots+q_n=(n+1)n/2} {\Delta(q_1, \ldots, q_n)^2 \over q_1!^2\ldots q_n!^2};\cr
}
$$
OTSYUDA
$$
\sum_{\scriptstyle q_1+\cdots+q_n=(n+1)n/2 \atop \scriptstyle q_1 \ldots q_n \ge 0} 
{\Delta(q_1,\ldots, q_n)^2\over q_1!^2 \ldots q_n!^2} = 1.
\eqno(36)
$$
v POSLEDNEJ SUMME OTSUTSTVUYUT NERAVENSTVA~$q_1>q_2>\ldots>q_n$, POTOMU CHTO 
SLAGAEMYE---SIMMETRICHNYE OTNOSITELXNO~$q$ FUNKCII, OBRASHCHAYUSHCHIESYA V~$0$ 
PRI~$q_i=q_j$. aNALOGICHNOE TOZHDESTVO POYAVLYAETSYA V UPR.~24.

fORMULU CHISLA TABLO MOZHNO VYRAZITX NESKOLXKO BOLEE INTERESNYM SPOSOBOM, 
ESLI VVESTI PONYATIE "UGOLKOV". v \dfn{UGOLOK,} SOOTVETSTVUYUSHCHIJ
\picture{rIS~5. uGOLKI I DLINY UGOLKOV.}
KLETKE TABLO, VHODIT SAMA |TA KLETKA PLYUS VSE KLETKI, LEZHASHCHIE SNIZU I 
SPRAVA OT NEE. nAPRIMER, ZASHTRIHOVANNYJ UCHASTOK NA RIS.~5---UGOLOK, 
SOOTVETSTVUYUSHCHIJ KLETKE~$(2, 3)$ STROKI~2 I STOLBCA~3; ON SOSTOIT IZ SHESTI 
KLETOK. v KAZHDOJ KLETKE NA RIS.~5 ZAPISANA DLINA SOOTVETSTVUYUSHCHEGO EJ UGOLKA.

eSLI TABLO IMEET FORMU~$(n_1, n_2,~\ldots, n_m)$, GDE~$n_m\ge 1$, TO 
DLINA SAMOGO DLINNOGO UGOLKA RAVNA~$n_1+m-1$. dALXNEJSHEE ISSLEDOVANIE 
DLIN UGOLKOV POKAZYVAET, CHTO STROKA~1 SODERZHIT VSE DLINY~$n_1+m-1$, 
$n_1+m-2$,~\dots, $1$, \emph{KROME $(n_1+m-1)-(n_m)$, $(n_1+m-1)-
%%82
-(n_{m-1}+1)$,~\dots, $(n_1+m-1)-(n_2+m-2)$.} nAPRIMER, NA RIS.~5 DLINY 
UGOLKOV V $1\hbox{-J}$ STROKE SUTX~$12$, $11$, $10$,~\dots, $1$, ZA 
ISKLYUCHENIEM~$10$, $9$, $6$, $3$, $2$; |TI ISKLYUCHENIYA SOOTVETSTVUYUT PYATI 
NESUSHCHESTVUYUSHCHIM UGOLKAM, NACHINAYUSHCHIMSYA V NESUSHCHESTVUYUSHCHIH KLETKAH~$(6, 3)$, 
$(5, 3)$, $(4, 5)$, $(3, 7)$, $(2, 7)$ I ZAKANCHIVAYUSHCHIMSYA V KLETKE~$(1, 7)$.
 aNALOGICHNO $j\hbox{-YA}$~STROKA SODERZHIT VSE DLINY 
UGOLKOV~$n_j+m-j$,~\dots, $1$, KROME~$(n_j+m-j)-(n_m)$,~\dots, 
$(n_j-m-j)-(n_{j+1}-m-j-1)$. oTSYUDA SLEDUET, CHTO PROIZVEDENIE DLIN VSEH 
UGOLKOV RAVNO
$$
(n_1+m-1)!\ldots{}(n_m)!/\Delta(n_1+m-1,~\ldots, n_m).
$$
eTO VYRAZHENIE VHODIT V FORMULU~(34); OTSYUDA SLEDUET

\proclaim tEOREMA~H. (dZH.~s.~fR|JM, zh.~rOBINSON, r.~m.~tROLL.) 
kOLICHESTVO TABLO DANNOJ FORMY, SOSTAVLENNYH IZ 
|LEMENTOV~$\set{1, 2,~\ldots, n}$, RAVNO~$n!$, DELENNOMU NA PROIZVEDENIE 
DLIN UGOLKOV. \endmark

tAKOJ PROSTOJ REZULXTAT ZASLUZHIVAET I PROSTOGO DOKAZATELXSTVA; ODNAKO 
(KAK I DLYA BOLXSHINSTVA DRUGIH FAKTOV, KASAYUSHCHIHSYA TABLO) BOLEE PRYAMOGO 
DOKAZATELXSTVA NE IZVESTNO. kAZHDYJ |LEMENT TABLO---MINIMALXNYJ V SVOEM 
UGOLKE; ESLI ZAPOLNITX KLETKI TABLO SLUCHAJNYM OBRAZOM, TO VEROYATNOSTX TOGO,
CHTO V KLETKE~$(i, j)$ OKAZHETSYA MINIMALXNYJ |LEMENT SOOTVETSTVUYUSHCHEGO 
UGOLKA, ESTX VELICHINA, OBRATNAYA DLINE UGOLKA. pEREMNOZHENIE |TIH 
VEROYATNOSTEJ PO VSEM~$i$, $j$ DAET TEOREMU~H. oDNAKO TAKOE 
RASSUZHDENIE OSHIBOCHNO, POSKOLXKU |TI VEROYATNOSTI OTNYUDX NE YAVLYAYUTSYA 
NEZAVISIMYMI. vSE IZVESTNYE DOKAZATELXSTVA TEOREMY~H OSNOVANY NA ODNOM 
NEUBEDITELXNOM INDUKTIVNOM RASSUZHDENII, KOTOROE NA SAMOM DELE NE OB®YASNYAET,
 POCHEMU ZHE TEOREMA VERNA (TAK KAK V NEM SOVERSHENNO NE ISPOLXZUYUTSYA 
SVOJSTVA UGOLKOV).

sUSHCHESTVUET INTERESNAYA SVYAZX MEZHDU TEOREMOJ~H I PERECHISLENIEM DEREVXEV, 
KOTOROE RASSMATRIVALOSX V GL.~2. mY VIDELI, CHTO BINARNYM DEREVXYAM S 
$n$~UZLAMI SOOTVETSTVUYUT PERESTANOVKI, KOTORYE MOZHNO POLUCHITX S POMOSHCHXYU 
STEKA, I CHTO TAKIM PERESTANOVKAM SOOTVETSTVUYUT 
POSLEDOVATELXNOSTI~$a_1\,a_2\,\ldots\,a_{2n}$ LITER~$S$ I~$X$, TAKIE, CHTO 
KOLICHESTVO LITER~$S$ NIKOGDA NE BYVAET MENXSHE KOLICHESTVA LITER~$X$, ESLI CHITATX 
POSLEDOVATELXNOSTX SLEVA NAPRAVO. (sM.~UPR.~2.3.1-6 I~2.2.1-3.) tAKIM 
POSLEDOVATELXNOSTYAM ESTESTVENNYM OBRAZOM SOPOSTAVLYAYUTSYA TABLO FORMY~$(n, n)$; 
V 1-YU STROKU POMESHCHAYUTSYA INDEKSY~$i$, TAKIE, CHTO~$a_i=S$, A VO 2-YU 
STROKU---INDEKSY, PRI KOTORYH~$a_i=X$. nAPRIMER, POSLEDOVATELXNOSTI
$$
S\; S\; S\; X\; X\; S\; S\; X\; X\; S\; X\; X
$$ 
SOOTVETSTVUET TABLO
$$
\tableau{
1 & 2 & 3 & 6 & 7 & 10 \cr
4 & 5 & 8 & 9 & 11 & 12 \cr
}
\eqno(37)
$$
%%83
uSLOVIE, NALAGAEMOE NA STOLBCY, UDOVLETVORYAETSYA V TAKOM TABLO V TOM I 
TOLXKO TOM SLUCHAE, KOGDA PRI CHTENII SLEVA NAPRAVO CHISLO LITER~X NIKOGDA NE 
PREVYSHAET CHISLA LITER~$S$. pO TEOREME~H KOLICHESTVO VSEVOZMOZHNYH TABLO 
FORMY~$(n, n)$ RAVNO
$$
(2n)!/(n+1)!n!;
$$
SLEDOVATELXNO, TAKOVO ZHE I CHISLO BINARNYH DEREVXEV S $n$~UZLAMI (CHTO 
SOGLASUETSYA S FORMULOJ~(2.3.4.4-13)). bOLEE TOGO, ESLI VOSPOLXZOVATXSYA 
TABLO FORMY~$(n, m)$ PRI~$n\ge m$, TO PRI POMOSHCHI |TOGO RASSUZHDENIYA MOZHNO 
RESHITX I BOLEE OBSHCHUYU "ZADACHU O BALLOTIROVKE", RASSMOTRENNUYU V OTVETE K 
UPR.~2.2.1-4. tAKIM OBRAZOM, TEOREMA~H V KACHESTVE PROSTYH CHASTNYH 
SLUCHAEV VKLYUCHAET V SEBYA NEKOTORYE VESXMA SLOZHNYE ZADACHI O PERECHISLENII.

vSYAKOMU TABLO~$A$ FORMY~$(n, n)$ IZ |LEMENTOV~$\set{1, 2,~\ldots, 2n}$ 
SOOTVETSTVUYUT DVA TABLO~$(P, Q)$ ODINAKOVOJ FORMY. sLEDUYUSHCHIJ SPOSOB 
POSTROENIYA TAKOGO SOOTVETSTVIYA PREDLOZHEN mAK-mAGONOM 
[Combinatory Analysis, {\bf 1} (1915), 130--131]. pUSTX~$P$ SOSTOIT IZ 
|LEMENTOV~$\set{1,~\ldots, n}$, RASPOLOZHENNYH, KAK V~$A$, A~$Q$ POLUCHAETSYA, 
ESLI VZYATX OSTALXNYE |LEMENTY~$A$, POVERNUTX VSYU KONFIGURACIYU NA~$180^\circ$ 
I ZAMENITX~$n+1$, $n+2$,~\dots, $2n$ NA SOOTVETSTVENNO~$n$, $n-1$,~\dots, $1$. 
nAPRIMER, TABLO~(37) RASPADAETSYA NA
$$
\tableau{
1 & 2 & 3 & 6 \cr
4 & 5 \cr
}
\hbox{ I }
\revtableau{
\omit &\omit \hfil\vrule& 7 & 10 \cr
8 & 9 & 11 & 12\cr
}\,;
$$
POSLE POVOROTA I PERENUMERACII IMEEM
$$
P=\tableau{
1 & 2 & 3 & 6 \cr
4 & 5 \cr
},\quad 
Q=\tableau{
1 & 2 & 4 & 5 \cr
3 & 6 \cr
}.
\eqno(38)
$$
nAOBOROT, KAZHDOJ PARE TABLO ODINAKOVOJ FORMY, SOSTOYASHCHIH IA $n$~|LEMENTOV I 
IZ NE BOLEE DVUH STROK, SOOTVETSTVUET TABLO FORMY~$(n, n)$. sLEDOVATELXNO 
(IZ~UPR.~7), \emph{CHISLO PERESTANOVOK~$a_1\,a_2\,\ldots\,a_n$ 
MNOZHESTVA~$\set{1, 2,~\ldots, n}$, NE SODERZHASHCHIH UBYVAYUSHCHIH 
PODPOSLEDOVATELXNOSTEJ~$a_i>a_j>a_k$ PRI~$i<j<k$, RAVNO CHISLU 
BINARNYH DEREVXEV S $n$~UGLAMI.} iNTERESNOE VZAIMNO ODNOZNACHNOE 
SOOTVETSTVIE MEZHDU TAKIMI PERESTANOVKAMI I BINARNYMI DEREVXYAMI, 
USTANOVLENNOE BOLEE PRYAMYM SPOSOBOM, CHEM TOT OKOLXNYJ PUTX POSREDSTVOM 
ALGORITMA~I. KOTORYM VOSPOLXZOVALISX MY, NASHEL d.~rOTOM 
[{\sl Inf.\ Proc.\ Letters,\/} {\bf 4} (1975), 58--61]; ANALOGICHNO, SUSHCHESTVUET 
DOVOLXNO PRYAMOE SOOTVETSTVIE MEZHDU BINARNYMI DEREVXYAMI I PERESTANOVKAMI, NE 
SODERZHASHCHIMI PODPOSLEDOVATELXNOSTEJ~$a_j>a_k>a_i$ I~$i<j<k$ (SM.~UPR.~2.2.1-5).

%% 84

 chISLO SPOSOBOV ZAPOLNITX TABLO FORMY~$(6, 4, 4, 1)$, OCHEVIDNO, RAVNO 
CHISLU SPOSOBOV POMETITX VERSHINY NAPRAVLENNOGO GRAFA
\picture{p.84}
CHISLAMI~$\set{1, 2,~\ldots, 15}$ TAK, CHTOBY METKA VERSHINY~$u$ BYLA 
MENXSHE METKI VERSHINY~$v$, ESLI~$u\to v$. iNACHE GOVORYA, ONO RAVNO 
CHISLU SPOSOBOV TOPOLOGICHESKI OTSORTIROVATX CHASTICHNOE UPORYADOCHENIE~(39) V 
SMYSLE P.~2.2.3.

v OBSHCHEM SLUCHAE MOZHNO ZADATX TOT ZHE VOPROS DLYA PROIZVOLXNOGO 
NAPRAVLENNOGO GRAFA, NE SODERZHASHCHEGO ORIENTIROVANNYH CIKLOV. bYLO BY HOROSHO,
ESLI BY SUSHCHESTVOVALA KAKAYA-NIBUDX PROSTAYA FORMULA, OBOBSHCHAYUSHCHAYA TEOREMU~H 
NA SLUCHAJ PROIZVOLXNOGO GRAFA; ODNAKO NE VSE GRAFY OBLADAYUT TAKIMI 
PRIYATNYMI SVOJSTVAMI, KAK GRAFY, SOOTVETSTVUYUSHCHIE TABLO. dRUGIE KLASSY 
NAPRAVLENNYH GRAFOV, DLYA KOTORYH ZADACHA O RAZMETKE VERSHIN IMEET PROSTOE 
RESHENIE, CHASTICHNO OBSUZHDAYUTSYA V UPRAZHNENIYAH V KONCE |TOGO PUNKTA. tAM 
TAKZHE IMEYUTSYA UPRAZHNENIYA, V KOTORYH POKAZANO, CHTO V RYADE SLUCHAEV 
NAPRAVLENNYH GRAFOV \emph{NE} SUSHCHESTVUET PROSTOJ FORMULY, 
SOOTVETSTVUYUSHCHEJ TEOREME~H. nAPRIMER, CHISLO SPOSOBOV POMETITX VERSHINY NE 
VSEGDA YAVLYAETSYA DELITELEM~$n!$.

zAVERSHIM NASHI ISSLEDOVANIYA PODSCHETOM OBSHCHEGO CHISLA TABLO, KOTORYE MOZHNO 
SFORMIROVATX IZ $n$~RAZLICHNYH |LEMENTOV. oBOZNACHIM |TO CHISLO CHEREZ~$t_n$.
pO SLEDSTVIYU IZ TEOREMY~B $t_n$~RAVNO CHISLU INVOLYUCIJ 
MNOZHESTVA~$\set{1, 2,~\ldots, n}$. pERESTANOVKA OBRATNA SAMOJ SEBE TOGDA I 
TOLXKO TOGDA, KOGDA EE PREDSTAVLENIE S POMOSHCHXYU CIKLOV SOSTOIT TOLXKO IZ 
EDINICHNYH CIKLOV (NEPODVIZHNYH TOCHEK) I CIKLOV IZ DVUH |LEMENTOV (TRANSPOZICIJ). 
pOSKOLXKU V~$t_{n-1}$ IZ~$t_n$ INVOLYUCIJ $(n)$---NEPODVIZHNAYA TOCHKA, A 
V~$t_{n-2}$ IZ NIH~$(j, n)$---CIKL IZ DVUH |LEMENTOV PRI NEKOTOROM 
FIKSIROVANNOM~$j<n$, TO POLUCHAEM FORMULU
$$
t_n=t_{n-1}+(n-1)t_{n-2},
\eqno(40)
$$
KOTORUYU VYVEL rOTE V~1800~G.\ DLYA POLUCHENII TABLICY ZNACHENIJ~$t_n$ PRI 
MALYH~$n$.

vYCHISLIM~$t_n$ DRUGIM SPOSOBOM. pUSTX IMEETSYA $k$~CIKLOV IZ
DVUH |LEMENTOV I $n-2k$~EDINICHNYH CIKLOV. sUSHCHESTVUET 
$\perm{n}{2k}$~SPOSOBOV VYBRATX NEPODVIZHNYE TOCHKI, I 
MULXTINOMIALXNYJ KO|FFICIENT~$(2k)!/(2!)^k$ RAVEN CHISLU SPOSOBOV 
ORGANIZOVATX OSTALXNYE
%%85
|LEMENTY V $k$~RAZLICHIMYH TRANSPOZICIJ. pODELIV NA~$k!$, CHTOBY SDELATX 
|TI TRANSPOZICII NERAZLICHIMYMI, POLUCHIM
$$
t_n=\sum_{k\ge 0} t_n(k), \quad t_n(k)={n!\over (n-2k)!2^k k!}.
\eqno(41)
$$
k SOZHALENIYU, NASKOLXKO |TO IZVESTNO, TAKUYU SUMMU UZHE NELXZYA UPROSTITX, 
PO|TOMU, DLYA TOGO CHTOBY LUCHSHE PONYATX POVEDENIE VELICHINY~$t_n$, MY PRIMENIM 
DVA KOSVENNYH PODHODA:
{\medskip\narrower
\item{a)}~mOZHNO NAJTI PROIZVODYASHCHUYU FUNKCIYU
$$
\sum_n t_n z^n/n! = e^{z+z^2/2};
\eqno(42)
$$
SM.~UPR.~25.

\item{b)}~mOZHNO OPREDELITX ASIMPTOTICHESKOE POVEDENIE VELICHINY~$t_n$. eTO 
POUCHITELXNAYA ZADACHA, EE RESHENIE SODERZHIT NESKOLXKO OBSHCHIH METODOV, KOTORYE 
BUDUT POLEZNY I V SVYAZI S DRUGIMI VOPROSAMI; PO|TOMU MY ZAKLYUCHIM |TOT 
PUNKT ANALIZOM ASIMPTOTICHESKOGO POVEDENIYA~$t_n$.
\medskip}

pERVYJ SHAG V ANALIZE ASIMPTOTICHESKOGO POVEDENIYA~(41) SOSTOIT V VYDELENII 
SLAGAEMYH, DAYUSHCHIH OSNOVNOJ VKLAD V SUMMU. pOSKOLXKU
$$
{t_n(k+1) \over t_n(k)} = {(n-2k)(n-2k-1)\over 2(k+1)},
\eqno(43)
$$
MOZHNO VIDETX, CHTO SLAGAEMYE POSTEPENNO VOZRASTAYUT, KOGDA $k$~MENYAETSYA 
OT~$k=0$ DO~$k$, RAVNOGO PRIBLIZITELXNO~${1\over2}(n-\sqrt{n})$, A ZATEM 
UBYVAYUT DO NULYA, KOGDA $k$~DOSTIGAET ZNACHENIYA, RAVNOGO 
PRIMERNO~${1\over 2}n$. yaSNO, CHTO OSNOVNOJ VKLAD DAYUT CHLENY V 
OKRESTNOSTI~$k={1\over2}(n-\sqrt{n})$. dLYA ANALIZA, ODNAKO, UDOBNEE, KOGDA
OSNOVNOJ VKLAD DOSTIGAETSYA PRI ZNACHENII~$0$, PO|TOMU PREDSTAVIM~$k$ V VIDE
$$
k={1\over 2}(n-\sqrt{n})+x
\eqno(44)
$$
I ISSLEDUEM VELICHINU~$t_n(k)$ KAK FUNKCIYU OT~$x$.

chTOBY IZBAVITXSYA OT FAKTORIALOV V~$t_n(k)$, POLEZNO VOSPOLXZOVATXSYA 
FORMULOJ sTIRLINGA (1.2.11.2-18). dLYA |TOJ CELI UDOBNO (KAK MY VSKORE 
UVIDIM) OGRANICHITX OBLASTX IZMENENIYA~$x$ PROMEZHUTKOM
$$
-(n^{\varepsilon+1/4})\le x \le n^{\varepsilon+1/4},
\eqno(45)
$$
GDE $\varepsilon$~RAVNO, SKAZHEM, $0.001$, TAK CHTO MOZHNO VKLYUCHITX 
SLAGAEMOE POGRESHNOSTI. pOSLE DOVOLXNO TRUDOEMKIH VYCHISLENIJ, KOTORYE NA 
SAMOM DELE DOLZHNY BYLI BYTX PRODELANY VYCHISLITELXNOJ
%%86
MASHINOJ, POLUCHAETSYA FORMULA
$$
\displaylines{
t_n(k)=\exp\left({1\over2}n\ln n-{1\over2}n+\sqrt{n}-{1\over4}\ln n -2x^2/\sqrt{n}-\right.\hfill\cr
\hfill\left.-{1\over4}-{1\over2}\ln \pi-{4\over3}x^3/n+2x/\sqrt{n}+{1\over3}/\sqrt{n}-{4\over3}x^4/n\sqrt{n}+O(n^{5\varepsilon-3/4})\right).\quad(46)\cr
}
$$
oGRANICHENIE~(45) NA~$x$ OPRAVDYVAETSYA TEM, CHTO MOZHNO 
POLOZHITX~$x=\pm n^{\varepsilon+1/4}$ DLYA POLUCHENIYA VERHNEJ OCENKI VSEH 
OTBROSHENNYH SLAGAEMYH, IMENNO
$$
e^{-2n^{2\varepsilon}}\cdot\exp\left({1\over2}n\ln n-{1\over2}n+\sqrt{n}
-{1\over4}\ln n-{1\over4}-{1\over2}\ln\pi+O(n^{3\varepsilon-1/4})\right),
\eqno(47)
$$
A ESLI UMNOZHITX |TO NA~$n$, TO POLUCHITSYA VERHNYAYA OCENKA SUMMY ISKLYUCHENNYH 
SLAGAEMYH. vERHNYAYA OCENKA IMEET MENXSHIJ PORYADOK, CHEM TE SLAGAEMYE, 
KOTORYE MY VYCHISLIM DLYA~$x$ V OGRANICHENNOM PROMEZHUTKE~(45), BLAGODARYA 
MNOZHITELYU~$\exp(-2n^{2\varepsilon})$, KOTORYJ MNOGO MENXSHE LYUBOGO POLINOMA 
OT~$n$. oCHEVIDNO, MOZHNO OTBROSITX V SUMME MNOZHITELX
$$
\exp\left({1\over2}n\ln n-{1\over2}n+\sqrt{n}-{1\over4}\ln n-{1\over4}
-{1\over2}\ln\pi+{1\over3}\big/\sqrt{n}\right),
\eqno(48)
$$
POSLE CHEGO NAM OSTANETSYA TOLXKO PROSUMMIROVATX
$$
\displaylines{
\exp\left(-2x^2/\sqrt{n}-{4\over3}x^3/n+2x/\sqrt{n}-{4\over3}x^4/n\sqrt{n}+O(n^{5\varepsilon-3/4})\right)=\hfill\cr
\hfill =\exp\left({-2x^2\over\sqrt{n}}\right)\left(1-{4\over3}{x^3\over n}+{8\over9}{x^6\over n^2}\right)
\times\left(1+2{x\over\sqrt{n}}+2{x^2\over n}\right)\left(1-{4\over3}{x^4\over n\sqrt{n}}\right)(1+O(n^{9\varepsilon-3/4}))
\quad (49)\cr
}
$$
PO VSEM~$x=\alpha$, $\alpha+1$,~\dots, $\beta-2$, $\beta-1$, GDE~$-\alpha$ 
I~$\beta$  (NE OBYAZATELXNO CELYE) RAVNY 
PRIBLIZITELXNO~$n^{\varepsilon+1/4}$. eSLI SMESTITX INTERVAL SUMMIROVANIYA, 
TO FORMULU SUMMIROVANIYA eJLERA~(1.2.11.2-10) MOZHNO ZAPISATX V VIDE
$$
\sum_{\alpha\le x<\beta} f(x)=\int_\alpha^\beta f(x)\,dx
-\left.{1\over2}f(x)\right\vert_\alpha^\beta
+{1\over2}B_2\cdot\left.{f'(x)\over1!}\right\vert_\alpha^\beta+\cdots
+{1\over m+1}B_{m+1}\cdot\left.{f^{(m)}(x)\over m!}\right\vert_\alpha^\beta
+R_{m+1}.
\eqno(50)
$$
zDESX~$\abs{R_m}\le (4/(2\pi)^m)\int_\alpha^\beta\vert{f^{(m)}(x)}\,dx$.
pOLAGAYA~$f(x)=x^t\times \exp(-2^2/\sqrt{n})^\alpha)$, 
GDE~$t$---FIKSIROVANNOE NEOTRICATELXNOE CELOE
%%87
CHISLO, NAJDEM, CHTO ~$\int_\alpha^\beta f(x)\,dx$ OTLICHAETSYA 
OT~$\int_{-\infty}^\infty f(x)\,dx$ NA~$O(\exp(-2\pi^\varepsilon))$, TAK 
CHTO MOZHNO VZYATX~$\alpha=-\infty$, $\beta=\infty$. v |TOM SLUCHAE FORMULA 
SUMMIROVANIYA eJLERA DAST ASIMPTOTICHESKIJ RYAD DLYA~$\sum f(x)$ 
PRI~$n\to\infty$, POSKOLXKU
$$
f^{(m)}(x)=n^{(t-m)/4} g^{(m)} (n^{-1/4}x),\quad
g(y)=y^i e^{-2y^2},
\eqno(51)
$$
I~$g(y)$---HOROSHAYA FUNKCIYA, NE ZAVISYASHCHAYA OT~$n$; OTSYUDA VIDNO,
CHTO~$R_m=O(n^{(t+1-m)/4})$. tAK KAK~$f^{(m)}(-\infty)=f^m(\infty)=0$, MY 
DOKAZALI, CHTO
$$
\sum_{\alpha \le x < \beta} f(x)=\int_{-\infty}^{\infty} f(x)\,dx+O(n^{-m})
\rem{DLYA LYUBOGO~$m\ge0$;}
\eqno (52)
$$
NA SAMOM DELE PRI |TOM KONKRETNOM VYBORE~$f(x)$ SUSHCHESTVEN TOLXKO INTEGRAL! 
iNTEGRAL NETRUDNO VYCHISLITX (SM.~UPR.~26); TAKIM OBRAZOM, MY MOZHEM 
VYPOLNITX UMNOZHENIE I SLOZHENIE V FORMULE~(49) I POLUCHITX
$$
\displaylines{
\sqrt{\pi\over 2} n^{1/4}\left(1-{1\over24}n^{-1/4}+O(n^{-1/2})\right);\cr
\hfill t_n={1\over \sqrt{2}} n^{n/2} e^{-n/2+\sqrt{n}-1/4}
\left(1+{7\over24} n^{-1/2}+O(n^{-3/4})\right).\hfill\llap{(53)}\cr
}
$$
v DEJSTVITELXNOSTI SLAGAEMYE V~$O(n^{-3/4})$ SODERZHAT ESHCHE |KSPONENTU 
OT~$9\varepsilon$, NO IZ NASHIH VYKLADOK YASNO, CHTO VELICHINA~$9\varepsilon$ 
DOLZHNA ISCHEZNUTX, ESLI PROIZVESTI VYCHISLENIYA S BOLXSHEJ TOCHNOSTXYU. v 
PRINCIPE |TOT METOD MOZHNO USILITX I VMESTO~$O(n^{-3/4})$ 
POLUCHITX~$O(n^{-k})$ PRI LYUBOM~$k$. eTOT ASIMPTOTICHESKIJ RYAD DLYA~$t_n$ 
VPERVYE NASHLI (DRUGIM SPOSOBOM) mOZER I~uAJM|N 
[{\sl Canadian. J.~Math.,\/} {\bf 7} (1955), 159--168]. dRUGIE PRIMERY I 
USILENIYA METODA, PRIMENENNOGO DLYA VYVODA FORMULY~(53), SM.\ V KONCE P.~5.2.2.

\excercises
\ex[16] kAKIE TABLO~$(P, Q)$ SOOTVETSTVUYUT DVUSTROCHNOMU MASSIVU
$$
\pmatrix{
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \cr
6 & 4 & 9 & 5 & 7 & 1 & 2 & 8 & 3 \cr
}
$$
V POSTROENII IZ TEOREMY~A? kAKOJ DVUSTROCHNYJ MASSIV SOOTVETSTVUET PARE TABLO
$$
B=\tableau{
1 & 4 & 7 \cr
2 & 8 \cr
5 & 9 \cr
},\quad
C=\tableau{
1 & 3 & 7 \cr
4 & 5 \cr
8 & 9 \cr
}?
$$

%%88

\ex[m21] dOKAZHITE, CHTO $(q, p)$~PRINADLEZHIT KLASSU~$t$ OTNOSITELXNO 
MASSIVA~(16) TOGDA I TOLXKO TOGDA, KOGDA $t$~RAVNO MAKSIMALXNOMU CHISLU 
INDEKSOV~$i_1$,~\dots, $i_t$, TAKIH, CHTO
$$
p_{i_1}<p_{i_2}<\ldots <p_{i_t}=p,\qquad 
q_{i_1}<q_{i_2}<\ldots <q_{i_t}=q.
$$

\rex[m24] pOKAZHITE, CHTO SOOTVETSTVIE V TEOREME~A MOZHNO TAKZHE 
USTANOVITX PUTEM POSTROENIYA TAKOJ TABLICY:
\ctable{
#\hfil\bskip &\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip\cr
sTROKA~0 & 1      & 3      & 5      & 6      & 8      \cr
sTROKA~1 & 7      & 2      & 9      & 5      & 3      \cr
sTROKA~2 & \infty & 7      & \infty & 9      & 5      \cr
sTROKA~3 &        & \infty &        & \infty & 7      \cr
sTROKA~4 &        &        &        &        & \infty \cr
}
zDESX V STROKAH~0 I~1 ZAPISAN DANNYJ DVUSTROCHNYJ MASSIV. pRI~$k\ge1$ 
STROKA~$k+1$ OBRAZUETSYA IZ STROKI~$k$ SLEDUYUSHCHIM OBRAZOM:
{\medskip\narrower
\item{a)}~uSTANOVITX~$p\asg\infty$.
%
\item{b)}~pUSTX STOLBEC~$j$---SAMYJ LEVYJ STOLBEC, V KOTOROM STROKA~$k$ 
SODERZHIT CELOE CHISLO~$<p$, A SOOTVETSTVUYUSHCHEE MESTO V STROKE~$k+1$ NE 
ZAPOLNENO. eSLI TAKOGO STOLBCA NET I~$p=\infty$, TO STROKA~$k+1$ 
ZAPOLNENA; ESLI TAKOGO STOLBCA NET I~$p<\infty$, TO VOZVRATITXSYA K~(a).
%
\item{c)}~vSTAVITX~$p$ V STOLBEC~$j$ V STROKE~$k+1$, POTOM USTANOVITX~$p$ 
RAVNYM |LEMENTU STOLBCA~$j$ I STROKI~$k$ I VERNUTXSYA K~(b).
\medskip}

pOSLE TOGO KAK TABLICA TAKIM OBRAZOM POSTROENA, STROKA~$k$ TABLO~$P$ 
SOSTAVLYAETSYA IZ TEH CELYH CHISEL STROKI~$k$ |TOJ TABLICY, KOTORYE 
OTSUTSTVUYUT V STROKE~$(k+1)$; STROKA~$k$ TABLO~$Q$ STROITSYA IZ TEH CELYH 
CHISEL STROKI~0, KOTORYE NAHODYATSYA V STOLBCAH, SODERZHASHCHIH~$\infty$ V 
STROKE~$(k+1)$.

\ex[M26] (m.~p.~shYUCENBERZHE). pUSTX~$\pi$---INVOLYUCIYA S 
$k$~NEPODVIZHNYMI TOCHKAMI. pOKAZHITE, CHTO TABLO, SOOTVETSTVUYUSHCHEE~$\pi$ V 
DOKAZATELXSTVE SLEDSTVIYA IZ TEOREMY~B, SODERZHIT ROVNO $k$~STOLBCOV 
NECHETNOJ DLINY.

\rex[m30] pUSTX~$a_1\,\ldots\,a_{j-1}\,a_j\,\ldots\,a_n$---PERESTANOVKA 
RAZLICHNYH |LEMENTOV I~$1<j\le n$.
pERESTANOVKA~$a_1\,\ldots\,a_{j-2}\,a_j\,a_{j-1}\,a_{j+1}\,\ldots\,a_n$, 
POLUCHAYUSHCHAYASYA IZ ISHODNOJ, ESLI POMENYATX MESTAMI~$a_{j-1}$ I~$a_j$, 
NAZYVAETSYA "DOPUSTIMOJ", ESLI LIBO
{\medskip\narrower
\item{i)}~$j\ge 3$ I~$a_{j-2}$ LEZHIT MEZHDU~$a_{j-1}$ I~$a_j$, LIBO
\item{ii)}~$j<n$ I~$a_{j+1}$ LEZHIT MEZHDU~$a_{j-1}$ I~$a_j$.
\medskip}
nAPRIMER, V PERESTANOVKE~$1\,5\,4\,6\,8\,3\,7$ MOZHNO PROIZVESTI ROVNO 
TRI DOPUSTIMYE ZAMENY: MOZHNO POMENYATX MESTAMI~$1$ I~$5$, POSKOLXKU~$1<4<5$;
MOZHNO POMENYATX MESTAMI~$8$ I~$3$, POSKOLXKU~$3<6<8$ (ILI~$3<7<8$); 
ODNAKO NELXZYA MENYATX MESTAMI~$5$ I~$4$ ILI~$3$ I~$7$.
{\medskip\narrower
\item{a)}~dOKAZHITE, CHTO PRI DOPUSTIMOJ ZAMENE NE MENYAETSYA TABLO~$P$, 
KOTOROE POLUCHAETSYA IZ PERESTANOVKI PUTEM POSLEDOVATELXNOJ VSTAVKI 
|LEMENTOV~$a_1$, $a_2$,~\dots, $a_n$ V PERVONACHALXNO PUSTOE TABLO.
%
\item{b)}~oBRATNO, POKAZHITE, CHTO LYUBYE DVE PERESTANOVKI, 
SOOTVETSTVUYUSHCHIE ODNOMU I TOMU ZHE TABLO~$P$, MOZHNO PREOBRAZOVATX ODNU V 
DRUGUYU POSLEDOVATELXNOSTXYU ODNOJ ILI BOLEE DOPUSTIMYH ZAMEN. [\emph{uKAZANIE:}
POKAZHITE, CHTO ESLI TABLO~$P$ IMEET FORMU~$(n_1, n_2,~\ldots, n_m)$, TO 
LYUBUYU SOOTVETSTVUYUSHCHUYU EMU PERESTANOVKU PRI POMOSHCHI 
POSLEDOVATELXNOSTI DOPUSTIMYH ZAMEN MOZHNO PREOBRAZOVATX V 
"KANONICHESKUYU PERESTANOVKU"~$P_{m1}\ldots{}P_{mn_m}\ldots{}P_{21}\ldots{}P_{2n_2}P_{11}\ldots{}P_{1n_1}$.]
\medskip}

\rex[m22] pUSTX~$P$---TABLO, SOOTVETSTVUYUSHCHEE PERESTANOVKE~$a_1\,a_2\,\ldots\,a_n$;
S POMOSHCHXYU UPR.~5 DOKAZHITE, CHTO TABLO~$P^T$ SOOTVETSTVUET 
PERESTANOVKE~$a_n\,\ldots\,a_2\,a_1$.
%%89

\ex[m 20] (k.~shENSTED). pUSTX~$P$---TABLO, SOOTVETSTVUYUSHCHEE 
PERESTANOVKE~$a_1\,a_2\,\ldots\,a_n$. dOKAZHITE, CHTO CHISLO \emph{STOLBCOV} 
V~$P$ RAVNO DLINE~$c$ MAKSIMALXNOJ VOZRASTAYUSHCHEJ 
PODPOSLEDOVATELXNOSTI~$a_{i_1}<a_{i_2}<\ldots<a_{i_c}$, 
GDE~$i_1<i_2<\ldots<i_c$; CHISLO \emph{STROK} V~$P$ RAVNO DLINE~$r$ 
MAKSIMALXNOJ UBYVAYUSHCHEJ 
PODPOSLEDOVATELXNOSTI~$a_{j_1}>a_{j_2}>\ldots>a_{j_r}$, 
GDE~$j_1<j_2<\ldots<j_r$.

\ex[m18] (p.~eRD¸SH, g.~sEKERESH). dOKAZHITE, CHTO V LYUBOJ PERESTANOVKE,
 SOSTOYASHCHEJ IZ BOLEE CHEM $n^2$~ |LEMENTOV, IMEETSYA MONOTONNAYA 
PODPOSLEDOVATELXNOSTX DLINY BOLEE~$n$; ODNAKO SUSHCHESTVUYUT PERESTANOVKI 
$n^2$~|LEMENTOV, NE SODERZHASHCHIE MONOTONNYH PODPOSLEDOVATELXNOSTEJ DLINY 
BOLEE~$n$. [\emph{uKAZANIE:} SM.~PREDYDUSHCHEE UPRAZHNENIE.]

\ex[m24] pRODOLZHAYA UPR.~8, NAJDITE "PROSTUYU" FORMULU TOCHNOGO 
CHISLA PERESTANOVOK MNOZHESTVA~$\set{1, 2,~\ldots, n^2}$, NE SODERZHASHCHIH 
MONOTONNYH PODPOSLEDOVATELXNOSTEJ DLINY BOLEE CHEM~$n$.

\ex[m20] dOKAZHITE, CHTO MASSIV~$P$ YAVLYAETSYA TABLO PO OKONCHANII 
RABOTY ALGORITMA~S, ESLI ON BYL TABLO DO |TOGO.

\ex[20] mOZHNO LI VOSSTANOVITX ISHODNYJ VID TABLO~$P$ PO OKONCHANII RABOTY 
ALGORITMA~S, ESLI IZVESTNY TOLXKO ZNACHENIYA~$r$ I~$s$?

\ex[m24] sKOLXKO RAZ VYPOLNYAETSYA SHAG~S3, ESLI ALGORITM~S 
MNOGOKRATNO PRIMENYAETSYA DLYA ISKLYUCHENIYA VSEH |LEMENTOV IZ TABLO~$P$ 
FORMY~$(n_1, n_2,~\ldots, n_m)$? kAKOVO MINIMALXNOE ZNACHENIE |TOJ VELICHINY 
PO VSEM FORMAM, TAKIM, CHTO~$n_1+n_2+\cdots+n_m=n$?

\ex[m28] dOKAZHITE TEOREMU~C.

\ex[m43] nAJDITE BOLEE PRYAMOE DOKAZATELXSTVO CHASTI~(c) TEOREMY~D.

\ex[m20] sKOLXKO PERESTANOVOK 
MULXTIMNOZHESTVA~$\set{l\cdot a, m\cdot b, n\cdot c}$ 
OBLADAYUT TEM SVOJSTVOM, CHTO ESLI CHITATX PERESTANOVKU SLEVA 
NAPRAVO, TO CHISLO PROCHITANNYH BUKV~$c$ NIKOGDA NE PREVYSHAET CHISLA BUKV~$b$,
KOTOROE V SVOYU OCHEREDX NE PREVYSHAET CHISLA BUKV~$a$? (nAPRIMER, 
PERESTANOVKA~$a\,a\,b\,c\,a\,b\,b\,c\,a\,c\,a$ OBLADAET |TIM SVOJSTVOM.)

\ex[m08] sKOLXKIMI SPOSOBAMI MOZHNO TOPOLOGICHESKI OTSORTIROVATX CHASTICHNOE 
UPORYADOCHENIE, PREDSTAVLYAEMOE GRAFOM~(39)?

\ex[vm25] pUSTX
$$
g(x_1, x_2, \ldots, x_n; y)=x_1\Delta(x_1+y, x_2, \ldots, x_n)
+x_2\Delta(x_1, x_2+y, \ldots, x_n)+\cdots+x_n\Delta(x_1, x_2, \ldots, x_n+y).
$$
dOKAZHITE, CHTO
$$
g(x_1, x_2, \ldots, x_n; y)=\left(x_1+x_2+\cdots+x_n+\perm{n}{2}y\right)
\Delta(x_1, x_2, \ldots, x_n).
$$
[\emph{uKAZANIE:} POLINOM~$g$ ODNORODNYJ (VSE SLAGAEMYE IMEYUT ODINAKOVUYU 
SUMMARNUYU STEPENX) I ANTISIMMETRICHNYJ PO~$x$ (ZNAK~$g$ IZMENITSYA, ESLI 
POMENYATX MESTAMI~$x_i$ I~$x_j$).]

\ex[vm30] oBOBSHCHAYA UPR.~17, VYCHISLITE PRI~$m\ge 0$ SUMMU
$$
x_1^m\Delta(x_1+y, x_2, \ldots, x_n)+\Delta x_2^m(x_1, x_2+y, \ldots, x_n)
+\cdots+x_n^m\Delta(x_1, x_2, \ldots, x_n+y).
$$

\ex[m40] nAJDITE FORMULU DLYA OPREDELENIYA CHISLA SPOSOBOV, KOTORYMI MOZHNO 
ZAPOLNITX MASSIV, PODOBNYJ TABLO, NO BEZ PERVYH DVUH KLETOK V PERVOJ
%%90
STROKE; NAPRIMER, MASSIV TAKOJ FORMY:
\picture{1. p.90}
(eLEMENTY V STROKAH I STOLBCAH DOLZHNY RASPOLAGATXSYA V VOZRASTAYUSHCHEM PORYADKE,
 KAK V OBYCHNYH TABLO.)

iNACHE GOVORYA, SKOLXKO IZ~$f(n_1, n_2,~\ldots, n_m)$~TABLO 
FORMY~$(n_1, n_2,~\ldots, n_m)$, SOSTAVLENNYH IZ 
|LEMENTOV~$\set{1, 2,~\ldots, n_1+\cdots+n_m}$, 
SODERZHAT |LEMENTY~$1$ I~$2$ V PERVOJ STROKE?

\rex[m24] dOKAZHITE, CHTO CHISLO SPOSOBOV POMETITX UZLY DANNOGO BINARNOGO 
DEREVA |LEMENTAMI~$\set{1, 2,~\ldots, n}$ TAK, CHTOBY METKA KAZHDOGO UZLA 
BYLA MENXSHE METKI LYUBOGO IZ EGO POTOMKOV, RAVNO CHASTNOMU OT DELENIYA~$n!$ 
NA PROIZVEDENIE "DLIN PODDEREVXEV", T.~E.~KOLICHESTV UZLOV V KAZHDOM 
PODDEREVE. (sR.~S~TEOREMOJ~n.). nAPRIMER, CHISLO SPOSOBOV POMETITX UZLY DEREVA
\picture{1. p.90}
RAVNO~$10!/10\cdot 4\cdot 5\cdot 1\cdot 2\cdot 3\cdot 1\cdot 1\cdot 1\cdot 1=9\cdot 8\cdot 7\cdot 6$.

\ex[BM3I] (r.~m.~tROLL). pUSTX CHISLA~$n_1>n_2>\ldots>n_m$ OPISYVAYUT FORMU 
"SDVINUTOGO TABLO", V KOTOROM STROKA~$i+1$ NACHINAETSYA NA ODNU POZICIYU, 
PRAVEE, CHEM STROKA~$i$; NAPRIMER, SDVINUTOE TABLO FORMY~$(7, 5, 4, 1)$
IZOBRAZHENO NA DIAGRAMME
\picture{3. p.90}
dOKAZHITE, CHTO CHISLO SPOSOBOV ZAPOLNITX SDVINUTOE TABLO 
FORMY~$(n_1, n_2,~\ldots, n_m)$ CHISLAMI~$1$, $2$,~\dots, 
$n=n_1+n_2+\cdots n_m$ TAK, CHTOBY 
CHISLA VO VSEH STROKAH I STOLBCAH RASPOLAGALISX V VOZRASTAYUSHCHEM PORYADKE, 
RAVNO CHASTNOMU OT DELENIYA~$n!$ NA PROIZVEDENIE "DLIN OBOBSHCHENNYH 
UGOLKOV"; NA RISUNKE ZASHTRIHOVAN OBOBSHCHENNYJ UGOLOK DLINY~$11$, 
SOOTVETSTVUYUSHCHIJ KLETKE STROKI~$1$ I STOLBCA~$2$. (uGOLKI V LEVOJ CHASTI 
MASSIVA, IMEYUSHCHEJ VID "PEREVERNUTOJ LESTNICY", IMEYUT
%% 91
FORMU BUKVY~U, POVERNUTOJ NA~$90^\circ$, A NE BUKVY~L.) iTAK, SUSHCHESTVUET
$$
17! / 12\cdot 11\cdot 8\cdot 7\cdot 5\cdot 4\cdot 1\cdot 9\cdot 6\cdot 
5\cdot 3\cdot 2\cdot 5\cdot 4\cdot 2\cdot 1\cdot 1
$$
SPOSOBOV ZAPOLNITX IZOBRAZHENNUYU VYSHE FORMU TAK, CHTOBY |LEMENTY VO 
VSEH STROKAH I STOLBCAH RASPOLAGALISX V VOZRASTAYUSHCHEM PORYADKE.

\rex[vm30] (d.~aNDR|). chEMU RAVNO CHISLO~$A_n$ SPOSOBOV ZAPOLNITX 
CHISLAMI~$\set{1, 2,~\ldots, n}$ MASSIV IZ $n$~YACHEEK
\picture{p.91}
TAK, CHTOBY VO VSEH STROKAH I STOLBCAH ONI RASPOLAGALISX V 
VOZRASTAYUSHCHEM PORYADKE? nAJDITE PROIZVODYASHCHUYU FUNKCIYU~$g(z)=\sum A_n z^n/n!$

\ex[M39] sKOLXKIMI SPOSOBAMI MOZHNO ZAPOLNITX MASSIV 
FORMY~$(n_1, n_2,~\ldots, n_m)$ |LEMENTAMI MNOZHESTVA~$\set{1, 2,~\ldots, N}$, \emph{ESLI 
DOPUSKAYUTSYA ODINAKOVYE |LEMENTY,} PRICHEM V STROKAH |LEMENTY DOLZHNY 
RASPOLAGATXSYA V NEUBYVAYUSHCHEM PORYADKE, A V STOLBCAH---V STROGO VOZRASTAYUSHCHEM? 
nAPRIMER,
PROSTUYU FORMU IZ $m$~STROK $(1, 1,~\ldots, 1)$ MOZHNO ZAPOLNITX $\perm{N}{m}$~SPOSOBAMI;
FORMU IZ ODNOJ STROKI~$m$ MOZHNO ZAPOLNITX $\perm{m+N-1}{m}$~SPOSOBAMI; 
FORMU~$(2, 2)$ MOZHNO ZAPOLNITX ${1\over3}\perm{N+1}{2}\perm{N}{2}$~SPOSOBAMI.

\ex[m28] dOKAZHITE, CHTO
$$
\displaylines{
\sum_{\scriptstyle q_1+\cdots+q_=t \atop \scriptstyle 0\le q_1,~\ldots, q_n\le m}
\perm{m}{q_1}\ldots\perm{m}{q_n}\Delta(q_1,~\ldots, q_n)^2=\hfill\cr
\hfill =n!\perm{nm-(n^2-n)}{t-{1\over 2}(n^2-n)} \perm{m}{n-1} 
\perm{m}{n-2}\ldots \perm{m}{0}\Delta(n-1,~\ldots, 0)^2. \cr
}
$$
[\emph{uKAZANIYA:} DOKAZHITE, 
CHTO~$\Delta(k_1+n-1,~\ldots, k_n)=\Delta(m-k_n+n-1,~\ldots, m-k_1)$; 
RAZLOZHITE TABLO FORMY~$n\times (m-n+1)$ SPOSOBOM, ANALOGICHNYM~(38), I 
PREOBRAZUJTE SUMMU, KAK PRI VYVODE TOZHDESTVA~(36).]


\ex[m20] pOCHEMU~(42) YAVLYAETSYA PROIZVODYASHCHEJ FUNKCIEJ DLYA INVOLYUCIJ?

\ex[vm21] vYCHISLITE~$\int_{-\infty}^\infty x^t \exp(-2x^2/ \sqrt{n})\,dx$ 
PRI NEOTRICATELXNOM CELOM~$t$.

\ex[m24] pUSTX~$Q$---TABLO yaNGA IZ |LEMENTOV~$\set{1, 2,~\ldots, n}$, I 
PUSTX |LEMENT~$t$ NAHODITSYA V STROKE~$r_i$ I STOLBCE~$c_i$. mY GOVORIM, 
CHTO~$i$ "VYSHE"~$j$, ESLI~$r_i<r_j$.
{\medskip\narrower
\item{a)}~dOKAZHITE, CHTO PRI~$1\le i < n$ |LEMENT~$i$ VYSHE~$i+1$ TOGDA I 
TOLXKO TOGDA, KOGDA~$c_i\ge c_{i+1}$.
%%92
\item{b)}~pUSTX~$Q$ TAKOE, CHTO $(P, Q)$~SOOTVETSTVUYUT PERESTANOVKE
$$
\pmatrix{
1 & 2 & \ldots & n \cr
a_1 & a_2 & \ldots & a_n \cr
}
$$
dOKAZHITE, CHTO~$i$ VYSHE~$i+1$ TOGDA I TOLXKO TOGDA, KOGDA~$a_i>a_{i+1}$.
(sLEDOVATELXNO, MOZHNO NAJTI CHISLO OTREZKOV PERESTANOVKI, ZNAYA TOLXKO~$Q$. 
eTOT REZULXTAT POLUCHEN shYUCENBERZHE.)
%
\item{c)}~dOKAZHITE, CHTO PRI~$1\le i < n$ |LEMENT~$i$ VYSHE~$i+1$ V~$Q$ 
TOGDA I TOLXKO TOGDA, KOGDA~$i+1$ VYSHE~$i$ V~$Q^S$.
\medskip}

\ex[m47] kAKOVO ASIMPTOTICHESKOE POVEDENIE SREDNEJ DLINY MAKSIMALXNOJ 
VOZRASTAYUSHCHEJ POSLEDOVATELXNOSTI V SLUCHAJNOJ PERESTANOVKE 
MNOZHESTVA~$\set{1, 2,~\ldots, n}$? (eTO SREDNYAYA DLINA PERVOJ STROKI V 
SOOTVETSTVII IZ TEOREMY~A. oBSHIRNYE TABLICY, VYCHISLENNYE r.~m.~bAEROM 
I~p.~bROKOM [{\sl Math. Comp.,\/} {\bf 22} (1968), 385--410], V SVYAZI S TEM, 
CHTO ONI NAZVALI "ESTESTVENNOJ SORTIROVKOJ", POZVOLYAYUT PREDPOLOZHITX, CHTO 
SREDNEE~$l_n$ RAVNO PRIMERNO~$2\sqrt{n}$; l.~shEPP I~b.~lOGAN DOKAZALI, 
CHTO~$\liminf_{n\to\infty} l_n / \sqrt{n}\ge 2$ (V PECHATI).

\ex[m50] iSSLEDUJTE TREHMERNYE MASSIVY, S TEM CHTOBY PONYATX, KAKIE SVOJSTVA 
DVUMERNYH TABLO MOZHNO OBOBSHCHITX.

\ex[m42] (m.~p.~shYUCENBERZHE). pOKAZHITE, CHTO OPERACIYA PEREHODA OT~$P$ 
K~$P^S$---CHASTNYJ SLUCHAJ OPERACII, KOTORUYU MOZHNO SVYAZATX S LYUBYM KONECHNYM 
CHASTICHNO UPORYADOCHENNYM MNOZHESTVOM, A NE TOLXKO S TABLO. pOMETXTE |LEMENTY 
CHASTICHNO UPORYADOCHENNOGO MNOZHESTVA CELYMI CHISLAMI~$\set{1, 2,~\ldots, n}$ 
TAK, CHTOBY |TA SISTEMA METOK BYLA SOGLASOVANA S CHASTICHNYM 
UPORYADOCHENIEM. nAJDITE DVOJSTVENNUYU SISTEMU METOK, ANALOGICHNUYU~(26), PUTEM 
POSLEDOVATELXNOGO UDALENIYA METOK~$1$, $2$,~\dots, PEREDVIGAYA PRI |TOM 
DRUGIE METKI SPOSOBOM, PODOBNYM ALGORITMU~S, I POMESHCHAYA METKI~(1), (2),~\dots{} 
NA OSVOBODIVSHIESYA MESTA. pOKAZHITE, CHTO |TA OPERACIYA, ESLI EE 
MNOGOKRATNO PRIMENYATX K DVOJSTVENNOJ SISTEME METOK S OBRATNYM OTNOSHENIEM 
PORYADKA DLYA CHISEL, DAET ISHODNUYU SISTEMU METOK; ISSLEDUJTE DRUGIE SVOJSTVA 
|TOJ OPERACII

\ex[vm30] pUSTX~$x_n$---CHISLO SPOSOBOV RAZMESTITX~$n$ VZAIMNO 
NEATAKUYUSHCHIH LADEJ NA SHAHMATNOJ DOSKE RAZMERA~$n\times n$ TAKIM OBRAZOM, 
CHTO RASPOLOZHENIE NE MENYAETSYA PRI OTRAZHENII DOSKI OTNOSITELXNO ODNOJ IZ 
GLAVNYH DIAGONALEJ I PRI POVOROTE NA~$180^\circ$. nAJDITE ASIMPTOTICHESKOE 
POVEDENIE~$x_n$.

%% 93
\bye