\input style
\chapnotrue\chapno=5\subchno=1\subsubchno=3
񎏎������ � ��� ������ ������������ ���� �� ���������������:
$$
\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)
$$
���~$x'=m+1-x$. 呋� ������������~(32) �������� $k$~�������� ����~$y \atop x$, 
�����, ���~$x<y$, ��~(33) ��������~$(m-1)p-k$ �����
��������, ������ ��� ���������� ����������� ���� ������~$y>1$, � 
�����������~$x<y$ ������������~$x' \ge m+2-y$. 
������~(32) ������������� ������������ � $k+1$~���������, 
�~(33)---������������ � $mp-p-k+1$~��������� � ��������������, 
�����������~(32) �~(33), �������� (��� �� ���������~(33) �~(32)), �� ��� 
����� �������� ������� ��������� 쀊-쀃���. ��� ����� ���������� 
���������� � ���.~14.

� ���� �������� ��������� ������� ����� �������� � ��������� 
������������ ������ 
���������~${1\over2}(( k+1)+(mp-p-k+1))=1+{1\over2}p(m-1)$. 퀏�����, ��� 
����������� ������ �������
����� ������ � �������� 휞����� �����~$25$ (��� ��� ������������� ����� 
�������� ���� �� ��������� ����� �� ������������� ��������).

� ����� ����, ��������� ������ ������� �����������, ����� ���������� 
������� ����� �������� � ����� ������ ��� \emph{������} ������� 
���������������~$\set{n_1\cdot x_1, n_2\cdot x_2,~\ldots, n_m\cdot x_m}$, 
��� ���~$x$ ��������. ��~$n=n_1+n_2+\cdots+n_m$, � ���������� ����, 
��� ��� ������������~$a_1\,a_2\,\ldots\,a_n$ ����� ��������������� 
�������� � ����� ����; ���������, ��� ����� $a_i$ ����������� 
������~$a_{i+1}$ ��� ������ ������������� ��������~$i$, $1 \le i < n$. 
����� �������, �����~$a_i>a_{i+1}$, ����� � �������� �������� ����� 
�������, �����~$a_i \ne a_{i+1}$, � �������� ������, ���~$a_i=a_{i+1}=x_j$ 
����� � $N n_j(n_j-1)/n(n-1)$~�������, ���~$N$---����� ����� ������������. 
񋅄���������, $a_i=a_{i+1}$ ����� �
$$
{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)
$$
�������, a~$a_i>a_{i+1}$ ����� �
$$
{N\over 2n(n-1)}(n^2-(n_1^2+\cdots+n_m^2))
$$
�������. 񓌌���� ��~$i$ � ���������~$N$, ������ ��� � ������ ������������ 
���� ������� ��������� ���������~$a_n$, ������� ����� ����� �������� �� 
����~$N$ �������������:
$$
N\left({n\over2}-{1\over 2n}(n_1^2+\cdots+n_m^2)+1\right).
\eqno(34)
$$
���� ��~$N$, ������� ������� ������� ����� ��������. 
%%62

� ��� ������� ����� ��� �������� "���������� ���������", ������� ������ 
�������� ����������, ����������� ��, � ��� ����� � ��������� ������ ����� 
��������, �� ������������� �����. 䎏����������� ���������� ����� ����� � 
����� �.~�.~䝂�� �~�.~�.~တ���� Combinatorial Chance (London: Griffin, 1962), 
��.~10, � � �������� ������ �.~�.~တ���� �~�.~�.~읋����� 
[{\sl Annals of Math. Statistics,\/} {\bf 36} (1965), 236--260]. 
䀋������� ����� ����� ������� ������ � �������������� ��������������� � 
������ �.~􎀒� �~�.~�.~���������� Th\'eorie G\'eom\'etrique des Polyn\^omes 
Eul\'eriens (Lecture Notes in Math., 138 (Berlin: Springer, 1970), 94~���.).

\excercises
\ex[�26] ⛂����� ������� ������~(13).

\rex[�22] (�)~�������� ������ ������� ����, �������������� � ������ ��� 
�������������� ���������~(8): ����������� ������������������~$a_1\,a_2\,
\ldots\,a_n$, ���������� �����~$q$ ��������� ���������, � ��������, ���
$$
\sum_k \eul{n}{k} \perm{k-1}{n-q}=\Stir{n}{q}q!.
$$
(b)~葏������ ��� ���������, ��������, ���
$$
\sum_k \eul{n}{k}\perm{k}{m}=\Stir{n+1}{n+1-m}(n-m)!
\rem{���~$n\ge m$.}
$$

\ex[��25] ⛗������ �����~$\sum_k \eul{n}{k}(-1)^k$.

\ex[�21] ���� ����� �����
$$
\sum_k (-1)^k\Stir{n}{k}k!\perm{n-k}{m}?
$$

\ex[�20] 퀉���� ��������~$\eul{p}{k}\bmod p$, ����~$p$---������� �����. 

\rex[�21] 숑��� 򓏈�� �������, ��� �� ������~(4) �~(13) ����� ��������
$$
n!=\sum_{k\ge0} \eul{n}{k}=\sum_{k\ge0}\sum_{j\ge0} (-1)^{k-j}\perm{n+1}{k-j}j^n.
$$
������ ������������ ������� ��~$k$, ����� ��~$j$, �� ���������, 
���~$\sum_{k\ge0} (-1)^{k-j}\perm{n+1}{k-j}=0$ ��� ����~$j\ge0$, 
������~$n!=0$ ��� �����~$n\ge0$. � �������� �� �� �����-������ ������?

\ex[��40] ߂������ �� ������������� ������������ ��� ��������, 
���������� ��������~(14), �������������� ����������? (�.~�~���.~1.2.10-13.)

\ex[�24] (�.~�.~쀊-쀃�� ) �����, ��� ����������� ����, ��� 
����� ������� ������� ���������� ������� ������������ ����~$l_1$, ����� 
������� 
%%63
����~$l_2$,~\dots, � ����� $k\hbox{-�� �������}\ge l_k$, �����
$$
\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] ��~$h_k(z)=\sum p_{km} z^m$, ���~$p_{km}$---����������� ����, 
��� ����� ����� ������ $k$~�������� (�����������) ��������� 
������������������ �����~$m$. 퀉���� "�������" ��������� ���~$h_1(z)$, 
$h_2(z)$ � ��� ������������ �������~$h(z, x)=\sum_k h_k(z) x^k$ �� ���� ����������.

\ex[BM30] ������� ��������������� ��������� �������� �������� 
� ��������� �������������~$h_k(z)$ �� ����������� ���������� ��� �������~$k$.

\ex[�40] ��~$H_k(z)=\sum p_{km} z^m$,  ���~$p_{km}$---����������� ����, 
��� ����� $k\hbox{-��}$~������� � ��������� (�����������) 
������������������ �����~$m$. ⛐�����~$H_1(z)$, $H_2(z)$ � ������������ 
�������~$H(z, x)=\sum_k H_k(z) x^k$ �� ���� ���������� ����� ��������� �������.

\ex[M33] (�.�.~쀊-쀃��.) ����� �������~(13) �� ������ ������������ 
���������������, �������, ��� ����� ������������ 
���������������~$\set{n_1\cdot 1, n_2\cdot 2,~\ldots, n_m\cdot m}$, 
������� ����� $k$~��������, �����
$$
\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},
$$
���~$n=n_1+n_2+\cdots+n_m$.

\ex[05] ꀊ�� ����� ������� ����� ������ � �������� 휞�����, 
���� ������������ ������� ������� ��� ������ (�� 52~����), ��������� 
����������� ����, �� ������, ���
$$
\clubsuit < \diamondsuit < \heartsuit < \spadesuit?
$$

\ex[M17]  ���������~$3\,1\,1\,1\,2\,3\,1\,4\,2\,3\,3\,4\,2\,2\,4\,4$ 
�������� $5$~��������; ������� � ������� ������������ � ������ ���������� 
��� ������� ��������� 쀊-쀃��� ��������������� ������������ � $9\hbox{-�}$~���������.

\rex[�21] \exhead(����������� �������.) � ������������ ���������� 
$19\hbox{-��}$~���� �� �������������� ������� �� �������� ������ �� 
�������� � �������������, ������� ������������� ��, �� ���� ��������� 
������, ����������� ����������� ������������ � ��������� "��������". �, 
���������, ��� ������������~$5\,3\,2\,4\,7\,6\,1\,8$ �������� $4$~�������
$$
5\,3\, 2, \quad     2\,4\,7,\quad    7\,6\,1,\quad    1\,8.
$$
(��� ������� ����� ������������ ��� ��������� � ����������� �� ����,
$a_1<a_2$ ���~$a_1>a_2$; ����� �������, ������������~$a_1\,a_2\ldots\, a_n$, 
$a_n\,\ldots\,a_2\,a_1$ �~$(n+1-a_1)\,(n+1-a_2)\ldots (n+1-a_n)$ ��� 
�������� ���������� ����� �������������� ��������.) 쀊��������� ����� 
�������� ����� ���� � ������������ $n$~��������� �����~$n-1$.

퀉���� ������� ����� �������������� �������� � ��������� 
������������ ���������~$\set{1, 2,~\ldots, n}$. 
[\emph{󊀇����:} ��������� ����� �������~(34).]

\ex[M30] ������ ���������� ����������. ��~$\Eul{n}{k}$---����� ������������
%%64
���������~$\set{1, 2,~\ldots, n}$, ������� ����� ����� 
$k$~�������������� ��������. 퀉���� ������������ �����������, � ������� 
�������� �����
��������� ������� ��������~$\Eul{n}{k}$; ������� ����� ��������������� 
������������ ����������� ��� ������������ 
�������~$G_n(z)=\sum_k \Eul{n}{k} z^k \big / n!$. 葏������ ��� ��������� 
������������ �����������, ������� ������� ������� ��� \emph{���������} ����� 
�������������� �������� � ��������� ������������ ���������~$\set{1,2,
~\ldots, n}$.

\ex[M25] 񓙅������ �����~$2^n$ ������������������� $a_1\,a_2\,a_n$, ��� 
������ �������~$a_j$---����~$0$, ����~$1$. 񊎋��� ����� ��� 
�������������������, ���������� ����� $k$~�������� (�.~�.~���������� 
�����~$k-1$  ���������~$a_j$, �����, ���~$a_j>a_{j+1}$)?

\ex[M27] 񓙅������ �����~$n!$ �������������������~$a_1\,a_2\,\ldots\,a_n$,
��� ������ �������~$a_j$---����� �����, ������� � 
���������~$0 \le a_j \le n-j$; ������� ����� ��� �������������������, 
���������� ����� 
$k$~�������� (�.~�.~���������� �����~$k-1$ ���������~$a_j$, �����, ���~$a_j>a_{j+1}$)?

