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

RAVNO CHISLU PERESTANOVOK |TIH CIKLOV (MULXTINOMIALXNOMU KO|FFICIENTU),
PROSUMMIROVANNOMU PO VSEM ZNACHENIYAM~$k$:
$$
\eqalignno{
N(A, B, C, m) &=
\sum_k { (C+m-k)! \over (m-k)! (C-A+m-k)! (C-B+m-k)!k! (A+B-C-2m+k)!}=\cr
&= \sum_k \perm{m}{k}\perm{A}{m}\perm{A-m}{C-B+m-k}\perm{C+m-k}{A}. &(25) \cr
}
$$
sRAVNIVAYA |TO S~(23), OBNARUZHIVAEM, CHTO DOLZHNO VYPOLNYATXSYA
TOZHDESTVO
$$
\sum_k \perm{m}{k} \perm{A-m}{C-B+m-k}\perm{C+m-k}{A}=
\perm{B}{C-A+m}\perm{C}{B-m}.
\eqno(26)
$$
oKAZYVAETSYA, S |TIM TOZHDESTVOM MY VSTRECHALISX V UPR.~1.2.6-31:
$$
\sum_j \perm{M-R+S}{j} \perm{N+R-S}{N-j}\perm{R+j}{M+N}=
\perm{R}{M}\perm{S}{N},
\eqno(27)
$$
GDE $M=A+B-C-m$, $N=C-B+m$, $R=B$, $S=C$, A~$j=C-B+m-k$.

aNALOGICHNO MOZHNO PODSCHITATX CHISLO PERESTANOVOK
MULXTIMNOZHESTVA~$\set{A\cdot a, B\cdot b, C\cdot c, D\cdot d}$, ESLI
KOLICHESTVO STOLBCOV RAZLICHNYH TIPOV V NIH ZADANO SLEDUYUSHCHIM OBRAZOM:
$$\let\ds=\displaystyle
\matrix{
\hbox{sTOLBEC:}\hfill   & a & a   & b & b   & c     & c   & d   & d    \cr
                        & d & b   & a & c   & b     & d   & a   & c    \cr
\hbox{kOLICHESTVO:}\hfill& r & A-r & q & B-q & B-A+r & D-r & A-q & D-A+q\cr
}
\eqno(28)
$$
(zDESX~$A+C=B+D$.) vOZMOZHNYMI CIKLAMI V RAZLOZHENII TAKOJ PERESTANOVKI NA
PROSTYE MNOZHITELI BUDUT
$$
\matrix{
\hbox{cIKL:}\hfill       & (a\, b) & (b\, c) & (c\, d) & (d\, a) & (a\, b\, c\, d) & (d\, c\, b\, a)\cr
\hbox{kOLICHESTVO:}\hfill & A-r-s   & B-q-s   & D-r-s   & A-q-s   & s               & q-A+r+s \cr
}
\eqno(29)
$$
PRI NEKOTOROM~$s$ (SM.~UPR.~12). v |TOM SLUCHAE CIKLY~$(a\, b)$ I~$(c\,d)$
KOMMUTIRUYUT, TAK ZHE KAK I CIKLY~$(b\, c)$ I~$(d\,a)$, PO|TOMU
NEOBHODIMO PODSCHITATX CHISLO RAZLICHNYH RAZLOZHENIJ NA PROSTYE MNOZHITELI.
oKAZYVAETSYA (SM.~UPR.~10), VSEGDA SUSHCHESTVUET EDINSTVENNOE RAZLOZHENIE,
TAKOE, CHTO CIKL~$(a\, b)$ NIKOGDA NE SLEDUET NEPOSREDSTVENNO ZA~$(c\, d)$,
A~$(b\, c)$ NE VSTRECHAETSYA SRAZU POSLE~$(d\,a)$.
%% 47
oTSYUDA, POLXZUYASX REZULXTATOM UPR.~13, POLUCHAEM TOZHDESTVO
$$
\displaylines{
\sum_{s,t}\perm{B}{t}\perm{A-q-s}{A-r-s-t}\perm{B+D-r-s-t}{B-q-s}\times
{D! \over (D-r-s)!(A-q-s)!s!(q-A+r+s)!}=\hfill\cr
\hfill=\perm{A}{r}\perm{B+D-A}{D-r}\perm{B}{q}\perm{D}{A-q}.\cr
}
$$
vYNOSYA IZ OBEIH CHASTEJ MNOZHITELX~$\perm{D}{A-q}$ I SLEGKA UPROSHCHAYA
FAKTORIALY, PRIHODIM K SLOZHNOMU NA VID PYATIPARAMETRICHESKOMU TOZHDESTVU
BINOMIALXNYH KO|FFICIENTOV:
$$
\sum_{s, t} \perm{B}{t}\perm{A-r-t}{s}\perm{B+D-r-s-t}{D+q-r-t}\times
\perm{D-A+q}{D-r-s}\perm{A-q}{r+t-q}=
\perm{A}{r}\perm{B+D-A}{D-r}\perm{B}{q}.
\eqno(30)
$$
pOLXZUYASX TOZHDESTVOM~(27), MOZHNO VYPOLNITX SUMMIROVANIE PO~$s$, A
POLUCHIVSHAYASYA SUMMA PO~$t$ LEGKO VYCHISLYAETSYA. tAKIM OBRAZOM, . POSLE VSEJ
PRODELANNOJ RABOTY NAM NE POSCHASTLIVILOSX OBNARUZHITX KAKOE-LIBO
TOZHDESTVO, KOTOROE MY BY ESHCHE NE UMELI VYVODITX. nO MY PO KRAJNEJ MERE
NAUCHILISX PODSCHITYVATX CHISLO PERESTANOVOK OPREDELENNOGO VIDA DVUMYA
RAZLICHNYMI SPOSOBAMI, A |TI METODY PODSCHETA---HOROSHAYA PODGOTOVKA K RESHENIYU
ZADACH, KOTORYE ESHCHE VPEREDI.

\excercises
\ex[m05] \emph{dA ILI NET?} pUSTX~$M_1$  I~$M_2$---MULXTIMNOZHESTVA. eSLI
$\alpha$---PERESTANOVKA~$M_1$, A~$\beta$---PERESTANOVKA~$M_2$,
TO~$\alpha\T \beta$---PERESTANOVKA~$M_1\cup M_2$.

\ex[10] sOEDINITELXNOE PROIZVEDENIE
PERESTANOVOK~$c\,a\,d\,a\,b$ I~$b\,d\,d\,a\,d$ VYCHISLENO V~(5);
NAJDITE SOEDINITELXNOE PROIZVEDENIE~$b\,d\,d\,a\,d\T c\,a\,d\,a\,b$,
KOTOROE POLUCHAETSYA, ESLI SOMNOZHITELI POMENYATX MESTAMI.

\ex[m13] vERNO LI UTVERZHDENIE, OBRATNOE~(9)? iNACHE GOVORYA, ESLI
PERESTANOVKI~$\alpha$ I~$\beta$ KOMMUTATIVNY OTNOSITELXNO OPERACII
SOEDINITELXNOGO PROIZVEDENIYA, TO SLEDUET LI IZ |TOGO, CHTO ONI NE
SODERZHAT OBSHCHIH BUKV?

\ex[M11] kANONICHESKOE RAZLOZHENIE PERESTANOVKI~(12) V SMYSLE TEOREMY~A
PRI~$a<b<c<d$ ZADAETSYA FORMULOJ~(17). nAJDITE SOOTVETSTVUYUSHCHEE
KANONICHESKOE RAZLOZHENIE V SLUCHAE, KOGDA~$d<c<b<a$.

\ex[m23] v USLOVII~(b) TEOREMY~B TREBUETSYA, CHTOBY~$x<y$; CHTO BUDET, ESLI
OSLABITX |TO TREBOVANIE, ZAMENIV EGO NA~$x\le y$?

\ex[m15] sKOLXKO SUSHCHESTVUET CEPOCHEK, SOSTOYASHCHIH ROVNO IZ~$m$ BUKV~$a$ I~$n$
BUKV~$b$, TAKIH, CHTO ROVNO~$k$ BUKV~$b$ STOYAT NEPOSREDSTVENNO PERED
BUKVAMI~$a$ I NET NIKAKIH DRUGIH BUKV, KROME~$a$ I~$b$?

\ex[m21] sKOLXKO CEPOCHEK IZ BUKV~$a$, $b$, $c$, UDOVLETVORYAYUSHCHIH
USLOVIYAM~(18), NACHINAETSYA S BUKVY~$a$? S BUKVY~$b$? S BUKVY~$c$?

