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

����� ����� ������������ ���� ������ (����������������� ������������),
����������������� �� ���� ���������~$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
}
$$
񐀂����� ��� �~(23), ������������, ��� ������ �����������
���������
$$
\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)
$$
��������, � ���� ���������� �� ����������� � ���.~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)
$$
��� $M=A+B-C-m$, $N=C-B+m$, $R=B$, $S=C$, �~$j=C-B+m-k$.

���������� ����� ���������� ����� ������������
���������������~$\set{A\cdot a, B\cdot b, C\cdot c, D\cdot d}$, ����
���������� �������� ��������� ����� � ��� ������ ��������� �������:
$$\let\ds=\displaystyle
\matrix{
\hbox{񒎋���:}\hfill   & a & a   & b & b   & c     & c   & d   & d    \cr
                        & d & b   & a & c   & b     & d   & a   & c    \cr
\hbox{ꎋ�������:}\hfill& r & A-r & q & B-q & B-A+r & D-r & A-q & D-A+q\cr
}
\eqno(28)
$$
(焅��~$A+C=B+D$.) ⎇������� ������� � ���������� ����� ������������ ��
������� ��������� �����
$$
\matrix{
\hbox{����:}\hfill       & (a\, b) & (b\, c) & (c\, d) & (d\, a) & (a\, b\, c\, d) & (d\, c\, b\, a)\cr
\hbox{ꎋ�������:}\hfill & A-r-s   & B-q-s   & D-r-s   & A-q-s   & s               & q-A+r+s \cr
}
\eqno(29)
$$
��� ���������~$s$ (��.~���.~12). � ���� ������ �����~$(a\, b)$ �~$(c\,d)$
�����������, ��� �� ��� � �����~$(b\, c)$ �~$(d\,a)$, �������
���������� ���������� ����� ��������� ���������� �� ������� ���������.
�������� (��.~���.~10), ������ ���������� ������������ ����������,
�����, ��� ����~$(a\, b)$ ������� �� ������� ��������������� ��~$(c\, d)$,
�~$(b\, c)$ �� ����������� ����� �����~$(d\,a)$.
%% 47
���, ��������� ����������� ���.~13, �������� ���������
$$
\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
}
$$
⛍��� �� ����� ������ ���������~$\perm{D}{A-q}$ � ������ �������
����������, �������� � �������� �� ��� �������������������� ���������
������������ �������������:
$$
\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)
$$
������ ����������~(27), ����� ��������� ������������ ��~$s$, �
������������ ����� ��~$t$ ����� �����������. 򀊈� �������, . ����� ����
����������� ������ ��� �� ��������������� ���������� �����-����
���������, ������� �� �� ��� �� ����� ��������. � �� �� ������� ����
��������� ������������ ����� ������������ ������������� ���� �����
���������� ���������, � ��� ������ ��������---������� ���������� � �������
�����, ������� ��� �������.

\excercises
\ex[�05] \emph{� ��� ���?} ��~$M_1$  �~$M_2$---���������������. 呋�
$\alpha$---������������~$M_1$, �~$\beta$---������������~$M_2$,
��~$\alpha\T \beta$---������������~$M_1\cup M_2$.

\ex[10] 񎅄���������� ������������
������������~$c\,a\,d\,a\,b$ �~$b\,d\,d\,a\,d$ ��������� �~(5);
������� �������������� ������������~$b\,d\,d\,a\,d\T c\,a\,d\,a\,b$,
������� ����������, ���� ����������� �������� �������.

\ex[�13] ⅐�� �� �����������, ��������~(9)? 荀�� ������, ����
������������~$\alpha$ �~$\beta$ ������������ ������������ ��������
��������������� ������������, �� ������� �� �� �����, ��� ��� ��
�������� ����� ����?

\ex[M11] ꀍ��������� ���������� ������������~(12) � ������ �������~A
���~$a<b<c<d$ �������� ��������~(17). 퀉���� ���������������
������������ ���������� � ������, �����~$d<c<b<a$.

\ex[�23] � �������~(b) �������~B ���������, �����~$x<y$; ��� �����, ����
�������� ��� ����������, ������� ��� ��~$x\le y$?

\ex[�15] 񊎋��� ���������� �������, ��������� ����� ��~$m$ ����~$a$ �~$n$
����~$b$, �����, ��� �����~$k$ ����~$b$ ����� ��������������� �����
�������~$a$ � ��� ������� ������ ����, �����~$a$ �~$b$?

\ex[�21] 񊎋��� ������� �� ����~$a$, $b$, $c$, ���������������
��������~(18), ���������� � �����~$a$? � �����~$b$? � �����~$c$?