\rex[M26] (�.~�������.) (�)~񊎋����� ��������� ����� ����������� 
$n$~����������� ����� (�.~�.~������� ��� �� ������ ���������� �� ����� ���������
\picture{
 ���.~4. 텀�������� ����� �� ��������� ����� ��� �������� ����� 
 ����� ���� ������� ���������.
}
��� �����������) �� ��������� ����� �������~$n\times n$ ���, ����� 
�����~$k$ �� ��� ���������� �� �������� ������� �� ������� ���������? 
(b)~񊎋����� ��������� ����� ����������� $k$~����������� ����� �� 
�������� ������� �� ������� ��������� ��������� ����� �������~$n\times n$?

퀏�����, �� ���.~4 ������� ���� �� $15619$~�������� ����������� 
������ ����������� ����� �� ������� ��������� ����� � ����� ������� �� 
���������������� ������� ���� ������� ���������, � ����� ���� �� 
$1050$~�������� ����������� ��� ����������� ����� �� ����������� �����.

\rex[�21] ㎂����, ��� ������������ ������� $k$~\emph{������,} ���� �� 
����� ����������� $k$~���, ����� �������, ����� ��������� ��� �������� � 
����������� �������. 퀏�����, ������������
$$
4\,9\,1\,8\,2\,5\,3\,6\,7
$$
%%65
������� ������� ������: ��� ������ ������ ��������~$1,2,3$; ��� 
������---$4, 5, 6, 7$; �����~$8$; �����~$9$. 퀉���� ����� ����� ��������� 
� ��������.

\ex[M22] 呋� ������������~$a_1\,a_2\,\ldots\,a_n$ 
���������~$\set{1, 2, ~\ldots, n}$ �������� $k$~�������� � ������� $j$~������ 
� ������ ���.~20, �� ��� ����� ������� � ������������~$a_n\,\ldots\,a_2\,a_1$?

\ex[M26] (�.~ꀐ���, �.~�.~������ �~�.~�.~񊎓����.) �����, ��� �� 
���������� ������������ ���������~$\set{1, 2,~\ldots, n}$ � 
$n+1-r$~���������, ��������� $s$~������, ����~$rs<n$, ������ ����� 
������������ ����������, ����~$n\ge n+1-r\ge s \ge 1$, $rs\ge n$.

\ex[BM42] (​���� ⅉ������.) "󄋈������ �������" 
������������~$a_1\,a_2\,\ldots\,a_n$ ����������, ���� ��������� ������������ 
�������� � ��� ������, ��� ���������� �������������� ������������; ���������� 
������� ������ ��� �������������, ��� � ���������� � ����������� �� ����, � 
����� ������� ����������� ������ ��� ��������, ��� ��� ����� ������� ����������� 
������� (�����, ��������, ����������)${}\ge2$. 퀏�����, 
������������~$7\,5\vert6\,2\vert3\,8\,9\vert1\,4$ �������� ������ ���������� 
�������. 퀉���� ������� ����� ������ ���� ���������� �������� ����������� 
������������ � ��������, ��� � ������� ����� ����������� ������� �����
$$
\left(1+\ctg{1\over2}\right)\Big/\left(3-\ctg{1\over2}\right)\approx 2.4202.
$$

\ex[M30] ⛐����� � ���� ������� ��~$p$ ������� ����� �������� � 
�������������������, ���������� �������, ������� ������ � ���.~5.1.1-18.

\subsubchap{*򀁋� � ���������} %5.1.4.
� ���������� ������ ������ ������������� ������� ������������ ������� 
��������� ������������� ���������, ����������� ������������ � ��������� 
����� �����, ����������� �����. \dfn{򀁋� ߍ�� �����~$(n_1, n_2,~\ldots, n_m)$,}  
���~$n_1\ge n_2 \ge \ldots \ge n_m \ge 0$, ��� ������������ 
$n_1+n_2+\cdots+n_m$~��������� ����� ����� � ������ �����, ����������� 
�� ������ ����, ��� � $i\hbox{-�}$~������ ���������� $n_i$~���������; 
��� ���� � ������ ������ �������� ���������� ����� �������, � �������� 
������� ������� ���������� ������ ����. 퀏�����,
$$
\tableau{
1 & 2 & 5 & 9 & 10 & 15 \cr
3 & 6 & 7 & 13 \cr
4 & 8 & 12 & 14 \cr
11 \cr
}
\eqno(1)
$$
---����� ߍ�� �����~$(6, 4, 4, 1)$. 򀊈� ������������ ���� ������� ߍ� 
�~1900~�. � �������� ���������������� �������� ��� �������� ���������� 
������������� ������������. 
[�., ��������, D.~�.~Rutherford, Substitutional Analysis (New York: Hafiier,
%%66
1968)]. 䋟 ��������� �� ����� ������ "����� ߍ��" �������� ������ "�����".

\dfn{荂������}---��� ������������, �������� ����� ����. 퀏�����, 
���������� 10 ��������� ���������~$\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)
$$
򅐌�� "���������" ������������� ������������� � ������������ ������� 
���������; ��������� � ����� ������, ��������������� �����, ���� ������� 
������� X.~�.~����, ����� �� ���� ������� �������� ������������ (��.~�.~5.1.1).

쎆�� ���������� ��������, ��� �� ������������� ����� � ��������� ������, 
�� ���������� ������������ ����� ����� ����� ���������, �� ��������, 
�������� ��, ���� � ����� �������� ���������: \dfn{����� ��������� 
���������~$\set{1, 2,~\ldots, n}$ ����� ����� �����, ������� ����� 
������������ �� ���������~$\set{1,2,~\ldots, n}$.} 퀏�����, 
��~$\set{1, 2, 3, 4}$ ����� ������������ ����� 10~�����
$$
\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)
$$
��� ������������� 10~����������~(2).

��� ����� ����� ����������� � ����� ������ �� ��������, �, ��-��������, �� 
���������� �������� ������� �� ��������. 䎊�����������, ������� �� 
�������, �������� ���������� �������� ���������� �����, ���������� � 
���������� ������� ������������ ����������; �� ������� �� ������ 
��������� ������� � ����� ����� ���������.

%% 67

��������, ��������, ��� ����� �������� �������~8 � �����
$$
\tableau{
1 & 3 & 5 & 9 & 12 & 16 \cr
2 & 6 & 10 & 15 \cr
4 & 13 & 14 \cr
11 \cr
17 \cr
}
\eqno (4)
$$
셒��, ������� �� ����� ������������, ������� � ���, ����� ������� 
���������~8 � $1\hbox{-�}$~������, � ������, ����� ����������~$9$,
���������~$9$---���������� �� ��������� ���� ������, 
�������~$8$. �������~$9$ "�����������" ����, � ������~$2$, ��� �� 
��������~$10$. 瀒��~$10$ "���������"~$13$ �� $3\hbox{-�}$~������ � 
$4\hbox{-�}$ �, ��������� � $4\hbox{-�}$~������ ��� �������� ������~$13$, 
������� ����������� �����������~$13$ � ������ ����� ������~$4$. 퀘� ����� 
��������������� �
$$
\tableau{
1 & 3 & 5 & 8 & 12 & 16 \cr
2 & 6 & 9 & 15 \cr
4 & 10 & 14 \cr
11 & 13 \cr
17 \cr
}
\eqno (5)
$$

򎗍�� �������� ����� �������� � ��������������� ����, ��� �� ������ 
��������� �������� �����, ���������� � ���������~I.

\alg I.(⑒���� � �����.) ��~$P=(P_{ij})$---����� ����� ������������� 
�����, �~$x$---����� ������������� �����, �� ������������ �~$P$. ���� 
�������� �����������~$P$ � ������ �����, ����������~$x$ ������ � ��������� 
����������~$P$. 펂�� ����� ����� �� �� �����, ��� � ������, � ��� ���� 
��������, ��� �� ����������� ������~$s$ � �������~$t$ �������� ����� 
�������, ���~$s$ �~$t$---��������, ������������ ����������.

(� ���� ��������� ��������� � ������� ������� ������������� ��� 
�������������� ��� ������������, ��������� �� �������� ����� ���������, 
��� ��� ��������� ����������� � ��� ������~$P$ ���������� ���������� 
����� �� ���������� ����� ��������. 䋟 �������� ����� ������������, ��� 
����� ����������
%% 68
������ ������ � ����� � ���������~$\infty$ ������ � �����, ��� 
��� �������~$P_{ij}$ ��������� ��� ����~$i$,~$j\ge 0$. 呋� ������ ���������
$$
a \simlt b \rem{����� � ������ �����, �����~$a<b$ ���~$a=b=\infty$,}
\eqno (6)
$$
�� ����������� ��� ����� ����� �������� � ������� �����:
$$
\displaynarrow{
P_{ij}=0, \rem{����~$i=0$ ���~$j=0$;}\cr
P_{ij}\simlt P_{i(j+1)} \rand P_{ij} \simlt P_{(i+1)j} 
\rem{��� ����~$i, j\ge 0$.}\cr
}
\eqno(7)
$$
󒂅������� "$x\notin P$" ��������, ��� ����~$x=\infty$, ����~$x$ �� 
�����~$P_{ij}$ �� ��� �����~$i, j\ge 0$.)

\st[₅���~$x$.] 󑒀������~$i\asg 1$, $x_1\asg x$, � $j$~���������� 
������ ����������� ��������, ������, ���~$P_{1j}=\infty$.

\st[퀉��~$x_{i+1}$.] (� ���� ������~$P_{(i-1)j} < x_i < P_{ij}$ 
�~$x_i\notin P$.) 呋� ~$x_i<P_{i(j-1)}$, �� ���������~$j$ ��~$1$ � 
��������� ���� ���. � ��������� ������ ����������~$x_{i+1}\asg P_{ij}$  
�~$r_i\asg j$.

\st[瀌����� ��~$x_i$.] (򅏅��~$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}$ 
�~$r_i=j$.) 󑒀������~$P_{ij}\asg x_i$.

\st[$x_{i+1}=\infty$?] 
(򅏅��~$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$ 
�~$x_{i+1}\notin P$.) 呋�~$x_{i+1}\ne \infty$, �� ���������~$i$ ��~$1$ � 
��������� � ����~\stp{2}.

\st[�������~$s$, $t$.] 󑒀������~$s\asg i$, $t\asg j$ � ��������� 
������ ���������. (� ����� ������� ����������� �������
$$
P_{st}\ne\infty, P_{(s+1)t}=P_{s(t+1)}=\infty.)
\eqno(8)
$$
\algend