\rex[20] nAJDITE VSE RAZLOZHENIYA PERESTANOVKI~(12) NA DVA
MNOZHITELYA~$\alpha\T \beta$.

%%48
\ex[33] nAPISHITE PROGRAMMY DLYA evm, KOTORYE BY PROIZVODILI RAZLOZHENIYA
ZADANNOJ PERESTANOVKI MULXTIMNOZHESTVA, OPISANNYE V TEOREMAH~A I~C.

\rex[M30] \emph{dA ILI NET?} sOGLASNO TEOREME~C, RAZLOZHENIE NA PROSTYE
MNOZHITELI NE VPOLNE ODNOZNACHNO, TEM NE MENEE MOZHNO SLEDUYUSHCHIM OBRAZOM
OBESPECHITX EDINSTVENNOSTX. "sUSHCHESTVUET LINEJNOE UPORYADOCHENIE~$\prec$ NA
MNOZHESTVE PROSTYH PERESTANOVOK, TAKOE, CHTO KAZHDAYA PERESTANOVKA
MULXTIMNOZHESTVA IMEET EDINSTVENNOE
RAZLOZHENIE~$\sigma_1 \T \sigma_2 \T \ldots \T \sigma_n$ NA PROSTYE MNOZHITELI,
UDOVLETVORYAYUSHCHEE
USLOVIYU~$\sigma_i \preceq \sigma_{i+1}$, ESLI $\sigma_i$ KOMMUTIRUET
S~$\sigma_{i+1}$, PRI~$1\le i < n$".

\ex[m26] pUSTX~$\sigma_1$, $\sigma_2$,~\dots, $\sigma_t$---CIKLY BEZ
POVTORYAYUSHCHIHSYA |LEMENTOV. oPREDELIM CHASTICHNOE UPORYADOCHENIE~$\prec$ NA
MNOZHESTVE $t$~|LEMENTOV $\set{x_1, \ldots, x_t}$, POLAGAYA~$x_i\prec x_j$,
ESLI~$i<j$ I $\sigma_i$  IMEET PO KRAJNEJ MERE ODNU OBSHCHUYU BUKVU
S~$\sigma_j$. dOKAZHITE SLEDUYUSHCHUYU SVYAZX MEZHDU TEOREMOJ~C I PONYATIEM
"TOPOLOGICHESKOJ SORTIROVKI" (P.~2.2.3): \dfn{CHISLO RAZLICHNYH RAZLOZHENIJ
PERESTANOVKI~$\sigma_1\T \sigma_2 \T \ldots \T \sigma_t$ NA PROSTYE
MNOZHITELI RAVNO KOLICHESTVU SPOSOBOV TOPOLOGICHESKI OTSORTIROVATX DANNOE
CHASTICHNOE UPORYADOCHENIE.} (nAPRIMER, V SOOTVETSTVII S~(22) SUSHCHESTVUET PYATX
SPOSOBOV TOPOLOGICHESKI OTSORTIROVATX UPORYADOCHENIE~$x_1\prec x_3$,
$x_2\prec x_4$, $x_1\prec x_4$.) oBRATNO, ESLI NA MNOZHESTVE IZ
$t$~|LEMENTOV ZADANO KAKOE-TO CHASTICHNOE UPORYADOCHENIE, TO SUSHCHESTVUET
MNOZHESTVO CIKLOV
$$
\set{\sigma_1, \sigma_2,\ldots, \sigma_t},
$$
KOTOROE OPREDELYAET |TO CHASTICHNOE UPORYADOCHENIE UKAZANNYM SPOSOBOM.

\ex[m16] pOKAZHITE, CHTO SOOTNOSHENIYA~(29) YAVLYAYUTSYA SLEDSTVIYAMI PREDPOLOZHENIJ~(28).

\ex[m21] dOKAZHITE, CHTO CHISLO PERESTANOVOK
MULXTIMNOZHESTVA~$\set{A\cdot a, B\cdot b, C\cdot c, D\cdot d, E\cdot e, F\cdot f}$,
NE SODERZHASHCHIH PAR STOYASHCHIH RYADOM BUKV~$c\,a$ I~$d\,b$, RAVNO
$$
\sum_t \perm{D}{A-t}\perm{A+B+E+F}{t}\perm{A+B+C+E+F-t}{B}\perm{C+D+E+F}{C,D,E,F}.
$$

\ex[M30] oDIN IZ SPOSOBOV OPREDELITX PERESTANOVKU~$\pi^{-1}$,
"OBRATNUYU" PERESTANOVKE~$\pi$, KOTORYJ PODSKAZAN NAM DRUGIMI OPREDELENIYAMI
|TOGO PUNKTA, |TO POMENYATX MESTAMI STROKI DVUSTROCHNOGO PREDSTAVLENIYA~$\pi$
I ZATEM VYPOLNITX USTOJCHIVUYU SORTIROVKU STOLBCOV, TAK CHTOBY |LEMENTY
VERHNEJ STROKI RASPOLOZHILISX V NEUBYVAYUSHCHEM PORYADKE. nAPRIMER,
ESLI~$a<b<c<d$, TO IZ |TOGO OPREDELENIYA SLEDUET,
CHTO~$c\,a\,b\,d\,d\,a\,b\,d\,a\,d^{-1}=a\,c\,d\,a\,d\,a\,b\,b\,d\,d$.

iSSLEDUJTE SVOJSTVA |TOJ OPERACII OBRASHCHENIYA; IMEETSYA LI, NAPRIMER,
KAKAYA-NIBUDX PROSTAYA SVYAZX MEZHDU NEJ I SOEDINITELXNYM
PROIZVEDENIEM? mOZHNO LI PODSCHITATX CHISLO PERESTANOVOK, TAKIH,
CHTO~$\pi=\pi^{-1}$?

\rex[m25] dOKAZHITE, CHTO PERESTANOVKA~$a_1\ldots{}a_n$ MULXTIMNOZHESTVA
$$
\set{n_1\cdot x_1, n_2\cdot x_2, \ldots, n_m\cdot x_m},
$$
GDE~$x_1<x_2<\ldots<x_n$ I~$n_1+n_2+\cdots+n_m=n$, YAVLYAETSYA CIKLOM TOGDA I
TOLXKO TOGDA, KOGDA NAPRAVLENNYJ GRAF S VERSHINAMI~$\set{x_1, x_2,~\ldots, x_m}$
I DUGAMI IZ~$x_j$ V~$a_{n_1+\cdots+n_j}$ SODERZHIT ROVNO ODIN
ORIENTIROVANNYJ CIKL. v |TOM SLUCHAE CHISLO
SPOSOBOV PREDSTAVITX PERESTANOVKU V VIDE CIKLA RAVNO DLINE |TOGO
ORIENTIROVANNOGO CIKLA. nAPRIMER, NAPRAVLENNYM GRAFOM, SOOTVETSTVUYUSHCHIM PERESTANOVKE
$$
\pmatrix{
a & a & a & b & b & c & c & c & d & d \cr
d & c & b & a & c & a & a & b & d & c \cr
}, \hbox{BUDET}
$$
% !!! KARTINKU VNUTRX
\picture{p. 48}
A DVA SPOSOBA PREDSTAVITX PERESTANOVKU V VIDE
CIKLA---|TO~$(b\,a\,d\,d\,c\,a\,c\,a\,b\,c)$
I~$(c\,a\,d\,d\,c\,a\,c\,b\,a\,b)$.

%%49
\ex[m35] v PREDYDUSHCHEM PUNKTE, FORMULA~(8), MY NASHLI PROIZVODYASHCHUYU FUNKCIYU
DLYA \emph{INVERSIJ} PERESTANOVOK V CHASTNOM SLUCHAE, KOGDA V
PERESTANOVKE UCHASTVUYUT |LEMENTY MNOZHESTVA. pOKAZHITE, CHTO V OBSHCHEM SLUCHAE
PERESTANOVOK \emph{MULXTIMNOZHESTVA} PROIZVODYASHCHAYA FUNKCIYA DLYA INVERSIJ
RAVNA "$z\hbox{-MULXTINOMIALXNOMU}$ KO|FFICIENTU"
$$
\perm{n}{n_1, n_2,~\ldots}_z={n!_z\over n_1!_z n_2!_z\ldots},
\rem{GDE~$m!_z=(1-z)(1-z^2)\ldots(1-z^m)$.}
$$ [sR.~S~(3); $z\hbox{-BINOMIALXNYE}$ KO|FFICIENTY OPREDELENY V
FORMULE~(1.2.6-37).]