\rex[20] 퀉���� ��� ���������� ������������~(12) �� ���
���������~$\alpha\T \beta$.

%%48
\ex[33] 퀏����� ��������� ��� ���, ������� �� ����������� ����������
�������� ������������ ���������������, ��������� � ��������~A �~C.

\rex[M30] \emph{� ��� ���?} 񎃋���� �������~C, ���������� �� �������
��������� �� ������ ����������, ��� �� ����� ����� ��������� �������
���������� ��������������. "񓙅������ �������� ������������~$\prec$ ��
��������� ������� ������������, �����, ��� ������ ������������
��������������� ����� ������������
����������~$\sigma_1 \T \sigma_2 \T \ldots \T \sigma_n$ �� ������� ���������,
���������������
�������~$\sigma_i \preceq \sigma_{i+1}$, ���� $\sigma_i$ �����������
�~$\sigma_{i+1}$, ���~$1\le i < n$".

\ex[�26] ��~$\sigma_1$, $\sigma_2$,~\dots, $\sigma_t$---����� ���
������������� ���������. ������ ��������� ������������~$\prec$ ��
��������� $t$~��������� $\set{x_1, \ldots, x_t}$, �������~$x_i\prec x_j$,
����~$i<j$ � $\sigma_i$  ����� �� ������� ���� ���� ����� �����
�~$\sigma_j$. 䎊����� ��������� ����� ����� ��������~C � ��������
"�������������� ����������" (�.~2.2.3): \dfn{����� ��������� ����������
������������~$\sigma_1\T \sigma_2 \T \ldots \T \sigma_t$ �� �������
��������� ����� ���������� �������� ������������� ������������� ������
��������� ������������.} (퀏�����, � ������������ �~(22) ���������� ����
�������� ������������� ������������� ������������~$x_1\prec x_3$,
$x_2\prec x_4$, $x_1\prec x_4$.) ����, ���� �� ��������� ��
$t$~��������� ������ �����-�� ��������� ������������, �� ����������
��������� ������
$$
\set{\sigma_1, \sigma_2,\ldots, \sigma_t},
$$
������� ���������� ��� ��������� ������������ ��������� ��������.

\ex[�16] �����, ��� �����������~(29) �������� ����������� �������������~(28).

\ex[�21] 䎊�����, ��� ����� ������������
���������������~$\set{A\cdot a, B\cdot b, C\cdot c, D\cdot d, E\cdot e, F\cdot f}$,
�� ���������� ��� ������� ����� ����~$c\,a$ �~$d\,b$, �����
$$
\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] � �� �������� ���������� ������������~$\pi^{-1}$,
"��������" ������������~$\pi$, ������� ��������� ��� ������� �������������
����� ������, ��� �������� ������� ������ ������������ �������������~$\pi$
� ����� ��������� ���������� ���������� ��������, ��� ����� ��������
������� ������ ������������� � ����������� �������. 퀏�����,
����~$a<b<c<d$, �� �� ����� ����������� �������,
���~$c\,a\,b\,d\,d\,a\,b\,d\,a\,d^{-1}=a\,c\,d\,a\,d\,a\,b\,b\,d\,d$.

葑������� �������� ���� �������� ���������; ������� ��, ��������,
�����-������ ������� ����� ����� ��� � ��������������
�������������? 쎆�� �� ���������� ����� ������������, �����,
���~$\pi=\pi^{-1}$?

\rex[�25] 䎊�����, ��� ������������~$a_1\ldots{}a_n$ ���������������
$$
\set{n_1\cdot x_1, n_2\cdot x_2, \ldots, n_m\cdot x_m},
$$
���~$x_1<x_2<\ldots<x_n$ �~$n_1+n_2+\cdots+n_m=n$, �������� ������ ����� �
������ �����, ����� ������������ ���� � ���������~$\set{x_1, x_2,~\ldots, x_m}$
� ������ ��~$x_j$ �~$a_{n_1+\cdots+n_j}$ �������� ����� ����
��������������� ����. � ���� ������ �����
�������� ����������� ������������ � ���� ����� ����� ����� �����
���������������� �����. 퀏�����, ������������ ������, ��������������� ������������
$$
\pmatrix{
a & a & a & b & b & c & c & c & d & d \cr
d & c & b & a & c & a & a & b & d & c \cr
}, \hbox{�����}
$$
% !!! �������� ������
\picture{p. 48}
� ��� ������� ����������� ������������ � ����
�����---���~$(b\,a\,d\,d\,c\,a\,c\,a\,b\,c)$
�~$(c\,a\,d\,d\,c\,a\,c\,b\,a\,b)$.