瀌����, ��� ���� �������� ���������� "������������������ ����������"
$$
x=x_1<x_2<\ldots<x_s<x_{s+1}=\infty,
\eqno(9)
$$
� ����� ��������������� ������������������ �������� ��������
$$
r_1\ge r_2 \ge \ldots \ge r_s = t;
\eqno(10)
$$
��� ���� �������~$P_{ir_i}$ ������ ���� �������� �~$x_{i+1}$ ��~$x_i$, 
$1\le i \le s$. 퀏�����, ����� � �����~(4) ���������� �������~$8$, 
������������������� ���������� ����~$8$, $9$, $10$, $13$, $\infty$, � 
��������������� �������������������---$4$, $3$, $2$, $2$. � ����� �� 
����������������� �������� ���, ����� �� ���������� ������ 
��������� ������ (���������� ������� ������ ������� ��������~$j$, $x_i$, $x_{i+1}$);
������������������~(9) �~(10) ���� ������� � ��� ���� �����, ����� ����� 
���� �������� ��������� ���������� �����, ���������� ����� ���������.

����� �������� ���������~I, ������� �� �� �������� ���������������, 
������� � ���, ��� �������� ����� "����������" � �������� �����������: 
�� ��������~$s$ �~$t$, ������������
%% 69
� ����~I5, ����� �������������~$P$ � ��������� ����, ����� � ������ 
�������~$x$, ������� ��� ��������. ����������, ��������, (5), � ����� 
��� ��������, ��� �������~$13$ �������� �������, ������� ������ ���� 
�����. 򎃄� �������~$13$, ������ ����, ��� �������� ���� �� 3-� ������ 
������~$10$, ������ ��� $10$---���������� ������� � ���� ������, 
�������~$13$; ����������, �������~$10$, ��-��������, ��� �������� �� 2-� 
������ ������~$9$, ������� � ���� ������� ���� ��������� �� 1-� ������ 
������~$8$. 򀊈� �������, ��~(5) ����� ��������� ������� �~(4). � 
��������� ��������� �������� ������ ���� �������.

\alg D.(󄀋���� �� �����.) � ��������� �����~$P$ � ����� ������������� 
������~$s$ �~$t$, ��������������� ��������~(8), ���� �������� 
�����������~$P$ � ������ ����� ����� ����� �� �����, �� �~$\infty$ �� 
����������� �������~$t$ � ������~$s$. ��������� ���������� 
�������~$x$ ��������� �� �����~$P$.

(ꀊ � � ���������~I, ��������� � ������� ������� �������� ��� 
���������� �������������� ����, ��� ������~$P$ ���������� ���������� 
����� �� ���������� ����� ��������.)

\st[₅���~$s$, $t$.] 󑒀������~$j\asg t$, $i\asg s$, $x_{s+1}\asg\infty$. 

\st[퀉��~$x_i$.] (� ���� ������~$P_{ij}<x_{i+1}\simlt P_{(i+1)j}$ 
�~$x_{i+1}\notin P$.) 呋�~$P_{i(j+1)}<x_{i+1}$, �� ���������~$j$ ��~$1$ � 
��������� ���� ���. � ��������� ������ ����������~$x_i\asg P_{ij}$ 
�~$r_i\asg j$.

\st[瀌����� ��~$x_{i+1}$.] (򅏅��~$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$.)   
󑒀������~$P_{ij}\asg x_{i+1}$.

\st[$i=1$?] (򅏅��~$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}$ �~$r_i=j$.) 呋�~$i>1$, 
�� ���������~$t$ ��~$1$ � ��������� � ����~\stp{2}.

\st[�������~$x$.] 󑒀������~$x\asg x_1$ � ��������� ������ ���������.
 (򅏅��~$0 < x < \infty$.)
\algend

������ � ����������~I �~D, ����������� � ������� ������, �� ������ 
������� ��� �������������� ���� �����, ��� ��� ��������� ��������� 
��������� �����, �� ��� ��������� ���������, ��� 
\emph{���������~I �~D ������� �������.} 呋� ������� ��������� ��������~I 
� ������ �����~$P$ � 
��������� ����� ������������� ������~$x\notin P$, �� �� �������~$x$ �~$P$ 
� ��������� ����� ������������� �����~$s$, $t$, ��������������� 
��������~(8). ��������~D, ����������� � ����������� ����������, 
����������� ��������~$x$ � �������������� ���~$P$. ����, ���� 
������� ��������� ��������~D � ������ �����~$P$ � ���������� ������ 
�������������� �������~$s$, $t$, ���������������� ��������~(8), �� �� 
������������~$P$, ������ ��������� ����� ������������� �����~$x$. 
��������~I, ����������� � ����������� ����������, ����������� ��������~$s$,
 $t$ � �������������� ���~$P$.
%% 70
���� ����������� � ���, ��� ���������� ��������� � �����~I3 �~D4 
��������� ��� ��, ��� � � �����~I4 �~D3; ��� ���������� ���������� 
��������~$j$. 񋅄���������, ��������������� ������������������~(9), 
(10) ���������, � ����� �������.

򅏅�� �� ������������ � �������������� ��������� �������� �����.

\proclaim 򅎐���~A. 񓙅������ ������� ����������� ������������ ����� 
���������� ���� ������������ ���������~$\set{1, 2,~\ldots, n}$ � 
���������� ���� ������������� ��� �����~$(P, Q)$, ���~$P$ 
�~$Q$---����� ���������� ����� �� ���������~$\set{1, 2,~\ldots, n}$.

(��� � ���� ������� ���������� � ����������� ���� ��������������.)

\proof 󄎁��� �������� ��������� ����� ����� ���������. � 
������������� ������������ �������
$$
\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{ ��� ������},\hfill\cr
}
\eqno (11)
$$
�������� ��������������� ��� �����~$P$ �~$Q$, ��� $P$~������� 
�� ���������~$\set{p_1, p_2,~\ldots, p_n}$, �~$Q$---�� 
���������~$\set{q_1, q_2,~\ldots, q_n}$, ������~$P$ �~$Q$ ����� ���������� �����.

��~$P$ �~$Q$ ������� �����. ~$i=1$, $2$,~\dots, $n$ (������ � ����� 
�������) ��������� ��������� ��������: �������~$P_i$ � �����~$P$ ��� 
������ ���������~I; ����� ���������~$Q_{st}\asg q_l$, ���~$s$ �~$t$ 
���������� ����� ����������� ������� �~$P$.

퀏�����, ���� ������ ������������~$
\pmatrix{
1 & 3 & 5 & 6 & 8 \cr
7 & 2 & 9 & 5 & 3 \cr
}$, ��������� ��������� �������:

{\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
\+ ⑒����~7: &
\tableau{
 7 \cr
} & 
\tableau{
1 \cr
}\cr
\+ ⑒����~2: &
\tableau{
2 \cr
7 \cr
} &
\tableau {
1 \cr
3 \cr
}
\cr
\+ ⑒����~9: &
\tableau{
2 & 9 \cr
7 \cr
} &
\tableau{
1 & 5 \cr
3 \cr
}
\cr
%% 71
\+ ⑒����~5: &
\tableau{
2 & 5 \cr
7 & 9 \cr
} &
\tableau{
1 & 5 \cr
3 & 6 \cr
} \cr
\rightline{(12)}
\+ ⑒����~3: &
\tableau{
2& 3 \cr
5 & 9 \cr
7\cr
} &
\tableau{
1 & 5 \cr
3 & 6 \cr
8 \cr
} \cr
\vskip\belowdisplayskip
}

񋅄���������, ���� �����~$(P, Q)$, ��������������� ������������
$\pmatrix{
1 & 3 & 5 & 6 & 8 \cr
7 & 2 & 9 & 5 & 3 \cr
}$, ������:
$$
P=\tableau{
2 & 3 \cr
5 & 9 \cr
7 \cr
}\,, \qquad
Q=\tableau{
1 & 5 \cr
3 & 6 \cr
8 \cr
}\,.
\eqno(13)
$$

� ���������� ����, ���~$P$ �~$Q$ ������ ����� ���������� �����. ꐎ�� 
����, ��������� �������� ������ ����������� �� �������~$Q$ � � 
������������ �������, ��~$Q$---�����.

����, ���� ������ ��� ����� ���������� �����, �� ��������������� 
����������� ������~(11) ����� ��������� ���. ��
$$
q_1 < q_2 < \ldots < q_n
$$%
---��������~$Q$. �� ���~$i=n$,~\dots, $2$, $1$ (������ � ����� �������) 
$p_i$---�������~$x$, ������� ��������� ��~$P$ �� ���������~D � 
�������������� ��������~$s$, $t$, �����, ���~$Q_{st}=q_i$.

퀏�����, ���� ��������� ��� ���������� � �����~(13) � ����������� 
����������, ��������~(12), �� ��� ���, ����~$P$ �� �����������, �� 
��������� ������ $\pmatrix{
1 & 3 & 5 & 6 & 8 \cr
7 & 2 & 9 & 5 & 3 \cr
}$.

������ ���������~I �~D ������� �������, �� ������� ������� � ��������� 
����� ��� ����������; ����� �������, ��������� ������� ����������� 
������������ �����������.
\proofend

񎎒��������, ������������ � �������������� �������~A, �������� 
���������� ������������� �������, � ������ �� ��������� � ������ 
��������� �� ���. 󁅄�������� ������� � ��������, ������ ��� ��������� 
������, �������� ���� �� �������� �� ���.~1, ����� ��������� � ����� ������������.

%%72

ꀊ ������ ������� �������� �� ������~1 � ������~2, �� ��� ������ �� 
������ �� ������~1; ����� ����, ������~2, 3,~\dots{} �������� �� 
������������������ "�����������" ��������� ����� ��� ��, ��� ������~1, 2,~\dots{} 
�������� �� �������� ������������. ��� ����� ������� �� ����� � 
���, ��� �� ���������� � �������~A ����� ��������� �����, ������� 
�������� ���� �� ������ ������~$P$ �~$Q$. 퀏�����, ������������ 
$\pmatrix{
1 & 3 & 5 & 6 & 8\cr
7 & 2 & 9 & 5 & 3 \cr
}$
�������� ��������� �������� ��� �������~1 [��.~�~(12)]:
$$
\vcenter{\halign{
#\hfil\bskip&\bskip #\hfil\bskip&\bskip$#$\hfil\cr
1: ⑒�����~$7$, & ���������� & Q_{11}\asg 1. \cr
3: ⑒�����~$2$, & ���������~$7$. \cr
5: ⑒�����~$9$, & ���������� & Q_{12}\asg 5. \cr
6: ⑒�����~$5$, & ���������~$9$. \cr
8: ⑒�����~$3$, & ���������~$5$.\cr
}}
\eqno(14)
$$
򀊈� �������, ������ ������~$P$---���~$2~3$, � ������ ������~$Q$---���~$1~5$. 
ꐎ�� ����, ��������� ������~$P$ �~$Q$ ���������� �����, ��������������� 
"������������" ������������ �������
$$
\pmatrix{
3 & 6 & 8 \cr
7 & 9 & 5 \cr
},
\eqno (15)
$$