\ex[M24] pOLXZUYASX PROIZVODYASHCHEJ FUNKCIEJ, NAJDENNOJ V UPR.~16, VYCHISLITE
SREDNEE ZNACHENIE I DISPERSIYU DLYA CHISLA INVERSIJ V SLUCHAJNOJ PERESTANOVKE
MULXTIMNOZHESTVA.

\ex[M30] (p.~a.~mAK-mAGON.) \emph{iNDEKS}
PERESTANOVKI~$a_1\,a_2\ldots{}a_n$ BYL OPREDELEN V PREDYDUSHCHEM PUNKTE;
MY DOKAZALI, CHTO CHISLO
PERESTANOVOK DANNOGO MNOZHESTVA, IMEYUSHCHIH DANNYJ INDEKS~$k$, RAVNO CHISLU
PERESTANOVOK, IMEYUSHCHIH $k$~INVERSIJ. vERNO LI |TO DLYA PERESTANOVOK
ZADANNOGO MULXTIMNOZHESTVA?

\ex[vm28] oPREDELIM \emph{FUNKCIYU m¸BIUSA}~$\mu(\pi)$ PERESTANOVKI~$\pi$:
ONA RAVNA~$0$, ESLI $\pi$~SODERZHIT POVTORYAYUSHCHIESYA |LEMENTY, I~$(-1)^k$ V
PROTIVNOM SLUCHAE, ESLI~$\pi$---PROIZVEDENIE $k$~PROSTYH PERESTANOVOK.
(sR.\ S OPREDELENIEM OBYCHNOJ FUNKCII m¸BIUSA, UPR.~4.5.2-10.) (a)~dOKAZHITE,
CHTO ESLI~$\pi\ne\varepsilon$, TO
$$
\sum \mu(\lambda)=0,
$$
GDE SUMMA BERETSYA PO VSEM PERESTANOVKAM~$\lambda$, YAVLYAYUSHCHIMSYA LEVYMI
SOMNOZHITELYAMI V RAZLOZHENII~$\pi$ (T.~E.~$\lambda\T\rho=\pi$,
GDE~$\rho$---NEKOTORAYA PERESTANOVKA) (b)~dOKAZHITE, CHTO
ESLI~$x_1<x_2<\ldots<x_m$ I~$\pi=x_{i_1} x_{i_2} \ldots x_{i_n}$,
GDE~$1\le i_l \le m$ PRI~$1\le j \le n$, TO
$$
\mu(\pi)=(-1)^m \varepsilon (i_1 i_2 \ldots i_n),
\rem{GDE~$\varepsilon(i_1 i_2 \ldots i_n)=\sign \prod_{1\le j < k \le n} (i_k-i_j)$.}
$$


\ex[vm33] (d.~fOATA.) pUSTX~$(a_{ij})$---PROIZVOLXNAYA MATRICA
DEJSTVITELXNYH CHISEL. pOLXZUYASX OBOZNACHENIYAMI UPR.~19~(b),
OPREDELIM~$\nu(\pi)=a_{i_1 j_1}\ldots a_{i_n j_n}$, ESLI DVUSTROCHNOE
PREDSTAVLENIE PERESTANOVKI~$\pi$ TAKOVO:
$$
\pmatrix{
x_{i_1} & x_{i_2} & \ldots & x_{i_n} \cr
x_{j_1} & x_{j_2} & \ldots & x_{j_n} \cr
}.
$$
eTA FUNKCIYA POLEZNA PRI VYCHISLENII PROIZVODYASHCHIH FUNKCIJ DLYA PERESTANOVOK
MULXTIMNOZHESTVA, POTOMU CHTO~$\sum \nu(\pi)$, GDE SUMMA BERETSYA PO VSEM
PERESTANOVKAM~$\pi$ MULXTIMNOZHESTVA
$$
\set{n_1\cdot x_1, \ldots, n_m\cdot x_m},
$$
BUDET PROIZVODYASHCHEJ FUNKCIEJ DLYA CHISLA PERESTANOVOK, UDOVLETVORYAYUSHCHIH
NEKOTORYM OGRANICHENIYAM. nAPRIMER, ESLI POLOZHITX~$a_{ij}=z$ PRI~$i=j$
I~$a_{ij}=1$  PRI~$i\ne j$, TO~$\sum \nu(\pi)$---PROIZVODYASHCHAYA FUNKCIYA DLYA
CHISLA "NEPODVIZHNYH TOCHEK" (STOLBCOV, V KOTORYH VERHNIJ I NIZHNIJ |LEMENTY
RAVNY). chTOBY MOZHNO BYLO ISSLEDOVATX~$\sum \nu(\pi)$ DLYA VSEH
MULXTIMNOZHESTV ODNOVREMENNO, RASSMOTRIM FUNKCIYU
$$
G=\sum \pi\nu(\pi),
$$
GDE SUMMA BERETSYA PO VSEM~$\pi$ IZ MNOZHESTVA~$\set{x_1,~\ldots, x_m}^*$
VSEH PERESTANOVOK MULXTIMNOZHESTV, SODERZHASHCHIH |LEMENTY~$x_1$,~\dots, $x_m$,
I POSMOTRIM NA KO|FFICIENTY PRI~$x_1^{n_1}\ldots x_m^{nm}$ V~$G$.

%%50

v |TOJ FORMULE DLYA~$G$ BUDEM RASSMATRIVATX~$\pi$ KAK PROIZVEDENIE
PEREMENNYH~$x$. nAPRIMER, PRI~$m=2$ IMEEM
$$
\eqalign{
G &= 1 + x_1\nu(x_1) +x_2\nu(x_2) +x_1x_1\nu(x_1x_1) +x_1x_2\nu(x_1x_2)+
x_2x_1\nu(x_2x_1) +x_2 x_2 \nu(x_2 x_2)+\ldots=\cr
&=1+ x_1 a_{11} +x_2 a_{22} +x_1^2 a_{11}^2  +x_1 x_2 a_{11}a_{22} +x_1
x_2 a_{21} a_{12} +x_2^2 a_{22}^2 +\ldots\,.\cr
}
$$
tAKIM OBRAZOM, KO|FFICIENT PRI~$x_1^{n_1}\ldots{}x_m^{n_m}$ V~$G$ RAVEN
SUMME~$\sum \nu(\pi)$ PO VSEM PERESTANOVKAM~$\pi$
MULXTIMNOZHESTVA~$\set{n_1\cdot x_1,~\ldots, n_m\cdot x_m}$. nETRUDNO
VIDETX, CHTO
|TOT KO|FFICIENT RAVEN TAKZHE KO|FFICIENTU PRI~$x_1^{n_1}\ldots{}x_m^{n_m}$
V VYRAZHENII
$$
(a_{11} x_1 +\cdots+ a_{1m} x_m)^{n_1}
(a_{21} x_1 +\cdots+ a_{2m} x_m)^{n_2} \ldots
(a_{m_1} x_1 +\cdots+ a_{mm} x_m)^{n_m}.
$$

cELX |TOGO UPRAZHNENIYA---DOKAZATX TO, CHTO p.~a.~mAK-mAGON V SVOEJ
KNIGE Combinatory Analysis (1915), TOM~1, RAZD.~3, NAZVAL "OSNOVNOJ
TEOREMOJ", A IMENNO FORMULU
$$
G=1/D, \rem{GDE
$\displaystyle D=\det \pmatrix{
1-a_{11} x_1 &  -a_{12} x_2 & \ldots &  -a_{1m} x_m \cr
 -a_{21} x_1 & 1-a_{22} x_2 & \ldots &  -a_{2m} x_m \cr
  \vdots     &              &        &  \vdots \cr
 -a_{m1} x_1 &  -a_{m2} x_2 & \ldots & 1-a_{mm} x_m\cr
}.$}
$$
nAPRIMER, ESLI~$a_{ij}=1$ PRI VSEH~$i$, $j$, TO |TA FORMULA DAET
$$
G=1/(1-(x_1+x_2+\cdots+x_m)),
$$
I KO|FFICIENT PRI~$x_1^{n_1}\ldots x_m^{n_m}$ OKAZYVAETSYA
RAVNYM~$(n_1+\cdots+n_m)!/n_1!\ldots n_m!$,
KAK EMU I POLOZHENO.