%%49
\ex[�35] � ���������� ������, �������~(8), �� ����� ������������ �������
��� \emph{��������} ������������ � ������� ������, ����� �
������������ ��������� �������� ���������. �����, ��� � ����� ������
������������ \emph{���������������} ������������ ������� ��� ��������
����� "$z\hbox{-�����������������}$ ������������"
$$
\perm{n}{n_1, n_2,~\ldots}_z={n!_z\over n_1!_z n_2!_z\ldots},
\rem{���~$m!_z=(1-z)(1-z^2)\ldots(1-z^m)$.}
$$ [�.~�~(3); $z\hbox{-������������}$ ������������ ���������� �
�������~(1.2.6-37).]

\ex[M24] ������ ������������ ��������, ��������� � ���.~16, ���������
������� �������� � ��������� ��� ����� �������� � ��������� ������������
���������������.

\ex[M30] (�.~�.~쀊-쀃��.) \emph{荄���}
������������~$a_1\,a_2\ldots{}a_n$ ��� ��������� � ���������� ������;
�� ��������, ��� �����
������������ ������� ���������, ������� ������ ������~$k$, ����� �����
������������, ������� $k$~��������. ⅐�� �� ��� ��� ������������
��������� ���������������?

\ex[��28] ������ \emph{������� 츁����}~$\mu(\pi)$ ������������~$\pi$:
��� �����~$0$, ���� $\pi$~�������� ������������� ��������, �~$(-1)^k$ �
��������� ������, ����~$\pi$---������������ $k$~������� ������������.
(�.\ � ������������ ������� ������� 츁����, ���.~4.5.2-10.) (a)~䎊�����,
��� ����~$\pi\ne\varepsilon$, ��
$$
\sum \mu(\lambda)=0,
$$
��� ����� ������� �� ���� �������������~$\lambda$, ���������� ������
������������� � ����������~$\pi$ (�.~�.~$\lambda\T\rho=\pi$,
���~$\rho$---��������� ������������) (b)~䎊�����, ���
����~$x_1<x_2<\ldots<x_m$ �~$\pi=x_{i_1} x_{i_2} \ldots x_{i_n}$,
���~$1\le i_l \le m$ ���~$1\le j \le n$, ��
$$
\mu(\pi)=(-1)^m \varepsilon (i_1 i_2 \ldots i_n),
\rem{���~$\varepsilon(i_1 i_2 \ldots i_n)=\sign \prod_{1\le j < k \le n} (i_k-i_j)$.}
$$


\ex[��33] (�.~􎀒�.) ��~$(a_{ij})$---������������ �������
�������������� �����. ������ ������������� ���.~19~(b),
���������~$\nu(\pi)=a_{i_1 j_1}\ldots a_{i_n j_n}$, ���� �����������
������������� ������������~$\pi$ ������:
$$
\pmatrix{
x_{i_1} & x_{i_2} & \ldots & x_{i_n} \cr
x_{j_1} & x_{j_2} & \ldots & x_{j_n} \cr
}.
$$
��� ������� ������� ��� ���������� ������������ ������� ��� ������������
���������������, ������ ���~$\sum \nu(\pi)$, ��� ����� ������� �� ����
�������������~$\pi$ ���������������
$$
\set{n_1\cdot x_1, \ldots, n_m\cdot x_m},
$$
����� ������������ �������� ��� ����� ������������, ���������������
��������� ������������. 퀏�����, ���� ��������~$a_{ij}=z$ ���~$i=j$
�~$a_{ij}=1$  ���~$i\ne j$, ��~$\sum \nu(\pi)$---������������ ������� ���
����� "����������� �����" (��������, � ������� ������� � ������ ��������
�����). ����� ����� ���� �����������~$\sum \nu(\pi)$ ��� ����
�������������� ������������, ���������� �������
$$
G=\sum \pi\nu(\pi),
$$
��� ����� ������� �� ����~$\pi$ �� ���������~$\set{x_1,~\ldots, x_m}^*$
���� ������������ ��������������, ���������� ��������~$x_1$,~\dots, $x_m$,
� ��������� �� ������������ ���~$x_1^{n_1}\ldots x_m^{nm}$ �~$G$.

%%50

