\input style
\chapnotrue
\chapno=5
\subchno=2
\subsubchno=0
\alg D.(�������������� �������.) 풎� �������� � �������������, ��� ��� 
�����---����� ����� � ��������� $u\le K_j\le v$ ��� $1\le j\le N$, ��������� 
������ $R_1$, \dots, $R_N$, ��������� ��������������� ������� 
$|COUNT|[u]$, \dots, $|COUNT|[v]$. � ����� ������ ��������� ��� ������ � 
��������� ������� ����������� � ������� ������ $S_1$, \dots, $S_N$.

\st[ၐ����� ��������.] 㑒������� $|COUNT|[u]$, \dots, 
$|COUNT|[v]$ ������� ����.

\st[戊� �� $j$.] ��������� ��� \stp{3} ��� $1\le j\le N$,  ����� ������� 
� ���� \stp{4}.

\st[ゅ������ $|COUNT| [K_j]$.] ゅ������ �������� $|COUNT|[K_j]$ �� 1.    

\st[ᓌ���������.] (� ����� ������� �������� $|COUNT|[i]$ ���� ����� 
������, ������ $i$.)  㑒������� 
$|COUNT|[i]\asg COUNT[i]+COUNT[i-l]$ ��� $i=u+l$, $u+2$, \dots, $v$.

\st[戊� �� $j$.] (� ����� ������� �������� $|COUNT|[i]$ ���� ����� ������,
 ������� ��� ������ $i$, � ��������� $|COUNT|[v]=N$.) ��������� ��� 
\stp{6} ��� $j=N$, $N-1$, \dots, 1 � ��������� ������ ���������.

\stp[����� $R_j$.] 㑒������� $i\asg |COUNT|[K_j]$, $S_i\asg R_i$, � 
$|COUNT| [K_j]\asg i-1$.
\algend
\noindent ������ ���������� ����� ��������� �������� � ���.~6; ��������� 
��� ������ \MIX\ ����� ����� � ���.~9. ��� ���������������� ���� 
�������� ��� ����� ������� ��������� .����������.

᎐������� ����������� ��������� � ��������, ���, � ��������� C, ������� 
����������� � ������ �.~X.~䐝��� 
[{\sl JACM\/},{\bf 3} (1965), 152],. ���� �� � �� ������ � ��� ��� � ����� 
����������� �����������. �������������� �������, ��� � ��������� D, 
������� ���������� X.~᜞������ � 1954~�. � ������������� ��� ����������� 
����������, ������� �� ������� ����� (��. �.~5.2.5); ���� ����� ����� -��� 
����������� ��� ��������� "Mathsort" � ������ W. Feurzig, {\sl CACM\/}, 
{\bf 3} (I960), 601.

\excercises
\ex[15] ����� �� �������� �������� �, ���� � ���� �2 �������� � 
����� ���������� �� $2$ �� $N$, � �� �� $N$ ��~$2$? 璎 ����������, ���� � 
���� C� �������� $j$ ����� ���������� �� $1$ �� $i-1$?

\ex[21] ��������, ��� �������� C �������� ��������� � ��� 
������� ���������� ������. ���� $K_j=K_i$  � $j<i$, �� ��� �������� � 
����� ������ $R_j$---�� ��� ����� $R_i$?

\rex[21] ����� �� �������� C �������� ���������, ���� � ���� C4 �������� 
�������� "$K_i<K_j$"  �� "$K_i\le K_j$"?

\ex[16] �������� \MIX-���������, ������� �������� ����������, ������� 
���������� C; ���� ��������� ������ ��������� ����� � ������ $|OUTPUT|+1$, 
\dots, $|OUTPUT|+N$ � ������������ �������. ኎���� ������� �������� �� 
��� ���� ���������?
%% 101

\ex[22] ㋓������ �� ��������� C � ���������� ��������� ���������?
$$
\indent\vtop{
\halign{#\bskip\hfill&\bskip |#|\hfill&|#|\hfill\cr
������ ����� ������ 8�:  & INCX  & 0, 2 \cr
�������� ������ 10:      & JGE    &5F\cr
�������� ������ 14:      & DECX &1\cr
��������� ������ 15. \cr
}
}
$$