dLYA DOKAZATELXSTVA OSNOVNOJ TEOREMY mAK-mAGONA POKAZHITE,
CHTO (a)~$\nu(\pi\T\rho)=\nu(\pi)\nu(\rho)$; (b)~V~OBOZNACHENIYAH UPR.~19
$D=\sum \pi \mu(\pi)\nu(\pi)$, GDE SUMMA BERETSYA PO VSEM PERESTANOVKAM~$\pi$
IZ MNOZHESTVA
$$
\set{x_1,\ldots, x_m}^*,
$$
I, NAKONEC, (c)~$D\cdot G=1$.

\subsubchap{*oTREZKI} % 5.1.3.
v P.~3.3.2 MY RASSMOTRELI "NEUBYVAYUSHCHIE OTREZKI" KAK ODIN IZ METODOV,
POZVOLYAYUSHCHIH PROVERITX SLUCHAJNOSTX POSLEDOVATELXNOSTI. eSLI POMESTITX
VERTIKALXNYE CHERTOCHKI S OBOIH KONCOV PERESTANOVKI~$a_1 a_2 \ldots a_n$, A
TAKZHE MEZHDU~$a_j$ I~$a_{j+1}$, KOGDA~$a_j>a_{j+1}$, TO \dfn{OTREZKAMI}
BUDUT NAZYVATXSYA SEGMENTY, OGRANICHENNYE PARAMI CHERTOCHEK. nAPRIMER, V PERESTANOVKE
$$
\vert 3\; 5\; 7\;\vert\;1\;6\; 8\; 9\;\vert\; 4\; 2\;
$$
---CHETYRE OTREZKA. mY NASHLI SREDNEE CHISLO OTREZKOV DLINY~$k$ V SLUCHAJNOJ
PERESTANOVKE MNOZHESTVA~$\set{1, 2,~\ldots, n}$, A TAKZHE KOVARIACIYU CHISLA
OTREZKOV DLINY~$j$ I DLINY~$k$. oTREZKI VAZHNY PRI IZUCHENII ALGORITMOV
SORTIROVKI, TAK KAK ONI PREDSTAVLYAYUT
%%51
UPORYADOCHENNYE SEGMENTY DANNYH. pO|TOMU-TO MY TEPERX VNOVX VERNEMSYA K
VOPROSU OB OTREZKAH. oBOZNACHIM CHEREZ
$$
\eul{n}{k}
\eqno(1)
$$
CHISLO PERESTANOVOK MNOZHESTVA~$\set{1, 2,~\ldots, n}$, IMEYUSHCHIH
ROVNO~$k$ VOZRASTAYUSHCHIH OTREZKOV. tAKIE CHISLA~$\eul{n}{k}$ VOZNIKAYUT I V DRUGIH
KONTEKSTAH; IH OBYCHNO NAZYVAYUT \dfn{CHISLAMI eJLERA,} POTOMU CHTO eJLER
OBSUDIL IH V SVOEJ ZNAMENITOJ KNIGE Institutiones calculi differentialis
(St.~Petersburg, 1755), 485--487
[Euler, {\sl Opera Omnia,\/} (1) {\bf 10} (1913), 373--375]; IH SLEDUET
OTLICHATX OT "|JLEROVYH CHISEL", O KOTORYH IDET RECHX V UPR.~5.1.4-22.

iZ LYUBOJ DANNOJ PERESTANOVKI MNOZHESTVA~$\set{1, 2,~\ldots, n-1}$ MOZHNO
OBRAZOVATX $n$~NOVYH PERESTANOVOK, VSTAVLYAYA |LEMENT~$n$ VO VSE VOZMOZHNYE
MESTA. eSLI V ISHODNOJ PERESTANOVKE SODERZHALOSX $k$~OTREZKOV, TO ROVNO
$k$~NOVYH PERESTANOVOK BUDUT IMETX $k$~OTREZKOV; V OSTALXNYH
$n-k$~PERESTANOVKAH BUDET PO $k+1$~OTREZKOV, POSKOLXKU VSYAKIJ RAZ, KOGDA
$n$~VSTAVLYAETSYA NE V KONEC UZHE SUSHCHESTVUYUSHCHEGO OTREZKA, CHISLO OTREZKOV
UVELICHIVAETSYA NA EDINICU. nAPRIMER, SREDI SHESTI PERESTANOVOK, POLUCHENNYH
IZ PERESTANOVKI~$3\,1\,2\,4\,5$,
$$
\matrix{
6\,3\,1\,2\,4\,5, & 3\,6\,1\,2\,4\,5, & 3\,1\,6\,2\,4\,5,\cr
3\,1\,2\,6\,4\,5, & 3\,1\,2\,4\,6\,5, & 3\,1\,2\,4\,5\,6;\cr
}
$$
VSE, KROME VTOROJ I POSLEDNEJ, SODERZHAT PO TRI OTREZKA VMESTO ISHODNYH
DVUH. oTSYUDA IMEEM REKURRENTNOE SOOTNOSHENIE
$$
\eul{n}{k}=k\eul{n-1}{k}+(n-k+1)\eul{n-1}{k-1},
\rem{GDE $n$~CELOE, $n\ge 1$; $k$~CELOE.}
\eqno (2)
$$
uSLOVIMSYA, CHTO
$$
\eul{0}{k}=\delta_{1k},
\eqno(3)
$$
T.~E.~BUDEM SCHITATX, CHTO V PUSTOJ PERESTANOVKE SODERZHITSYA ODIN OTREZOK.
chITATELX, VOZMOZHNO, NAJDET NEBEZYNTERESNYM SRAVNITX~(2) S REKURRENTNYM
SOOTNOSHENIEM DLYA CHISEL sTIRLINGA [FORMULY~(1.2.6-42)]. v TABL.~1 PRIVEDENY
CHISLA eJLERA DLYA MALYH~$n$.

v TABL.~1 MOZHNO ZAMETITX NEKOTORYE ZAKONOMERNOSTI. pO OPREDELENIYU IMEEM
$$
\eqalignno{
& \eul{n}{0}+\eul{n}{1}+\cdots+\eul{n}{n}=n!; & (4)\cr
& \eul{n}{0}=0, \quad \eul{n}{1}=1; & (5) \cr
& \eul{n}{n}=1 \rem{PRI $n\ge 1$.} & (6) \cr
}
$$
%% 52
\htable{tABLICA~1}%
{chISLA eJLERA}%
{\hfil$#$&&\bskip\hfil$\displaystyle #$\bskip\cr
n & \eul{n}{0} &\eul{n}{1} &\eul{n}{2} &\eul{n}{3} &\eul{n}{4} &\eul{n}{5} &\eul{n}{6} &\eul{n}{7}\cr
\noalign{\hrule}
0 & 0 & 1 &   0 &    0 &    0 &    0 &   0 & 0 \cr
1 & 0 & 1 &   0 &    0 &    0 &    0 &   0 & 0 \cr
2 & 0 & 1 &   1 &    0 &    0 &    0 &   0 & 0 \cr
3 & 0 & 1 &   4 &    1 &    0 &    0 &   0 & 0 \cr
4 & 0 & 1 &  11 &   11 &    1 &    0 &   0 & 0 \cr
5 & 0 & 1 &  26 &   66 &   26 &    1 &   0 & 0 \cr
6 & 0 & 1 &  57 &  302 &  302 &   57 &   1 & 0 \cr
7 & 0 & 1 & 120 & 1191 & 2416 & 1191 & 120 & 1 \cr
\noalign{\hrule}
}
vYPOLNYAETSYA TAKZHE SVOJSTVO SIMMETRII
$$
\eul{n}{k}=\eul{n}{n+1-k}, \rem{$n\ge1$,}
\eqno(7)
$$
KOTOROE VYTEKAET IZ TOGO FAKTA, CHTO KAZHDOJ
PERESTANOVKE~$a_1\,a_2\,\ldots{}\,a_n$, SODERZHASHCHEJ $k$~OTREZKOV, SOOTVETSTVUET
PERESTANOVKA~$a_n\,\ldots{}a_2\,a_1$, SODERZHASHCHAYA $n+1-k$~OTREZKOV.