� ���� ������� ���~$G$ ����� �������������~$\pi$ ��� ������������
����������~$x$. 퀏�����, ���~$m=2$ �����
$$
\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
}
$$
򀊈� �������, ����������� ���~$x_1^{n_1}\ldots{}x_m^{n_m}$ �~$G$ �����
�����~$\sum \nu(\pi)$ �� ���� �������������~$\pi$
���������������~$\set{n_1\cdot x_1,~\ldots, n_m\cdot x_m}$. 텒�����
������, ���
���� ����������� ����� ����� ������������ ���~$x_1^{n_1}\ldots{}x_m^{n_m}$
� ���������
$$
(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}.
$$

���� ����� ����������---�������� ��, ��� �.~�.~쀊-쀃�� � �����
����� Combinatory Analysis (1915), ���~1, ����.~3, ������ "��������
��������", � ������ �������
$$
G=1/D, \rem{���
$\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
}.$}
$$
퀏�����, ����~$a_{ij}=1$ ��� ����~$i$, $j$, �� ��� ������� ����
$$
G=1/(1-(x_1+x_2+\cdots+x_m)),
$$
� ����������� ���~$x_1^{n_1}\ldots x_m^{n_m}$ �����������
������~$(n_1+\cdots+n_m)!/n_1!\ldots n_m!$,
��� ��� � ��������.

䋟 �������������� �������� ������� 쀊-쀃��� ��������,
��� (a)~$\nu(\pi\T\rho)=\nu(\pi)\nu(\rho)$; (b)~�~������������ ���.~19
$D=\sum \pi \mu(\pi)\nu(\pi)$, ��� ����� ������� �� ���� �������������~$\pi$
�� ���������
$$
\set{x_1,\ldots, x_m}^*,
$$
�, �������, (c)~$D\cdot G=1$.

\subsubchap{*����} % 5.1.3.
� �.~3.3.2 �� ����������� "����������� �������" ��� ���� �� �������,
����������� ��������� ����������� ������������������. 呋� ���������
������������ �������� � ����� ������ ������������~$a_1 a_2 \ldots a_n$, �
����� �����~$a_j$ �~$a_{j+1}$, �����~$a_j>a_{j+1}$, �� \dfn{���������}
����� ���������� ��������, ������������ ������ ��������. 퀏�����, � ������������
$$
\vert 3\; 5\; 7\;\vert\;1\;6\; 8\; 9\;\vert\; 4\; 2\;
$$
---������ �������. � ����� ������� ����� �������� �����~$k$ � ���������
������������ ���������~$\set{1, 2,~\ldots, n}$, � ����� ���������� �����
�������� �����~$j$ � �����~$k$. ���� ����� ��� �������� ����������
����������, ��� ��� ��� ������������
%%51
������������� �������� ������. ����-�� �� ������ ����� �������� �
������� �� ��������. ������ �����
$$
\eul{n}{k}
\eqno(1)
$$
����� ������������ ���������~$\set{1, 2,~\ldots, n}$, �������
�����~$k$ ������������ ��������. 򀊈� �����~$\eul{n}{k}$ ��������� � � ������
����������; �� ������ �������� \dfn{������� ������,} ������ ��� �����
������� �� � ����� ���������� ����� Institutiones calculi differentialis
(St.~Petersburg, 1755), 485--487
[Euler, {\sl Opera Omnia,\/} (1) {\bf 10} (1913), 373--375]; �� �������
�������� �� "��������� �����", � ������� ���� ���� � ���.~5.1.4-22.

� ����� ������ ������������ ���������~$\set{1, 2,~\ldots, n-1}$ �����
���������� $n$~����� ������������, �������� �������~$n$ �� ��� ���������
�����. 呋� � �������� ������������ ����������� $k$~��������, �� �����
$k$~����� ������������ ����� ����� $k$~��������; � ���������
$n-k$~������������� ����� �� $k+1$~��������, ��������� ������ ���, �����
$n$~����������� �� � ����� ��� ������������� �������, ����� ��������
������������� �� �������. 퀏�����, ����� ����� ������������, ����������
�� ������������~$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
}
$$
���, ����� ������ � ���������, �������� �� ��� ������� ������ ��������
����. ��� ����� ������������ �����������
$$
\eul{n}{k}=k\eul{n-1}{k}+(n-k+1)\eul{n-1}{k-1},
\rem{��� $n$~�����, $n\ge 1$; $k$~�����.}
\eqno (2)
$$
󑋎�����, ���
$$
\eul{0}{k}=\delta_{1k},
\eqno(3)
$$
�.~�.~����� �������, ��� � ������ ������������ ���������� ���� �������.
��������, ��������, ������ ��������������� ��������~(2) � ������������
������������ ��� ����� 񒈐����� [�������~(1.2.6-42)]. � ����.~1 ���������
����� ������ ��� �����~$n$.