\ex[18] �������������� ������� ������ ��������� D,  ��������� 
������������� ����������, ������������ ��� ���������� 16 �������
$$
\hbox{5�, 0�, 5U, 00, 9, 1N, 8S, 2R, 6A, 4A, 1G, 5L, 6T, 61, 70, 7N.}
$$
����� �����---��� �����, � �����---������������� ���������� � �������.

\ex[13] ����� �� �������� D ���������� "����������" ����������? 
\ex[15] ����� �� �������� D �������� ���������, ���� � ���� D5 �������� 
$j$ ����� ���������� �� $1$ �� $N$, � �� �� $N$ �� $1$?

\ex[23] �������� \MIX-��������� ��� ��������� D, ����������� ��������� C 
� ���.~4. �������� ����� ������ ����� ��������� � ���� ������� �� $N$ � $(v-u)$.

\ex[25] ���������� ����������� ��������, ������� �� ������� $N$ ������� 
$(R_1, \dots, R_N)$ �������������� �� $(R_{p(1)}, \dots, R_{p(1)}))$, ���� 
���� �������� $R_1$, \dots, $R_N$ � ������������ $p(1)$ \dots $p (N)$ 
��������� 
$\{1, \dots,  N\}$. ������������ �� ������������ ��������� ������������ 
������. (풀 ������ ���������, ����� ��������� �������������� � ������ 
������ ����� ���������� ������� �������, �� �������� ������ �� $2N$ �������.)

\ex[M27] �������� \MIX-��������� ��� ��������� �� ���.~10 � 
��������������� ��. �������������.

\rex[25] ���������� ����������� �������� �������������� � ������ ������� 
$R_1$, \dots, $R_N$ � ��������������� ������� ����� ���������� ���������� 
������ (���.~7). ������������ �� ������������ ��������� ������������ ������.

\rex[27] ��������� D ���������  ������������ ��� $2N$ ������� 
$R_1$, \dots $R_N$  � $S_1$, \dots, $S_N$. ��������, ��� ����� �������� 
������������� ��� $N$ ������� $R_1$, \dots, $R_N$, ���� ������ ����� D5 � 
D6 ���������� ����� ��������������� ���������. ( �� �������, ������ 
������� � ���, ����� ����������� ��������, ������� �� ������������ ������ 
$R_1$, \dots, $R_N$.  ����������� �� ���������
$$
|COUNT| [u], \ldots |COUNT| [v]
$$
����� ���������� ���� D4, �� ��������� �������������� ������; ���, 
�� ��������, ��������� ������, ������������� � ���. 10.)

\subsubchap{᎐������� ���������} % 5.2.1
���� �� ������ ��������-������� ���������� �������� �� ���������� � 
������ \S~5.2 �������, ������� ���������� ������ � �����; ��������������, 
��� ����� ������������� ������ $R_j$ ���������� ������ $R_1$, \dots, 
$R_{j-1}$ ��� �����������, � $R_j$ ����������� � ��������������� �����. �� 
������ ���� ����� �������� ��������� ���������� ��������.

\section ������� �������. ���������� ���������� ��������� ��������� � 
�������� ���������. ����� $1 <j  \le  N$  �  ������ $R_1$, \dots, $R_{j-1}$
%% 102
��� ��������� ���, ���
$$
K_1\le K_2\le \ldots \le K_{j-1}.
$$
(��������, ��� � ���� ����� ����� $K_j$ ������������ ���� ������ $R_j$.) 
����� ���������� �� ������� $K_j$ � $K_{j-1}$, $K_{j-2}$, \dots �� ��� ���, 
���� �� ���������, ��� ������ $R_j$ ������� �������� ����� $R_i$ � 
$R_{i+1}$; ����� �������� ������ $R_{i+1}$, \dots, $R_{j-1}$ �� ���� ����� 
����� � �������� ����� ������ � ������� $i+1$. ㄎ��� ��������� �������� 
��������� � �����������, ��������� �� ���� � ������, ��� �������� � 
��������� ���������; ��������� ������ $R_j$ ��� �� "��������� �� 
���������� �� �������", ���� ������ ����� �������� \dfn{������������}, 
��� \dfn{�����������}.