dRUGOE VAZHNOE SVOJSTVO CHISEL eJLERA VYRAZHAETSYA FORMULOJ
$$
\sum_k \eul{n}{k}\perm{m+k-1}{n}=m^n, \rem{$n\ge0$,}
\eqno(8)
$$
KOTORUYU MOZHNO DOKAZATX, ISPOLXZUYA PONYATIE SORTIROVKI. rASSMOTRIM
$m^n$~POSLEDOVATELXNOSTEJ $a_1\,a_2\ldots{}a_n$, GDE~$1\le a_i \le m$.
lYUBUYU TAKUYU POSLEDOVATELXNOSTX MOZHNO USTOJCHIVO OTSORTIROVATX TAKIM
OBRAZOM, CHTOBY |LEMENTY RASPOLOZHILISX V NEUBYVAYUSHCHEM PORYADKE:
$$
a_{i_1}\le a_{i_2}\le \ldots \le a_{i_n},
\eqno(9)
$$
GDE~$i_1\,i_2\,\ldots{}\,i_n$---ODNOZNACHNO OPREDELENNAYA PERESTANOVKA
MNOZHESTVA~$\set{1, 2,~\ldots, n}$, TAKAYA, CHTO~$i_j<i_{j+1}$,
ESLI~$a_{i_j}=a_{i_{j+1}}$; DRUGIMI SLOVAMI, IZ~$i_j>i_{j+1}$
SLEDUET~$a_{i_j}<a_{i_{j+1}}$. pOKAZHEM, CHTO ESLI V
PERESTANOVKE~$i_1\,i_2\,\ldots\,i_n$ SODERZHITSYA $k$~OTREZKOV, TO CHISLO
SOOTVETSTVUYUSHCHIH EJ
POSLEDOVATELXNOSTEJ~$a_1\,a_2\ldots{}a_n$ RAVNO~$\perm{m+n-k}{n}$; TEM
SAMYM BUDET DOKAZANA FORMULA~(8), ESLI ZAMENITX~$k$ NA~$n+1-k$.

pUSTX, NAPRIMER, $n=9$, $i_1\,i_2\ldots{}i_n=3\,5\,7\,1\,6\,8\,9\,4\,2$ I
TREBUETSYA PODSCHITATX CHISLO POSLEDOVATELXNOSTEJ~$a_1a_2\ldots{}a_9$,
TAKIH, CHTO
$$
1\le a_3 \le a_5 \le a_7 < a_1 \le a_6 \le a_8 \le a_9 < a_4 < a_2 \le m;
\eqno (10)
$$
ONO RAVNO CHISLU POSLEDOVATELXNOSTEJ~$b_1\,b_2\ldots{}b_9$, TAKIH, CHTO
$$
1\le b_1 < b_2 < b_3 < b_4 < b_5 < b_6 < b_7 < b_8 < b_9 \le m+5,
$$
%%53
TAK KAK MOZHNO POLOZHITX~$b_1=a_3$, $b_2=a_5+1$, $b_3=a_7+2$, $b_4=a_1+2$,
$b_5=a_6+3$ I~T.~D. chISLO SPOSOBOV, KOTORYMI MOZHNO VYBRATX |LEMENTY~$b$,
RAVNO PROSTO-NAPROSTO CHISLU SPOSOBOV VYBRATX 9~PREDMETOV IZ~$m+5$,
T.~E.~$\perm{m+5}{9}$; ANALOGICHNOE DOKAZATELXSTVO GODITSYA
DLYA PROIZVOLXNYH~$n$ I~$k$ I LYUBOJ PERESTANOVKI~$i_1\,i_2\ldots{}i_n$
S $k$~OTREZKAMI.

tAK KAK V OBEIH CHASTYAH RAVENSTVA~(8) STOYAT POLINOMY OT~$m$, TO VMESTO~$m$
MOZHNO PODSTAVITX LYUBOE DEJSTVITELXNOE CHISLO, POLUCHIV INTERESNOE VYRAZHENIE
STEPENEJ CHEREZ POSLEDOVATELXNYE BINOMIALXNYE KO|FFICIENTY:
$$
x^n=\eul{n}{1}\perm{x}{n}+\eul{n}{2}\perm{x+1}{n}+\cdots+\eul{n}{n}\perm{x+n-1}{n},
\rem{$n\ge1$.}
\eqno(11)
$$
nAPRIMER,
$$
x^3=\perm{x}{3}+4\perm{x+1}{3}+\perm{x+2}{3}.
$$
v OSNOVNOM BLAGODARYA IMENNO |TOMU SVOJSTVU CHISLA eJLERA VESXMA POLEZNY PRI
IZUCHENII DISKRETNOJ MATEMATIKI. pOLOZHIV V~(11) $x=1$, DOKAZHEM ESHCHE RAZ, CHTO
$$
\eul{n}{n}=1,
$$
POSKOLXKU BINOMIALXNYE KO|FFICIENTY OBRASHCHAYUTSYA V~$0$ VO VSEH SLAGAEMYH,
KROME POSLEDNEGO. pOLOZHIV~$x=2$, POLUCHIM
$$
\eul{n}{n-1}=2^n-n-1, \rem{$n\ge1$.}
\eqno(12)
$$
pODSTAVIV~$x=3$, $4$,~\dots, UBEDIMSYA, CHTO VSE CHISLA~$\eul{n}{k}$ POLNOSTXYU
OPREDELYAYUTSYA SOOTNOSHENIEM~(11), I PRIDEM K FORMULE, VPERVYE NAJDENNOJ eJLEROM:
$$
\eqalignno{
\eul{n}{k}&= k^n-(k-1)^n\perm{n+1}{1}+(k-2)^n\perm{n+1}{2}-\cdots+(-1)^k0^n\perm{n+1}{k}=\cr
&=\sum_{0\le j \le k} (-1)^j(k-j)^n\perm{n+1}{j},\rem{$n\ge0$, $k\ge 0$.} & (13)\cr
}
$$

iZUCHIM TEPERX PROIZVODYASHCHUYU FUNKCIYU DLYA OTREZKOV. eSLI POLOZHITX
$$
g_n(z)=\sum_k \eul{n}{k} z^k/n!,
\eqno(14)
$$
%%54
TO KO|FFICIENT PRI~$z^k$ RAVEN VEROYATNOSTI TOGO, CHTO
SLUCHAJNAYA PERESTANOVKA MNOZHESTVA~$\set{1, 2,~\ldots, n}$ SODERZHIT ROVNO
$k$~OTREZKOV. pOSKOLXKU $k$~OTREZKOV V PERESTANOVKE STOLX ZHE VEROYATNY,
KAK I~$n+1-k$, TO SREDNEE CHISLO OTREZKOV DOLZHNO
RAVNYATXSYA~${1\over2}(n+1)$, I, SLEDOVATELXNO, $g'_n(1)={1\over2}(n+1)$. v
UPR.~2(b) POKAZANO, CHTO IMEET MESTO PROSTAYA FORMULA DLYA \emph{VSEH}
PROIZVODNYH FUNKCII~$g_n(z)$ V TOCHKE~$z=1$:
$$
g_n^{(m)}(1)=\Stir{n+1}{n+1-m}/\perm{n}{m}, \rem{$n\ge m$.}
\eqno(15)
$$
tAK, V CHASTNOSTI, DISPERSIYA~$g''_n(1)+g'_n(1)-g'_n(1)^2$ RAVNA~$(n+1)/12$
PRI~$n\ge2$, CHTO UKAZYVAET NA DOVOLXNO USTOJCHIVOE RASPREDELENIE OKOLO
SREDNEGO ZNACHENIYA. (mY NASHLI |TU ZHE VELICHINU V UPR.~3.3.2-18; TAM ONA
NAZYVALASX~$\covar(R'_1, R'_1)$.) fUNKCIYA~$g_n(z)$---POLINOM, PO|TOMU S
POMOSHCHXYU FORMULY~(15) MOZHNO RAZLOZHITX EE V RYAD tEJLORA
$$
\eqalignno{
g_n(z)&={1\over n!}\sum_{0\le k \le n} (z-1)^{n-k} k! \Stir{n+1}{k+1}=\cr
      &={1\over n!}\sum_{0\le k \le n} z^{k+1}(1-z)^{n-k} k! \Stir{n+1}{k+1}. &(16)\cr
}
$$
vTOROE RAVENSTVO SLEDUET IZ PERVOGO, TAK KAK PO SVOJSTVU SIMMETRII~(7)
$$
g_n(z)=z^{n+1} g_n(1/z), \rem{$n\ge1$.}
\eqno(17)
$$
iZ REKURRENTNOGO SOOTNOSHENIYA DLYA CHISEL sTIRLINGA
$$
\Stir{n+1}{k+1}=(k+1)\Stir{n}{k+1}+\Stir{n}{k}
$$
POLUCHAYUTSYA DVA CHUTX BOLEE PROSTYH PREDSTAVLENIYA:
$$
\eqalignno{
g_n(z)&={1\over n!}\sum_{0\le k \le n} z(z-1)^{n-k} k! \Stir{n}{k}=\cr
&={1\over n!}\sum_{0\le k \le n} z^k (1-z)^{n-k} k! \Stir{n}{k}. & (18)\cr
}
$$