� ����.~1 ����� �������� ��������� ��������������. � ����������� �����
$$
\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{��� $n\ge 1$.} & (6) \cr
}
$$
%% 52
\htable{򀁋���~1}%
{����� ������}%
{\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}
}
⛏�������� ����� �������� ���������
$$
\eul{n}{k}=\eul{n}{n+1-k}, \rem{$n\ge1$,}
\eqno(7)
$$
������� �������� �� ���� �����, ��� ������
������������~$a_1\,a_2\,\ldots{}\,a_n$, ���������� $k$~��������, �������������
������������~$a_n\,\ldots{}a_2\,a_1$, ���������� $n+1-k$~��������.

䐓��� ������ �������� ����� ������ ���������� ��������
$$
\sum_k \eul{n}{k}\perm{m+k-1}{n}=m^n, \rem{$n\ge0$,}
\eqno(8)
$$
������� ����� ��������, ��������� ������� ����������. ����������
$m^n$~������������������� $a_1\,a_2\ldots{}a_n$, ���~$1\le a_i \le m$.
랁�� ����� ������������������ ����� ��������� ������������� �����
�������, ����� �������� ������������� � ����������� �������:
$$
a_{i_1}\le a_{i_2}\le \ldots \le a_{i_n},
\eqno(9)
$$
���~$i_1\,i_2\,\ldots{}\,i_n$---���������� ������������ ������������
���������~$\set{1, 2,~\ldots, n}$, �����, ���~$i_j<i_{j+1}$,
����~$a_{i_j}=a_{i_{j+1}}$; ������� �������, ��~$i_j>i_{j+1}$
�������~$a_{i_j}<a_{i_{j+1}}$. ����, ��� ���� �
������������~$i_1\,i_2\,\ldots\,i_n$ ���������� $k$~��������, �� �����
��������������� ��
�������������������~$a_1\,a_2\ldots{}a_n$ �����~$\perm{m+n-k}{n}$; ���
����� ����� �������� �������~(8), ���� ��������~$k$ ��~$n+1-k$.

��, ��������, $n=9$, $i_1\,i_2\ldots{}i_n=3\,5\,7\,1\,6\,8\,9\,4\,2$ �
��������� ���������� ����� �������������������~$a_1a_2\ldots{}a_9$,
�����, ���
$$
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)
$$
��� ����� ����� �������������������~$b_1\,b_2\ldots{}b_9$, �����, ���
$$
1\le b_1 < b_2 < b_3 < b_4 < b_5 < b_6 < b_7 < b_8 < b_9 \le m+5,
$$
%%53
��� ��� ����� ��������~$b_1=a_3$, $b_2=a_5+1$, $b_3=a_7+2$, $b_4=a_1+2$,
$b_5=a_6+3$ �~�.~�. ����� ��������, �������� ����� ������� ��������~$b$,
����� ������-�������� ����� �������� ������� 9~��������� ��~$m+5$,
�.~�.~$\perm{m+5}{9}$; ����������� �������������� �������
��� ������������~$n$ �~$k$ � ����� ������������~$i_1\,i_2\ldots{}i_n$
� $k$~���������.

� ��� � ����� ������ ���������~(8) ����� �������� ��~$m$, �� ������~$m$
����� ���������� ����� �������������� �����, ������� ���������� ���������
�������� ����� ���������������� ������������ ������������:
$$
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)
$$
퀏�����,
$$
x^3=\perm{x}{3}+4\perm{x+1}{3}+\perm{x+2}{3}.
$$
� �������� ��������� ������ ����� �������� ����� ������ ������ ������� ���
�������� ���������� ����������. ���� �~(11) $x=1$, ������� ��� ���, ���
$$
\eul{n}{n}=1,
$$
��������� ������������ ������������ ���������� �~$0$ �� ���� ���������,
����� ����������. ����~$x=2$, �������
$$
\eul{n}{n-1}=2^n-n-1, \rem{$n\ge1$.}
\eqno(12)
$$
������~$x=3$, $4$,~\dots, ��������, ��� ��� �����~$\eul{n}{k}$ ���������
������������ ������������~(11), � ������ � �������, ������� ��������� �������:
$$
\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
}
$$