\alg S.(᎐������� �������� ���������.) ������ $R_1$, \dots,  $R_N$ 
��������������� �� ��� �� �����; ����� ���������� ���������� �� ����� 
����� �����������: $K_1\le \ldots \le K_N$.

\st[戊�. �� $j$.] ��������� ���� �� \stp{2} �� \stp{5} ���  $j= 2$, 3, 
\dots, $N$ � ����� ����� ��������� ��������.
\picture{���. 10.  �������� S: ������� �������.}
\st[㑒������� $i$, $K$, $R$.] 㑒������� $i\asg j-1$,  $K\asg K_j$,  
$R\asg R_j$.(� ����������� ����� �� ���������� �������� ������ $R$ � 
������ �����, ��������� $K$ � $K_i$ ��� ��������� ��������� $i$.)

\st[᐀����� $K$ �  $K_i$.] ���� $K\ge K_i$, �� ������� � ����  
\stp{5}. (�� ����� ������� ����� ��� ������ $R$.)

\st[����������� $R_i$, ��������� $i$.] 㑒������� $R_{i+1}\asg R_i$,
 $i\asg i-1$. ���� $i>0$, �� ��������� � ���� \stp{3}. (���� $i=0$, �� 
$K$---���������� �� ������������� �� ��� ��� ������, �, ������, ������ $R$ 
������ ������ ������ �������.)
\st[$R$ �� ����� $R_{i+1}$.] 㑒������� $R_{i+1}\asg R$.
\algend
� ����.~1 �������� ���������� ��������� S � ����������� ������, ������ 
���� ��� ��������. 풎� ����� ����������� ������ ����������� �� 
�������������� ������; ���������� ��������� \MIX-���������---����� 
�������� �� ���� ���������� �������� ���������� � ���� �����.
%% 103

\prog S.(᎐������� �������� ���������). ������, ������� ���� 
�������������, ��������� � ������� $|INPUT|+1$, \dots,  $|INPUT|+N$; ��� 
����������� � ��� �� ������� �� �����, ����������� ���� ����� �������. 
����� $|rI1|\equiv j-N$; $|rI2|\equiv i$, $|rA|\equiv R\equiv K$; 
��������������, ��� $N\ge 2$.
\code
START &ENT1 &2-N       &1      & S1.戊� no $j$. $j\asg 2$. 
2H    &LDA  &INPUT+N,1 &N-1    & S2. 㑒������� $i$, $K$, $R$
      &ENT2 &N-1,1     &N-1    & $i\asg j-1$.
3H    &CMPA &INPUT,2   &B+N-1-A& S3. ᐀����� $K$, $K_i$
      &JGE  &5F        &B+N-1-A& � S5, ���� $K\ge K_i$.
4H    &LDX  &INPUT,2   &�      & S4. ����������� $R_i$, ��������� $i$
      &STX  &INPUT+1,2 &�      & $R_{i+1}\asg R_i$.
      &DEC2 &1         &B      & $i\asg i-1$.
      &J2P  &3B        &B      & � S3, ���� $i>0$.
5H    &STA  &INPUT+1,2 &N-1    & S5. $R$ �� ����� $R_i+1$.
      &INC1 &1         &N-1
      &J1NP &2B        &N-1    & $2\le j \le N$.
\endcode
\progend
����� ������ ���� ��������� ����� $9B+10N-3A-9$ ������, ��� $N$---����� 
����������� �������, $A$---����� �������, ����� � ���� S4 �������� $i$ 
������� �� 0, � $B$---����� �����������. �, ��� $A$ ����� ����� �������, 
����� $K_j<(K_1, \ldots, K_{j-1})$ ��� $1< j \le N$, �. �. ��� ����� 
������������� ���������---��������, ������� ���� ��������� ����������� � 
�.~1.2.10. ������� �������, �������� ������, ��� $B$---���� ��������� 
��������: ����� ����������� ��� ������������� $j$ ����� ����� �������� 
����� $K_j$, ��� ��� $B$ ����� ����� �������� ������������ $K_1$, $K_2$, 
\dots, $K_N$. ዅ����������, �������� �������� (1.2.10--16) � (5.1.1--12, 
13),
$$
\eqalign{
A&=(\min 0, \ave H_N-1, \max N-1,  \dev\sqrt{H_n-H_n^{(2)}});\cr
B&=(\min 0, \ave (N^2-N)/4, \max (N^2-N)/2,
\dev\sqrt{N(N-1)(N+2.5)/6}),\cr
}
$$
� ������� ����� ������ ��������� S � �������������, ��� ����� �������� � 
����������� � ��������� �������, ����� $(2.25N^2+7.75N-3H_N-6)u$. � 
���.~33 ��������, ��� ����� ����-���� ��������� ��� �����.