����� ������, ��� �������� ������~1, ����� ������� ��������, ���������� 
� ������ ������� ���� ������. ᓄ�� ��������, ��� ����~$(q_i, p_i)$ 
����������� ������~$t$ ������������ ������������ �������
$$
\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{ ��� ������,}\hfill\cr
}
\eqno(16)
$$
����~$p_i=P_{1t}$ ����� ���������� ���������~I ��������������� �~$p_1$, 
$p_2$,~\dots, $p_i$, ������� � ������� �����~$P$. (퀏�����, ���
��������~I ������ ��������� ������ ������� � 1-� ������.)

녃�� ������, ���~$(q_i, p_i)$ ����������� ������~1 ����� � ������ �����, 
����� $p_i$~����� $(i-1)$~��������, 
�.~�.~$p_i=\min\set{p_1, p_2,~\ldots, p_i}$---"������������� �������". 呋� 
� �������~(16) ���������� ������� ������~1, �� ��������� 
������ ����������� ������:
$$
\pmatrix{
q'_1 & q'_2 & \ldots & q'_m \cr
p'_1 & p'_2 & \ldots & p'_m \cr
}
\eqno(17)
$$
�����, ��� ����~$(q, p)$ ����������� ������~$t$ ������������~(17) ����� � 
������ �����, ����� ��� ����������� ������~$t+1$ ������������ 
�������~(16). ����� �������� ��~(16) �~(17) �������������
%%73
�������� ������� ����� ������� ������~1. ��� 
���� ��������������� ������ ����������� �������. 퀏�����, � ������������ 
$\pmatrix{
1 & 3 & 5 & 6 & 8 \cr
7 & 2 & 9 & 5 & 3 \cr
}$ 
�������������� ���������� �������� ��������~$7$ �~$2$, ��� ��� 
�����~1---���~$\set{(1, 7), (3, 2)}$; � ���������� �������
$\pmatrix{
5 & 6 & 8 \cr
9 & 5 & 3 \cr
}$
��� �������� ����������, ��� ��� �����~2---���~$\set{(5, 9), (6, 5), (8, 3)}$. 
� "�����������" �������~(15) �����~1---���~$\set{(3, 7), (8, 5)}$, � 
�����~2---$\set{(6, 9)}$.

䋟 ������ ��������������~$t$ �������� ������~$t$ ����� ��������
$$
(q_{i_1}, p_{i_1}), \ldots, (q_{i_k}, p_{i_k}),
$$
��� ����� ����������� �����������
$$
\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)
$$
��������� ��� ������ ��������� ������� ������� �����~$P_{1t}$ ��������� 
��������� ������������������ ��������~$p_{i_1}$,~\dots, $p_{i_k}$. � ����� ����������
$$
p_{1t}=p_{i_k}, \quad Q_{1t}=q_{i_1},
\eqno(19)
$$
� ����������� ����������� ������, ������� ������������ ������~2, 3,~\dots{} 
�����~$P$ �~$Q$, �������� �������
$$
\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)
$$
� ����� ������ �������, ����������� ������� ���������� �� ������ �������.

��� ���������� �������� � �������� ������ ����������~$P$ �~$Q$ ������� 
(��.~���.~3), � ����� ������������� �������� ��� �������������� ������ 
������ ������������ ����������.

\proclaim 򅎐���~B. 呋� � ���������� �� �������~A ������������
$$
\pmatrix{
1 & 2 & \ldots & n \cr
a_1 & a_2 & \ldots & a_n \cr
}
$$
������������� �����~$(P, Q)$, �� �������� �� ������������ ������������� 
�����~$(Q, P)$.

��� �������� ������������ ����, ������ ��� � �������~A �����~$P$ �~$Q$ 
����������� ���������� ������� ���������, � �������� ������������ 
���������� � ���������� ������ ����������� ����������� �������� 
������������ �������.

%% 74
\proof  ��������, � ��� ���� ����������� ������~(16);
������� ������� ��� ������ � ������������ ������� ���, ����� �������� 
����� ������� ������ ������������� � ����������� �������, ������� 
"��������" ������
$$
\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{ ��� ������.}\hfill\cr
}\cr
}
\eqno(21)
$$
����, ��� ��� �������� ������������� ������~$(P, Q)$ ��~$(Q, P)$ � 
���������� �� �������~A.

� ���.~2 ���� ��������� �� ����������� ������� ����������������� ����� 
�������, ��� �����, � �������� ��������� ����~$(q_i, p_i)$, �� ������� �� 
���� �����, ��� ��������~$q_1$, $q_2$,~\dots, $q_n$ ����������� � 
������������ �������. ������ �������������� ������� ����������� 
������������~$p$ �~$q$, �� ��������~(21) �� �������� ��������� �������; 
����~$(q, p)$ ����������� ������~$t$ ������������~(16), ��~$(p, q)$ 
����������� ������~$t$ ������������~(21). ����, ���� ���������� 
�������� ����� ���������� ������~$t$ ���, �����
$$
\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)
$$
[��.~�~(18)], �� �������
$$
P_{1t}=q_{i_1}, Q_{1t}=p_{i_k},
\eqno (23)
$$
��� �~(19), � �������
$$
\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)
$$
������ � ����������� ������, ��� �~(20). 񋅄���������, ������ 
������~$P$ �~$Q$ �������� �������. ꐎ�� ����, ����������� ����������� 
������ ���~(21) �������� �������� �� ��������� � ������������ ������������ 
������� ���~(16), ��� ��� �������������� ����������� ����������� 
�������� �� ����� ����� � �����.
\proofend

\proclaim 񋅄�����. ꎋ������� �����, ������� ����� ������������ �� 
���������~$\set{1, 2,~\ldots, n}$, ����� ���������� ��������� 
���������~$\set{1, 2,~\ldots, n}$.

\proof 呋�~$\pi$---���������, ��������������� ���� �����~$(P, Q)$, 
��~$\pi=\pi^{-1}$ ������������� ����~$(Q, P)$. 񋅄���������,
%% 75
$P=Q$. ����, ����~$\pi$---�����-���� ������������, 
��������������� ����~$(P, P)$, ��~$\pi^{-1}$ ���� ������������� ����~$(P,P)$;
������~$\pi=\pi^{-1}$. 򀊈� �������, ���������� ������� 
����������� ������������ ����� �����������~$\pi$ � �����~$P$.
\proofend

ߑ��, ��� ������� � ����� ������� ���� ����� ������ ����������. ��� 
������� �� ����� � ��������� ������� ���������� ��������� �����. 񍀗��� 
����� ��������� �� ��� �����, ����������� �������� ��������~I, � 
���������� ���������� ������� �������� � ����. 瀒�� ���� ���������� 
������� ���������, � ��������� �������� ��������������� ���, ����� 
������������ ������ �����; ����� ��������� ����� ����������� ������� � �.�.

���� ������� ���������, ��� ����������, ����� �� ������� ������� 
������� �� �����
$$
\tableau{
1 & 3 & 5 & 8 & 12 & 16\cr
2 & 6 & 9 & 15\cr
4 & 10 & 14 \cr
11 & 13 \cr
17\cr
}
\eqno (25)
$$
�� ��������~$1$ �� �������������� ����� ���������� ���������~$2$. 
瀒�� ����� �������~$4$ �� ����� ������, ������~$11$ ������ ������� �� 
�����~$4$, �� �� ��� ����� ����� ���������~$10$, � �����~$13$ �� 
�����~$10$. � ����� ������ �������� � ��������� ���������.

\alg S.(󄀋���� �������� ��������.) ���� �������� ������� ������� �� 
������ �������� ���� �����~$P$ � ���������� ��������� �������� ���, ����� 
����������� �������� �����. 葏��������� �� �� �����������, ��� � � 
����������~I �~D.

\st[퀗������ ���������.] 󑒀������~$r\asg 1$, $s\asg 1$.

\st[ꎍ��?] 呋�~$P_{rs}=\infty$, �� ������� ��������.

\st[񐀂����.] 呋�~$P_{(r+1)s}\simlt P_{r(s+1)}$, �� ������� � 
����~\stp{5}. (񐀂������ �������� ������ � ����� �� ���������� ����� � 
����������� ������� �� ���.)

\st[������ �����.] 󑒀������~$P_{rs}\asg P_{r(s+1)}$, $s\asg s+1$  � 
��������� �~\stp{3}.

\st[������ �����.] 󑒀������~$P_{rs}\asg P_{(r+1)s}$, $r\asg r+1$ � 
��������� �~\stp{2}.
\algend

녃�� ��������, ��� ����� �������� �������� �������� � ������� 
���������~S, $P$---��-�������� ����� (��.~���.~10). 򀊈�
%%76
�������, �������� ��������~S �� ��� ���, ����~$P$ �� �����������, ����� 
��������� ��� �������� � ������������ �������. � ���������, ���� �������� 
���������� ����������� �� ����� �����������, ��� ������ ���������, ������� 
��� ��� ��������� �����������. 숍�������� ����� ��� ������ ���������������~$n^{1.5}$;
����������� ���������, ������������ ������ ����� �������, ����������� 
����� �������~$n\log n$.

��������~S, ���� � �� �������� � �������� ������������ ��������� 
����������, �������� ���������� ����� ����������� ����������.

\proclaim 򅎐���~C. (�.~�.~����������.) 呋�~$P$---�����, �����������, ��� 
� �������~A, �� ������������~$a_1\,a_2,\ldots\,a_n$, 
�~$a_i=\min\set{a_1, a_2, \ldots, a_n}$, �� ��������~S �����������~$P$ � 
�����, ��������������� ������������~$a_1\,\ldots\,a_{i-1}\,a_{i+1}\,\ldots\,a_n$.

\proof �. ���. 13.
\proofend