臓��� ������ ������������ ������� ��� ��������. 呋� ��������
$$
g_n(z)=\sum_k \eul{n}{k} z^k/n!,
\eqno(14)
$$
%%54
�� ����������� ���~$z^k$ ����� ����������� ����, ���
��������� ������������ ���������~$\set{1, 2,~\ldots, n}$ �������� �����
$k$~��������. ������ $k$~�������� � ������������ ����� �� ��������,
��� �~$n+1-k$, �� ������� ����� �������� ������
���������~${1\over2}(n+1)$, �, �������������, $g'_n(1)={1\over2}(n+1)$. �
���.~2(b) ��������, ��� ����� ����� ������� ������� ��� \emph{����}
����������� �������~$g_n(z)$ � �����~$z=1$:
$$
g_n^{(m)}(1)=\Stir{n+1}{n+1-m}/\perm{n}{m}, \rem{$n\ge m$.}
\eqno(15)
$$
�, � ���������, ���������~$g''_n(1)+g'_n(1)-g'_n(1)^2$ �����~$(n+1)/12$
���~$n\ge2$, ��� ��������� �� �������� ���������� ������������� �����
�������� ��������. (� ����� ��� �� �������� � ���.~3.3.2-18; ��� ���
����������~$\covar(R'_1, R'_1)$.) �������~$g_n(z)$---�������, ������� �
������� �������~(15) ����� ��������� �� � ��� 򅉋���
$$
\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
}
$$
⒎��� ��������� ������� �� �������, ��� ��� �� �������� ���������~(7)
$$
g_n(z)=z^{n+1} g_n(1/z), \rem{$n\ge1$.}
\eqno(17)
$$
� ������������� ����������� ��� ����� 񒈐�����
$$
\Stir{n+1}{k+1}=(k+1)\Stir{n}{k+1}+\Stir{n}{k}
$$
���������� ��� ���� ����� ������� �������������:
$$
\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
}
$$

��������� ������� �� ���� ����������\note{1}%
{� ��������� "super generating function". 񎎒������������ �������
� ������������� ���������� �� ����������.---{\sl �. ���.\/}}
$$
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
�����, �������������,
$$
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)
$$
��� ��� ���� �����������, ������������� �������.

䐓��� �������� ����� ������ ����� ����� � �������� ������  �.~ꀐ����
[{\sl Math. Magazine,\/} {\bf 33} (1959), 247--260]; ��.~����� �.~�������,
₅����� � ������������� ������, ��, �., 1963, ���.~50, 253, 254.

���������� ������ ����� ��������; ������ � ������� ����� �������? �
�.~3.3.2 �� ��� ������� �������������� �������� ����� �������� ������
�����; ������� ����� ������� ����� ��������~2 � �������� � ��� ������,
��� � ��������� ������������
�����~$n$ ���������� � ������� ${1\over2}(n+1)$~��������. ����������
� ���������� ���������� ������� ��������� �������� ����� ������;
���������� ����� $k\hbox{-��}$~����� ������� ������������
���~$k=1$, $2$,~$\ldots\,$.

ꀊ���, ��������, ����� ������� (�������� �����) ������� ���������
������������~$a_1\,a_2\,\ldots\,a_n$? 僎 ����� ������~$\ge 1$; ���~$\ge2$
����� � �������� ������� (� ������, ����~$a_1<a_2$). 僎 �����~$\ge3$
����� ��� $1/6$~������� (����~$a_1<a_2<a_3$). ⎎��� ��� �����~$\ge m$ �
������������~$q_m=1/m!$ ���~$1\le m \le n$. 񋅄���������, �����������
����, ��� ����� ����� ������� ����� � ��������~$m$, ����
$$
\eqalignno{
p_m &= q_m-q_{m+1}=1/m!-1/(m+1)! \rem{��� $1\le m < n$;} \cr
p_n &= 1/n!. & (21) \cr
}
$$
񐅄��� ����� �����, ����� �������,
$$
\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
}
$$
��� ���~$n\to\infty$ �����~$e-1=1.71828\ldots$, � ��� ��������~$n$  ���
�������� �����~$e-1-\delta_n$, ��� $\delta_n$~�������� ����:
$$
\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)!}.
$$
���� ��� ������������ ����� ������ ����������� ������� ���������
\emph{�����������} ������������������ ��������� �����
$$
a_1, a_2, a_3, \ldots;
$$
��� "������������" ������������������ �� ����� ������������� ��, ��� ���
$n!$~��������� �������� ������������ ������~$n$
%%56
��������� ������������������ �������������. � ��� ������� ����� �������
������� ��������� ����������� ������������������ �����~$e-1$.