pROIZVODYASHCHAYA FUNKCIYA OT DVUH PEREMENNYH\note{1}%
{v ORIGINALE "super generating function". sOOTVETSTVUYUSHCHEGO TERMINA
V OTECHESTVENNOJ LITERATURE NE SUSHCHESTVUET.---{\sl pRIM. RED.\/}}
$$
g(z, x)=\sum_{n\ge 0} g_n(z)x^n =\sum_{k, n \ge 0} \eul{n}{k} z^k x^n \Big/ n!
\eqno(19)
$$
%%55
RAVNA, SLEDOVATELXNO,
$$
z\sum_{k, n\ge 0} {((z-1)x)^n \over (z-1)^k}\Stir{n}{k}{k!\over n!}=
z\sum_{k\ge0}\left({e^{(z-1)x}-1\over z-1}\right)^k= {z(1-z)\over e^{(z-1)x}-z};
\eqno(20)
$$
|TO ESHCHE ODNO SOOTNOSHENIE, OBSUZHDAVSHEESYA eJLEROM.

dRUGIE SVOJSTVA CHISEL eJLERA MOZHNO NAJTI V OBZORNOJ STATXE  l.~kARLICA
[{\sl Math. Magazine,\/} {\bf 33} (1959), 247--260]; SM.~TAKZHE dZH.~rIORDAN,
vVEDENIE V KOMBINATORNYJ ANALIZ, il, m., 1963, STR.~50, 253, 254.

rASSMOTRIM TEPERX DLINU OTREZKOV; KAKOVA V SREDNEM DLINA OTREZKA? v
P.~3.3.2 MY UZHE IZUCHILI MATEMATICHESKOE OZHIDANIE CHISLA OTREZKOV DANNOJ
DLINY; SREDNYAYA DLINA OTREZKA RAVNA PRIMERNO~2 V SOGLASII S TEM FAKTOM,
CHTO V SLUCHAJNOJ PERESTANOVKE
DLINY~$n$ SODERZHITSYA V SREDNEM ${1\over2}(n+1)$~OTREZKOV. pRIMENITELXNO
K ALGORITMAM SORTIROVKI POLEZNA NESKOLXKO OTLICHNAYA TOCHKA ZRENIYA;
RASSMOTRIM DLINU $k\hbox{-GO}$~SLEVA OTREZKA PERESTANOVKI
PRI~$k=1$, $2$,~$\ldots\,$.

kAKOVA, NAPRIMER, DLINA PERVOGO (KRAJNEGO SLEVA) OTREZKA SLUCHAJNOJ
PERESTANOVKI~$a_1\,a_2\,\ldots\,a_n$? eGO DLINA VSEGDA~$\ge 1$; ONA~$\ge2$
ROVNO V POLOVINE SLUCHAEV (A IMENNO, ESLI~$a_1<a_2$). eGO DLINA~$\ge3$
ROVNO DLYA $1/6$~SLUCHAEV (ESLI~$a_1<a_2<a_3$). vOOBSHCHE EGO DLINA~$\ge m$ S
VEROYATNOSTXYU~$q_m=1/m!$ PRI~$1\le m \le n$. sLEDOVATELXNO, VEROYATNOSTX
TOGO, CHTO DLINA |TOGO OTREZKA RAVNA V TOCHNOSTI~$m$, ESTX
$$
\eqalignno{
p_m &= q_m-q_{m+1}=1/m!-1/(m+1)! \rem{PRI $1\le m < n$;} \cr
p_n &= 1/n!. & (21) \cr
}
$$
sREDNYAYA DLINA RAVNA, TAKIM OBRAZOM,
$$
\eqalignno{
p_1+2p_2+\cdots+np_n &= \cr
&=(q_1-q_2)+2(q_2-q_3)+\cdots+(n-1)(q_{n-1}-q_n)+nq_n=\cr
&=q_1+q_2+\cdots+q_n=\cr
&={1\over 1!}+{1\over 2!}+\cdots+{1\over n!}. & (22) \cr
}
$$
pREDEL PRI~$n\to\infty$ RAVEN~$e-1=1.71828\ldots$, A DLYA KONECHNYH~$n$  |TO
ZNACHENIE RAVNO~$e-1-\delta_n$, GDE $\delta_n$~DOVOLXNO MALO:
$$
\delta_n={1\over (n+1)!)}\left(1+{1\over n+2}+{1\over
(n+2)(n+3)}+\cdots\right)< {e-1\over (n+1)!}.
$$
pO|TOMU DLYA PRAKTICHESKIH CELEJ UDOBNO RASSMOTRETX OTREZKI SLUCHAJNOJ
\emph{BESKONECHNOJ} POSLEDOVATELXNOSTI RAZLICHNYH CHISEL
$$
a_1, a_2, a_3, \ldots;
$$
POD "SLUCHAJNOSTXYU" POSLEDOVATELXNOSTI MY ZDESX PODRAZUMEVAEM TO, CHTO VSE
$n!$~VOZMOZHNYH VZAIMNYH RASPOLOZHENII PERVYH~$n$
%%56
|LEMENTOV POSLEDOVATELXNOSTI RAVNOVEROYATNY. tAK CHTO SREDNYAYA DLINA PERVOGO
OTREZKA SLUCHAJNOJ BESKONECHNOJ POSLEDOVATELXNOSTI RAVNA~$e-1$.

nESKOLXKO USOVERSHENSTVOVAV |TOT METOD, MOZHNO USTANOVITX SREDNYUYU DLINU
$k\hbox{-GO}$~OTREZKA SLUCHAJNOJ POSLEDOVATELXNOSTI.
pUSTX $q_{km}$---VEROYATNOSTX TOGO, CHTO OBSHCHAYA DLINA PERVYH~$k$ OTREZKOV~$\ge m$;
TOGDA $q_{km}$~RAVNO VELICHINE~$1/m!$, UMNOZHENNOJ NA CHISLO
PERESTANOVOK MNOZHESTVA~$\set{1, 2, \ldots, m}$, SODERZHASHCHIH NE BOLEE $k$~OTREZKOV:
$$
q_{km}=\left(\eul{m}{1}+\cdots+\eul{m}{k}\right)\Big/ m!.
\eqno(23)
$$
vEROYATNOSTX TOGO, CHTO OBSHCHAYA DLINA PERVYH $k$~OTREZKOV RAVNA~$m$,
 ESTX~$q_{km}-q_{k(m+1)}$. sLEDOVATELXNO, OBOZNACHIV CHEREZ~$L_k$