䀂���� ����� ���������� ���������~S �������� �� ����� �������������� 
����� ��������� ������� � �������, ������ ����� �������, ��� �� ����� ���� 
�� �� �������� ������ �����. �����, ��������, ��� ��������� � 
�����~(25), �� �������� ��
$$
\tableau{
2 & 3 & 5 & 8 & 12 & 16\cr
4 & 6 & 9 & 15\cr
10 & 13 & 14 \cr
11 & (1) \cr
17 \cr
}
$$
� ��� ��� ���������� �������� �
$$
\tableau{
4 &  5 & 8 & 12 & 16 & (2)\cr
6 & 9 & 14 &15\cr
10 & 13 & (3) \cr
11 & (1) \cr
17\cr
}
$$
%% 77
������ �� ��� ���, ���� ��� �������� �� �������� � �������, � ����� 
������, ������� ������������
$$
\tableau{
17 & 15 & 14 & 13 & 11 & 2 \cr
16 & 10 & 6 & 4 \cr
12 & 5 & 3 \cr
9 & 1 \cr
8 \cr
}
\eqno(26)
$$
������� �� �� �����, ��� � �������� �����~(25). ��� ������������ ����� 
������� \dfn{������������ �����,} ������ ��� ��� ������ �� ����� � ��� 
���� ��������, ��� ����������� "������������ ��������� �������" ($<$ 
�~$>$ ���������� ������). ������ ������������ �����, ���������� ��~$P$ 
����� ��������, �����~$P^S$.

򀁋�~$P$ ������������ ��~$P^S$ ������������ �������. � ����� ����, 
�������� ����� ����� �������� ��~$P^S$ ��� ������ ���� �� ������ ��������� 
(� �������� ���������� �������, ��������� $P^S$---������������ �����). 
퀏�����, ���������� �~(26) ���� ����� ����� ��������� ����
$$
\tableau{
15 & 14 & 13 & 11 & 2 & (16)\cr
12 & 10 & 6 & 4\cr
9 & 5 & 3 \cr
8 & 1 \cr
(17)\cr
}
$$
� � ����� ������ ����� ���������� �����~(25). ���� ������������� 
���������---���� �� ��������� ����� ��������� �������.

{\let\newpar=\par
\proclaim 򅎐��� D. (�.~�������, �.~�.~����������.) ��
$$
\pmatrix{
q_1 & q_2 & \ldots & q_n \cr
p_1 & p_2 & \ldots & p_n \cr
}
\eqno(27)
$$
---����������� ������, ��������������� ���� �����~$(P, Q)$.
%% 78
{\medskip\narrower
\item{a)}呋� ������������ ������������ (��������) ���������� ������� 
���~$q$, �� �� ���~$p$, �� ����������� ������
$$
\pmatrix{
q_n & \ldots & q_2 & q_1 \cr
p_n & \ldots & p_2 & p_1 \cr
}
\eqno(28)
$$
������������� ����~$(P^T, (Q^S)^T)$.
\newpar
{\noindent \rm (ꀊ ������, �����~$T$ ���������� �������� ����������������;
$P^T$---�����, a~$(Q^S)^T$---������������ �����, ��������� 
��������~$q$ ����������� � �������� �������.)}
\newpar
\item{b)}呋� ������������ ������������ ���������� ������� ���~$p$, �� �� 
���~$q$, �� ����������� ������~(37) ������������� ����~$((P^S)^T, Q^T)$.
\newpar
\item{c)}呋� ������������ ������������ ���������� ������� ��� ���~$p$, 
��� � ���~$q$, �� ����������� ������~(28) ������������� ����~$(P^S, Q^S)$.
\newpar}
\par
}

\proof � �������� �������� �������������� ���� �������. �, ��� 
������~(a) ������������� ����~$(P^T, X)$, ���~$X$---��������� ������������ 
�����, �������� � ���.~6; �������������, �� �������~B, ������~(b) 
������������� ����~$(Y, Q^T)$, ���~$Y$---��������� ������������ ����� ��� �� 
�����, ��� �~$P^T$.

��~$p_i=\min\set{p_1,~\ldots, p_n}$; ��� ���~$p_i$---"����������" 
������� ��� ������������ ��������� �������, �� �� �������� 
�� �������~$Y$ � �� ��������� ������� ��������� ��� ���������� �� 
�������~A. 򀊈� �������, ���� ��������������� ��������� 
��������~$p_1$,~\dots, $p_{i-1}$, $p_{i+1}$,~\dots, $p_n$, �������� ������������ 
��������� �������, �� ���������~$Y-\set{p_i}$, �.�.~$Y$, �� �������� 
������ �������~$p_i$. � �������~C, ���� ��������������� ��������� 
��������~$p_1$,~\dots, $p_{i-1}$, $p_{i+1}$,~\dots, $p_n$, �������� 
������� ��������� �������, �������� �����~$d(P)$, ������� ���������� ����� 
���������� �~$P$ ���������~S. 荄����� ��~$n$ 
����~$Y-\set{p_i}=(d(P)^S)^T$. � ���������
$$
(P^S)^T-\set{p_i}=(d(P)^S)^T
\eqno (29)
$$
�� ����������� ��������~$S$, � $Y$~����� �� �� �����, ��� �~$(P^S)^T$, �� 
������ ����� ����� ���������~$Y=(P^S)^T$.

� ����� �������� �����������~(b); (a)~���������� ����������� �������~B.
������������� ����������~(a) �~(b) ����������, ��� ������~(c) 
������������� ����~$(((P^T)^S)^T, ((Q^S)^T)^T)$, a ��� �����~$(P^S, Q^S)$, 
��� ���~$(P^S)^T=(P^T)^S$ ���������� ��������� ��������~$S$ �� ��������� � 
������� � ��������.
\proofend

��� �������, � ���������, ������������� ��� ������������ �����, ���������� 
��������� ������� � �����. 呋� � ���������� ���������������� ������� 
��������� ���������~$p_1$,~\dots, $p_n$
%% 79
� ������ ����� ���������� �����~$P$, �� � ���������� ������� ���� 
��������� � �������� �������---$p_n$,~\dots, $p_1$, 
��������� \dfn{�����������������} �����~$P^T$. 呋� �� �� �� ������ 
������ ��������� �������� � �������~$p_n$,~\dots, $p_1$, �� � �������� 
������~$<$ �~$>$, � �����~$0$ �~$\infty$, �� ������� ������������ 
�����~$P^S$. 퀑��������� ����������� �������� �������� ��� �������� 
�� ���������� ������� ��������. 텎������ ������� ���� ���������� ����� 
������� ���������� � ������������� �����-�� ���������� ���. � ��� ��� 
�� �������� ������-���� �������� ���������� �������� �������; �������, �� 
���������� �������� ������� �������� ���� ��, ��� ������~(c) ������������� 
����� ��� �� \emph{�����,} ���~$P$ �~$Q$.

񎎒��������, ��������������� ��������~A, ������� �.~���������� 
[{\sl American J.\ Math.,\/} {\bf 60} (1938), 745--760, Sec.~5]
� ��������� ���� � �������� �������� ����� ��� ����� ������� ������ 
������� ������ �� ������ �����. 텒����� ���������, ��� ��� ���������� � 
�������� ��������� ������������ �����. � ������������� �������~B ��� 
��������������. 썎�� ��� ������ �.~������� ���������� ������ ������ ��� 
������������, ������� �� ������������� �� �������� � ��� �� �����, 
����� ������������ �� 
[{\sl Canadian J.\ Math.,\/} {\bf 13} (1961), 179--191]. � ����� ������� 
"$P$"-����� �������~D~(a). �.~�.~����������
[{\sl Math. Scand.,\/} {\bf 12} (1963), 117--128] ������� �������~B � 
"$Q$"-����� �������~D~(a), �� ������� �������~(b) �~(c). ��� 
������������ ����� �������������� � �� ������������ ��������������;
������, �����~$p_1$,~\dots, $p_n$ �� ����������� ��������, 
���������� �������, � "������������" ��������� �� ������, ����� �~$p$, 
�~$q$ ����� ��������� ������������� ��������, ����������� ꍓ���
[{\sl Pacific J.\ Math.,\/} {\bf 34} (1970), 709--727].

������ ������ � ������������ �������: \emph{������� �����, ������������ 
�� ���������~$\set{1, 2,~\ldots, n}$, ����� ������ 
�����~$(n_1, n_2,~\ldots, n_m)$, ���~$n_1+n_2+\cdots+n_m=n$?} ������ ��� 
����� �����~$f(n_1, n_2,~\ldots, n_m)$; ��� ������ ������������� ������������
$$
\displaylines{
f(n_1, n_2, \ldots, n_m)=0, 
\rem{���� �� ��������� �������~$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{���� $n_1\ge n_2 \ge \ldots \ge n_m \ge 1$.}\quad (32)\cr
}
$$
������ ������������ ����������� �������� �� ���� �����, ��� ��� 
�������� ����������� �������� ����� ������ ����� ���������� �����; 
��������, ���������� ����� �����~$(6, 4, 4, 1)$ 
�����~$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)$, ������ ��� ������ ����� �����~$(6, 4, 4, 1)$
�� ���������~$\set{1, 2,~\ldots, 15}$ ���������� � ���������� ������� 
��������~$15$ � ���������� ����� � ����� �����~$(5, 4, 4, 1)$, $(6, 4, 3, 1)$
���~$(6, 4, 4)$. 臎������ ��� �� �����
\picture{p. 80, (33)}

�������~$f(n_1, n_2,~\ldots, n_m)$, ��������������� ����� ������������, 
����� �������� ������� ���:
$$
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{���~$n_1+m-1\ge n_2+m-2 \ge \ldots \ge n_m,$} 
\eqno (34)
$$ ��� �����~$\Delta$ ��������� �����������
$$
\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)
$$
􎐌���~(34) ����� �.~��������� 
[Sitzungsberichte Preuss. Akad.\ der Wissenchaften (Berlin, 1900), 516--534, Sec.~3], 
������ ������������� ������ ������ �����; �� 
����������� �������� �������� ������������, ����������� �� ������ �����. 
ꎌ���������� �������������� ���������� ����� 쀊-쀃�� 
[{\sl Philosophical Trans.,\/} {\bf A-209} (London, 1909), 153--175]. ��� 
������� ����� �������� �� ��������, ��� ���~(30) �~(31) ������������ ��� 
�����, � �������~(32) ����������, ���� ��������~$y=-1$ � ��������� ���.~17.

� �������~A � ����� � ���� �������� ��� ����� ����� �������� 
������������� ���������. ⇟� ����� �� ������������ %%81
������ �����, �������
$$
\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
}
$$
������
$$
\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)
$$
� ��������� ����� ����������� �����������~$q_1>q_2>\ldots>q_n$, ������ ��� 
���������---������������ ������������~$q$ �������, ������������ �~$0$ 
���~$q_i=q_j$. ����������� ��������� ���������� � ���.~24.