텑������ ���������������� ���� �����, ����� ���������� ������� �����
$k\hbox{-��}$~������� ��������� ������������������.
�� $q_{km}$---����������� ����, ��� ����� ����� ������~$k$ ��������~$\ge m$;
����� $q_{km}$~����� ��������~$1/m!$, ���������� �� �����
������������ ���������~$\set{1, 2, \ldots, m}$, ���������� �� ����� $k$~��������:
$$
q_{km}=\left(\eul{m}{1}+\cdots+\eul{m}{k}\right)\Big/ m!.
\eqno(23)
$$
⅐�������� ����, ��� ����� ����� ������ $k$~�������� �����~$m$,
 ����~$q_{km}-q_{k(m+1)}$. 񋅄���������, ��������� �����~$L_k$
������� ����� $k\hbox{-��}$~�������, �������, ���
$$
\eqalign{
L_1+\cdots+L_k&=\hbox{(������� ����� ����� ������ $k$~��������)} =\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
}
$$
⛗����~$L_1+\cdots+L_{k-1}$ � ��������� ��������~$q_{km}$, ��~(23)
�������� ������ ��� �������:
$$
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)
$$
������~$\eul{0}{k}=0$ ���~$k\ne 1$, ��������~$L_k$ ����������� ������
������������ ���~$z^k$ � ������������ �������~$g(z, 1)-z$. (��.~(19));
����� �������, �����
$$
L(z)=\sum_{k\ge0} L_k z^k = {z(1-z) \over e^{z-1}-z}-z.
\eqno(25)
$$
� ������� ������~(13) ������� �������������~$L_k$ � ���� �������� ��~$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
��� ������� ���~$L_k$ ������� �������� �.~�.~㝑����
[{\sl CACM,\/} {\bf 10} (1967), 89--93]. 茅��, � ���������,
$$
\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
}
$$
蒀�, ������� �������, ��� ������ ������� ����� ������� �������, �
������ ������� ����� � ������� ��� �������! � ������ ������ ��� �����
���������� ��������, �� ����� ��������� ����������� ���������� ����, ���,
��������� ������ ������� ������� ������� ����� ������ ����� ����� ������
(������ ��� ������ �������� ��������� ������� �������), � �������
������� ������ ������ ��������� �������, ��� � �������. 򅍄����� ������,
��� ������ ������� �������� ������� ����� ���� ������, ��� ������ �������
������� �������.

�����~$L_k$ ����� � ������ ���������� ����������� ������ � ����������
(�.~5.4.1), ������� ��������� �������� ������� �� ��������. � ����.~2,
����������� �.~�.~������~(��.), ��������� ������~18 ��������~$L_k$ �
��������� ��~15 ���������� ������. �����������, ����������� � ����������
������, ����� ������� ����������, ���~$L_{k+1}>L_k$; �� ����� �� ����
�������� ����������, �� ���������, �� ������. 瀌����, ���~$L_k$
������ ������������ � ����������� ��������~2; ������ ������������� ��, ���
��� ������������� �������� �� ���������������� �����~$e$ ��� ������
�������� � ������������� �����~2! �����~(26) ������������ ���������
������� � � ����� ������ ���������� �������, ������ ���������� ��������
������ �������� ���� ��� ��������� ����� ������ �����; ���������
19-������� ���������� � ��������� ������, 㝑���� ������ � ���������
���������� � ���, ���~$L_{12}>2$, � ���� �������, ��� 42-������� ����������
\htable{򀁋���~2}%
{񐅄��� ����� ��������}%
{\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
� ��������� ������ ����~$L_{28}$ ���� � ��������� �� 29~�������� ����.

��������������� ���������~$L_k$ ����� ����������, ������ �� �������
��������� ������ ������� ������������ �����������.
\picture{���.~3 ꎐ�� ���������~$e^{z-1}=z$. ������� ����� �������������
���������~$e^{x-1}\cos y = x$, �������� �����---���������~$e^{x-1}\sin y = y$.
}
獀�������� �~(25) ���������� � ���� ���� ���~$e^{z-1}=z$,
�.~�.\ (�������~$z=x+iy$) �����
$$
e^{x-1}\cos y = x \rand e^{x-1}\sin y =y.
\eqno(27)
$$
� ���.~3, ��� �������� ��� ������� ���� ���������, �����, ��� ���
������������ � ������~$z=z_0$, $z_1$, $\bar z_1$, $z_2$, $\bar z_2$,~\dots;
�����~$z_0=1$,
$$
z_1= (3.08884\,30156\,13044-)+(7.46148\,92856\,54255-)i
\eqno (28)
$$
� ��� �������~$k$ ������ �����~$\Im(z_{k+1})$ ����� ��������������~$\Im(z_k)+2\pi$.
%% 59
� ���
$$
\lim_{z\to z_k} \left({1-z \over e^{z-1}-z}\right)(z-z_k)=-1
\rem{���~$k>0$}
$$
� ���� ������ �����~$-2$ ���~$k=0$, �� �������
$$
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}
$$
�� ����� ������������ � ����������� ��������� ���~$\abs{z}<\abs{z_{m+1}}$.
獀���, $R_m(z)$ ����� ��������� � ��������� ���~$\sum_k \rho_k z^k$,
�o�op�� �������� ��������� ���~$\abs{z}<\abs{z_{m+1}}$; ������ �������,
���~$\rho_k M^k \to 0$ ���~$k\to\infty$, ���~$M=\abs{z_{m+1}}-\varepsilon$.
ꎝ����������� ���~$L(z)$ ������ ������������ ���������� �������
$$
{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,
$$
� ������
$$
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)
$$
���� ��������
$$
z_k=r_k e^{i\theta_k}.
\eqno  (30)
$$
��� ����� ���������� ��������������� ���������~$L_n$. 茅��
$$
\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)
$$
����� �������, ������� ����� �~$L_n-2$ ����~$r_1$ �~$\theta_1$, �
���~(29) �������� ����� ������. �������� ����� ��������~$r_1$
�~$\theta_1$ ������� �.~�.~������~(��.) 䀋������� ������
[W.~W.~Hooker, {\sl CACM,\/} {\bf 12} (1969), 411--413] ����������,
���~$R_m(z)\to -z$ ���~$m\to\infty$; �������������,
���~$2\sum_{k\ge 0} z_k^{-n}\cos n\theta_k$  ������������� \emph{��������}
�~$L_n$ ���~$n>1$.