SREDNYUYU DLINU $k\hbox{-GO}$~OTREZKA, NAHODIM, CHTO
$$
\eqalign{
L_1+\cdots+L_k&=\hbox{(SREDNYAYA OBSHCHAYA DLINA PERVYH $k$~OTREZKOV)} =\cr
&= (q_{k1}-q_{k2}) = 2(q_{k2}-q_{k3})+ 3(q_{k3}-q_{k4})+\cdots=\cr
&= q_{k1}+q_{k2}+q_{k3}+\cdots\,.\cr
}
$$
vYCHITAYA~$L_1+\cdots+L_{k-1}$ I ISPOLXZUYA ZNACHENIYA~$q_{km}$, IZ~(23)
POLUCHAEM NUZHNUYU NAM FORMULU:
$$
L_k={1\over 1!}\eul{1}{k}+{1\over 2!}\eul{2}{k}+{1\over 3!}\eul{3}{k}+\cdots=
\sum_{m\ge1}\eul{m}{k}{1\over m!}.
\eqno(24)
$$
pOSKOLXKU~$\eul{0}{k}=0$ PRI~$k\ne 1$, ZNACHENIE~$L_k$ OKAZYVAETSYA RAVNYM
KO|FFICIENTU PRI~$z^k$ V PROIZVODYASHCHEJ FUNKCII~$g(z, 1)-z$. (SM.~(19));
TAKIM OBRAZOM, IMEEM
$$
L(z)=\sum_{k\ge0} L_k z^k = {z(1-z) \over e^{z-1}-z}-z.
\eqno(25)
$$
iZ FORMULY eJLERA~(13) POLUCHIM PREDSTAVLENIE~$L_k$ V VIDE POLINOMA OT~$e$:
$$
\eqalignno{
L_k &= \sum_{m\ge 0} \sum_{0\le j \le k}(-1)^{k-j}\perm{m+1}{k-j}{j^m\over m!}=\cr
&=\sum_{0\le j \le k} (-1)^{k-j} \sum_{m\ge 0}\perm{m}{k-j}{j^m\over m!}+
 \sum_{0\le j \le k}(-1)^{k-j}\sum_{m\ge0}\perm{m}{k-j-1}{j^m\over m!}=\cr
&= \sum_{0\le j \le k} {(-1)^{k-j} j^{k-j} \over (k-j)!} \sum_{n\ge0}{j^n\over n!}+
 \sum_{0\le j \le k} {(-1)^{k-j} j^{(k-j-1)} \over (k-j-1)!}\sum_{n\ge0}{j^n\over n!}=\cr
&= k \sum_{0\le j \le k} {e^j (-1)^{k-j} j^{k-j-1}\over (k-j)!}. & (26) \cr
}
$$
%%57
eTU FORMULU DLYA~$L_k$ VPERVYE POLUCHILA b.~dZH.~g|SSNER
[{\sl CACM,\/} {\bf 10} (1967), 89--93]. iMEEM, V CHASTNOSTI,
$$
\eqalignter{
L_1 &= e-1 & \approx 1.71828\,\ldots; \cr
L_2 &=e^2-2e &\approx 1.95249\,\ldots;\cr
L_3&=e^3-3e^2+{3\over 2}e &\approx 1.99579\,\ldots\,.\cr
}
$$
iTAK, SLEDUET OZHIDATX, CHTO VTOROJ OTREZOK BUDET DLINNEE PERVOGO, A
TRETIJ OTREZOK BUDET V SREDNEM ESHCHE DLINNEE! nA PERVYJ VZGLYAD |TO MOZHET
POKAZATXSYA STRANNYM, NO POSLE MINUTNOGO RAZMYSHLENIYA STANOVITSYA YASNO, CHTO,
POSKOLXKU PERVYJ |LEMENT VTOROGO OTREZKA BUDET SKOREE VSEGO MALYM CHISLOM
(IMENNO |TO SLUZHIT PRICHINOJ OKONCHANIYA PERVOGO OTREZKA), U VTOROGO
OTREZKA BOLXSHE SHANSOV OKAZATXSYA DLINNEE, CHEM U PERVOGO. tENDENCIYA TAKOVA,
CHTO PERVYJ |LEMENT TRETXEGO OTREZKA BUDET DAZHE MENXSHE, CHEM PERVYJ |LEMENT
VTOROGO OTREZKA.

chISLA~$L_k$ VAZHNY V TEORII SORTIROVKI POSREDSTVOM VYBORA S ZAMESHCHENIEM
(P.~5.4.1), PO|TOMU INTERESNO PODROBNO IZUCHITX IH ZNACHENIYA. v TABL.~2,
VYCHISLENNOJ dZH.~u.~rENCHEM~(ML.), PRIVEDENY PERVYE~18 ZNACHENIJ~$L_k$ S
TOCHNOSTXYU DO~15 DESYATICHNYH ZNAKOV. rASSUZHDENIYA, PRIVEDENNYE V PREDYDUSHCHEM
ABZACE, MOGUT VYZVATX PODOZRENIE, CHTO~$L_{k+1}>L_k$; NA SAMOM ZHE DELE
ZNACHENIYA KOLEBLYUTSYA, TO VOZRASTAYA, TO UBYVAYA. zAMETIM, CHTO~$L_k$
BYSTRO PRIBLIZHAYUTSYA K PREDELXNOMU ZNACHENIYU~2; VESXMA PRIMECHATELXNO TO, CHTO
|TI NORMIROVANNYE POLINOMY OT TRANSCENDENTNOGO CHISLA~$e$ TAK BYSTRO
SHODYATSYA K RACIONALXNOMU CHISLU~2! pOLINOMY~(26) PREDSTAVLYAYUT NEKOTORYJ
INTERES I S TOCHKI ZRENIYA CHISLENNOGO ANALIZA, BUDUCHI PREKRASNYM PRIMEROM
POTERI ZNACHASHCHIH CIFR PRI VYCHITANII POCHTI RAVNYH CHISEL; ISPOLXZUYA
19-ZNACHNUYU ARIFMETIKU S PLAVAYUSHCHEJ TOCHKOJ, g|SSNER PRISHLA K NEVERNOMU
ZAKLYUCHENIYU O TOM, CHTO~$L_{12}>2$, A rENCH OTMETIL, CHTO 42-ZNACHNAYA ARIFMETIKA
\htable{tABLICA~2}%
{sREDNIE DLINY OTREZKOV}%
{\hfil$#$\hfil&\hfil\bskip$#$\hfil\hskip 1cm & \hfil$#$\hfil&\hfil\bskip$#$\hfil\cr
k & L_k & k & L_k \cr
\noalign{\hrule}
1& 1.71828\,18284\,59045+ & 10 & 2.00000\,00012\,05997+\cr
2& 1.95249\,24420\,12560- & 11 & 2.00000\,00001\,93672+\cr
3& 1.99579\,13690\,84285- & 12 & 1.99999\,99999\,99909+\cr
4& 2.00003\,88504\,76806- & 13 & 1.99999\,99999\,97022-\cr
5& 2.00005\,75785\,89716+ & 14 & 1.99999\,99999\,99719+\cr
6& 2.00000\,50727\,55710- & 15 & 2.00000\,00000\,00019+\cr
7& 1.99999\,96401\,44022+ & 16 & 2.00000\,00000\,00006+\cr
8& 1.99999\,98889\,04744+ & 17 & 2.00000\,00000\,00000+\cr
9& 1.99999\,99948\,43434- & 18 & 2.00000\,00000\,00000-\cr
\noalign{\hrule}
}
%%58
S PLAVAYUSHCHEJ TOCHKOJ DAET~$L_{28}$ LISHX S TOCHNOSTXYU DO 29~ZNACHASHCHIH CIFR.

aSIMPTOTICHESKOE POVEDENIE~$L_k$ MOZHNO OPREDELITX, ISHODYA IZ PROSTYH
POLOZHENIJ TEORII FUNKCIJ KOMPLEKSNOGO PEREMENNOGO.
\picture{rIS.~3 kORNI URAVNENIYA~$e^{z-1}=z$. pUNKTIRNAYA LINIYA SOOTVETSTVUET
URAVNENIYU~$e^{x-1}\cos y = x$, SPLOSHNAYA LINIYA---URAVNENIYU~$e^{x-1}\sin y = y$.
}
zNAMENATELX V~(25) OBRASHCHAETSYA V NULX LISHX PRI~$e^{z-1}=z$,
T.~E.\ (POLAGAYA~$z=x+iy$) KOGDA
$$
e^{x-1}\cos y = x \rand e^{x-1}\sin y =y.
\eqno(27)
$$
nA RIS.~3, GDE NANESENY OBA GRAFIKA |TIH URAVNENIJ, VIDNO, CHTO ONI
PERESEKAYUTSYA V TOCHKAH~$z=z_0$, $z_1$, $\bar z_1$, $z_2$, $\bar z_2$,~\dots;
ZDESX~$z_0=1$,
$$
z_1= (3.08884\,30156\,13044-)+(7.46148\,92856\,54255-)i
\eqno (28)
$$
I PRI BOLXSHIH~$k$ MNIMAYA CHASTX~$\Im(z_{k+1})$ RAVNA PRIBLIZITELXNO~$\Im(z_k)+2\pi$.
%% 59
tAK KAK
$$
\lim_{z\to z_k} \left({1-z \over e^{z-1}-z}\right)(z-z_k)=-1
\rem{PRI~$k>0$}
$$
I |TOT PREDEL RAVEN~$-2$ PRI~$k=0$, TO FUNKCIYA
$$
R_m(z)=L(z)+{2\over z-z_0}+{z_1\over z-z_1}+{\bar z_1 \over z-\bar z_1}
 +{z_2\over z-z_2}+{\bar z_2 \over z-\bar z_2}+\cdots+{z_m \over z-z_m}
 +{\bar z_m \over z-\bar z_m}