􎐌��� ����� ����� ����� �������� ��������� ����� ���������� ��������, 
���� ������ ������� "�������". � \dfn{������,} ���������������
\picture{���~5. 󃎋�� � ����� �������.}
������ �����, ������ ���� ��� ������ ���� ��� ������, ������� ����� � 
������ �� ���. 퀏�����, �������������� ������� �� ���.~5---������, 
��������������� ������~$(2, 3)$ ������~2 � �������~3; �� ������� �� ����� 
������. � ������ ������ �� ���.~5 �������� ����� ���������������� �� ������.

呋� ����� ����� �����~$(n_1, n_2,~\ldots, n_m)$, ���~$n_m\ge 1$, �� 
����� ������ �������� ������ �����~$n_1+m-1$. 䀋������� ������������ 
���� ������� ����������, ��� ������~1 �������� ��� �����~$n_1+m-1$, 
$n_1+m-2$,~\dots, $1$, \emph{����� $(n_1+m-1)-(n_m)$, $(n_1+m-1)-
%%82
-(n_{m-1}+1)$,~\dots, $(n_1+m-1)-(n_2+m-2)$.} 퀏�����, �� ���.~5 ����� 
������� � $1\hbox{-�}$ ������ ����~$12$, $11$, $10$,~\dots, $1$, �� 
�����������~$10$, $9$, $6$, $3$, $2$; ��� ���������� ������������� ���� 
�������������� �������, ������������ � �������������� �������~$(6, 3)$, 
$(5, 3)$, $(4, 5)$, $(3, 7)$, $(2, 7)$ � ��������������� � ������~$(1, 7)$.
 ���������� $j\hbox{-�}$~������ �������� ��� ����� 
�������~$n_j+m-j$,~\dots, $1$, �����~$(n_j+m-j)-(n_m)$,~\dots, 
$(n_j-m-j)-(n_{j+1}-m-j-1)$. ��� �������, ��� ������������ ���� ���� 
������� �����
$$
(n_1+m-1)!\ldots{}(n_m)!/\Delta(n_1+m-1,~\ldots, n_m).
$$
��� ��������� ������ � �������~(34); ������ �������

\proclaim 򅎐���~H. (�.~�.~�����, �.~��������, �.~�.~򐎋�.) 
ꎋ������� ����� ������ �����, ������������ �� 
���������~$\set{1, 2,~\ldots, n}$, �����~$n!$, ��������� �� ������������ 
���� �������. \endmark

򀊎� ������� ��������� ����������� � �������� ��������������; ������ 
(��� � ��� ����������� ������ ������, ���������� �����) ����� ������� 
�������������� �� ��������. ꀆ��� ������� �����---����������� � ����� 
������; ���� ��������� ������ ����� ��������� �������, �� ����������� ����,
��� � ������~$(i, j)$ �������� ����������� ������� ���������������� 
������, ���� ��������, �������� ����� ������. ��������� ���� 
������������ �� ����~$i$, $j$ ���� �������~H. ��� ����� 
����������� ��������, ��������� ��� ����������� ������ �� �������� 
������������. ⑅ ��������� �������������� �������~H �������� �� ����� 
�������������� ����������� �����������, ������� �� ����� ���� �� ���������,
 ������ �� ������� ����� (��� ��� � ��� ���������� �� ������������ 
�������� �������).

񓙅������ ���������� ����� ����� ��������~H � ������������� ��������, 
������� ��������������� � ��.~2. � ������, ��� �������� �������� � 
$n$~������ ������������� ������������, ������� ����� �������� � ������� 
�����, � ��� ����� ������������� ������������� 
������������������~$a_1\,a_2\,\ldots\,a_{2n}$ �����~$S$ �~$X$, �����, ��� 
���������� �����~$S$ ������� �� ������ ������ ���������� �����~$X$, ���� ������ 
������������������ ����� �������. (�.~���.~2.3.1-6 �~2.2.1-3.) 򀊈� 
������������������� ������������ ������� �������������� ����� �����~$(n, n)$; 
� 1-� ������ ���������� �������~$i$, �����, ���~$a_i=S$, � �� 2-� 
������---�������, ��� �������~$a_i=X$. 퀏�����, ������������������
$$
S\; S\; S\; X\; X\; S\; S\; X\; X\; S\; X\; X
$$ 
������������� �����
$$
\tableau{
1 & 2 & 3 & 6 & 7 & 10 \cr
4 & 5 & 8 & 9 & 11 & 12 \cr
}
\eqno(37)
$$
%%83
󑋎���, ���������� �� �������, ��������������� � ����� ����� � ��� � 
������ ��� ������, ����� ��� ������ ����� ������� ����� �����~X ������� �� 
��������� ����� �����~$S$. � �������~H ���������� ������������ ����� 
�����~$(n, n)$ �����
$$
(2n)!/(n+1)!n!;
$$
�������������, ������ �� � ����� �������� �������� � $n$~������ (��� 
����������� � ��������~(2.3.4.4-13)). ᎋ�� ����, ���� ��������������� 
����� �����~$(n, m)$ ���~$n\ge m$, �� ��� ������ ����� ����������� ����� 
������ � ����� ����� "������ � ������������", ������������� � ������ � 
���.~2.2.1-4. 򀊈� �������, �������~H � �������� ������� ������� 
������� �������� � ���� ��������� ������ ������� ������ � ������������.

⑟���� �����~$A$ �����~$(n, n)$ �� ���������~$\set{1, 2,~\ldots, 2n}$ 
������������� ��� �����~$(P, Q)$ ���������� �����. 񋅄����� ������ 
���������� ������ ������������ ��������� 쀊-쀃���� 
[Combinatory Analysis, {\bf 1} (1915), 130--131]. ��~$P$ ������� �� 
���������~$\set{1,~\ldots, n}$, �������������, ��� �~$A$, �~$Q$ ����������, 
���� ����� ��������� ��������~$A$, ��������� ��� ������������ ��~$180^\circ$ 
� ��������~$n+1$, $n+2$,~\dots, $2n$ �� ��������������~$n$, $n-1$,~\dots, $1$. 
퀏�����, �����~(37) ����������� ��
$$
\tableau{
1 & 2 & 3 & 6 \cr
4 & 5 \cr
}
\hbox{ � }
\revtableau{
\omit &\omit \hfil\vrule& 7 & 10 \cr
8 & 9 & 11 & 12\cr
}\,;
$$
����� �������� � ������������� �����
$$
P=\tableau{
1 & 2 & 3 & 6 \cr
4 & 5 \cr
},\quad 
Q=\tableau{
1 & 2 & 4 & 5 \cr
3 & 6 \cr
}.
\eqno(38)
$$
퀎�����, ������ ���� ����� ���������� �����, ��������� �� $n$~��������� � 
�� �� ����� ���� �����, ������������� ����� �����~$(n, n)$. 񋅄��������� 
(��~���.~7), \emph{����� ������������~$a_1\,a_2\,\ldots\,a_n$ 
���������~$\set{1, 2,~\ldots, n}$, �� ���������� ��������� 
����������������������~$a_i>a_j>a_k$ ���~$i<j<k$, ����� ����� 
�������� �������� � $n$~������.} 荒������� ������� ����������� 
������������ ����� ������ �������������� � ��������� ���������, 
������������� ����� ������ ��������, ��� ��� �������� ���� ����������� 
���������~I. ������� ��������������� ��, ����� �.~����� 
[{\sl Inf.\ Proc.\ Letters,\/} {\bf 4} (1975), 58--61]; ����������, ���������� 
�������� ������ ������������ ����� ��������� ��������� � ��������������, �� 
����������� ����������������������~$a_j>a_k>a_i$ �~$i<j<k$ (��.~���.~2.2.1-5).

%% 84

 ����� �������� ��������� ����� �����~$(6, 4, 4, 1)$, ��������, ����� 
����� �������� �������� ������� ������������� �����
\picture{p.84}
�������~$\set{1, 2,~\ldots, 15}$ ���, ����� ����� �������~$u$ ���� 
������ ����� �������~$v$, ����~$u\to v$. 荀�� ������, ��� ����� 
����� �������� ������������� ������������� ��������� ������������~(39) � 
������ �.~2.2.3.

� ����� ������ ����� ������ ��� �� ������ ��� ������������� 
������������� �����, �� ����������� ��������������� ������. ᛋ� �� ������,
���� �� ������������ �����-������ ������� �������, ���������� �������~H 
�� ������ ������������� �����; ������ �� ��� ����� �������� ������ 
��������� ����������, ��� �����, ��������������� �����. 䐓��� ������ 
������������ ������, ��� ������� ������ � �������� ������ ����� ������� 
�������, �������� ����������� � ����������� � ����� ����� ������. � 
����� ������� ����������, � ������� ��������, ��� � ���� ������� 
������������ ������ \emph{��} ���������� ������� �������, 
��������������� �������~H. 퀏�����, ����� �������� �������� ������� �� 
������ �������� ���������~$n!$.

瀂����� ���� ������������ ��������� ������ ����� �����, ������� ����� 
������������ �� $n$~��������� ���������. ������ ��� ����� �����~$t_n$.
� ��������� �� �������~B $t_n$~����� ����� ��������� 
���������~$\set{1, 2,~\ldots, n}$. ��������� ������� ����� ���� ����� � 
������ �����, ����� �� ������������� � ������� ������ ������� ������ �� 
��������� ������ (����������� �����) � ������ �� ���� ��������� (������������). 
������ �~$t_{n-1}$ ��~$t_n$ ��������� $(n)$---����������� �����, � 
�~$t_{n-2}$ �� ���~$(j, n)$---���� �� ���� ��������� ��� ��������� 
�������������~$j<n$, �� �������� �������
$$
t_n=t_{n-1}+(n-1)t_{n-2},
\eqno(40)
$$
������� ����� ���� �~1800~�.\ ��� ��������� ������� ��������~$t_n$ ��� 
�����~$n$.

⛗�����~$t_n$ ������ ��������. �� ������� $k$~������ ��
���� ��������� � $n-2k$~��������� ������. 񓙅������ 
$\perm{n}{2k}$~�������� ������� ����������� �����, � 
���������������� �����������~$(2k)!/(2!)^k$ ����� ����� �������� 
������������ ���������
%%85
�������� � $k$~���������� ������������. ���� ��~$k!$, ����� ������� 
��� ������������ �������������, �������
$$
t_n=\sum_{k\ge 0} t_n(k), \quad t_n(k)={n!\over (n-2k)!2^k k!}.
\eqno(41)
$$
� ���������, ��������� ��� ��������, ����� ����� ��� ������ ���������, 
�������, ��� ���� ����� ����� ������ ��������� ��������~$t_n$, �� �������� 
��� ��������� �������:
{\medskip\narrower
\item{a)}~쎆�� ����� ������������ �������
$$
\sum_n t_n z^n/n! = e^{z+z^2/2};
\eqno(42)
$$
��.~���.~25.