쎆�� �������� ����� ���������� ������������ ������������, ����� ���������
���������� ������������� ������������ ���  ����� $k\hbox{-��}$~������� �
��� ����� ����� ������~$k$ �������� (��.~���.~9, 10, 11), ��������
�����~$L_1+\cdots+L_k$ �������������� ������������ �~$2k-1/3$.

%% 60

� ���������� ����� ������ ���������� �������� �������� � ������, ����� �
������������ ����������� ���������� ��������. ᅑ��������� ��������,
������� �������� ���� ������ ���������� ������������ �������� 19-�� ����
񀉌�� 휞����, ����� ���������������� ��������� � ������������� ���
�������. � ���� ������ ���� � ��������� �� � ���� ������ �� ��� ���,
���� ��� ��� � ����������� ������� �� �����������; ��� ������ ���������
����� ����������� ������ ����������, �� ������� ����� ������. � �����
����� ����������� ����, ��� � ���������� ��� ������ �������� ����������� �
�������� ���������� ������.

瀄��� 񀉌��� 휞����� �������, �������������, � ����������
������������� ������������ ��� �������� ��������� ������������
���������������. � ����� ������ ����� �������� ������ (��. ���.~12), ����
�� ��� ������, ��� ������ ������ � ������� ������, ����� ��� �����
�������� �� �����������. � �������������� ����� ������� ������� ���
\emph{��������} ����� ������ � ���� ��������.

�� ������� $m$ ��������� ����� ���� � ������ ����������� ����� $p$ ���.
퀏�����, � ������� ������ ��� ������ $m=13$, � $p=4$, ���� ������������
��������� �����. 瀌���������� ��������� ��������� � ���� ������
�.~�.~쀊-쀃�� [Combinatory Analysis (Cambridge, 1915), ���~1,
���.~212--213]: ����� ������������ � $k+1$~��������� ����� �����
������������ � $mp-p-k+1$~���������. ��� ����������� ����� ���������
���~$p=1$ (������� (7)), ������ ��� $p > 1$ ��� ������� �������� �����������.

쎆�� �������� ��� �������� ���������, ��������� ������� �����������
������������ ����� ��������������, �����, ��� ������ ������������ �
$k+1$ ��������� ������������� ������, � $mp-p-k+1$~���������. �
���������� ����������� �������� ������ ����������� ����� �����
������������, ������ ��� ��������� ������.

ꀊ���-������ ����� �������� ������������ �� �� �� ��������;
�������������� 쀊-쀃��� �������� �� ������������ ��������, � �� ��
������������� ����������. ��� ������������� 􎀒�� ������������
(�������~5.1.2�) ��������� ��������� ������, ��� ��� ��� ������������
������������� ������� ������������ ������������ ����� �������������� �
$k+1$~��������� � ��������������, � ����������� ������������� �������
���������� ����� $k$~�������� $y\atop x$, �����, ��� $x<y$.

�� ���� ��������������� $\set{p\cdot 1, p\cdot2, \ldots, p\cdot m}$;
���������� ������������ � ����������� ������������
$$
\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