����������� � �������� ������� � ����.~1 ������ �������� 16~���������; 
������� ��� ������������� ��������, 087 �~061, �, ��� �� ������ � 
���������� ������, 41 ��������. ዅ����������, $N=16$, $A=2$, $B=41$, � 
����� ����� ���������� ����� $514u$.

\section �������� ������� � ����������� �������. ����� ��� 
���������� �������� ��������� �������������� $j$-� ������, �� ���� 
������������ � ������� �������� � $j/2$ ����� ���������������� �������; 
%% 104
{\catcode`\!=\active\def!{\hidewidth{}_{\hbox{\tentt\char"5E}}}
 \catcode`\@=\active\def@{{}_{\hbox{\tentt\char"5E}}\hidewidth}
 \catcode`\:=\active\def:{\hidewidth{\char`\:}}
\ctable{\bskip$#$\bskip&&\bskip$#$\bskip\cr
\noalign{\rightline{ ���� 1}}
\noalign{\centerline{������ ���������� ������� �������}}
!503&:087 &\cr
 087& 503@&:512\cr
!087& 503 & 512 &:061\cr
 061& 087 & 503 & 512@&:908\cr
 061& 087@& 503 & 512 & 908 &:170\cr
 061& 087 & 170 & 503 & 512@& 908 &:897\cr
\noalign{\line{\null\leaders\hbox to 1em{\hss.\hss}\hfill\null}}\cr
 061& 087 & 154 & 170 & 275 &426 &503 &509 &512 &612 &653 &677@&765 &897 &908 &:703\cr
 061& 087 & 154 & 170 & 275 &426 &503 &509 &512 &612 &653 &677 &703 &765 &897 & 908\cr
}
}
������� ����� ����� ��������� ����� 
�������������� $(1+2+\cdots+N)/2\approx N^2/4$, � ��� ����� �����, ���� 
���� $N$ �������� ������. � �.~6.2.1 �� ������ ������ "��������� ������",
 ������� ���������, ���� ��������� $j$-� ������� ����� �������������� 
$\log_2 j$ ��������������� ������� ��������� ���������. ��������, ���� 
����������� 64-� ������, ����� ������� �������� ���� $K_{64}$ � 
$K_{32}$; �����, ���� �� ������, ���������� ��� � $K_{16}$, ���� ������---� 
$K_{48}$ � �. �., ��� ��� ����� ��� $R_{64}$ ����� ������� ����� ����� 
���� ����� ���������. ����� ����� ��������� ��� $N$ ����������� ��������� 
����� �������������� $N \log_2 N$, ��� ����������� �����, ��� $N^2/4$; � 
�.~6.2.1 ��������, ��� ��������������� ��������� �� ����������� ������� 
�������, ��� ��������� ��� ������� �������. 풎� ����� ���������� 
\dfn{��������� ���������}. �� ���������� ������ ����� ��� � 1946~�., � 
������ ���������� �� �������� ����������.

������������ ������� � ���, ��� �������� ������� ������ ������ ������ 
����������: 
����� ����, ��� �� �����, ����  ��������� ������ $R_j$, ��� 
����� ����� ��������� �������� $j/2$ ����� ��������������� �������, ����� 
���������� ����� ��� $R_j$ ��� ��� ����� ����� ������ ��������, �� 
��������, ���������������� $N_2$. ��������� �������������� ������ 
(��������, IBM 705) ����� ���������� ���������� "����������", 
����������� �������� ����������� � ������� ���������, �� � ������ $N$ 
����������� �� $N^2$ � ����� ������ �������� �����������, ��������, ������,
 ����������� X. �������� 
[{\sl CACM\/}, {\bf 3} (1960), 618--620],
����������, ��� �� ������� ������������� �������� ������� ��� ���������� 
����� $N=128$ ������� �� ������ IBM~705, ���� ������ ������ ������� �� 80 
�����; ����������� ������ �������� � � ������ �������.
%% 105
{
\catcode`\!=\active\def!{\hidewidth{}_{\hbox{\tentt\char"5E}}}
 \catcode`\@=\active\def@{{}_{\hbox{\tentt\char"5E}}\hidewidth}
 \catcode`\:=\active\def:{\hidewidth{\char`\:}}
\ctable{\bskip$#$\bskip&&\bskip$#$\bskip\cr
\noalign{\rightline{ ���� 2}}
\noalign{\centerline{����������� �������}}
   &   &   &     &!503 \cr
   &   &   & 087 & 503@ \cr
   &   &   &!087 & 503 &512 \cr
   &   &061& 087 & 503 &512@ \cr
   &   &061& 087@& 503 &512 & 908 \cr
   &061&087& 170 & 503 &512 &@908 \cr
   &061&087& 170@& 503 &512 & 897 & 908 \cr
061&087&170& 276 & 503 &512 & 897 & 908 \cr
}
}

����������, ��������������� ����������� ����� ��������� �����-������ 
�������, ����������� ��������� ����� ����������� �����������; ������ 
����� �����, ������������ � ������ 50-� �����, ���������������� � 
����.~2. ����� ������ - ������� ���������� � �������� ������� ������, � 
����� ��� ����������� ��������� ������������� ��� ������ ������� ����� ��� 
������, ����, ���� �������.  �� ������� ������� ���������� �������� 
�������� ������� ������ �� ��������� � �������� ��������� �� ���� 
���������� ���������� ���������. ����� ��������� ���� �����, ��������� �� 
������ ������, ��� ��������� ��� $N$ ������� (��. ���. 6), �� �� �� ������ 
������ ������������� �� ����� "�����������" ��������, ��� ��� 
���� ����������� ������� ����� ���������� ������.

\section ����� 腋��. ��� ��������� ����������, ������� ������ 
��� ���������� ������ ������ �� ���� �������, ������� ����� ������ ����� � 
������ ������ ��������������� $N^2$, ������ ��� � �������� ���������� 
������ ������ ������ ������ � ������� ����� $N/3$ ������� (��. ���.~7). 
�������, ���� �� ����� �������� �����, ����������� ������������� �� 
�������� ������� �������, �� ��������� ��������� ��������, � ������� 
�������� ������ ����� �� ������������ �������� ��������, � �� ��������� �������.

 �� ����� ��������� � 1959~�. ��������� �. 腋��� [{\sl CACM\/}, {\bf 2} 
(July, 1959), 30--32]; �� ����� �������� ��� \dfn{����������� � ��������� 
�����}. � ����.~3 ����������������� ����� ����, ������� � ������ ����� 
������. ፀ���� ����� 16 ������� �� 8 ����� �� ��� ������ � ������ 
������: $(R_1, R_9)$, $(R_2, R_{10})$, \dots, $(R_8, R_{16})$. � 
���������� ���������� ������ ������ ������� �� ����������� �������� �� 
������ ������ ����. 3,
%% 106
\picture{ ���� 3}
��� ���������� "������ ����������". �������, ��� �������� 154 � 512 
���������� �������, � 908 � 897 ������������� ������. �������� ������ 
������ �� ������ ������ �� ������ � ������:
$(R_1, R_5, R_9, R_{13})$, \dots, $(R_4, R_8, R_{12}, R_{16})$---� ����� 
����������� ������ ������ � �����������; ���� ������ �������� �������� � 
������� ������ �������. ��� ������� ��������� ����������� ��� ������ �� 
������ �������; ������� ����������� ��������� ����������, �� ����� 
�������� ����������� ��� 16 �������. � ������ �� ���� ������������� 
��������� ���������� ��������� ���� ������������ �������� �����, ���� 
��� ������������ ������ ������������� �����, ������� �� ������ 
����� ����� ������������ �������� ���������; ������ �������� 
������ ��������� ������ ��������� ���������.

������������������ ����� 8, 4, 2, 1 �� ������� ������� ����������, ����� 
������������ \emph{�����} ������������������� $h_t$, $h_{t-1}$, \dots, 
$h_1$, � ������� ��������� ��� $h_1$ ����� 1. ��������, � ����.~4 ����� 
�������� ���������� ��� �� ������ � ������ 7, 5, 3, 1. ���� 
������������������ ����������� ������� ����� ������; �� ������� ����� 
������������������� ����� �����.

\alg D.(᎐������� � ��������� �����.) ������ $R_1$, \dots, 
$R_N$ ��������������� �� ��� �� �����. ����� ���������� ���������� �� 
����� ����� �����������: $K_1 \le \ldots \le K_N$. ��� 
���������� ��������� ���������� ������������ ��������������� 
������������������ ����� $h_t$, $h_{t-1}$, \dots, $h_1$, ��� $h_1=l$; 
��������� ������ ��� ����������, ����� ����������� ��������� ����� 
����������. ��� $t = 1$ ���� �������� �������� � ��������� S.

\st[戊� �� $s$.] ��������� ��� \stp{2} ��� $s=t$,  $t-1$, \dots, 1,
����� ���� ��������� ������ ���������.

\st[戊� �� $j$.] 㑒������� $h\asg h_s$ � ��������� ���� \stp{3}, \dots
%% 107
\stp{6} ��� $h<j\le N$. (��� ���������� ���������, ��������� ���� �� 
����� �� $h$ �������, ������������� �������� ��������� � � ���������� 
������� $K_i\le K_{i+h}$ ��� $1\le i\le N-h$. 考� \stp{3}, \dots, \stp{6},
 �� ��������, ����� ��, ��� �������������� S2, \dots, S5 � ��������� S.) 

\st[㑒������� $i$, $K$, $R$.] 㑒������� $i\asg j-h$, $K\asg K_j$,
$R\asg R_j$.

\st[᐀����� $K$, $K_i$.] ���� $K\ge K_i$, �� ������� � ���� \stp{6}.

\st[����������� $R_i$, ��������� $i$.] 㑒������� $R_{i+h}\asg R_i$,
����� $i\asg i-h$. ���� $i >0$, �� ������������ � ���� \stp{4}.

\st[$R$ �� ����� $R_{i+h}$.] 㑒������� $R_{i+h}\asg R$.
\algend

ᎎ������������ \MIX-��������� �� ������� �������, ��� ���� ��������� ��� 
������� �������. ᒐ��� 08--19 ���� ��������� ���������� �� ��������� S 
� ����� ����� �������� ��������� D.

\prog D.(᎐������� � ��������� �����.) ��������������, ��� ���� 
���������� �������� �� ��������������� ������� � $h_s$ ��������� � ������ 
$|H|+s$; ��� ���� ���������� ������ $N$. ᎄ������� ���������: 
$|rI1|\equiv j-N$; $|rI2|\equiv i$; $|rA|\equiv R \equiv K$; 
$|rI3|\equiv s$; $|rI4|\equiv h$. �������, ��� ��� ��������� ���� ���� 
��������. 풎 
������� ��� ����, ����� �������� ����� ������������ ���������� 
����������� �����.
\code
START &ENT3 &�        &1        & D1. 戊� �� $s$. $s\asg t$.
1H    &LD4  &H,3      &T        & D2. 戊� �� $j$.$h\asg h_s$.
      &ENT1 &INPUT,4  &�        & �������� ������ � ����
      &ST1  &6F(0:2)  &�        & ����������� �
      &ST1  &7F(0:2)  &�        & �������� �����.
      &ENN1 &-N, 4    &�        & $|rIl|\asg N-h$.
      &ST1  &4F(0:2)  &T
      &ENT1 &1-N, 4   &T        & $j\asg h+1$.
2H    &LDA  &INPUT+N,1&NT-S     & D3. 㑒������� $i$, $K$, $R$.
4H    &ENT2 &N-H,1    &NT-S     & $i\asg j-h$. (���������� ����������)
5�    &�� &INPUT,2  &B+NT-S-A & D4. ᐀����� $K$, $K_i$.
      &JOE  &7F       &B+NT-S-A & � ���� D6, ���� $K\ge K_i$.
      &LDX  &INPUT,2  &B        & D5. �����������  $R_i$, ��������� $i$.
6�    &STX  &INPUT+H,2&�        & $R_{i+h}\asg R_i$. (���������� ����������)
      &DEC2 &0,4      &�        & $i\asg i-h$.
      &J2P  &5�       &�        & � ���� D4, ���� $i>0$.
7�    &STA  &INPUT+H,2&NT-S     & D6. $R$ �� ����� $R_{i+h}$. (���������� ����������)
8�    &INC1 &1        &NT-S     & $j\asg j+1$.
      &J1NP &2�       &NT-S     & � D3, ���� $j\le N$.
      &DEC3 &1        &�
      &J3P  &1�       &�        & $t\ge s\ge 1$.
\endcode
\progend

%% 108

\section *������ ������ 腋��. 璎�� ������� ������� ������������������ 
����� ���������� ��� ��������� D, ����� ���������������� ����� ������ 
��� ������� �� ���� �����. 풎 �������� � ����� ��������, �� ��� �� �� 
����� �������� �������������� �������; ������ �� ��� ��� �� ������� 
����� ��������� ��������� ������������������ ����� ��� ������� $N$. ⅌ 
�� ����� �������� �������� ����� ���������� ������ � ��������� ���������� 
������� 腋�� � ��������� �����, � �� ����� �� ������ �������; ����������� 
����� ����� � ����������� ���� �����������. [爒������, �� ������� 
���������� � ����������, ����� ���������� ��������� ��������� �������, 
�� ������ (8).]

ᗅ����� ������ ���������� � ��������� D ����������, ��� �� ����� 
���������� ������ ���� ��������: ������ ����� $N$, ����� ���������� (�.�. 
����� �����) $T=t$, ����� �����
$$
S=h_1+\cdots+h_t,
$$
����� ��������� $B+NT-S-A$ � ����� ����������� $B$. ��� � ��� ������� 
��������� S, ����� $A$ ����� ����� ������������� ���������, 
������������� ��� ������������� ��������� ����������, � $B$ ����� ����� 
�������� � ���������. �������� ��������, �� �������� ������� ����� ������, 
�������� �������� $B$, ������� �� ��� �� � ������� ������� ������� ���� 
��������. ��� ������� ����� ��������������, ��� ����� �������� � 
������������� ����������� � ��������� �������.

������� �������� ���� D2 "$h$-�����������". ⎃�� ���������� ������� 
腋�� ������� �� $h_t$-����������, �� ������� ������� $h_{t-1}$-����������,
 \dots, �� ������� ������� $h_1$-����������. 䀉�, � ������� $K_i\le 
K_{i+h}$ ��� $1\le i \le N-h$, ����� ��������  $h\hbox{-�������������}$.

���������� ������� ���������� ��������� ������� �������, ����� ������� 
����� ��� ���� $h_2=2$ � $h_1=1$. �� ����� ������� ��������� ����� 
2-������������� ������������������ ������ $K_1$ $K_2$ \dots $K_N$. ����� 
������, ��� ����� ������������ $a_1$ $a_2$~\dots $a_n$ ��������� $\{1, 2, 
\ldots, �\}$, �����, ��� $a_i\le a_{i+2}$ ��� $l\le i \le n-2$, �����
$$
\perm{n}{\floor{n/2}},
$$
��� ��� ���������� ����� ���� 2-������������� ������������ ��� ������� 
������ $\floor{n/2}$ ���������, ������������� � ������ �������� $a_2a_4$, 
\dots, ����� ��������� $\ceil{n/2}$ ��������� �������� � ������� � 
��������� ��������. ����� 2-���������� ���������� ����� � ���������� 
������������ ����� ���������� ����� 2-������������� ������������. ������ 
������� ����� �������� �� ���� ����� �������������?
%% 109
\bye