\item{b)}~쎆�� ���������� ��������������� ��������� ��������~$t_n$. ��� 
������������ ������, �� ������� �������� ��������� ����� �������, ������� 
����� ������� � � ����� � ������� ���������; ������� �� �������� ���� 
����� �������� ���������������� ���������~$t_n$.
\medskip}

��� ��� � ������� ���������������� ���������~(41) ������� � ��������� 
���������, ������ �������� ����� � �����. ������
$$
{t_n(k+1) \over t_n(k)} = {(n-2k)(n-2k-1)\over 2(k+1)},
\eqno(43)
$$
����� ������, ��� ��������� ���������� ����������, ����� $k$~�������� 
��~$k=0$ ��~$k$, ������� ��������������~${1\over2}(n-\sqrt{n})$, � ����� 
������� �� ����, ����� $k$~��������� ��������, ������� 
��������~${1\over 2}n$. ߑ��, ��� �������� ����� ���� ����� � 
�����������~$k={1\over2}(n-\sqrt{n})$. 䋟 �������, ������, �������, �����
�������� ����� ����������� ��� ��������~$0$, ������� ����������~$k$ � ����
$$
k={1\over 2}(n-\sqrt{n})+x
\eqno(44)
$$
� ��������� ��������~$t_n(k)$ ��� ������� ��~$x$.

����� ���������� �� ����������� �~$t_n(k)$, ������� ��������������� 
�������� 񒈐����� (1.2.11.2-18). 䋟 ���� ���� ������ (��� �� ������ 
������) ���������� ������� ���������~$x$ �����������
$$
-(n^{\varepsilon+1/4})\le x \le n^{\varepsilon+1/4},
\eqno(45)
$$
��� $\varepsilon$~�����, ������, $0.001$, ��� ��� ����� �������� 
��������� �����������. �� �������� ���������� ����������, ������� �� 
����� ���� ������ ���� ���� ��������� ��������������
%%86
�������, ���������� �������
$$
\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
}
$$
��������~(45) ��~$x$ ������������� ���, ��� ����� 
��������~$x=\pm n^{\varepsilon+1/4}$ ��� ��������� ������� ������ ���� 
����������� ���������, ������
$$
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)
$$
� ���� �������� ��� ��~$n$, �� ��������� ������� ������ ����� ����������� 
���������. ⅐���� ������ ����� ������� �������, ��� �� ���������, 
������� �� �������� ���~$x$ � ������������ ����������~(45), ��������� 
���������~$\exp(-2n^{2\varepsilon})$, ������� ����� ������ ������ �������� 
��~$n$. �����, ����� ��������� � ����� ���������
$$
\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)
$$
����� ���� ��� ��������� ������ ��������������
$$
\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
}
$$
�� ����~$x=\alpha$, $\alpha+1$,~\dots, $\beta-2$, $\beta-1$, ���~$-\alpha$ 
�~$\beta$  (�� ����������� �����) ����� 
��������������~$n^{\varepsilon+1/4}$. 呋� �������� �������� ������������, 
�� ������� ������������ ������~(1.2.11.2-10) ����� �������� � ����
$$
\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)
$$
焅��~$\abs{R_m}\le (4/(2\pi)^m)\int_\alpha^\beta\vert{f^{(m)}(x)}\,dx$.
����~$f(x)=x^t\times \exp(-2^2/\sqrt{n})^\alpha)$, 
���~$t$---������������� ��������������� �����
%%87
�����, ������, ��� ~$\int_\alpha^\beta f(x)\,dx$ ���������� 
��~$\int_{-\infty}^\infty f(x)\,dx$ ��~$O(\exp(-2\pi^\varepsilon))$, ��� 
��� ����� �����~$\alpha=-\infty$, $\beta=\infty$. � ���� ������ ������� 
������������ ������ ���� ��������������� ��� ���~$\sum f(x)$ 
���~$n\to\infty$, ���������
$$
f^{(m)}(x)=n^{(t-m)/4} g^{(m)} (n^{-1/4}x),\quad
g(y)=y^i e^{-2y^2},
\eqno(51)
$$
�~$g(y)$---������� �������, �� ��������� ��~$n$; ������ �����,
���~$R_m=O(n^{(t+1-m)/4})$. � ���~$f^{(m)}(-\infty)=f^m(\infty)=0$, �� 
��������, ���
$$
\sum_{\alpha \le x < \beta} f(x)=\int_{-\infty}^{\infty} f(x)\,dx+O(n^{-m})
\rem{��� ������~$m\ge0$;}
\eqno (52)
$$
�� ����� ���� ��� ���� ���������� ������~$f(x)$ ��������� ������ ��������! 
荒����� �������� ��������� (��.~���.~26); ����� �������, �� ����� 
��������� ��������� � �������� � �������~(49) � ��������
$$
\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
}
$$
� ���������������� ��������� �~$O(n^{-3/4})$ �������� ��� ���������� 
��~$9\varepsilon$, �� �� ����� �������� ����, ��� ��������~$9\varepsilon$ 
������ ���������, ���� ���������� ���������� � ������� ���������. � 
�������� ���� ����� ����� ������� � ������~$O(n^{-3/4})$ 
��������~$O(n^{-k})$ ��� �����~$k$. ���� ��������������� ��� ���~$t_n$ 
������� ����� (������ ��������) 쎇�� �~󀉌�� 
[{\sl Canadian. J.~Math.,\/} {\bf 7} (1955), 159--168]. 䐓��� ������� � 
�������� ������, ������������ ��� ������ �������~(53), ��.\ � ����� �.~5.2.2.

\excercises
\ex[16] ꀊ�� �����~$(P, Q)$ ������������� ������������ �������
$$
\pmatrix{
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \cr
6 & 4 & 9 & 5 & 7 & 1 & 2 & 8 & 3 \cr
}
$$
� ���������� �� �������~A? ꀊ�� ����������� ������ ������������� ���� �����
$$
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[�21] 䎊�����, ��� $(q, p)$~����������� ������~$t$ ������������ 
�������~(16) ����� � ������ �����, ����� $t$~����� ������������� ����� 
��������~$i_1$,~\dots, $i_t$, �����, ���
$$
p_{i_1}<p_{i_2}<\ldots <p_{i_t}=p,\qquad 
q_{i_1}<q_{i_2}<\ldots <q_{i_t}=q.
$$

\rex[�24] �����, ��� ������������ � �������~A ����� ����� 
���������� ����� ���������� ����� �������:
\ctable{
#\hfil\bskip &\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip\cr
񒐎��~0 & 1      & 3      & 5      & 6      & 8      \cr
񒐎��~1 & 7      & 2      & 9      & 5      & 3      \cr
񒐎��~2 & \infty & 7      & \infty & 9      & 5      \cr
񒐎��~3 &        & \infty &        & \infty & 7      \cr
񒐎��~4 &        &        &        &        & \infty \cr
}
焅�� � �������~0 �~1 ������� ������ ����������� ������. ~$k\ge1$ 
������~$k+1$ ���������� �� ������~$k$ ��������� �������:
{\medskip\narrower
\item{a)}~󑒀������~$p\asg\infty$.
%
\item{b)}~�� �������~$j$---����� ����� �������, � ������� ������~$k$ 
�������� ����� �����~$<p$, � ��������������� ����� � ������~$k+1$ �� 
���������. 呋� ������ ������� ��� �~$p=\infty$, �� ������~$k+1$ 
���������; ���� ������ ������� ��� �~$p<\infty$, �� ������������ �~(a).
%
\item{c)}~⑒�����~$p$ � �������~$j$ � ������~$k+1$, ����� ����������~$p$ 
������ �������� �������~$j$ � ������~$k$ � ��������� �~(b).
\medskip}

�� ���� ��� ������� ����� ������� ���������, ������~$k$ �����~$P$ 
������������ �� ��� ����� ����� ������~$k$ ���� �������, ������� 
����������� � ������~$(k+1)$; ������~$k$ �����~$Q$ �������� �� ��� ����� 
����� ������~0, ������� ��������� � ��������, ����������~$\infty$ � 
������~$(k+1)$.

\ex[M26] (�.~�.~����������). ��~$\pi$---��������� � 
$k$~������������ �������. �����, ��� �����, ���������������~$\pi$ � 
�������������� ��������� �� �������~B, �������� ����� $k$~�������� 
�������� �����.

\rex[�30] ��~$a_1\,\ldots\,a_{j-1}\,a_j\,\ldots\,a_n$---������������ 
��������� ��������� �~$1<j\le n$.
���������~$a_1\,\ldots\,a_{j-2}\,a_j\,a_{j-1}\,a_{j+1}\,\ldots\,a_n$, 
������������ �� ��������, ���� �������� �������~$a_{j-1}$ �~$a_j$, 
���������� "����������", ���� ����
{\medskip\narrower
\item{i)}~$j\ge 3$ �~$a_{j-2}$ ����� �����~$a_{j-1}$ �~$a_j$, ����
\item{ii)}~$j<n$ �~$a_{j+1}$ ����� �����~$a_{j-1}$ �~$a_j$.
\medskip}
퀏�����, � ������������~$1\,5\,4\,6\,8\,3\,7$ ����� ���������� ����� 
��� ���������� ������: ����� �������� �������~$1$ �~$5$, ���������~$1<4<5$;
����� �������� �������~$8$ �~$3$, ���������~$3<6<8$ (���~$3<7<8$); 
������ ������ ������ �������~$5$ �~$4$ ���~$3$ �~$7$.
{\medskip\narrower
\item{a)}~䎊�����, ��� ��� ���������� ������ �� �������� �����~$P$, 
������� ���������� �� ������������ ����� ���������������� ������� 
���������~$a_1$, $a_2$,~\dots, $a_n$ � ������������� ������ �����.
%
\item{b)}~����, ��������, ��� ����� ��� ������������, 
��������������� ������ � ���� �� �����~$P$, ����� ������������� ���� � 
������ ������������������� ����� ��� ����� ���������� �����. [\emph{󊀇����:}
��������, ��� ���� �����~$P$ ����� �����~$(n_1, n_2,~\ldots, n_m)$, �� 
����� ��������������� ��� ������������ ��� ������ 
������������������ ���������� ����� ����� ������������� � 
"������������ ������������"~$P_{m1}\ldots{}P_{mn_m}\ldots{}P_{21}\ldots{}P_{2n_2}P_{11}\ldots{}P_{1n_1}$.]
\medskip}

\rex[�22] ��~$P$---�����, ��������������� ������������~$a_1\,a_2\,\ldots\,a_n$;
� ������� ���.~5 ��������, ��� �����~$P^T$ ������������� 
������������~$a_n\,\ldots\,a_2\,a_1$.
%%89