$$
NE IMEET OSOBENNOSTEJ V KOMPLEKSNOJ PLOSKOSTI PRI~$\abs{z}<\abs{z_{m+1}}$.
zNACHIT, $R_m(z)$ MOZHNO RAZLOZHITX V STEPENNOJ RYAD~$\sum_k \rho_k z^k$,
KoTopYJ SHODITSYA ABSOLYUTNO PRI~$\abs{z}<\abs{z_{m+1}}$; OTSYUDA SLEDUET,
CHTO~$\rho_k M^k \to 0$ PRI~$k\to\infty$, GDE~$M=\abs{z_{m+1}}-\varepsilon$.
kO|FFICIENTAMI DLYA~$L(z)$ SLUZHAT KO|FFICIENTY RAZLOZHENIYA FUNKCII
$$
{2\over 1-z}+{1\over 1-z/z_1}+{1\over z/\bar z_1}+\cdots
+{1\over z-z/z_m}+{1\over z-z/\bar z_m}+R_m z,
$$
A IMENNO
$$
L_n= 2+2r_1^{-n}\cos n\theta_1+2r_2^{-n}\cos n\theta_2
+\cdots+2r_m^{-n}\cos n\theta_m + O(r_{m+1}^{-n}),
\eqno (29)
$$
ESLI POLOZHITX
$$
z_k=r_k e^{i\theta_k}.
\eqno  (30)
$$
oTSYUDA MOZHNO PROSLEDITX ASIMPTOTICHESKOE POVEDENIE~$L_n$. iMEEM
$$
\displaynarrow{
\eqalign{
r_1 &= 8.07556\,64528\,89526-,\cr
\theta_1 &= 1.17830\,39784\,74668+;\cr
}\cr
\eqalign{
r_2 &= 14.35457-,\cr
r_3 &= 20.62073+,\cr
r_4 &= 26.88795+,\cr
}
\qquad
\eqalign{
\theta_2 &=1.31269-;\cr
\theta_3 &= 1.37428-;\cr
\theta_4 &= 1.41050-;\cr
}\cr
}
\eqno(31)
$$
TAKIM OBRAZOM, GLAVNYJ VKLAD V~$L_n-2$ DAYUT~$r_1$ I~$\theta_1$, I
RYAD~(29) SHODITSYA OCHENX BYSTRO. pRIVEDENNYE ZDESX ZNACHENIYA~$r_1$
I~$\theta_1$ NAJDENY dZH.~u.~rENCHEM~(ML.) dALXNEJSHIJ ANALIZ
[W.~W.~Hooker, {\sl CACM,\/} {\bf 12} (1969), 411--413] POKAZYVAET,
CHTO~$R_m(z)\to -z$ PRI~$m\to\infty$; SLEDOVATELXNO,
RYAD~$2\sum_{k\ge 0} z_k^{-n}\cos n\theta_k$  DEJSTVITELXNO \emph{SHODITSYA}
K~$L_n$ PRI~$n>1$.

mOZHNO PROVESTI BOLEE TSHCHATELXNOE ISSLEDOVANIE VEROYATNOSTEJ, CHTOBY POLNOSTXYU
OPREDELITX RASPREDELENIE VEROYATNOSTEJ DLYA  DLINY $k\hbox{-GO}$~OTREZKA I
DLYA OBSHCHEJ DLINY PERVYH~$k$ OTREZKOV (SM.~UPR.~9, 10, 11), oKAZYVAETSYA
SUMMA~$L_1+\cdots+L_k$ ASIMPTOTICHESKI PRIBLIZHAETSYA K~$2k-1/3$.

%% 60

v ZAKLYUCHENIE |TOGO PUNKTA RASSMOTRIM SVOJSTVA OTREZKOV V SLUCHAE, KOGDA V
PERESTANOVKE DOPUSKAYUTSYA ODINAKOVYE |LEMENTY. bESCHISLENNYE PASXYANSY,
KOTORYM POSVYASHCHAL SVOI DOSUGI ZNAMENITYJ AMERIKANSKIJ ASTRONOM 19-GO VEKA
sAJMON nXYUKOMB, IMEYUT NEPOSREDSTVENNOE OTNOSHENIE K INTERESUYUSHCHEMU NAS
VOPROSU. oN BRAL KOLODU KART I SKLADYVAL IH V ODNU STOPKU DO TEH POR,
POKA ONI SHLI V NEUBYVAYUSHCHEM PORYADKE PO STARSHINSTVU; KAK TOLXKO SLEDUYUSHCHAYA
KARTA OKAZYVALASX MLADSHE PREDYDUSHCHEJ, ON NACHINAL NOVUYU STOPKU. oN HOTEL
NAJTI VEROYATNOSTX TOGO, CHTO V REZULXTATE VSYA KOLODA OKAZHETSYA RAZLOZHENNOJ V
ZADANNOE KOLICHESTVO STOPOK.

zADACHA sAJMONA nXYUKOMBA SOSTOIT, SLEDOVATELXNO, V NAHOZHDENII
RASPREDELENIYA VEROYATNOSTEJ DLYA OTREZKOV SLUCHAJNOJ PERESTANOVKI
MULXTIMNOZHESTVA. v OBSHCHEM SLUCHAE OTVET DOVOLXNO SLOZHEN (SM. UPR.~12), HOTYA
MY UZHE VIDELI, KAK RESHATX ZADACHU V CHASTNOM SLUCHAE, KOGDA VSE KARTY
RAZLICHNY PO STARSHINSTVU. mY UDOVLETVORIMSYA ZDESX VYVODOM FORMULY DLYA
\emph{SREDNEGO} CHISLA STOPOK V |TOM PASXYANSE.

pUSTX IMEETSYA $m$ RAZLICHNYH TIPOV KART I KAZHDAYA VSTRECHAETSYA ROVNO $p$ RAZ.
nAPRIMER, V OBYCHNOJ KOLODE DLYA BRIDZHA $m=13$, A $p=4$, ESLI PRENEBREGATX
RAZLICHIEM MASTI. zAMECHATELXNUYU SIMMETRIYU OBNARUZHIL V |TOM SLUCHAE
p.~a.~mAK-mAGON [Combinatory Analysis (Cambridge, 1915), TOM~1,
STR.~212--213]: CHISLO PERESTANOVOK S $k+1$~OTREZKAMI RAVNO CHISLU
PERESTANOVOK S $mp-p-k+1$~OTREZKAMI. eTO SOOTNOSHENIE LEGKO PROVERITX
PRI~$p=1$ (FORMULA (7)), ODNAKO PRI $p > 1$ ONO KAZHETSYA DOVOLXNO NEOZHIDANNYM.

mOZHNO DOKAZATX |TO SVOJSTVO SIMMETRII, USTANOVIV VZAIMNO ODNOZNACHNOE
SOOTVETSTVIE MEZHDU PERESTANOVKAMI, TAKOE, CHTO KAZHDOJ PERESTANOVKE S
$k+1$ OTREZKAMI SOOTVETSTVUET DRUGAYA, S $mp-p-k+1$~OTREZKAMI. mY
NASTOJCHIVO REKOMENDUEM CHITATELYU SAMOMU POPROBOVATX NAJTI TAKOE
SOOTVETSTVIE, PREZHDE CHEM DVIGATXSYA DALXSHE.

kAKOGO-NIBUDX OCHENX PROSTOGO SOOTVETSTVIYA NA UM NE PRIHODIT;
DOKAZATELXSTVO mAK-mAGONA OSNOVANO NA PROIZVODYASHCHIH FUNKCIYAH, A NE NA
KOMBINATORNOM POSTROENII. oDNAKO USTANOVLENNOE fOATOJ SOOTVETSTVIE
(TEOREMA~5.1.2v) POZVOLYAET UPROSTITX ZADACHU, TAK KAK TAM UTVERZHDAETSYA
SUSHCHESTVOVANIE VZAIMNO ODNOZNACHNOGO SOOTVETSTVIYA MEZHDU PERESTANOVKAMI S
$k+1$~OTREZKAMI I PERESTANOVKAMI, V DVUSTROCHNOM PREDSTAVLENII KOTORYH
SODERZHITSYA ROVNO $k$~STOLBCOV $y\atop x$, TAKIH, CHTO $x<y$.

pUSTX DANO MULXTIMNOZHESTVO $\set{p\cdot 1, p\cdot2, \ldots, p\cdot m}$;
RASSMOTRIM PERESTANOVKU S DVUSTROCHNYM OBOZNACHENIEM
$$
\pmatrix{
1 & \ldots & 1 & 2 & \ldots & 2& \ldots & m & \ldots & m\cr
x_{11} & \ldots & x_{1p} &x_{21} & \ldots & x_{2p} &\ldots &x_{m1} & \ldots & x_{mp}\cr
}.
\eqno(32)
$$
%% 61
\bye