\ex[� 20] (�.~�������). ��~$P$---�����, ��������������� 
������������~$a_1\,a_2\,\ldots\,a_n$. 䎊�����, ��� ����� \emph{��������} 
�~$P$ ����� �����~$c$ ������������ ������������ 
���������������������~$a_{i_1}<a_{i_2}<\ldots<a_{i_c}$, 
���~$i_1<i_2<\ldots<i_c$; ����� \emph{�����} �~$P$ ����� �����~$r$ 
������������ ��������� 
���������������������~$a_{j_1}>a_{j_2}>\ldots>a_{j_r}$, 
���~$j_1<j_2<\ldots<j_r$.

\ex[�18] (�.~�����, �.~񅊅���). 䎊�����, ��� � ����� ������������,
 ��������� �� ����� ��� $n^2$~ ���������, ������� ���������� 
��������������������� ����� �����~$n$; ������ ���������� ������������ 
$n^2$~���������, �� ���������� ���������� ���������������������� ����� 
�����~$n$. [\emph{󊀇����:} ��.~���������� ����������.]

\ex[�24] ������ ���.~8, ������� "�������" ������� ������� 
����� ������������ ���������~$\set{1, 2,~\ldots, n^2}$, �� ���������� 
���������� ���������������������� ����� ����� ���~$n$.

\ex[�20] 䎊�����, ��� ������~$P$ �������� ����� �� ��������� 
������ ���������~S, ���� �� ��� ����� �� �����.

\ex[20] 쎆�� �� ������������ �������� ��� �����~$P$ �� ��������� ������ 
���������~S, ���� �������� ������ ��������~$r$ �~$s$?

\ex[�24] 񊎋��� ��� ����������� ���~S3, ���� ��������~S 
����������� ����������� ��� ���������� ���� ��������� �� �����~$P$ 
�����~$(n_1, n_2,~\ldots, n_m)$? ꀊ��� ����������� �������� ���� �������� 
�� ���� ������, �����, ���~$n_1+n_2+\cdots+n_m=n$?

\ex[�28] 䎊����� �������~C.

\ex[�43] 퀉���� ����� ������ �������������� �����~(c) �������~D.

\ex[�20] 񊎋��� ������������ 
���������������~$\set{l\cdot a, m\cdot b, n\cdot c}$ 
�������� ��� ���������, ��� ���� ������ ������������ ����� 
�������, �� ����� ����������� ����~$c$ ������� �� ��������� ����� ����~$b$,
������� � ���� ������� �� ��������� ����� ����~$a$? (퀏�����, 
������������~$a\,a\,b\,c\,a\,b\,b\,c\,a\,c\,a$ �������� ���� ���������.)

\ex[�08] 񊎋����� ��������� ����� ������������� ������������� ��������� 
������������, �������������� ������~(39)?

\ex[��25] ��
$$
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).
$$
䎊�����, ���
$$
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{󊀇����:} �������~$g$ ���������� (��� ��������� ����� ���������� 
��������� �������) � ���������������� ��~$x$ (����~$g$ ���������, ���� 
�������� �������~$x_i$ �~$x_j$).]

\ex[��30] ���� ���.~17, ��������� ���~$m\ge 0$ �����
$$
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[�40] 퀉���� ������� ��� ����������� ����� ��������, �������� ����� 
��������� ������, �������� �����, �� ��� ������ ���� ������ � ������
%%90
������; ��������, ������ ����� �����:
\picture{1. p.90}
(�������� � ������� � �������� ������ ������������� � ������������ �������,
 ��� � ������� �����.)

荀�� ������, ������� ��~$f(n_1, n_2,~\ldots, n_m)$~����� 
�����~$(n_1, n_2,~\ldots, n_m)$, ������������ �� 
���������~$\set{1, 2,~\ldots, n_1+\cdots+n_m}$, 
�������� ��������~$1$ �~$2$ � ������ ������?

\rex[�24] 䎊�����, ��� ����� �������� �������� ���� ������� ��������� 
������ ����������~$\set{1, 2,~\ldots, n}$ ���, ����� ����� ������� ���� 
���� ������ ����� ������ �� ��� ��������, ����� �������� �� �������~$n!$ 
�� ������������ "���� �����������", �.~�.~��������� ����� � ������ 
���������. (�.~�~��������~�.). 퀏�����, ����� �������� �������� ���� ������
\picture{1. p.90}
�����~$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] (�.~�.~򐎋�). �� �����~$n_1>n_2>\ldots>n_m$ ��������� ����� 
"���������� �����", � ������� ������~$i+1$ ���������� �� ���� �������, 
������, ��� ������~$i$; ��������, ��������� ����� �����~$(7, 5, 4, 1)$
���������� �� ���������
\picture{3. p.90}
䎊�����, ��� ����� �������� ��������� ��������� ����� 
�����~$(n_1, n_2,~\ldots, n_m)$ �������~$1$, $2$,~\dots, 
$n=n_1+n_2+\cdots n_m$ ���, ����� 
����� �� ���� ������� � �������� ������������� � ������������ �������, 
����� �������� �� �������~$n!$ �� ������������ "���� ���������� 
�������"; �� ������� ����������� ���������� ������ �����~$11$, 
��������������� ������ ������~$1$ � �������~$2$. (󃎋�� � ����� ����� 
�������, ������� ��� "������������ ��������", �����
%% 91
����� �����~U, ���������� ��~$90^\circ$, � �� �����~L.) 蒀�, ����������
$$
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
$$
�������� ��������� ������������ ���� ����� ���, ����� �������� �� 
���� ������� � �������� ������������� � ������������ �������.

\rex[��30] (�.~�����). ���� ����� �����~$A_n$ �������� ��������� 
�������~$\set{1, 2,~\ldots, n}$ ������ �� $n$~�����
\picture{p.91}
���, ����� �� ���� ������� � �������� ��� ������������� � 
������������ �������? 퀉���� ������������ �������~$g(z)=\sum A_n z^n/n!$

\ex[M39] 񊎋����� ��������� ����� ��������� ������ 
�����~$(n_1, n_2,~\ldots, n_m)$ ���������� ���������~$\set{1, 2,~\ldots, N}$, \emph{���� 
����������� ���������� ��������,} ������ � ������� �������� ������ 
������������� � ����������� �������, � � ��������---� ������ ������������? 
퀏�����,
������� ����� �� $m$~����� $(1, 1,~\ldots, 1)$ ����� ��������� $\perm{N}{m}$~���������;
����� �� ����� ������~$m$ ����� ��������� $\perm{m+N-1}{m}$~���������; 
�����~$(2, 2)$ ����� ��������� ${1\over3}\perm{N+1}{2}\perm{N}{2}$~���������.

\ex[�28] 䎊�����, ���
$$
\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{󊀇����:} ��������, 
���~$\Delta(k_1+n-1,~\ldots, k_n)=\Delta(m-k_n+n-1,~\ldots, m-k_1)$; 
��������� ����� �����~$n\times (m-n+1)$ ��������, �����������~(38), � 
������������ �����, ��� ��� ������ ���������~(36).]


\ex[�20] ���~(42) �������� ������������ �������� ��� ���������?

\ex[��21] ⛗������~$\int_{-\infty}^\infty x^t \exp(-2x^2/ \sqrt{n})\,dx$ 
��� ��������������� �����~$t$.

\ex[�24] ��~$Q$---����� ߍ�� �� ���������~$\set{1, 2,~\ldots, n}$, � 
����� �������~$t$ ��������� � ������~$r_i$ � �������~$c_i$. � �������, 
���~$i$ "����"~$j$, ����~$r_i<r_j$.
{\medskip\narrower
\item{a)}~䎊�����, ��� ���~$1\le i < n$ �������~$i$ ����~$i+1$ ����� � 
������ �����, �����~$c_i\ge c_{i+1}$.
%%92
\item{b)}~��~$Q$ �����, ��� $(P, Q)$~������������� ������������
$$
\pmatrix{
1 & 2 & \ldots & n \cr
a_1 & a_2 & \ldots & a_n \cr
}
$$
䎊�����, ���~$i$ ����~$i+1$ ����� � ������ �����, �����~$a_i>a_{i+1}$.
(񋅄���������, ����� ����� ����� �������� ������������, ���� ������~$Q$. 
���� ��������� ������� ����������.)
%
\item{c)}~䎊�����, ��� ���~$1\le i < n$ �������~$i$ ����~$i+1$ �~$Q$ 
����� � ������ �����, �����~$i+1$ ����~$i$ �~$Q^S$.
\medskip}

\ex[�47] ꀊ��� ��������������� ��������� ������� ����� ������������ 
������������ ������������������ � ��������� ������������ 
���������~$\set{1, 2,~\ldots, n}$? (��� ������� ����� ������ ������ � 
������������ �� �������~A. ����� �������, ����������� �.~�.~စ��� 
�~�.~ᐎ��� [{\sl Math. Comp.,\/} {\bf 22} (1968), 385--410], � ����� � ���, 
��� ��� ������� "������������ �����������", ��������� ������������, ��� 
�������~$l_n$ ����� ��������~$2\sqrt{n}$; �.~���� �~�.~뎃�� ��������, 
���~$\liminf_{n\to\infty} l_n / \sqrt{n}\ge 2$ (� ������).

\ex[�50] 葑������� ���������� �������, � ��� ����� ������, ����� �������� 
��������� ����� ����� ��������.

\ex[�42] (�.~�.~����������). �����, ��� �������� �������� ��~$P$ 
�~$P^S$---������� ������ ��������, ������� ����� ������� � ����� �������� 
�������� ������������� ����������, � �� ������ � �����. ����� �������� 
�������� �������������� ��������� ������ �������~$\set{1, 2,~\ldots, n}$ 
���, ����� ��� ������� ����� ���� ����������� � ��������� 
�������������. 퀉���� ������������ ������� �����, �����������~(26), ����� 
����������������� �������� �����~$1$, $2$,~\dots, ���������� ��� ���� 
������ ����� ��������, �������� ���������~S, � ������� �����~(1), (2),~\dots{} 
�� �������������� �����. �����, ��� ��� ��������, ���� �� 
����������� ��������� � ������������ ������� ����� � �������� ���������� 
������� ��� �����, ���� �������� ������� �����; ���������� ������ �������� 
���� ��������

\ex[��30] ��~$x_n$---����� �������� ����������~$n$ ������� 
����������� ����� �� ��������� ����� �������~$n\times n$ ����� �������, 
��� ������������ �� �������� ��� ��������� ����� ������������ ����� �� 
������� ���������� � ��� �������� ��~$180^\circ$. 퀉���� ��������������� 
���������~$x_n$.

%% 93
\bye
