\input style
\chapno=5\subchno=4\subsubchno=3\chapnotrue

ꀑ������ �������, ������� ������������, ���������� �
"������� �������������" �������� �� ������, ���� ������� �������
������������� ������� �� ������ �.~5.4.2. ꀆ��� ������
������� ������������ ������ ������ �� \emph{����} ������. ���~2,
��������, ���������� ����������� ���������� ������������ ������� �~T1,
T2, T3, T4, T5 ��~T6, ����~T5 �� ������ ������ (��� ���� ��~T6 ����������
15~�������� ������������� �����~5), ����� ��������������� ������� �~T1, T2,
T3, T4 ��~T5, ����� ������������ ������� ��~T4, ������������ �������
��~T3 �, �������, ������������ ������� (�������� �����������) �~T1
��~T2. ���~3 ���������� ����� �� ������� ����� ���������� �������
������������ �������, ���� ���� ����� �� ������ ������, �����
��������������� �~�.~�. (���, ��� ����� ������ ����� ��������� ��
��������� �����~5.4.3.2.1, � ��~5.4.3!)

ߑ��, ��� �������� ����������� �������, � �� ����� ���� �� ��������.
􀊒������, ������, � ������ ����� ���� ��� ����������� �������� ������
��������� ������� ����� �������. ��������, ������� ���������� �������
������������, �������� � ����������� ������� ����������. 򎋜��~25 ��~950
�������������� �������� ����������� ����� ������. ᎋ���� �����
������� ��������� ������������ � ��������������� ��������.

� ������ ������ ����� ����������, ��� ��������� �����---�������� ������
������� � ��������� � �����������, ��� ��� ����������� ����������� �����
���������� ��� ����� $(T-1)\hbox{-�������}$ �������, � �� ����� ���
��������� ���������� $(T-1)\hbox{-�������}$, $(T-2)\hbox{-�������}$,
$(T-3)\hbox{-�������}$ �~�.~�., �� � ���������������� ��� ��������������
\emph{�����,} ��� �����������, ��� ����� � ����� ����! ꀊ �� ������ �
�.~5.4.2, ������� ������� ������� �� �������� ��������� �������������. �
����.~1 �������� �������������� ���������� ���������� ������� ��
�������� � �������� �������� �.~5.4.2.

텒����� ������� "������ �������������" ��� ���������� �������. 䋟 �����
���� �����
$$
\matrix{
\hbox{󐎂���} & T1 & T2 & T3 & T4 & T5 \cr
0 &   1 &   0 &   0 &   0 &  0 \cr
1 &   1 &   1 &   1 &   1 &  1 \cr
2 &   5 &   4 &   3 &   2 &  1 \cr
3 &  15 &  14 &  12 &   9 &  6 \cr
4 &  55 &  50 &  41 &  29 & 15 \cr
5 & 190 & 175 & 146 & 105 & 55 \cr
\multispan{6}\dotfill\cr
n & a_n & b_n & c_n & d_n & e_n \cr
n+1 & a_n+b_n+c_n+d_n+e_n & a_n+b_n+c_n+d_n & a_n+b_n+c_n & a_n+b_n & a_n \cr
}
\eqno(1)
$$
%%344
\htable{򀁋��� 1}%
{�������� ��������� ���������� �������}%
{\strut\hfill # && \bskip\hfill$#$\hfill\bskip\cr
녍��  & \hbox{����} & \hbox{����} & \hbox{������}\cr
 & \hbox{(� ������������)} & \hbox{(��� �����������)} &\hbox{�����}\cr
\noalign{\hrule}
 3 & 2.078\ln S+0.672 & 1.504\ln S+0.992 &  1.6180340\cr
 4 & 1.235\ln S+0.754 & 1.102\ln S+0.820 &  2.2469796\cr
 5 & 0.946\ln S+0.796 & 0.897\ln S+0.800 &  2.8793852\cr
 6 & 0.796\ln S+0.821 & 0.773\ln S+0.808 &  3.5133371\cr
 7 & 0.703\ln S+0.839 & 0.691\ln S+0.822 &  4.1481149\cr
 8 & 0.639\ln S+0.852 & 0.632\ln S+0.834 &  4.7833861\cr
 9 & 0.592\ln S+0.861 & 0.587\ln S+0.845 &  5.4189757\cr
10 & 0.555\ln S+0.869 & 0.552\ln S+0.854 &  6.0547828\cr
20 & 0.397\ln S+0.905 & 0.397\ln S+0.901 & 12.4174426\cr
\noalign{\hrule}
}

���� ���������� �������� ���� �����---�� ������������� �������� ��������
����� � ������� ���������� ����������� $(2T-1)\hbox{-���������}$. 퀏�����,
���� ���������� �������������������� �� ���.~73 ����� ������������� �����,
����� ������� �~190, 175, 146, 105 �~55! � ������� ���� ������������� ����
\picture{���.~73. ㅎ����������� ������������� ��������� �����.}
������� � ���� ������, � ����� ������, ��� ������������� �������,
������������� �� $(T-1)\hbox{-�������}$ �������, $(T-2)\hbox{-�������}$
�������,~\dots, ����������� �������, �������������� ���������������
\emph{���������} ���� ���� ����������.

\section *퀗������ ������������� ��������. 呋� ����� ���������
�������� � ���������������� �� ���� ����� 􈁎�����, �� �����,
��� ������, �������� ��������� �������. ���������� ������ ��������
����������, ��� ����� ������������ ��������� �������� �����������, ���
��� ��������� ������� ������ ������������
%%345
������ �������; ���� ������� 190~��������� ��������, �� ������ ������
�������������� ���� ���, ��� � ����������� ���� �������, �� ���� �������
191~�������, ��, ��������, ������� ��������� �������, � ������ ������
������ ����� �������������� ����� ���. � �������, � ���������������� �����
�������� ������ ������� ������. 䝂��~�.~􅐃���� ����� ������ ���
������������ ��������� �������, ��� ������ �������� �� ����� ������
\picture{
  ���.~74. ������������� ���������� ������� � ��������������
  �� ���������~D.
}
���� ������� �������� � ����������� ����������� �����. 呋� ������ �����
����������� (������ ������� "����������" ������ ��������� ��������� ��
��������� � "����������" �������, ��� � ���������~5.4.2D), �� �������
������������ ������� ������� � ������ �� �������, ��� ���������� �� ���.~74.

��������, ��� $(a, b, c, d, e)$, ���~$a\ge b \ge c \ge d \ge e$---������
�������������. ���������� ������������ ����� �����������
� ����������� ���������� ������������, �� ����� �����������, ��� ��������
�������������---���~$(e, d, c, b, a)$,
%%346
�.~�.~$a$~�������� ��~T5, $b$~��~�4 �~�.~�. 񋅄����� ������
�������������---��� $(a+b+c+d+e,  a+b+c+d, a+b+c, a+b, a)$;
� ���� ���� ������������� ������, ��� �� ��������� ����� ����������
������, �� ����� �������, ��� ����� ��������
��������������~$(D_1, D_2, D_3, D_4, D_5)$ ��������� ��������, ���
$$
\displaynarrow{
D_1 \le a+b+c+d,\quad D_1 \le a+b+c,\quad D_3\le a+b,\cr
D_4 \le a,\quad D_5=0;\qquad D_1\ge D_2 \ge D_3 \ge D_4 \ge D_5.\cr
}
\eqno(2)
$$

� ������ ������������ ����, ��� ��� ��������� ������� ���������� ��
������ � ����� ������� �����. �����������, ��� ������ ������ �������
���� $a$~�������� ����������� ������������ �������, ����� $b$~��������
����������� ��������������� �~�.~�. 퀘� ���� ������� � ������������
��������� �������� ����� �������, ����� �������� ������� ������������.
󄎁�� ��������� ������ ������ ������� ��������� �������:

1.~呋�~$D_4=a$, �� �������~$a$ �� ����~$D_1$, $D_2$, $D_3$, $D_4$ �
�������, ���~T5---��������� �������. 呋�~$D_4<a$, �� ����� $a$~�������� �
����~T1 ��~T5, ��������� ���������� ��������� ����� ��������� ��������
�� ������~T1--T5 ���, ����� ����� ��������~$D_1$, $D_2$, $D_3$, $D_4$
������������� ������������
$$
\displaynarrow{
D_1\le b+c+d,\quad D_2\le b+c,\quad D_3\le b,\cr
D_4=0;\qquad  D_1\ge D_2\ge D_3\ge D_4.\cr
}
\eqno(3)
$$
򀊈� �������, ����~$D_2$ ���� �������������~$\le b+c$, �� ��
�� ���������� �� ������ ���������� ������� � ���� ����� �� ������ ����; �
�� �� �����, ����~$b+c<D_2\le a+b+c$, �� ���������� �����~$D_2-b-c$
��������� ��������.

2.~(���� ��� ���������� ����~1, �� � ��������� "�������".) 呋�~$D_3=b$,
�� �������~$b$ �� ����~$D_1$, $D_2$, $D_3$ � �������, ���~T4---���������
�������. 呋�~$D_3<b$, �� ����� $b$~�������� � ����~T1--T4, ��������, ����
����������, ����� ��������� ��������, ����� �������
$$
D_1\le b+c,\quad D_2\le b,\quad D_3=0;\qquad D_1\ge D_2\ge D_3.
$$

3.~� ��� �����.

셒�� 􅐃����� ������������� �������� �� ������ ����� �����������������,
���������� ������� �������� � ������~3 �� �������~4 �~(1). 䎏�����, ���
"����������" ����� (T1,~\dots, T5) ��������� ��������������
$(5, 9, 12, 14, 15)$~�������� � ��� �� ����� ������� ��� � �������� �����
��~$(55, 50, 41, 29, 15)$. ��� ��������� ����� ���� ������ �������� ���:
%%347
\ctable{
$#$\hfill&&\hfill\bskip$#$\bskip\hfill\cr
 & \hbox{䎁�����} &\hbox{䎁�����} &\hbox{䎁�����} &\hbox{䎁�����} &\hbox{䎁�����} &\hbox{񝊎���������}\cr
\hbox{���} &\hbox{� T1} &\hbox{� T2} &\hbox{� T3} &\hbox{� T4} &\hbox{� T5} &\hbox{��������}\cr
(1, 1)& 9 &  0 &  0 &  0 &  0 & 15+14+12+5\cr
(2, 2)& 3 & 12 &  0 &  0 &  0 &  15+14+9+5\cr
(2, 1)& 9 &  0 &  0 &  0 &  0 &    15+14+5\cr
(3, 3)& 2 &  2 & 14 &  0 &  0 &    15+12+5\cr
(3, 2)& 3 & 12 &  0 &  0 &  0 &     15+9+5\cr
(3, 1)& 9 &  0 &  0 &  0 &  0 &       15+5\cr
(4, 4)& 1 &  1 &  1 & 15 &  0 &       14+5\cr
(4, 3)& 2 &  2 & 14 &  0 &  0 &       12+5\cr
(4, 2)& 3 & 12 &  0 &  0 &  0 &        9+5\cr
(4, 1)& 9 &  0 &  0 &  0 &  0 &          5\cr
}
񍀗��� �������� ������ �������� ��~T1, ����� $(3, 12)$---��~T1 �~T2 �~�.~�.
呋� ���� �����������, ������, �� ����� ����~$(3, 2)$, �� "�������������
��������" ����������~$15+9+5$. ��� ��������, ��� �� �������� ������������
������� 15~��������,  ������������ ������� 9~�������� � ������������
������� 5~�������� ����������� ���������� ��������� ��������.
䐓���� �������, $15+9+5$ ��������, �������������� �� ������~3,
�� �������������� � ������� ������ ���� �������.

񋅄����� �������� �������� ��������� ���� �������.

\alg C.(񎐒������ ��������� �������� �� ����������� ��������������.) ����
�������� ������������ ��������� ������� �� ������ ������� �� ��������,
���� ����� ��������� �������� �� �����������. 瀒�� �� ����������, ���
������� ������� �����, �����������, ��� ������� $T\ge 3$~��������������
���������, ��� ���� ������������ ����� �������
$(T-1)\hbox{-�������}$~������� �
�������� ����������� ������� �����������. 녍��~$T$ �����
���� ������������ ��� �������� �����, ��� ��� �� ��� �� �������� �� ����
��������� �������. �������� �������� �� ���������� ���������:
{\let\mypar=\par\ctable{
$#$,\bskip\hfill&$#$:\bskip\hfill&
\vtop{\parindent=0pt \hsize=13cm #\mypar}\cr
|A|[j]    & 1 \le j \le T &
   ������ ������ ��������� �������������, ������� ���� ����������. \cr
|AA|[j]   & 1 \le j \le T &
   򎗍�� ��������� �������������, � �������� �� ���������. \cr
|D|[j]    & 1 \le j \le T &
   ����� ��������� ��������, �������������� ��������������� �� ����������
   �������������� ���������� � �������~$j$. \cr
|M|[j]    & 1 \le j \le T &
   쀊��������� ����� ��������� ��������, ������� ���������� ����� ��
   ���������� �������������� ���������� � �������~$j$. \cr
|TAPE|[j] & 1 \le j \le T &
   펌�� ����������� ��������������� ����������, ����������������
   ����������� ��������������� ���������� � �������~$j$.\cr
}}
%%348
\st[퀗������ ���������.] 󑒀������ $|A|[k]\asg |AA|[k]\asg |D|[k]\asg 0$
���~$2\le k \le T$; ���������� $|A|[1]\asg 0$, $|AA|[1]\asg 1$,
$|D|[1]\asg 1$; ����������~$|TAPE|[k]\asg k$ ���~$1\le k \le T$. 퀊����,
����������~$i\asg T-2$, $j\asg 1$, $k\asg 1$, $l\asg 0$, $m\asg 1$ �
������� � ����~\stp{5} (��� ������� �������� ����� �� �������� ������
������ ��������������� �� ���������� ����� � ��������������� ����������
����������� ����������).

\st[퀗��� ����� �������.] (� ������ ��� �������� ������ �������������.
� ��� ��� ��� ������� �������� ������, �� ���������� ������������� �
���������� ������.) 󂅋�����~$l$ ��~1. 󑒀������~$|A|[k]\asg |AA|[k]$
���~$1\le k \le T$, ����� ����������~$|AA|[T-k]\asg |AA|[T-k+1]+|A|[k]$
���~$k=1$, 2,~\dots, $T-1$ (� ����� �������). 󑒀������ $(|TAPE|[1],
|TAPE|[2],~\ldots, |TAPE|[T-1])\asg (|TAPE|[T-1],~\ldots, |TAPE|[2],
|TAPE|[1])$ � ����������~$|D|[k]\asg |AA|[k+1]$ ���~$1\le k < T$.
퀊����, ����������~$i\asg 1$.

\st[퀗��� ����������~$i$.] 󑒀������~$j\asg i$. (�������~$i$
�~$j$ ������������ "���~$(i,j)$" � �������, �������������� ����� 􅐃�����.)

\st[퀗��� ���~$(i, j)$.] 󑒀������~$k\asg j$ �~$m\asg
|A|[T-j-1]$. 呋�~$m=0$ �~$i=j$, �� ����������~$i\asg T-2$ �
��������� �~\stp{3}; ����~$m=0$ �~$i\ne j$, ��������� �~\stp{2}.
(�������~$m$ ������������ ����� ����� ��������, ������� ������
���� �������� �� �����~$|TAPE|[k]$; $m$~������ �����~0, ������ ����~$l=1$.)

\st[₅��� �� �����~$|TAPE|[k]$.] 瀏����� ���� ������� ��
����� �����~$|TAPE|[k]$ � ���������~$|D|[k]$ ��~1. 瀒��, ����
���� ��������, ���������� ��� ����� � ������� � ����~\stp{7}.

\st[��������.] 󌅍�����~$m$ ��~1. 呋�~$m>0$, ��������� � ����~\stp{5}.
 � ��������� ������ ���������~$k$ ��~1; ����~$k>0$, ����������~$m\asg
|A|[T-j-1]-|A|[T-j]$ � ��������� �~\stp{5}, ����~$m>0$. � ��������� ������
���������~$j$ ��~1;
����~$j>0$, ������� � ����~\stp{4}. � ��������� ������ ���������~$i$
��~1; ����~$i<T<1$, ��������� � ����~\stp{3}. � ��������� ������ �������
�~\stp{2}.

\st[������� � �������.] (� ����� ������� ��������� �������������
���������, � �������~|A|, |AA|, |D| �~|TAPE| ��������� ��������� ����
���� � ������ ������.) 󑒀������~$|M|[k]\asg|AA|[k+1]$ ���~$1\le k < T$ �
����������~$|FIRST|\asg 1$. (�������~|FIRST| ��������� ���������
�������� ������ �� ����� ������� ������� �������.)

\st[ꀑ���.] 呋�~$l=0$, ������������; ���������� ���������, �����
��������� ��~$|TAPE|[1]$. � ��������� ������ ���~$p=T-1$, $T-2$,~\dots, 1
(� ����� �������) ��������� $p\hbox{-�������}$ ������� �
����~$|TAPE|[1]$,~\dots, $|TAPE|[p]$ ��~$|TAPE|[p+1]$ ��������� �������:
%% 349

呋�~$p=1$, �� ������������ ����������� �������
������� ����������~$|TAPE|[2]$ � �������~$|TAPE|[1]\xchg |TAPE|[2]$. �
��������� ������, ����~$|FIRST|=1$ �~$|D|[p-1]=|M|[p-1]$, �� ������������
$p\hbox{-�������}$ �������, ������ ������� $|TAPE|[p]\xchg |TAPE|[p+1]$,
���������~$|TAPE|[p]$ � �����~$M[p-1]$ �� �������~$|D|[1]$,~\dots,
$|D|[p-1]$, $|M|[1]$,~\dots, $|M|[p-1]$. � ��������� ������
�������~$|M|[p-1]$ �� ����~$|M|[1]$,~\dots, $|M|[p-1]$. 瀒�� ����� ��
������ ������� � ������~$|TAPE|[j]$, �����, ���~$1\le j \le p$
�~$|D|[j]\le |M|[j]$; ������� ������� �� �������~$|D|[j]$, ������,
���~$1\le j \le p$ �~$|D|[j]>|M|[j]$, � ��������� �������� �������
��~$|TAPE|[p+1]$. ������� ������, ���� $|TAPE|[p]$ �� ������ ������.
瀒�� ����������~$|TAPE|[p]$ �~$|TAPE|[p+1]$.

\st[������� �� ���� �������.] 󌅍�����~$l$ ��~1,
����������~$|FIRST|\asg 0$, ����������
$(|TAPE|[1],~\ldots, |TAPE|[T])\asg (|TAPE|[T],~\ldots, |TAPE|[1])$. (�
����� ������� ���~|D| �~|M|---���� � �������� ���������.) ⅐������ �~\stp{8}.
\algend

����~C1--C6 ����� ��������� ��������� �������������, ����~C7--C9 ���������
�������; ��� ��� ����� ���������� ���������� ���� �� ������, � ����� ����
�� �������~$|M|[k]$ �~$|AA|[k+1]$ � ����� � ��� �� ������� ������.
\picture{���.~75. ꀑ������ ������� �� ����������� ��������������.}
\section *������ ���������� �������. ꀑ������ ������� ��������� �������
� ������� ������, ��� �����������. � ���� ������ �������� ���������,
��������� �������� ����� ������������� ������. 퀑��������� �����������
���������, �������������� ���������� �����������, ��������������
���������������� ��������� �������������, ������ ��� ������ ������, ���� �����
%%350
����� ��� ����� ��������� �������, ��������� �������---���� ������������! �
������� ����� ���� ���� �� ������ ��������, ������� ������ �������� ��
������ ��������� �����������.

䋟 �������� ���������� ������ ����� ����.  ���� ����� ���������
�������� �������, ������� ���������� �� ������ ������~$T$. 񎎒�������~(1)
�������� � ������ �������� �������:
$$
\eqalignter{
a_n &= a_n &=\perm{0}{0}a_n,\cr
b_n &= a_n-e_{n-1}=a_n-a_{n-2} &=\perm{1}{0}a_n-\perm{2}{2}a_{n-2},\cr
c_n &= b_n-d_{n-1}=b_n-a_{n-2}-b_{n-2} &=\perm{2}{0}a_n-\perm{3}{2}a_{n-2}+\perm{4}{4}a_{n-4},\cr
d_n &= c_n-c_{n-1}=c_n-a_{n-2}-b_{n-2}-c_{n-2} &=\perm{3}{0}a_n-\perm{4}{2}a_{n-2}+\perm{5}{4}a_{n-4}-\perm{6}{6}a_{n-6},\cr
e_n &= d_n-b_{n-1}=d_n-a_{n-2}-b_{n-2}-c_{n-2}-d_{n-2} &=\perm{4}{0}a_n-\perm{5}{2}a_{n-2}+\perm{6}{4}a_{n-4}-\perm{7}{6}a_{n-6}+\perm{8}{8}a_{n-8}.\cr
}
\eqno(4)
$$
������~$A(z)=\sum_{n\ge0} a_n z^n$,~\dots, $E(z)=\sum_{n\ge0}e_n z^n$ �
��������� ����������
$$
\eqalignno{
q_m(z)&=\perm{m}{0}-\perm{m+1}{2}z^2+\perm{m+2}{4}z^4-\cdots=\cr
      &=\sum_{k\ge 0}\perm{m+k}{2k}(-1)^k z^{2k}
        = \sum_{0\le k \le m}\perm{2m-k}{k}(-1)^{m-k} z^{2m-2k}. & (5)\cr
}
$$
���������~(4) ������ ����� ����������� ���,
���~$B(z)-q_1(z)\times A(z)$,~\dots, $E(z)-q_4(z)A(z)$ �������� �
�������� ������, ���������������
��������� ��������, � ������ ���������~$a_{-1}$, $a_{-2}$, $a_{-3}$,~\dots,
������� ���������� �~(4) (��� ���������~$n$), �� �� �~$A(z)$. �����
�������� ���������� ��������� �������, �������� ������������ �����������
� �������� ������� ��� ������������� ������� �� ������~$-8$:
\ctable{
\hfill$#$\bskip&&\hfill\bskip$#$\bskip\cr
\hfill n & \hfill a_n & \hfill b_n & \hfill c_n & \hfill d_n & \hfill e_n \cr
 0 &  1 &   0 &  0 &   0 &  0\cr
-1 &  0 &   0 &  0 &   0 &  1\cr
-2 &  1 &  -1 &  0 &   0 &  0\cr
-3 &  0 &   0 &  0 &  -1 &  2\cr
-4 &  2 &  -3 &  1 &   0 &  0\cr
-5 &  0 &   0 &  1 &  -4 &  5\cr
-6 &  5 &  -9 &  5 &  -1 &  0\cr
-7 &  0 &  -1 &  6 & -14 & 14\cr
-8 & 14 & -28 & 20 &  -7 &  1\cr
}
(䋟 ���� ���� ������� ���� �� �����������, ������ ������ � ���������~$n$
���� �� �������� ������ �� ���� �������.) 򀉍�
������������������~$a_0$, $a_{-2}$, $a_{-4},~\ldots=1, 1, 2, 5, 14,~\ldots$
��������� ������������ ������������ �� �����������, ��� ���
%%351
��� ������������������ ����������� � ����� � ����� ������� �������������
����������� (��������, � ���.~2.2.1-4 � �������~2.3.4.4-13)). 蒀�, ��
������������, ��� � ������ $T$~����
$$
\eqalignrem{
a_{-2n}&=\perm{2n}{n}{1\over n+1} & ��� $0\le n \le T-2$; \cr
a_{-2n-1}&=0 & ��� $0\le n \le T-3$.\cr
}
\eqno(6)
$$
����� ��������� ������������ ����� �������������, ���������� ��������,
���~(6) �~(4) �������� � ���������� ����������� ��� �������~0 �~1. 䋟
������~1 ��� ��������, � ��� ������~0 ��� ���� ���������, ���
$$
\perm{m}{0}a_0-\perm{m+1}{2}a_{-2}+\perm{m+2}{4}a_{-4}-\perm{m+3}{6}a_{-6}+\cdots
=\sum_{k\ge0}\perm{m+k}{2k}\perm{2k}{k}{(-1)^k\over k+1}
=\delta_{m0}
\eqno(7)
$$
���~$0\le m \le T-2$. � �������, ��� ����� ����� ��������� ������������
�������� (��� "������~2", ���� �� �������� �������� � ������ �.~4.2.6).

򅏅�� ����� ��������� ������������~$B(z)-q_1(z)A(z)$ �~�.~�. ����������,
��������, ����������� ���~$z^{2m}$ �~$D(z)-q_3(z)A(z)$. � �����
$$
\eqalign{
\sum_{k\ge0}\perm{3+m+k}{2m+2k}(-1)^{m+k}a_{-2k}
&=\sum_{k\ge0}\perm{3+m+k}{2m+2k}\perm{2k}{k}{(-1)^{m+k}\over k+1}=\cr
&=(-1)^m\left(\perm{2+m}{2m-1}-\perm{3+m}{2m}\right)=\cr
&=(-1)^{m+1}\perm{2+m}{2m}\cr
}
$$
�� ���������� "������~3" �~�.~1.2.6. 򀊈� �������, �� ������ �������
$$
\eqalign{
A(z) &=q_0(z)A(z);\cr
B(z) &=q_1(z)A(z)-q_0(z);\cr
C(z) &=q_2(z)A(z)-q_1(z);\cr
D(z) &=q_3(z)A(z)-q_2(z);\cr
E(z) &=q_4(z)A(z)-q_3(z).\cr
}
\eqno (8)
$$
ꐎ�� ����, �����~$e_{n+1}=a_n$; �������������, $zA(z)=E(z)$ �
$$
A(z)=q_3(z)/(q_4(z)-z).
\eqno (9)
$$

��������� ������� ���� �������� ��� ������ $q\hbox{-�����������}$,
������� �� ����� ����� �������~$q$. � ���� ��������� ������� ���.~1.2.9-15,
��� ��� ��� ���� ��������� � ���������
%%352
����, ������� ����� ���� �������� ���
$$
q_m(z)={((\sqrt{4-z^2}+iz)/2)^{2m+1}+((\sqrt{4-z^2}-iz)/2)^{2m+1}
\over \sqrt{4-z^2}}
\eqno(10) $$
⑅ ����������, ���� ������ ��������~$z=2 \sin\theta$:
$$
\eqalignno{
q_m(2\sin\theta)=&
{(\cos\theta+i\sin\theta)^{2m+1}+(\cos\theta-i\sin\theta)^{2m+1}\over 2\cos\theta}=\cr
&={\cos(2m+1)\theta\over \cos\theta}. & (11)\cr
}
$$
(��� ���������� ���������� ������, ��� ����������~$q_m(z)$ ������
�������� � ����������; � �������������, �������� � ���������������
�������, �����, ���~$q_m(z)$, �� ��������, ��������� �������� ������� ����,
 � ������~$(-1)^m U_{2m}(z/2)$ � ������� ������������.)

򅏅�� ����� ���������� ����� ����������� �~(9):
$q_4(2\sin\theta)=2\sin\theta$ �������� �
$$
\cos 9\theta = 2 \sin \theta \cos \theta = \sin 2\theta.
$$
������� ����� ����������� ��������, ����
������~$\pm9\theta=2\theta+\left(2n-{1\over2}\right)\pi$; ���
�����~$\theta$ ���� ����� ����������� �~(9) ��� �������,
���~$\cos\theta\ne 0$. (呋�~$\cos\theta=0$, ��~$q_m(\pm2)=\pm(2m+1)$,
������� �� �����~$\pm2$.) 񋅄���������, �������� 8~��������� ������:
$$
\displaylines{
q_4(z)-z=0 \qquad \hbox{ ��� }  z=2\sin{-5\over 14}\pi,\quad
2\sin{-1 \over 14}\pi,\quad 2\sin{3 \over 14}\pi, \cr
2\sin{-7 \over 22}\pi,\quad 2\sin{-3 \over 22}\pi,\quad
2\sin{1 \over 22}\pi, \quad 2\sin{5 \over 22}\pi,\quad 2\sin{9 \over 22}\pi.\cr
}
$$
� ���~$q_4(z)$---��������� �������~8, �� ���� ��� �����. ��� ��� ��
���� �������� ����~$q_3(z)=0$, ��� ���~$q_3(z)$ �~$q_4(z)-z$  ����� �����
��������� ��������� ������� �������. ������ ���� ������ ���������
��������������� ���������� �������������~$A(z)$, ���� ���������~(9) �
������������ �����.

���� � ������������ ������ ������ $T$~����,
�������~$\theta_k=(4k+1)\pi/(4T-2)$. ��������� �������~$A(z)$ ���
$T\hbox{-���������}$ ��������� ����� ��������� ���
$$
{4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}{\cos^2\theta_k\over 1-z/(2\sin\theta_k)}
\eqno(12)
$$
(��.~���.~8); �������������,
$$
a_n={4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}\cos^2\theta_k \left({1\over 2\sin\theta_k}\right)^n.
\eqno(13)
$$
%% 353
񎎒�������~(8) �������� ������ � ����������� ��������:
$$
\eqalign{
b_n&={4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}\cos\theta_k\cos3\theta_k\left({1\over 2\sin\theta_k}\right)^n;\cr
c_n&={4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}\cos\theta_k\cos5\theta_k\left({1\over 2\sin\theta_k}\right)^n;\cr
d_n&={4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}\cos\theta_k\cos7\theta_k\left({1\over 2\sin\theta_k}\right)^n\cr
}
\eqno(14)
$$
�~�.~�. � ���.~9 ��������, ��� ��� ��������� ����������� ��� ����~$n\ge0$,
� �� ������ ��� �������~$n$. � ������ ����� ���� �~$k=0$ �����������
����������� ��� ���������, �������� ����~$n$ ���������� ������;
�������������, "��������� �����" ����
$$
{1\over 2\sin\theta_0}={2\over\pi}T-{1\over\pi}+{\pi\over 48T}+O(T^{-2}).
\eqno(15)
$$

ꀑ������ ���������� ������� ���� ����������� �.~�.~ꀐ�����
[Proc.\ IFIP Congress (1962), 62--66], ������� ������� ��������� ����������
��� ��������� ��������~$T$, � 䝂���� 􅐃������
[{\sl CACM,\/} {\bf 7} (1964), 297], ������� ������ ������ ��� ����� �
��������������� ���������~(15)  ��������� �����.
녒�� 1964~�.\ �.~�.~􋎉� ������� ����� ���~$1/(2\sin\theta_0)$
��� ��������� �����, ��� ��� ������ �������
����� ���� ������������ ��� ����~$T$. ㋓����� ������ ��������� ����� ���
���������� �������� �.~�.~𝉍�
[{\sl Canadian J.~Math.,\/} {\bf 18} (1966), 332--349],
������� ��������� �� ��� ���������� ������ �����,
�� ���� ���� � �����������. 𝉍� �������� �������� � �����������
(���.~73) � ����� ����� ������ ���������� ������� ���� �����. 􋎉�
�~𝉍� � ����� ��������������� ����������� � ��������� (��.~���.~6).

\section 쎄�������� ��������� ����������. 呋� ��������� ��� ���� �����,
�� ����� ��� ����� ��������� � ������� ��������� ���������� �����
����������. 퀏�����, �� ����� �������~T1--T5 ��~T7, �����~T1--T4 ��~T6,
�����~T1--T3 ��~T5 (������� � ����� ������� ��� ����������), �����~T1--T2
��~T4 � ������ ��������� ������, ����� ��~T4 ����� ����������
������������ ������� ������. ������������� ����� �������� �����
����������� �� ��������� ����������� ���� ������� ����������
������ (���������� ����������� ��.~�~�.~5.4.6).

񕅌� "�������������� �������", ������� �������� ����������� � ���������
����� ��� ������� ������, ���� ���������� �.~�.~ꍓ��� � [{\sl CACM,\/}
{\bf 6} (1963), 585--587]. ꀆ��� ���� ������� ��~$(T-1)\hbox{-��������}$,
$(T-2)\hbox{-��������}$,~\dots, $P\hbox{-��������}$ �������, ��� $P$---�����
������������� ����� �����~1 �~$T-1$. 呋�~$P=T-1$, �� ���---�����������
�����; ����~$P=1$, ���---������
%%354
��������� �����; ����~$P=2$, ���---��������� ����� ��� ���
�����������. ������ ����� ����� ��� �������� �.~�����
[{\sl IBM Systems J.,\/} {\bf 5} (1966), 226--247] �~�.~�.~ᓐ���
[Proc. IFIP Congress, {\bf 1} (1971), 454---459]. ᓐ� �����
������������ �������~$\sum T_n(x) z^n$ ���
�������~$(P, T)\hbox{-��������������}$ �������,
���������� �����������~(5.4.2-16); ��
�������, ��� ��������� ��������~$P$ (� ����� ������ ����������� �����
�������������� ��������� ��������), ��� ������� ��~$S$
���~$S\to\infty$ (���� ��������������� ������������ ����� �������������
� ���������� �������� ���������), ���� ��������������
$(2, 3, 3, 4, 4, 4, 3, 3, 4)$ ���~$T=(3, 4, 5, 6, 7, 8, 9, 10, 11)$.
��� ��������~$P$ �
������~$T$ ������� ����������� � ������� ����������, � �� ������������
������, � �����������, ��� ������������� ������� ������� �� ������
����������� ����� ����������. � ������ �������, ��� ����������� ������
������� � ������������� ��������� ��������, ��� ������� � �.~5.4.2, ������
����������� ����� ������� ��������� ����� ���� ������������� �������.
� ���������, ����������� ������������� ������������ ������ �����������.

�.~�.~鎍��� [{\sl BIT,\/} {\bf 6} (1966), 129--143] ����������
��������� ����������������� � ������������ �������; �����������
����������������� ������� � ����������� ��������� ���� ����������
�.~㎒��� [Digital Computer User's Handbook, ed.~by.~M.~Klerer
and~G.~A.~Korn (New York: McGraw-Hill, 1967), 1.311--1.312]; �����
����������� ���� � ������ ������ ��������� �����.

\excercises
\ex[10] 葏������ ����.~1, �������� ��������� ������� � ���������
� �.~5.4.2 ������� ������������ ������� � "������������ ����". ꀊ��
����� �����? (␅����� ��������� ����������.)

\rex[22] 񐀂���� ��������� ���������� � ����� �������,
������������ ��������~C, � ����������� ���������� � ����� �������,
������������ ��������~5.4.2D ꀊ�� �������� � �������� �� �a�e���e?

\ex[20] 񎑒����� �������, ������������, ��� ���������� ��� ���������� ��
����� ������ 100~��������� �������� ��� ������ ���������~C.

\ex[�20] (�.~�.~𝉍�.) "ꀑ������ ������������� $n\hbox{-��}$ ������"
���� ���������������, ������������ ��������� ������� (� ������ ����� ����):
$\set{1, 0, 0, 0, 0}$ ���� ��������� ������������� �������� ������;
����~$\set{a, b, c, d, e}$---��������� ������������� $n\hbox{-��}$~������,
��~$\set{a+b+c+d+e, a+b+c+d, a+b+c, a+b, a}$ ����� ���������
�������������� $(n+1)\hbox{-��}$ ������ (� ��� ��������������� ��
�����������, �� �� ������������� ������������� $n\hbox{-��}$~������ �����
���������� ��~5 ��������� ������������� $(n+1)\hbox{-��}$~������.)
(a)~䎊�����, ��� \emph{�����}
���������������~$\set{a, b, c, d, e}$ �� ������� ������� ����� ��������
��������� �������������� $n\hbox{-��}$~������ ��� ���������~$n$.
(b)~䎊�����, ��� �������������, ������������ � ��������� ����������,
\emph{����������} � ��� ������, ��� ����~$\set{a, b, c, d, e}$---�����
������������� $n\hbox{-��}$~������, ������~$a\ge b \ge c \ge d \ge e$, ��
����� �����~$a\le a_n$, $b\le b_n$, $c\le c_n$, $d\le d_n$, $e\le e_n$,
���~$\set{a_n, b_n, c_n, d_n, e_n}$---�������������, ������������ �~(1).

\rex[20] 䎊�����, ��� ��������� �����, ������������ �~(1), �������������
%%355
������
$$
a_k a_{n-k}+b_k b_{n-k}+c_k c_{n-k}+d_k d_{n-k}+e_k e_{n-k}=a_n
\rem{���~$ 0\le k \le n$.}
$$
[\emph{󊀇����:} ��� ������� ��������� ����� ����������� �����������,
������� �������� ��������� ����� ��������� � ������� $k\hbox{-��}$~�������
������ ��������� ����������.]

\ex[�20] 퀉���� $5\times5$-�������~$Q$, �����, ��� ������ ������~$Q^n$
�������� ��������� ����� ��� ����� ����~$a_n b_n c_n d_n e_n$ ���
����~$n\ge 0$.

\ex[�20]  ������� ��� ��������� ������� ����������� �
������� ������������� $a_n$~��������� ��������, ������� ������� ���
�������� ������������� ������, ����� ����������� ����������� �������.

\ex[��23] ⛂����� �������~(12).

\ex[��26] ⛂����� �������~(14).

\rex[�28] ⌅��� �������~(4) ��� �������� ��������� ����� ��������������
� �������� �������� �����������
$$
\eqalignter{
e_n&=a_{n-1}  &= \perm{1}{1}a_{n-1};\cr
d_n&=2a_{n-1}-e_{n-2} &=\perm{2}{1}a_{n-1}-\perm{3}{3}a_{n-3};\cr
c_n&=3a_{n-1}-d_{n-2}-2e_{n-2} &=\perm{3}{1}a_{n-1}-\perm{4}{3}a_{n-3}+\perm{5}{5}a_{n-5}\cr
}
$$
�~�.~�. ����
$$
r_m(z)=\perm{m}{1}z-\perm{m+1}{3}z^3+\perm{m+2}{5}z^5-\ldots,
$$
��������~$A(z)$, $B(z)$ �~�.~�.\ ����� ��� $r\hbox{-����������}$.

\ex[�38] ��
$$
f_m(z)=\sum_{0\le k \le m} \perm{\floor{(m+k)/2}}{k}(-1)^{\ceil{k/2}}z^k.
$$
䎊�����, ��� ������������ �������~$A(z)$ ��� $T\hbox{-���������}$
��������� ����� �����~$f_{T-3}(z)/f_{T-1}(z)$, ������ ��������� �
����������� ����� ��������� �� ����� ����� ���������.

\ex[�40] 䎊�����, ��� ����� ������������� 􅐃����� ���������� � ���
������, ��� ��� ����� ������ ������ ���������� ��������� ��������,
���������������~(2), �� ����� ������� ������� ����� ��������������
�� ������ ��������� ��������, \emph{��� �������} ��� �� ����� �����
������� ������������ ��������� �����~C7--C9.

\ex[40] � ������ ������������ ������� ����� ������� ��������� ���������
����� ���������� �������������� �����. ������������ ��� ����. (퀏�����,
�����, ���������� � ������, �������� �������� ��������� �����~T4;
�� ����� �� ����� ���������~T4 �� ������ ���� ������� ���������� �������?)

\subsubchap{������ ����� � �������� �����������} %% 5.4.4
썎��� �������������� ���������� ��������� ������ ����� � �����������,
��������������� ����, � ������� ��� ������ �� ���. 񕅌� �������, �
�������� �� ����������� �� ��� ���, ������ ���������� ���������� �� �����
� ������ �����������,
%%  356
����� ������������ �����, ������ �� � ������ ����������� � �����
������������. (􀉋� �� �����, �������������, ����� ���� ��� �������
"������ ����������---������ �����������".) ����� ������ ���������
�������� ��� ����� �������� ���������:
�� ���������� �� ����� � ������ ����������� � ������ �� � ��������. (�
���� ������ ����� ����� ���� ��� �����, ��������� ����� ��������� �������
"��������� ����������---������ �����������".)

񕅌� �����������������, ������������ � ���������� ������� �����
������������ ��� ��������� ������. ����� ������� ������� � ���, ���
\emph{������� �������� ������� ��������,} ���� �� ������ � ������
����������� � ���������� � ��������. 呋� ��� ������� ��������� �� ����� �
������������ �������, �� �� ����� �����, ����� � �������� �����������, ��
��� ���� ������� ������ ���������. ������� ����� �����
��������� ������� ������ ������������� �� ��������� �������; ����� �������,
 �������� ������� ������ ����� �������� � ��������� ����� �����������.
���������, ������� �������������� � �������� �������, ����� ����������,
��� �� ����� �� ������!

� �������� ������� ��������� ������ ���������� ������� ������� 8~���������
�������� � �������������� \emph{�����������������} ������� �� 4~������.
쎆�� ��������� ������� �������� ���� ��������:
\ctable{
# \hfil & \bskip\hfil$#$\hfil\bskip & \bskip\hfil$#$\hfil\bskip &
\bskip\hfil$#$\hfil\bskip & \bskip\hfil$#$\hfil\bskip & # \hfil \cr
 & T1 & T2 & T3 & T4 \cr
���~1. &  A_1 A_1 A_1 A_1 &  A_1 A_1 A_1 A_1  & -       & -       & 퀗������ ������������� \cr
���~2. &  -               & -                 & D_2 D_2 & D_2 D_2 & 񋈟��� ��~$T3$ �~$T4$\cr
���~3. &  A_4             & A_4               & -       & -       & 񋈟��� ��~$T1$ �~$T2$\cr
���~4. &  -               & -                 & D_8     & -       & ���������� ������� ��~$T3$\cr
}
焅�� $A_r$~���������� �������, ������� ������������� �����~$r$ �
������������� � ������������ �������, ���� ����� �������� � ������
�����������, ��� � ���������� ����� ��������; $D_r$---�����������
����������� ��� ���������� ������� �����~$r$. � ����� 2-��~�������
������������ ������� ���������� ����������: ��� ����������� ����������
��� �����, ��� ��� �� ������ � �������� �����������.  ����� ��������
���������� �� 3-�~�������.

瀌����, ��� ��������� ������� ����������� ����������� �� �����~$T3$ �
\emph{���������} �������. 呋� ��� ����� (��� ������� �� ����, ������ ��
��������� �������� � �������� �����������, ��� �� �����, ���������� ���,
������ ���� ����� � �������� ��� �������� �������������), �� �����
����������� ��� �� ������ �����, ������� �����������. ᎋ�� �������
�������� ���� ��
%%357
���������~$T1$ �~$T2$ ����� 3-��~�������, ��� ���� �� ����� 4-��~�������
����������~$A_8$. 噅 ������� ���� �� ������ � ������ \emph{���������}
�������� �� 1-�~�������, ��� ��� ��� �������� ������� ���~$A$ �~$D$.
��� ��� ����������������� ������� 16~��������� �������� �������������
��, ����� ��������� ������� ���� �������������, � ��� ��� �� ������ ��
����� �������, ������� ��������� �������� ����� ����������, �� ����������
 ������� ���� ���������� �����������. 񋅄���������, ���� ��������� �����
3-��~�������, ��������, ���������.

\emph{ꀑ������} ������� ������������� ����� �� ��������. ����������,
��������, ���������� 14~��������� �������� �� ������� ������:
\ctable{
# \hfil & \bskip\hfil$#$\hfil\bskip & \bskip\hfil$#$\hfil\bskip &
\bskip\hfil$#$\hfil\bskip & \bskip\hfil$#$\hfil\bskip & # \hfil \cr
 & T1 & T2 & T3 & T4 \cr
���~1. & A_1 A_1 A_1 A_1 A_1 A_1 & A_1 A_1 A_1 A_1 A_1 &  A_1 A_1 A_1 & - \cr
���~2. & -                       & D_1                 &  D_2 D_2     & D_3 D_3 D_3 \cr
���~3. & A_6                     & A_5                 &  A_3         & - \cr
���~4. & -                       & -                   &  -           & D_{14} \cr
\noalign{\noindent
񍎂� ������~$D_{14}$ ����� ��������~$A_{14}$, ���� ����������~$T1$, $T2$,
$T3$ ��������������� ����� ��������� ��������. 瀌����, ��� ��� "������"
��������� ������� � ��� ������, ��� ��� ����������� ������� ���������
����� �������. 呋� �� �� ��������� �������� �����������, ��� �
���������~5.4.3D, �� ����� 2-��~������� ����������� �� � ���������
}
& A_1  & - & D_2D_2 & D_3D_3D_3 \cr
}
� ���� �� ���������� ���������� ������, ��������� ����������� �������, ���
��� �� �� ����� ������� ������� ��������������� �����������! 쎆�� ����
�� �������� �������� �����������~$T1$ ��~$T2$, ���� ����������~$T1$ �
������ ������ �� � ������ ����������� �� ����� ��������� ���� ������� (�
�� ����� ���~$T3$ �~$T4$ �������� � �������� �����������). � �����
�������� �� ����� ����������~$T1$ ����� �������, ��� ��� ����
����� �������� ���� ����������� �� ��� ���������.

򀊈� �������, ����� ������������� ���������~5.4.3C �������� ���
��������� ������ �� ����� ����������, ��� ��� ������� ������; ���������
������� ����� ���������� ������ ���, ����� ����� ��������� ��������
�������� ����� "������" ��������� �������������. ����� �������� �����
������� ������ ����� ������� ���������� ���������������, �����
������������ ���� ����� ������������� (��.~���.~17).

\section ����� ������ � ����������� �������. � ������ ������ (�
���� �� ������ � ������!) ����� ������������ ������� ������� ����������
������������ ��� ��������� ������. ��������, ��������, ��� �������
13~��������� �������� � ��� �����.
%%358
\ctable{
# \hfil &  \bskip\hfil$#$\hfil\bskip & \bskip\hfil$#$\hfil\bskip &
\bskip\hfil$#$\hfil\bskip \cr
       & T1                  & T2                              & T3 \cr
􀇀~1.& A_1 A_1 A_1 A_1 A_1 & A_1 A_1 A_1 A_1 A_1 A_1 A_1 A_1 & - \cr
􀇀~2.& -                   & A_1 A_1 A_1                     & D_2 D_2 D_2 D_2 D_2\cr
}
焅�� �� ������ � �����; ����� ���� �� ����������~$T2$ ���~$T3$ � �����
������ �� � ������ �����������, � �� ����� ��� ��������� �����---�
��������. � ��� ������ �������� �� ����, � ������ �� ��������� ������
���� �� ������������ ����.

������� ����, ��������� ���������, ������� � ���,
����� \emph{���������� ����������� �������� �� ������ �����.} 򎃄�
������� ����� ����������� ������ ������������:
\ctable{
# \hfil &  \bskip\hfil$#$\hfil\bskip & \bskip\hfil$#$\hfil\bskip & \bskip\hfil$#$\hfil\bskip \cr
􀇀~1. & A_1 D_1 A_1 D_1 A_1 & D_1 A_1 D_1 A_1 D_1 A_1 D_1 A_1 & - \cr
􀇀~2. & -                   & D_1 A_1 D_1                     & D_2 A_2 D_2 A_2 D_2 \cr
􀇀~3. & A_3 D_3 A_3         & -                               & D_2 A_2 \cr
􀇀~4. & A_3                 & D_5 A_5                         & - \cr
􀇀~5. & -                   & D_5                             & D_8 \cr
􀇀~6. & A_{13}              & -                               & - \cr
}
���� ������� ��� ������ �������� �.~�.~㈋������ � ��� ������ ������ �
����������� �������, ����� ����� �� ������ ���
�~{\sl CACM,\/} {\bf 6} (1963), 220--223.

���� $ADA\hbox{-�����}$ ����� �������� ��� ������������ ������� �
\emph{�����} ������ ����; ����� ��������, ���~$A$ �~$D$
����������� ��������������� ������� �� ������ ����, ��� ��� ������
�������, ��� ������ ���������� ������������� ��������� ������������
�������~$A$ �~$D$ �� ������ ����� � ��� ������ ����� ���������
��������~$A$ (��� ������ ����� ��������� ��������~$D$). � ��� ���������
�������, ������������ � ���� ������ �� ����� ����� ����, ����� �����������,
 ��������������� ����������� ���������� ��������������� ������� �� �����
�����, �� ��������� ���� ������ ������� ���� ������� � ����������
�����������. 䀋��, �� ������ � ���.~5.4.2-13, ��� ����������� ������
������������� ������������� ������� \emph{���������} ����� �������� ��
����� ����� (������������� �������� �����) � ������� ����� �������� ��
���� ��������� ������. 呋�~$T1$ ������������� ��� ��������� ������, ��
�� �����, �������������, �������������, ��� ��� ����� ����� ���������
��������~$A$, ���� �����~$T1$ ������ �~$A$, � ��� ��������� �����---�~$D$.
쎆�� ������������ ����� �������������, ����������� ���������~5.4.2D,
������� ��� ����� �������, ����� ������������� �� ������ ������ ����� �
�������� �������� �����~$T1$.
(� ���������� ������~$1$, $T+1$, $2T+1$,~\dots, ��� ��� ��� �� ������,
�� ������� �������� �������� ������ �������� ������������� ������ �����.)
퀏�����, � ������ ����� ���� ����� ������������
%% 358
������~(5.4.2-1) ��������� ������������� ��������:
$$
\vcenter{\halign{
\hfil$#$\hfil&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\hfil$#$\hfil\cr
& & & & & & & \hbox{����������} \cr
\hbox{󐎂���} &  T1 & T2 & T3 & T4 & T5 & \hbox{񓌌�} & \hbox{����� �� �����}\cr
0 &  1 &   0 &   0 &   0 &  0 &   1 & T1 \cr
2 &  1 &   2 &   2 &   2 &  2 &   9 & T1 \cr
3 &  3 &   4 &   4 &   4 &  2 &  17 & T1 \cr
4 &  7 &   8 &   8 &   6 &  4 &  33 & T1 \cr
5 & 15 &  16 &  14 &  12 &  8 &  65 & T1 \cr
6 & 31 &  30 &  28 &  24 & 16 & 129 & T1 \cr
8 & 61 & 120 & 116 & 108 & 92 & 497 & T1 \cr
}}
\eqno(1)
$$
򀊈� �������, ��~$T1$ ������ ���������� �������� ����� ��������, �����
��� �� ����� �~$T2$ ��~$T5$---������ ����� (� ��������� ������� ���
��������� ���������� ��������� ��������). 򀊎� ������������� ����� ��
������������, ��� �������� �������� ����� �������� ������� ���������� ��
����� ��������� ��������, ������� �������� ������������. ��������
(��.~���.~3), ��� ���� ������������ ��� �����, �� ��������� ������ �����
��~$T1$ � ������������ �������.

䐓��� ������ ����������� ������������� ��� ����������� ����� � ��������
������� ��� ��������� �.~�.~㓄����� �~�.~�.~⅍���
[{\sl CACM,\/} {\bf 7} (1964), 315]. � ����� ������������ �������, ����� ���
� ���������~5.4.2D, ������� � $D\hbox{-�������}$ �� ������ �����. ꎃ�� ����
��������, �� ������������ ���� ��������� $A\hbox{-�������}$
������������� � ������ ������������ "��������" �����, ���� ������ ��
���������� ������������� �� ����� ��������� �������. ������ ���������
������� �� ������������ ���� �������������� � ����� ���� ���
���������������� � ���� � ��������. ⎏��� �� ����������� ����������
��������� �������� ������������� ���� � ���.~5.

\section �������� ����� �������. � ��� ��� �� ��������� ���������
����� ������� � �������, �� ������� ����� �����, "��������� �� ���������".
�������� ����������� ����� ������� �������� ������� � ������ �������
������, ��� �������������� ������� ��������� � ������� ������� � ������
��������� �������. � ������ �������, ���� �������
�������������� ����������� ��������� ������ � ������ ������, ��, ��
��������, ��� ��������� ����������� � ����������� ���������
���� �������� ������� �������������� ����������� ������ �������.
������~�.~ꀐ� ��������� ��������� ���������� �������� � ���� ������, �
�� ��������� ���� ����� ����������� �������� �� ������.

�-������, ��� ��������� ����� ������� ������ �������� ���� ������� ������
�������� ������������ ������ "����������� ����", ������� ��������������
����. ꀐ� ��������� ���
%%360
����� �������---\emph{��������� ������������� ����� �������} �
\emph{������������� � ���� ������.}  ������������� ������� �� ��������,
 � �� ������ �� �� �������.

⅊������ ������������� ����� ������� ������� �� ������������������
"�������� �������" $y^m\ldots{}y^1 y^0$, ������ �� ������� �����
$T$~���������; $y^{(i)}$ ��������� ������� ���������� $i\hbox{-�}$ � �����
��� �������:
$$
y^{(i)}_j=\cases{
          +1, & ���� ����� � �������~$j$ �������� ������� ��� ������� �������; \cr
\phantom{-}0, & ���� ����� � �������~$j$ �� ������������ � ������ �������;\cr
          -1, & ���� �� ����� � �������~$j$ ��������� ��������� ������� �������.\cr
}
\eqno(2)
$$
򀊈� �������, ����� ���� ����������~$y^{(i)}$ �����~$-1$,
��������� ���������� �����~0 �~1. 蒎����� ������~$y^{(0)}$ ������; ���
��������� ������, �������~1 � �������~$j$, ����
������������� ��������������� ��������� ����������� �� ����������~$j$, �~0
� ��������� ������. � ����� ����������� �������, ��� ��������� �����
$$
v^{(i)}=y^{(i)}+y^{(i-1)}+\cdots+y^{(0)}
\eqno(3)
$$
������������ ����� ������������� �������� �� ������ ���������������
����� $i\hbox{-�}$ � ����� ����� �������, ������ �� �����~$j$ ���������
$v^{(i)}_j$~��������. � ���������, ��~$v^{(m)}$ ����� ������, �������
�������� �������� �� ������ ����� ��������� ������ �������������.

� ����� �������, ��������� ����� � ���� ������ � ��������� �����,
����� ��������� ��������� �������������:
{\def\!{\phantom{+}}\def\y#1{y^{(#1)}}\ctable{
$#$&$\hbox{}# \quad$ & $#$&$\hbox{}#\quad $ & $#$&$\hbox{}#$ \cr
\omit \hfil 񁀋������������ \hfil \span & \omit \hfil  ꀑ������  \hfil \span & \omit \hfil 썎�������� \hfil \span \cr
\omit \hfil ($T=4$, $S=8$)  \hfil \span & \omit \hfil  ($T=4$, $S=14$) \hfil \span & \omit \hfil  ($T=3$, $S=13$) \hfil\span\cr
v^{(7)} &=(\!4,\!4,\!0,\!0) & v^{(10)} &= (\!6,\!5,\!3,\!0) & v^{(12)} &=(\!5,\!8,\!0)\cr
\y{7} &= (+1, +1, -1,\!0) & \y{10}&= (+1, +1, +1, -1) & \y{12} &= ( +1, +1, -1)\cr
\y{6} &= (+1, +1,\!0, -1) & \y{9} &= (+1, +1, +1, -1) & \y{11} &= (+1, +1, -1)\cr
\y{5} &= (+1, +1, -1,\!0) & \y{8} &= (+1, +1, +1, -1) & \y{10} &=(+1, +1, -1)\cr
\y{4} &= (+1, +1,\!0, -1) & \y{7} &= (+1, +1, -1,\!0) & \y{9} &= (+1, +1, -1)\cr
\y{3} &= (-1,\!0, +1, +1) & \y{6} &= (+1, +1, -1,\!0) & \y{8} &= (+1, +1, -1)\cr
\y{2} &=(\!0, -1, +1, +1) & \y{5} &= (+1, -1,\!0,\!0) & \y{7} &= (-1, +1, +1)\cr
\y{1} &= (+1, +1, -1,\!0) & \y{4} &= (-1, +1, +1, +1) & \y{6} &= (-1, +1, +1)\cr
\y{0} &=(\!0,\!0,\!1,\!0) & \y{3} &=(\!0, -1, +1, +1) & \y{5} &= (-1, +1, +1)\cr
            \omit & \omit & \y{2} &=(\!0,\!0, -1, +1) & \y{4} &= (+1, -1, +1)\cr
            \omit & \omit & \y{1} &= (+1, +1, +1, -1) & \y{3} &= (+1, -1, +1)\cr
            \omit & \omit & \y{0} &=(\!0,\!0,\!0,\!1) & \y{2} &= (+1, +1, -1)\cr
                        \omit & \omit & \omit & \omit & \y{1} &= (-1, +1, +1)\cr
                        \omit & \omit & \omit & \omit & \y{0} &= (\!1,\!0,\!0)\cr
}}
%%361
쎆�� ���������� ��������� ���������� ��� ������� � ����� ���, �����
$y^{(m)}$~��������� ������, � $y^{(0)}$---���������, �� ��� ������ �����
������ ����������� ���������������� ��� ���������� ������. 䋟 ������
������������ ������ ������� ������ � ���������������� ������ � �����������
����, ��� ��� ����� "�������" �� ��������� �����, ����� "�������" ��
�~�.~�., ������������ ���������������� �������������~$v^{(0)}$,
$v^{(1)}$, $v^{(2)}$,~\dots � �������, �������� ����, � ������� ��� �
���������������� ���������� � �������� ����������. 􀊒������ ������ ����
������ ��� ��� ����������� ���� ��� ������� ������������ � ���������� �������.

ꀆ��� ����� �������, ��������, ����� ��������� �������������. � �������,
��� ����� ������, ������������������
��������~$y^{(m)}\ldots{}y^{(1)}y^{(0)}$ ������������� �������� �����
������� ����� � ������ �����, ����� ����������� ��������� ��� �������:

{\medskip\narrower
\item{i)}~������~$y^{(0)}$ �������� ���������;

\item{ii)}~����� ���� ���������� �������~$y^{(i)}$ �����~$-1$, ���
��������� ���������� �����~$0$ ���~$+1$, $m\ge i \ge 1$;

\item{iii)}~��� ���������� �������~$y^{(i)}+\ldots+y^{(1)}+y^{(0)}$
��������������, $m\ge i \ge 1$.
\medskip
}

���������� ����� ������� � ���� ������ ���� ������ ����������� ��� ��
����������. � ������ ������ � ����� ������� "��������" ����� ��� �������
���������� ������� � � ����� ���������� ����� ��� ������� �������,
����������� � ���������� �������, ����� �������, ��� ���������
������ ����������� ���� �������� �������, �� ������� �� ��� �����������.
ꀆ��� ���������� ���� ���������� ������� ����, �� ������� ��� ���������
��������������� �������, ��� ���� ���� ���������� � �������� �������, ���
� ��������� �������������;
����� ����, ����� ��������������� ��� ������ ����� ���������� ������
�����, �� ������� ����������� ���� �������. 퀏�����, ��� ����������� ����
����� ����� ������������� � ���� ������, ������������ �� ���.~76, ���� ��
������� �����~$A$, $B$, $C$, $D$, � ��~$T1$, $T2$, $T3$, $T4$.

��� ������� � ��������� ������������� ������ ������������ ������� �����
�������; ��������, ���� ������� �� ������~$0$ ������ (������) ������ ����
������������, �� ������� �� ������~$1$ ������ ���� ����������, ������� ��
������~$2$---������������� �~�.~�.; ��������� ��������� �������
�������� ������������ ����� � ������ �����, ����� ��������������� �������
���� ��������� �� ������ � ������ �������. 䀋��, ��������� ����������
��������� ��������, �������������� ��� ������� (�� ������� ���������
�������������), � �������� ����� \emph{����� �������� ����} ������, ���
��� ������ ��������� ������� �� ������~$k$ �������������� ����� $k$~���.

%%362
\picture{���.~76. ���������� ���� ���� ������� � ���� ������.}

랁�� ����� ������� ����� ������������� � ���� ������, �� �� ������ ������
���������� ����� �������. 䅐���, ���������� ���� �������� ��������
������� ��~$1$ ��~$m$ � ����� �������� �������� ������� ����, ����������
���������� ����� ������� � �������� ������� ����� � ������ �����, �����

a)~������� ��� �����, ������� � ����� ���������� �����, �� �����
����������� ����� �����;

b)~����~$i>j$ � ���� $A$~���� ��� �����, �� ������ �� �������� ������������
\picture{p.362}
%%363

c)~����~$i<j<k<l$ � ����~$A$---��� �����, �� ������ �� �������� ����� ���:
\picture{p.363.1}
󑋎���~(a) ��������, ��� ��� ������� � �������� ����� ������� ������
���� ��������; �������~(b) ����� ��������. 󑋎��� "�������������"~(c)
�������� ����������� ��� �������� ��������� ������ ����� �����������
"��������� ���������� --- ������ �����������". ����, ������������ ��
����~$k$, ������ ���� ������ ������ �������, ��������������� �����
�� ��� �� �����; �������������, ������������~(4) ����������. 텒�����
���������, ��� ����� ���������� ������, ��������������� ��������~(a),
(b), (c), ������������� ������������� ��������� ����� ������� � ��������
�������.

呋� ������� $T$~��������� ���������, �� �� �������~(a) �������, ���
������� ������� ����������� ���� �����~$T-1$ ��� ������. ���������
���������� ����� ���� ����� �������� �� ������ ��������; ��������,
����~$T=3$, �� �� ���������� ����� ������� � ������� ����
\picture{p.363.2}
򀊀� ����� ������ ������� �� � ����������� ����� �������, ���� �� ��
������ ��������������� ������� ��������� ������ ����� � ������ ����,
��������� ��� ������������ ������ � ����������� ������ �������� ����
����� ��������, ������� ������ ������� ����. � � ���� ��������� ����
��������� �������, �� ��������, ������ ���� ������ �������� ��, ��������
�������~(a) �~(b):
\picture{p.363.3}
%%364
��� ��� ���� ���������� �������~(c). 䅐���, ������� ����� ����
�������� � ������������ � ����������� ��������� � ��������������~$T$ ���
������ ���� ����, ���������� $T\hbox{-lifo}$\note{1}%
{"Lifo"---������������ ��� "last in---first out" (��������� ����������---
������ �����������).---{\it �. �����.\/}} �������.

䐓��� ������ ��������������� ��� ���������� �������, ������� �����
���������� �� ����� �������, ������� � ���, ����� �����������, ��� ���
�������� ������� ����� ���� "��������". 퀗��� � ���������� ����� �����,
������~$A$, � � ������ ������
\picture{p.364.1}
���~$i$ ����� ������ ������� � ������ ��������� ���� ����~$B$, $B_1$,
$B_2$,~\dots, $B_k$ � ������ \emph{����� ����� �������������} ����,
 ����������������~$B$,
\picture{p.364.2}
��� ������� "��������� ���������---������ ������" � �������� ���������
������ ���������� ������������� � ���� ������ ��������������� ��
���������� �������������.

�������� ������ ����������� $T\hbox{-���������}$ ����� �������,
�.~�.~������, �������� ����������� ����� ���� �����
���� $T\hbox{-lifo}$~�������� � ������ ������ ������� �����, �������
������  ������� �������. 񋅄����� ����������� �����, ��������,
����������� ��������� �������� ����� ���� ��������� ��������, ����
������ ����� � ����� � �������� �����������:
%%365
�������� ������� ���������� �� �������� ��� ���������� ��������!
(�.~���.~8.) � ������ �������, �� ��� ������ ���� �����������,
\emph{��������������} ����������� ��� ������ ��������������~$T$.

��~$K_T(n)$---����������� ����� �������� ����, ���������� �
$T\hbox{-lifo}$~������ � $n$~�������� ������. 葏������ ������, �������� �
�.~2.3.4.5, �������� ��������, ���
$$
K_T(n)\ge nq - \floor{((T-1)^q-n)/(T-2)}, \quad
q=\ceil{\log_{T-1} n},
\eqno(9)
$$
��� ��� ��� ����������� ����� �������� ���� ������ ������ � $n$~��������
������ � �������� ������ ����~$<T$. � ���������� ������� ��������
������������ �������� ������ ��������~$K_T(n)$. 焅�� ��������� ���������
������� ������, �������, ��������, �����:
$$
\vbox{\halign{
\hfil$#$ &&\bskip \hfil$#$ \cr
       n = 1 & 2 & 3 & 4 &  5&  6&  7&  8&  9& 10& 11& 12& 13& 14& 15\cr
K_3(n) \le 0 & 2 & 5 & 9 & 12& 16& 21& 25& 30& 34& 39& 45& 50& 56& 61\cr
K_4(n) \le 0 & 2 & 3 & 6 &  8& 11& 14& 17& 20& 24& 27& 31& 33& 37& 40\cr
}}
\eqno (10)
$$

ꀐ� ���������, ��� ����� ������ � ����������� ������ �������~$< T$
�������� \emph{�����} $T\hbox{-lifo}$~������� � ��� ������, ��� ��� �����
���� ������� $T\hbox{-lifo}$ � ������� ������ ��������� ������� ����� ��
����������� �������. 􀊒������ ���������� ���������� ����������� �����
�����������, �������� ������. ��~$A$---���������� ��� �����. ᓄ��
����������� ��������� �������:
\medskip

{\sl ���~1.\/} ������ ����� ���� ������ ��������� ������ ����� ��������,
 ����������� � ��������~(a), ��������� ����, ������ ���, ����� �����������
���~$A$ �������������� ������ � ����� ����� ����� �����.

\smallskip
{\sl ���~2.\/} 瀌����� ������ ������� ���� ����
\picture{p.365}
���� ������~$B\ne A$.

\smallskip
{\sl ���~3.\/} 瀍��������� ���������� ���� � ������ �������\note{1}%
{�.~�.~2.3.1.---{\sl �. �����.\/}}.
����������� ����� ����������� �����, ��������������� ��������~(a), (b), (c).
\medskip
%%366

퀏�����, ���� �� ������ � ������
\picture{p.366.1}
� ���� ����, �� ��� ��������� ����� �� ��������� ����� ����� �������:
\picture{p.366.2}
텒����� ���������, ��� ����������� ꀐ�� ������������� ����������
"��������� ���������---������ ������" � ���� ������� ������� ������� (��.~���.~12).

瀌����, ��� ����������� ����� ���������� �������� ����� �������, �
������� ��� ��������� ������� ���������� �� �����~$A$. ��� ������������
��������� ����� ������������� � ����������, ������� ����� �������
�������� � \emph{������ �������.}

%% !!! ���������� �����, ��������� � ����������
{\medskip\narrower
\item{\bf P1.}~������������ ��������� ������� �� �����~$A$, ���� ���� ��
����� ��������. ��~$S$---����� ���� ��������� ��������.

\item{\bf P2.}~⛏������ ����������� ���� ����������, ���������
$(T-1)\hbox{-�����}$ ������ � $S$~�������� ������ � ����������� ������
����, ������� $T\hbox{-lifo}$~������, ����� �������� ���� ��������
��������� ������ �������~(9) �� �����, ��� ��~$S$.

\item{\bf P3.}~񋈂��� ������� � ������������ � ���� ������.
\endmark
\medskip}

��������� � ��������� ����� ���������� �� ����� ������ �����. �
\emph{��� ����� ����� ���� ��������� �����.}
(∄�� �� ��������, ��� ������ ����� ����� ����������� ��������?) 䅋�
%%367
� ���, ��� ����� �������, ����� ������������� ��������� �� �������� ��~$A$
���� �������������, � ���������---���������� � ����������� �� ����,
���������� �� ��������������� ������� ���� �� �������� ��� ������ ������.
��� �������� ����� ���������, �� ����~$S$ �������, ����� �����������
��������, ������� ������ ���� ����������, �� ��������������� ����� (���
�����) ��������������� ����� ���, ��� ��� ���������. 򎃄� ���������
���������� ��������, ���������� � ������ ��������� ��������, �������� ������
$$
S \log_{T-1} S+O(S).
\eqno(13)
$$

򀊈� �������, ������� � ������ ������� ����������� ����� ������������ ���
���������� ���~$S\to\infty$; � ���������������� ��� ��������������
\emph{����������,} ��� ���~(9) ����������, ���~$S\log_{T-1} S+O(S)$---���
���������, ��� �� ������ ����� ��������� �������� � $T$~�������. � ������
�������, ��� ������������ ��������� ��������~$S$, ������ �������������
�� ��������, ������� � ������ ������� ������ ������������;
����������� ��� ��������� ������ ����� � �������, ���� $S$~������������
����. ⎇�����, ������� ��������� ������� ����� ������������� � �������,
������� �������� � ����������� � ��������� ��� ���������~$S$ �
�������������� ���������� ��� �������~$S$.

툆� � ����������� ������ ����� ���������������, ��� ꀐ� �����������
������� �������� ������ ��� ������� � \emph{������ �������.} 򅎐��
����������� � ���� ������ �����������- ����� �������, ���� ���� ��������
��������� ������ ���������� ����������.

\excercises  (������ �����)
\ex[17]  ������� � ������ ������� ����� ������ �������� ����� �������
������� �� ����� ����� ���������� ������������� "��������" ������ �
������~$+\infty$. ꀊ ������� ������������ ���� ����� ��� �������� ������?

\ex[20] ᓄ�� �� ������� �������, �����������~(1), ������ ������������,
��� ������ ������, ����� ��� �������� "��������" ������� � ���������
����� ��� �������� �� ������ ������ � ����������?

\rex[20] 䎊�����, ��� ����� ������������ �������������, ��������� � �����
�~(1), ���� ����� ���������� ���������� �� �����~T1, ������ �������~$A$,
���� ������������� ��~T1 ����~$ADA\ldots$, � ��~T2--T5 ����~$DAD\ldots\,$.

\ex[22] ꀊ �� ���������� ���� ��������� ����������� ������� � ��������
�������, ����������� ��� ������� � \emph{������������} ������� � ������,
 ��� ��� �������~"$D$" ������������� ��������� ���������� ���������?

\rex[23] ꀊ�� ������� ��� ����� ����� ������� ������~(8), (9), (10)
�~(11) ��~5.4.2 ����� ����������� ��� ������������ ������� � ��������
�������? 臎������� ����� ������� ��� ������������� ������ ������ ��
����� ������, ��������� ���������, ����������� ���.~71(a).

\ex[07] ꀊ��� ��������� ������������� ����� �������,
�������������� ������� � ���� ������ ��������~(8)?

%%368
\ex[16] 퀐������ ������������� � ���� ������ ����� ������� � ��������
�������, ������������ ��������� ������������������� ��������:
{\def\!{\phantom{+}}\def\y#1{y^{(#1)}}\ctable{
$#$&$\hbox{}#$ \bskip & $#$&$\hbox{}#$ \bskip& $#$&$\hbox{}#$ \cr
v^{(33)} &= (\!20,\!9,\!5) & \y{22} &= (+1, -1, +1) & \y{10} &= (+1, +1, -1)\cr
\y{33} &= (+1, -1, +1) & \y{21} &= (-1, +1, +1) & \y{9} &= (+1, -1, +1) \cr
\y{32} &= (+1, +1, -1) & \y{20} &= (+1, +1, -1) & \y{8} &= (+1, +1, -1) \cr
\y{31} &= (+1, +1, -1) & \y{19} &= (-1, +1, +1) & \y{7} &= (+1, +1, -1) \cr
\y{30} &= (+1, +1, -1) & \y{18} &= (+1, +1, -1) & \y{6} &= (+1, +1, -1) \cr
\y{29} &= (+1, -1, +1) & \y{17} &= (+1, +1, -1) & \y{5} &= (-1, +1, +1) \cr
\y{28} &= (-1, +1, +1) & \y{16} &= (+1, +1, -1) & \y{4} &= (+1, -1, +1) \cr
\y{27} &= (+1, -1, +1) & \y{15} &= (+1, +1, -1) & \y{3} &= (-1, +1, +1) \cr
\y{26} &= (+1, -1, +1) & \y{14} &= (+1, -1, +1) & \y{2} &= (+1, -1, +1) \cr
\y{25} &= (+1, +1, -1) & \y{13} &= (+1, -1, +1) & \y{1} &= (-1, +1, +1) \cr
\y{24} &= (+1, -1, +1) & \y{12} &= (-1, +1, +1) & \y{0} &=(\!1,\!0,\!0) \cr
\y{23} &= (+1, -1, +1) & \y{11} &= (+1, +1, -1)\cr
}}

\ex[23] 䎊�����, ���~(8)---����������� ������ ������� � �������� �������
���~$S=7$ �~$T=4$ � ��� ��� ������, ���������� ������������ �������, ����.

\ex[�22] 䎊����� ������ ������~(9).

\ex[41]  ������ ��� ��������� ������� ������ ��������~$K_T(n)$.

\rex[20] ⅐�� �� �����������, ��� ��� ����� ����� ������� � ��������
�������, �� ������������ ������, ����� $(T-1)\hbox{-��������}$ �������,
����������, ����� ������� �� ������ ����� ������������: $ADAD\ldots$,
�.~�.\ ��� �� ����� ��������, ���� ��� �������� ������� �������� ��������� ��������������?

\ex[22] 䎊�����, ��� ����������� � ������ �������� ꀐ�� ������ ���������
���������� ������, ��������������� ��������~(a), (b), (c).

\ex[1�] 񄅋����~(12) ����� �����������, ������ ��� �����
������ ����������� �������, ������ ���, ����� ������ ������� ��� ��� �����
���������� ����������� ����� � ���������� �����.

\ex[40] ������� ��������, ������� ��������� ������� � ������
������� ��� ������ ���������� ������ � �����~P2 �~P�, ��������� ������
$O(\log S)$~���� ������ ��� ���������� ��������.

\ex[�39] ꎍ�������� ꀐ�� � ������ �������� ��������� ������� �
����������� �������� � ��������� ������������ �����. 䎊�����,
��� ����~$T=3$, �� ����� ��������� ��������������� �����������
$3\hbox{-lifo}$~�������, � ������� ������������ ������ ����������� �������

䐓���� �������, ����� $\hat K_T(n)$~����� ����������� ������ ��������
���� ����� ���� $T\hbox{-lifo}$~�������� � $n$~�������� ������, �����, ���
������ ���������� ���� ����� �������~$T-1$. 䎊�����,
���~$\hat K_3(n)=n\log_2 n+O(n)$.

\ex[�46] (񎕐������� ����������� ���.~15) ⅐�� ��,
���~$\hat K_T(n)=n\log_{T-1}(n)+O(n)$ ��� \emph{����}~$T\ge 3$,
����~$n \equiv 1 \pmod{T-1}$?

\rex[28] (������~�.~��.) ����� �������� ������������ ������� �
��������� ������� � �������� �������, �� ����� �� �����������
\emph{�������} ����� �������� �������; ��� ������������, ��� �����
���������� ������������� ��������� ������� �� ���������~5.4.3C.
(a)~臌�����~(5.4.3-1) ���, ����� ���� ������������ ������ ������
�������������, ������� ������� ������� ����� �������� �������. (b)
񊎍���������� ����� ���������� �������������,
%% 369
�������������� ������������ ����� ����� �������
���������������. [荀�� ������, ���� ����� ��������� �������� ��������
����� ������� ���������������, �� ���������� ����� ��������� (�� �� ���)
������� ������, ����� ���������� ������� �������������.]

\ex[46] ��������, ��� ������� $T$~��������� ��������� ���
����������~$T\ge3$ � ��� $T1$~�������� $N$~�������, � �� ����� ���
��������� ����� �����. ⎇����� �� �������� ������� ������� ��~$T1$ ��
����� �����, �������~$O(N\log N)$, ��� ��������� ������? (��� ��������
��������, �������, �����������, ���� ����������� �������� ������.)
�.~�~���.~5.2.5-14 ����� ����� ����������, �������, ������, ������
������� $N \log N$~�����.

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


񋅄����� ���������� ��������� ������ ���������� ������� � ������ �������.
� ���� ������ ������ ����� ��������� ��� �������, � �� ��� ����. 񕅌�
������� ����� ����������� �������������������
��������~$y^{(n)}\ldots{}y^{(1)}y^{(0)}$ ����� ��� ��, ��� � ������, ��
����� �� ����������� ��������� ������������� � ������������� � ���� ������,
�� �� �������� ������� "��������� ���������---������ ������" �� "������
���������---������ ������". 򀊈� �������, ������������ ������������~(4)
������ ���� �������� ��
\picture{p.369}
䅐���, ������� ����� ���� �������� ���, ����� ���������� ������� �
������ ������� �� $T$~������, ����������~$T\hbox{-fifo}$%
\note{1}%
{"Fifo"---������������ �� "first in first out" (������ ����������---������
�����������).---{\sl �. �����.\/}}
�� �������� � ��������~$T\hbox{-lifo}$ � ������ ��������� ������.

呋� ����� ����� ��������� � �������� �����������, ��� �������� �����
������� �����. �, � ���������, ��� �� ����� ���������� ����� �������
������������� �������. 呋� �� � ������������ ������� ���������� � ������
�� ������� "������ ����������---������ �����������", �� ���������� �������
����� ������� �� ��������� �� ����� ����� ����� � ������. ���� ����---��
������ ��������� ����� �����! � ������������ � ��� �� ���������, ��� �
�������� ������ ������� �� ������� ������ [��.\ �����������~(2.2.2-4)
�~(2.2.2-5)], �� ������� � ����~(2.2.2-6) �~(2.2.2-7) �� ��������� �
������, ��� ��� ��� �� �������� ����������. ���� ������ ����� ��������
\emph{�������} $T\hbox{-fifo}$~�������, ���� ��� ����� ���� �������� ���,
 ����� ��������������� ����� ������� ������������ �����, ����������
������ ����������: "��������, ����������, ��������� ���, ����������;
��������, ����������, ��������� ���, ����������; � �.~�.".

\ex[22] (�.~�.~ꀐ�.) 퀉���� �������� ������, ������� ��
��������~$3\hbox{-fifo}$.

\rex[22] 񔎐��������� ������� "�������� $T\hbox{-fifo}$" ������ �
�������� ���������� �������� ������� ������������ ������������
������������ ����� ����, ������������ ($4'$).

\ex[18] 퀐������ ������������� � ���� ������ ����� ������� � ������
�������; ������������ ����������� �������� � ���.~7. ߂������ ��
��� ������ �������~$3\hbox{-fifo}$?

\ex[28] (�.~�.~ꀐ�.) 䎊�����, ��� ������������� � ���� ������
������������ � ���������� ������� � ������ �������������� ��������� ���������
%% 370
��� � ������ ��������� ������, ��� � � ������ ������� ������, ��
����������� �������, �������� �������� ���������� ����. 퀉���� �����
������� ����� ���������, ������������� ���� �������, ��� ������� ��� �����.

\ex[24] (�.~�.~ꀐ�.) ᓄ�� ��������, ��� �������~$y^{(q)}\ldots{}y^{(r)}$
����� ������� �������� \dfn{�������,} ���� ������� �������� ����� ��
������������ � ���������� ��� �������, �.~�.\ ���� �� ����������~$i$, $j$,
$k$, �����, ���~$q\ge i> k \ge r$ �~$y^{(i)}_j=-1$, $y^{(k)}_j=+1$. ����
����� ����������---��������, ��� \emph{��������� ������� ������������ �����
������} ����� ���� ���� ������� � ��� �� ������ ���� � ��������� ��������.

󄎁�� ������ ��������� �����������. ᓄ�� ������~$v\to w$, ����~$v$
�~$w$---����� $T\hbox{-�������}$, ��� ���������� ����� �������, ������� �
����� ������ ������ ���������~$w$ �~$v$ (�.~�.\ ���������� �����
�������~$y^{(m)}\ldots{}y^{(0)}$, �����, ���
$y^{(m)}\ldots{}y^{(l+1)}$~�������� �������, $w=y^{(m)}+\cdots+y^{(0)}$
�~$v=y^{(l)}+\cdots+y^{(0)}$). ᓄ�� ������~$v\preceq w$, ����~$v$
�~$w$---$T\hbox{-�������}$, �����, ��� ����� ���������� $k$~���������
�������~$v$ �� ��������� ����� ���������� $k$~��������� �������~$w$
���~$1\le k \le T$. �, ��������,
$(2, 1, 2, 2, 2, 1) \preceq (1, 2, 3, 0, 3, 1)$,
��� ��� $2\le 3$,  $2+2\le 3+3$,~\dots, $2+2+2+2+ 1+1\le 3+3+2+1+1 +0$.
퀊����, ����~$v=(v_1,~\ldots, v_T)$,
�� �����~$C(v)=(s_T, s_{T-2}, s_{T-3},~\ldots, s_1, 0)$,  ��� $s_k$~����
����� ���������� $k$~��������� �������~$v$.

%% !!! ������ �� ����������
(a)~䎊�����, ���~$v\to C(v)$. (b)~䎊�����, ���~$v\preceq w$
������~$C(v)\preceq C(w)$. (c)~񗈒�� ��������� ��������� ���.~24,
��������, ��� ��������� ������� ������������ ����� ������.

%% !!! ������ �� ����������
\ex[�35] 葏������ ����������� ���.~23, ��������, ���~$v\to w$
������~$w\preceq C(v)$.

%% !!! ������ �� ����������
\ex[�36] (�.~�.~ꀐ�.) ᓄ�� ��������, ���
�������~$y^{(q)}\ldots{}y^{(r)}$ ����� ������� �������� \dfn{�����,} ����
�� ���� �� ���� �� ������������ � ��� �����, � ��� ������, �.~�.\ ���� ��
����������~$i$, $j$, $k$, �����, ���~$q\ge i$, $k\ge r$ �~$y^{(i)}_j=+1$,
$y^{(k)}_j=-1$. ���� ����� ����������---����������� ����� �������, �������
������������ ����� ���. � ����� ������~$v \To w$, ����~$w$ ����� ����
������������� �~$v$ �� ���� ���� (��.~�~�������� ������������,
��������� � ���.~23), � �����~$D_k(v)=(s_k+t_{k+1}, s_k+t_{k+2},~\ldots,
s_k+t_T, 0,~\ldots, 0)$, ���~$t_j$ ����������~$j\hbox{-�}$ � �������
�������� �������~$v$ �~$s_k=t_1+\cdots+t_k$. (a)~䎊�����, ���~$v\To
D_k(v)$ ���~$1\le k < T$. (b)~䎊�����, ��� ��~$v\preceq w$
�������~$D_k(v)\preceq D_k(w)$ ���~$1\le k < T$. (c)~䎊�����, ���
��~$v\To w$ �������~$w\preceq D_k(v)$ ��� ����������~$k$, $1\le k < T$.
(d)~񋅄���������, ����� �������, ����������� ������������ ����� ���������
�������� �� $T$~������ �� $q$~���, ����� ���� ����������
������������������� .����� �����~$k_1 k_2~\ldots k_q$, �����,
��� ��������� ������������� ����~$D_{k_q}(\ldots D_{k_2}(D_{k_1}(u))\ldots)$,
%!!! ������ �� ����������
���~$u=(1, 0,~\ldots, 0)$. ��� ��������� �������� ���, ����� �������
$T\hbox{-fifo}$~�������������, � ��� ����� ������ � ����� ���� ���.~22.
ꎃ��~$T=3$, ��� \emph{�����������} �����, � ���~$T=4$, 5, 6, 7 ���
�������� \emph{����������������} �����.

%!!! ������ �� ����������
\ex[�46] (�.~�.~ꀐ�). ⅐�� ��, ��� ����������� ������������������~$k_1
k_2~\ldots k_q$, ���������� � ���.~25, ������
�����~$1\ceil{T/2}\floor{T/2}\ceil{T/2}\floor{T/2}~\ldots$  ��� ����~$T\ge
4$ � ���� ���������� �������~$q$?

\subsubchap{���������� ����������}%5.4.5

噅 ���� ������ � ���������� �������� ��� ��������� �������� 񎁅��� �
[{\sl JACM,\/} {\bf 9} (1962), 372--375]. ⌅��� ���� ����� �������� �
������� �������������, ����� ��� ��������� ������� �������������� ��
������, �� ��������� ��������, ������� ������������� �� �� �������������,
�� �� �������, ��� ��� ������� ����� ���������� ���������� ��� �� ����,
 ��� ��� �������� ���������� ����� ��������� �����������.
%%371
��������, ��������, ��� ��� ������� ������������ ���� ����. � ������
񎁅�� 16~��������� �������� ����� ������������� ��������� �������:
\ctable{
#\hfil\bskip&#\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip
&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip
&#\hfil\cr
       & \hfil �����& T1    & T2    & T3  & T4     & T5    & \hbox{񒎈�����} \cr
􀇀~1.& ������������� & A_1   & A_1   & A_1 & A_1    & -     &  4\cr
􀇀~2.& 񋈟���       & -     & -     & -   & -      & D_4   &  4\cr
􀇀~3.& ������������� & -     & A_1   & A_1 & A_1    & D_4A_1&  4\cr
􀇀~4.& 񋈟���       & D_4   & -     & -   & -      & D_4   &  4\cr
􀇀~5.& ������������� & D_4A_1& -     & A_1 & A_1    & D_4A_1&  4\cr
􀇀~6.& 񋈟���       & D_4   & D_4   & -   & -      & D_4   &  4\cr
􀇀~7.& ������������� & D_4A_1& D_4A_1& -   & A_1    & D_4A_1&  4\cr
􀇀~8.& 񋈟���       & D_4   & D_4   & D_4 & -      & D_4   &  4\cr
􀇀~9.& 񋈟���       & -     & -     & -   & A_{16} & -     & 16\cr
}
焅��, ��� � � �.~5.4.4, �� ����������~$A_r$ �~$D_r$ ��� �����������
�������������� ������������ � ��������� �������� ������������� �����~$r$.
 ��������������� ����� �������� � ������ �� ������ ���������� ������� ��
������ �� ������� ���� � ������� �� (����� � �������� �����������) ��
����� �����. �� �������������� �������������, �� ���� ���
���������� ��������� ��~1 ������ �� ��������� � ������, � ������ �������
���� ��� ���� �������~$D_4$. ꎃ�� ���� �������� ������������ ������
�������~$D_4$, �������������� ������� �������~$A_{16}$. ���� �����
����������, �������� ��� ���~$A_{16}$, ������ �� �~$D_{64}$ �~�.~�.\ ��
��� ���, ���� �� ����������� �������� ������. � ����� ����� �������
����� �������� ������.

呋� ����� ��������� ��������~$S$ ����~$4^m$, �� �������� ������, ��� ����
����� ������������ ������ ������ ����� $m+1$~��� (���� ��� �� �����
������������� � $m$~��� �� ����� �������). 呋�~$S$ ����� �����~$4^{m-1}$
�~$4^m$, �� ����� � ������� ��������� �������� ���������~$S$ ��~$4^m$;
�������������, ����� ����� ���������� ����� ������������
$\ceil{\log_4 S}+1$~��������� �� ���� ������. ��� ��� ��� ��, ��� �����������
��� ���������������� ���������� �� \emph{������} ������; � ����� ������
������������� ���������� � $T$~�������� �������
������������ ����������������� ������� � $2(T-1)$~�������, ��� ���
��� ������ $\ceil{\log_{T-1} S}+1$~�������� �� ������. 呋�
$S$~����������� ��������~$T-1$, �� ��� ����� ������, ��� ����� ��������
��� \emph{�����} ������ � $T$~�������, ��� ��� ����� �����������
������ ������ �� �����������~(5.4.4-9). � ������ �������,
����~$S$ �����~$(T-1)^{m-1}+1$, �.~�.\ ����� �� ������� ������
�������~$T-1$, �� ���� ����� ������ ����� ����� ������.

� ���.~2 ��������, ��� ��������� ����� ���� ������ ������, ���������
����������� ��������� ���������. 噅 ���� ������������������ ����
���������� � 1966~�. 䅍����~�.~ᝍ�����,
%% 372
������� ������ ���� ��������� ������������ ��������.
[�.~H.~Wedekind, Datenorganisation (Berlin W. de Gruyter, 1970). 164--166,
 �~U.~S.~Patent~3540000 (10~������ 1970).] ����� ���� ������� � ���,
����� �������� ������� �� ��� ���, ���� �� ����� ��������� ������ ��������
��~$S$. � ������� ��������� ���������� ����� �������������� ����� ᝍ����.

��� ���������� ������������� ���������� ��������� ��������� �������:
\ctable{
#\hfil\bskip&#\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip
&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip
&#\hfil\cr
       & �����     & T1    & T2    & T3    & T4    & �5  &
\hbox{񒎈�����} \cr
􀇀~1.& �������������& -     & A_1   & A_1   & A_1   & A_1   & 4\cr
􀇀~2.& �������������& -     & A_1   & A_1A_1& A_1A_1& A_1A_1& 3\cr
􀇀~3.& 񋈟���      & D_4   & -     & A_1   & A_1   & A_1   & 4\cr
􀇀~4.& �������������& D_4A_1& -     & A_1   & A_1A_1& A_1A_1& 3\cr
􀇀~5.& 񋈟���      & D_4   & D_4   & -     & A_1   & A_1   & 4\cr
􀇀~6.& �������������& D_4A_1& D_4A_1& -     & A_1   & A_1A_1& 3\cr
􀇀~7.& 񋈟���      & D_4   & D_4   & D_4   & -     & A_1   & 4\cr
􀇀~8.& �������������& D_4A_1& D_4A_1& D_4A_1& -     & A_1   & 3\cr
􀇀~9.& 񋈟���      & D_4   & D_4   & D_4   & D_4   & -     & 4\cr
\noalign{\smallskip
\noindent
� ���� ������ �� �� ������� ���~$D_4$ �~$A_{16}$, (���� ������ ��
��������, ��� �������� ������ ���������); ���� ����� ����, ��� ����������
\smallskip}
􀇀~15.& 񋈟��� & D_4 D_4 & D_4 D_4 & D_4 D_4 & D_4 & - & 4 \cr
\noalign {\smallskip
\noindent ����� ������� ������ �������~$A_{16}$:
\smallskip}
􀇀~16. & 񋈟��� &  D_4 & D_4 & D_4 - & A_{16} & 16 \cr
\noalign{\smallskip
\noindent ⒎��� �������~$A_{16}$ �������� ����� �������� ��� ����~$D_4$:
\smallskip}
􀇀~22. & 񋈟��� & D_4 D_4 & D_4 D_4 & D_4 & - & A_{16}D_4 & 4\cr
􀇀~23. & 񋈟��� & D_4 & D_4 & - & A_{16} & A_{16} & 16 \cr
}
�~�.~�.\ (��.~�~������~1--5). ��������� ����� ᝍ���� ����� ������,
���� �������, ��������, ������ ���� ��������� ��������: �������������
���������� (�� ����������� �� ���.~2) ��������� �� �������������� �������
(�� ����~2), �� ������� ��������� �� ����������� ������� � �����
����������~$4+4+4+1+5= 14$, ����� ��� ����� ᝍ���� ��������� ��
����������� ������� (�� ����~3), �� ������� ��������� �� ��������������
������� � ����� ����������~$4+1+2+5=12$. ( ������ ����� �������
��������� �������������� ������, ������ ����������� ��������� �����
������������� ��������.)

%%373

򎗍�� �������� ������ ᝍ���� ���������� ���� � ���������~B. �
���������, ��������������� ���������, ��-��������, ������� ������, ���
�����������������; ����� ��������� ���� ����� ���, ��� ������������!
�������� ��� ���������� �� ��� �������, ��� ����������� ����� ������� �
����������� ���� � ����� ���������� ��������� �����������; ��������,
��������, ���������, ��� ���������� ��������� ��� ���������� �� �������
���������, ����� ������������� ��������, ��� �� ����������.

\alg B.(���������� ���������� � ������������ ��������������.) ����
�������� ����� �������������� ������� � ������������ �� �� ������, �����
�� ������� �������� ������� �������������, ����� ����� ����������
��������� ����.
\picture{���.~77. ���������� ���������� � ������������ ��������������.}
� ��������� ������������ $P\hbox{-�������}$ ������� � ��������������,
��� ���� $T=P+1\ge 3$~��������� ��������� (�� ������ ����������, �������
����� ���� ���������� ��� �������� �������� ������). 녍������ ����������
������ ��������� ������ ��� � ������, ��� � � �������� �����������; ���
���������� �������~0, 1,~\dots, $P$. 葏��������� ��������� �������:
{\medskip\narrower

\item{$|D|[j]$,} $0\le j \le P$---����� ��������� ��������, ������� �������
�������������� � ����� �����~$j$.


\item{$|A|[l, j]$,} $0\le l \le L$, $0\le j \le P$. 焅��~$L$---����������
������� �����, �����, ��� �����  ������� �� �����~$P^{L+1}$ ���������
��������. 呋�~$|A|[l, j]=k \ge 0$, �� �� �����~$j$ ������� �������
����������� �����~$P^k$, ��������������� "������~$l$" ������ ���������.
���� ������� ������������, ���� $k$~�����, � ���������, ���� $k$~�������.
$|A|[l, j]=-1$~��������, ��� �� ������~$l$ �����~$j$ �� ������������.
\medskip}

\noindent 荑������� "�������� ��������� ������� �� �����~$j$"
�������� ����������� ������������ ��������� ��������:
%%374
{\medskip\narrower
\noindent 󑒀������~$|A|[l, j]\asg 0$. 呋� �������� ������ ���������, ��
���������~$|D|[j]$ ��~1; � ��������� ������ �������� ������� ��
�����~$j$ (� ������������ �������).
\medskip}
\noindent 荑������� "����� �� �����~$j$" ������������ ��� �������
����������� ��������� ��������:
{\medskip\narrower
\noindent 呋�~$|D|[i]>0$ ��� ����~$i\ne j$, �� ���������~$|D|[i]$ ��~1
��� ����~$i\ne j$ � ���������~$|D|[j]$ ��~1. � ��������� ������ ����� ����
������� �� �����~$j$ �� ���� ����~$i\ne j$, �����, ���~$|D|[i]=0$, �
���������~$|D|[i]$ ��~1 ��� ���� ���������~$i\ne j$.
\medskip}

\st[퀗������ ���������.] 󑒀������~$|D|[j]\asg 0$ ���~$0\le j \le P$.
瀒�� �������� ��������� ������� �� �����~$j$ ���~$1 \le j \le P$.
󑒀������~$|A|[0,0]\asg -1$, $l\asg 0$, $q\asg 0$.

\st[₎� ��������?] (� ���� ������ �����~$q$ ����� � ������ ������ �����
�������� ����� ������� ���� �������.) 呋� ��� ���� �������� ������,
������� � ����~\stp{3}. ��� ���� ���� ��������, �� ���������� ���
�����~$j\ne q$, �����, ��� $|A|[0, j]$~�����; ����� ����� �� �����~$q$,
����� ��� ������ ��� ������������ ����� � ������ �����������, �
��������� �����---� ��������. ���� ����������� ����������; ���������
��������� �� �����~$q$ � ������������ �������.

\st[퀗��� ����� �������.] 󑒀������~$l \asg l+1$, $r \asg q$, $s \asg 0$
�~$q\asg (q+1) \bmod T$. 瀏����� ��������� ������� �� �����~$(q+j) \bmod T$
���~$1 \le j \le T-2$. (򀊈� �������, ��������� ������� ������������ ��
��� �����, ����� ����~$q$ �~$r$.) 󑒀������~$|A|[l, q]\asg -1$
�~$|A|[l, r] \asg -1$.

\st[쎆�� �� �������?] 呋�~$|A|[l-1, q]\ne s$, ��������� � ����~\stp{3}.

\st[񋈟���.] (� ���� ������ $|A|[l-1, q]=|A|[l, j]=s$ ���
����~$j\ne q$, $j \ne r$.) 񋈒� �� �����~$r$. (�.\ ���� ����������� ����
��������.) 瀒�� ����������~$s \asg s+1$, $l \asg l-1$,
$|A|[l, r]\asg s$ �~$|A|[l, q] \asg -1$. 󑒀������~$r \asg (2q-r)\bmod T$.
(� ����� ������ �� �����~$r=(q-1)\bmod T$, ���� $s$~�����,
�~$r=(q+1) \bmod T$, ���� $s$~�������.)

\st[瀊����� �� �������?] 呋�~$l=0$, ������� �~\stp{2}. � ���������
������, ����~$|A|[l, j]=s$ ��� ����~$j\ne q$ �~$j\ne r$, �� �������
�~\stp{4}. � ��������� ������ ��������� �~\stp{3}.
\algend

����� �������� ������������ ����� ���������, �� ����� ������������
�������������� ���� "����������� ��������", ��� �� ��� �� ������ ���
���������~2.3.1T. ��������, ��� �� �������� � ����~B3 �~$l=l_0$,
$q=q_0$, $s_+=|A|[l_0, (q_0+1)\bmod T]$ �~$s_-=|A|[l_0, (q_0-1)\bmod T]$,
� ��������, ����� ����, ��� ����~$s_+=0$, ����~$s_-=1$, ����~$s_+=2$,
����~$s_-=3$, ����~$\ldots\,$. 쎆�� ��������� �� ��������, ��� �������� �
����� ������ ������ � ����~B5, �� ������� � ������� ��~$l\hbox{-�}$
������~|A| � �� ����������
%%375
����������~$l=l_0+1$, $q=q_0\pm 1$, $r=q_0$
�~$s=s_+ \ror s_-$, ������ �� �������� ����~$+$,
����~$s_+=0 \ror  (s_+=2 \rand  s_-\ne 1) \ror (s_+=4 \rand s_-\ne 1, 3)
\ror \ldots$, � �� �������� ����~$-$,
����~$(s_-=1 \rand s_+=0) \ror (s_-=3 \rand s_+\ne 0, 2)\ror \ldots\,$.
�������� ����� �������� �������������� �� ����� ���������, �� �
��� �������� ������������� � ����, ������� ������ ������� ��� ����������,
��� ��� �������� ������������.
\picture{���.~78 ������������� ������������� ����������, ������������
����� ���������~B �~���.~3.}

� ���.~78 �������� ������������� ���������~B, ���������� ������� ������
������� ������ ������ � ����������� ��~$S$---����� ��������� ��������,
������ ��������������, ��� ��������� ������� �������������� ����� ��
�����. (񎎒����������� ������� ��� ����������� � ��������� ����������
��������� �� ���.~70 �~74.)  ���������� ���.~78 ������ ���������
������������������, ���������� � ���.~3.

%%376

\section ��� ������. 񕅌� ������������� ����������, ��-��������,
 ������� ����������� ��������� ������, ��������� ���������� ���-��
����������� ������� ������� �� ���� ����, ��� �� ������� ����� ���������
�������� �������. � �� ����� �.~�.~㎒�
[Proc. AFIPS Spring Jt. 񎒐. Conf.; {\bf 25} (1964), 599--607] �����
������ ��������� ������������� ����������, ��������� ������ ������ ������
� ������� ���������. 僎 ����� � ����� ���������� �� ��������� ����,
������� �� ������ � ���� �����, ���������

a)~������ ������ ������������ � ������ �����, ������ ��������������, ���
������, ����������� � \emph{��������} ���� �����, �� �����������;

b)~��� ��������� ������ ����� ������������� ������������ �����.
󑋎���~(a) �������� �������� "������ ����������---������ �����������",
�������, ��� �� ������������, �������� ��������������� ������� ������,
������ ��� ����� ���� ������� �����������, ���� ����� ���������
��������� ����������� ���������� ������ ����� � ���� � ������ �������
���������� "�������� ��������". 󑋎���~(b) ����������� ��
��������� ������� �������������� ������������ ������������� ������ � ����������.

���������� ���������� ㎒�� � ������ ������� ����� ���� ������
�����---��� ���� �� ������ ����������, ������� ��� ������������ ��� ��������,
 � �� ��� ���������� ���������� [U.~S.~Patent~3380029 (23~������ 1968)].
呋� ��������� �� ���������, �� ��� ��������, ��� �������� ������
������������ � ��������� ��� ���������� ��������� �������. 셒��
ᝍ���� (������������� ���������� � �������� �������) ��� ������������
IBM ����������� ������ �����. [򀊈� �������, �������� ����� ���, �����
������������ �� �������� ������ ��������� ��������� �����������
���������������! � ��� ���������������� ���������� �� �������� ������,
� ��������� ��� ��� ������ ����� �����, �� ������������ ����������
�������� ����������. ꎍ����, �������� �������������� �����,
����������� ����� ��������� � ������� �������, ����������� ����,
��� ������� ����������� ����������, ������� �������� �������������� �
������� ���� ������������� �������.]

����������� ���� � ������ ㎒�� ������� � ����� ������������� ����,
����� ������ ����� ���������� � ������� ������������� �����~1, ��
������� �������� �� ������� ������������� �����~$P$, �����~$P^2$ �~�.~�.
퀏�����, ����~$T=5$, �� ���������� ���������� ��������� �������
("."~��������� ������� ��������� ������� ������-������ �� ������ �����):
%%377
\ctable{
#\hfil\bskip&#\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip
&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip&\hfil$#$\hfil\bskip
&\hfil$#$\hfil\bskip&#\hfil\cr
        & �����     & T1            & T2      & T3     & T4     & T5 &
 \hbox{񒎈�����} & ������� \cr
􀇀~1. & �������������& A_1           & .A_1    & .A_1   & .A_1   & A_1.
  &  5& [T5 �� ��������������]\cr
􀇀~2. & 񋈟���      & A_1.          & A_1.    & A_1.   & A_1.   &
A_1A_4. &  4& [������ ���� ���]\cr
􀇀~3. & �������������& A_1           & .A_1    & .A_1   & A_1.   &
.A_1A_4 &  4& [T4 �� ��������������]\cr
􀇀~4. & 񋈟���      & A_1.          & A_1.    & A_1.   & A_1A_4.&
A_1.A_4 &  4& [������ ���� ����]\cr
􂝀~5. & �������������& A_1           & .A_1    & A_1.   & .A_1A_4&
.A_1A_4 &  4& [T3 �� ��������������]\cr
􀇀~6. & 񋈟���      & A_1.          & A_1.    & A_1A_4.& A_1.A_4&
A_1.A_4 &  4& [������ ���� ����]\cr
􀇀~7. & �������������& A_1           & A_1.    & .A_1A_4& .A_1A_4&
.A_1A_4 &  4& [T2 �� ��������������]\cr
􀇀~8. & 񋈟���      & A_1.          & A_1A_4. & A_1.A_4& A_1.A_4&
A_1.A_4 &  4& [������ ���� ����]\cr
����~9. & �������������& A_1.          & .A_1A_4 & .A_1A_4& .A_1A_4&
.A_1A_4 &  4& [T1 �� ��������������]\cr
􀇀~10.& 񋈟���      & A_1A_4.       & A_1.A_4 & A_1.A_4& A_1.A_4&
A_1.A_4 &  4& [텒 ���������]\cr
􀇀~11.& 񋈟���      & A_1A_4A_{16}. & A_1A_4. & A_1A_4.& A_1A_4.&
A_1A_4. & 16& [������ ���� ����]\cr
}
� ��� �����. � ����� ����~1 �����~T1 �������������� � ������������
��~T2 ������������ �������� ������, ����� ��������������~T2 �
������������ ��~T3 ������������ �������� ������ �~�.~�. � ����� ������,
����� �������� ������ ���������, �������� ���������� ��������� �������, �
������ ���������� ����������, ��� ��� �������� ���� �� ����� ������
�����. 퀏�����, ����~$S=18$, �� �������~$A_1$ ��~T4 �~T5 �����
���������� �� ����� ����~9; ��� �������� ������������ ������ ��~T4 �~T5
��� ������� �~T2 �~T3 ��~T1 �� ����� ����~10, ��� ��� ��� ���� ���������
�� ��������~$A_4$ ��~T4 �~T5 ��� ���������� � ����~11. � ������ �������,
��������� �������~$A_1$ ��~T1 �� ����������� ������ ������������ ����.
򀊈� �������, "����� ����" ��������� ����������. 噅 � �����
�������� ���������� ����� ������ �� ���������� � ��������� ������.

\excercises
\ex[22] � ������ ������� ����������� ������������� ���������� 񎁅�� � ��
������������ ���� ���~$T=5$ �~$S=16$. 䀉�� ������ ����������� ���������,
 � ������� ��� ��������� ���������� � ����������� $S=P^L$~���������
�������� �� $T=P+1\ge 3$~������. ��������� ����� ��������,
������� ����� ���� ����� ������ ������.

\ex[24] 呋� � ����������� ������ 񎁅�� $S=6$, �� �� ����� �� �������,
 ���~$S=16$ � ��� ������� 10~��������� ��������. 򎃄� ����~3 � ������� �
������ ��������� �� ��������� �������~$A_0$ ��~T4 �~T5; ����~4 �����
�� �������~$A_1$ ��~T2 �~T3 �~$D_2$ ��~T1; ����~5--8 �� ������ �� ������;
����~9 �������� ��~$A_6$ ��~T4. 듗�� �� ����������~T2 �~T3 ����� �����
����~3 � ����� ���������� ��������~$A_6$ ��~T4 � ������� ������������ �������.

�����, ���, ����������� �� ���� ����, �������� ��������� ��������� ��
���.~1, ����~$S$ �� �������� ������ ��������~$P$.
\rex[24] 񎑒����� �������, ������������ ��������� ���������~B, ����~$T=3$,
 �����������, ��� ������� 9~��������� ��������. �����, ���
��� ��������� �������� ������������ � ����� �����, � ����������
��������� � ���������~B, ������� ���������� ���������.

\ex[21] � ����~B3 ������� ��������� ���~$|A|[l, q]$, ��� �~$|A|[l, r]$
�~$-1$. �����, ��� ���� �� ���� �������� ������ ������, ��� ���
��������������� ������� �������~|A| ������� �� ���������������.

\ex[�25] ��~$S$---����� ��������� �������� � ��������� �������� ������
��� ���������~B.  ����� ���������~$S$ �� ��������� \emph{�� �����
���������} �� ����~B2?
%%378

\bye\input style
\chapno=5\subchno=4\subsubchno=3\chapnotrue

ꀑ������ �������, ������� ������������, ���������� �
"������� �������������" �������� �� ������, ���� ������� �������
������������� ������� �� ������ �.~5.4.2. ꀆ��� ������
������� ������������ ������ ������ �� \emph{����} ������. ���~2,
��������, ���������� ����������� ���������� ������������ ������� �~T1,
T2, T3, T4, T5 ��~T6, ����~T5 �� ������ ������ (��� ���� ��~T6 ����������
15~�������� ������������� �����~5), ����� ��������������� ������� �~T1, T2,
T3, T4 ��~T5, ����� ������������ ������� ��~T4, ������������ �������
��~T3 �, �������, ������������ ������� (�������� �����������) �~T1
��~T2. ���~3 ���������� ����� �� ������� ����� ���������� �������
������������ �������, ���� ���� ����� �� ������ ������, �����
��������������� �~�.~�. (���, ��� ����� ������ ����� ��������� ��
��������� �����~5.4.3.2.1, � ��~5.4.3!)

ߑ��, ��� �������� ����������� �������, � �� ����� ���� �� ��������.
􀊒������, ������, � ������ ����� ���� ��� ����������� �������� ������
��������� ������� ����� �������. ��������, ������� ���������� �������
������������, �������� � ����������� ������� ����������. 򎋜��~25 ��~950
�������������� �������� ����������� ����� ������. ᎋ���� �����
������� ��������� ������������ � ��������������� ��������.

� ������ ������ ����� ����������, ��� ��������� �����---�������� ������
������� � ��������� � �����������, ��� ��� ����������� ����������� �����
���������� ��� ����� $(T-1)\hbox{-�������}$ �������, � �� ����� ���
��������� ���������� $(T-1)\hbox{-�������}$, $(T-2)\hbox{-�������}$,
$(T-3)\hbox{-�������}$ �~�.~�., �� � ���������������� ��� ��������������
\emph{�����,} ��� �����������, ��� ����� � ����� ����! ꀊ �� ������ �
�.~5.4.2, ������� ������� ������� �� �������� ��������� �������������. �
����.~1 �������� �������������� ���������� ���������� ������� ��
�������� � �������� �������� �.~5.4.2.

텒����� ������� "������ �������������" ��� ���������� �������. 䋟 �����
���� �����
$$
\matrix{
\hbox{󐎂���} & T1 & T2 & T3 & T4 & T5 \cr
0 &   1 &   0 &   0 &   0 &  0 \cr
1 &   1 &   1 &   1 &   1 &  1 \cr
2 &   5 &   4 &   3 &   2 &  1 \cr
3 &  15 &  14 &  12 &   9 &  6 \cr
4 &  55 &  50 &  41 &  29 & 15 \cr
5 & 190 & 175 & 146 & 105 & 55 \cr
\multispan{6}\dotfill\cr
n & a_n & b_n & c_n & d_n & e_n \cr
n+1 & a_n+b_n+c_n+d_n+e_n & a_n+b_n+c_n+d_n & a_n+b_n+c_n & a_n+b_n & a_n \cr
}
\eqno(1)
$$
%%344
\htable{򀁋��� 1}%
{�������� ��������� ���������� �������}%
{\strut\hfill # && \bskip\hfill$#$\hfill\bskip\cr
녍��  & \hbox{����} & \hbox{����} & \hbox{������}\cr
 & \hbox{(� ������������)} & \hbox{(��� �����������)} &\hbox{�����}\cr
\noalign{\hrule}
 3 & 2.078\ln S+0.672 & 1.504\ln S+0.992 &  1.6180340\cr
 4 & 1.235\ln S+0.754 & 1.102\ln S+0.820 &  2.2469796\cr
 5 & 0.946\ln S+0.796 & 0.897\ln S+0.800 &  2.8793852\cr
 6 & 0.796\ln S+0.821 & 0.773\ln S+0.808 &  3.5133371\cr
 7 & 0.703\ln S+0.839 & 0.691\ln S+0.822 &  4.1481149\cr
 8 & 0.639\ln S+0.852 & 0.632\ln S+0.834 &  4.7833861\cr
 9 & 0.592\ln S+0.861 & 0.587\ln S+0.845 &  5.4189757\cr
10 & 0.555\ln S+0.869 & 0.552\ln S+0.854 &  6.0547828\cr
20 & 0.397\ln S+0.905 & 0.397\ln S+0.901 & 12.4174426\cr
\noalign{\hrule}
}

���� ���������� �������� ���� �����---�� ������������� �������� ��������
����� � ������� ���������� ����������� $(2T-1)\hbox{-���������}$. 퀏�����,
���� ���������� �������������������� �� ���.~73 ����� ������������� �����,
����� ������� �~190, 175, 146, 105 �~55! � ������� ���� ������������� ����
\picture{���.~73. ㅎ����������� ������������� ��������� �����.}
������� � ���� ������, � ����� ������, ��� ������������� �������,
������������� �� $(T-1)\hbox{-�������}$ �������, $(T-2)\hbox{-�������}$
�������,~\dots, ����������� �������, �������������� ���������������
\emph{���������} ���� ���� ����������.

\section *퀗������ ������������� ��������. 呋� ����� ���������
�������� � ���������������� �� ���� ����� 􈁎�����, �� �����,
��� ������, �������� ��������� �������. ���������� ������ ��������
����������, ��� ����� ������������ ��������� �������� �����������, ���
��� ��������� ������� ������ ������������
%%345
������ �������; ���� ������� 190~��������� ��������, �� ������ ������
�������������� ���� ���, ��� � ����������� ���� �������, �� ���� �������
191~�������, ��, ��������, ������� ��������� �������, � ������ ������
������ ����� �������������� ����� ���. � �������, � ���������������� �����
�������� ������ ������� ������. 䝂��~�.~􅐃���� ����� ������ ���
������������ ��������� �������, ��� ������ �������� �� ����� ������
\picture{
  ���.~74. ������������� ���������� ������� � ��������������
  �� ���������~D.
}
���� ������� �������� � ����������� ����������� �����. 呋� ������ �����
����������� (������ ������� "����������" ������ ��������� ��������� ��
��������� � "����������" �������, ��� � ���������~5.4.2D), �� �������
������������ ������� ������� � ������ �� �������, ��� ���������� �� ���.~74.

��������, ��� $(a, b, c, d, e)$, ���~$a\ge b \ge c \ge d \ge e$---������
�������������. ���������� ������������ ����� �����������
� ����������� ���������� ������������, �� ����� �����������, ��� ��������
�������������---���~$(e, d, c, b, a)$,
%%346
�.~�.~$a$~�������� ��~T5, $b$~��~�4 �~�.~�. 񋅄����� ������
�������������---��� $(a+b+c+d+e,  a+b+c+d, a+b+c, a+b, a)$;
� ���� ���� ������������� ������, ��� �� ��������� ����� ����������
������, �� ����� �������, ��� ����� ��������
��������������~$(D_1, D_2, D_3, D_4, D_5)$ ��������� ��������, ���
$$
\displaynarrow{
D_1 \le a+b+c+d,\quad D_1 \le a+b+c,\quad D_3\le a+b,\cr
D_4 \le a,\quad D_5=0;\qquad D_1\ge D_2 \ge D_3 \ge D_4 \ge D_5.\cr
}
\eqno(2)
$$

� ������ ������������ ����, ��� ��� ��������� ������� ���������� ��
������ � ����� ������� �����. �����������, ��� ������ ������ �������
���� $a$~�������� ����������� ������������ �������, ����� $b$~��������
����������� ��������������� �~�.~�. 퀘� ���� ������� � ������������
��������� �������� ����� �������, ����� �������� ������� ������������.
󄎁�� ��������� ������ ������ ������� ��������� �������:

1.~呋�~$D_4=a$, �� �������~$a$ �� ����~$D_1$, $D_2$, $D_3$, $D_4$ �
�������, ���~T5---��������� �������. 呋�~$D_4<a$, �� ����� $a$~�������� �
����~T1 ��~T5, ��������� ���������� ��������� ����� ��������� ��������
�� ������~T1--T5 ���, ����� ����� ��������~$D_1$, $D_2$, $D_3$, $D_4$
������������� ������������
$$
\displaynarrow{
D_1\le b+c+d,\quad D_2\le b+c,\quad D_3\le b,\cr
D_4=0;\qquad  D_1\ge D_2\ge D_3\ge D_4.\cr
}
\eqno(3)
$$
򀊈� �������, ����~$D_2$ ���� �������������~$\le b+c$, �� ��
�� ���������� �� ������ ���������� ������� � ���� ����� �� ������ ����; �
�� �� �����, ����~$b+c<D_2\le a+b+c$, �� ���������� �����~$D_2-b-c$
��������� ��������.

2.~(���� ��� ���������� ����~1, �� � ��������� "�������".) 呋�~$D_3=b$,
�� �������~$b$ �� ����~$D_1$, $D_2$, $D_3$ � �������, ���~T4---���������
�������. 呋�~$D_3<b$, �� ����� $b$~�������� � ����~T1--T4, ��������, ����
����������, ����� ��������� ��������, ����� �������
$$
D_1\le b+c,\quad D_2\le b,\quad D_3=0;\qquad D_1\ge D_2\ge D_3.
$$

3.~� ��� �����.

셒�� 􅐃����� ������������� �������� �� ������ ����� �����������������,
���������� ������� �������� � ������~3 �� �������~4 �~(1). 䎏�����, ���
"����������" ����� (T1,~\dots, T5) ��������� ��������������
$(5, 9, 12, 14, 15)$~�������� � ��� �� ����� ������� ��� � �������� �����
��~$(55, 50, 41, 29, 15)$. ��� ��������� ����� ���� ������ �������� ���:
%%347
\ctable{
$#$\hfill&&\hfill\bskip$#$\bskip\hfill\cr
 & \hbox{䎁�����} &\hbox{䎁�����} &\hbox{䎁�����} &\hbox{䎁�����} &\hbox{䎁�����} &\hbox{񝊎���������}\cr
\hbox{���} &\hbox{� T1} &\hbox{� T2} &\hbox{� T3} &\hbox{� T4} &\hbox{� T5} &\hbox{��������}\cr
(1, 1)& 9 &  0 &  0 &  0 &  0 & 15+14+12+5\cr
(2, 2)& 3 & 12 &  0 &  0 &  0 &  15+14+9+5\cr
(2, 1)& 9 &  0 &  0 &  0 &  0 &    15+14+5\cr
(3, 3)& 2 &  2 & 14 &  0 &  0 &    15+12+5\cr
(3, 2)& 3 & 12 &  0 &  0 &  0 &     15+9+5\cr
(3, 1)& 9 &  0 &  0 &  0 &  0 &       15+5\cr
(4, 4)& 1 &  1 &  1 & 15 &  0 &       14+5\cr
(4, 3)& 2 &  2 & 14 &  0 &  0 &       12+5\cr
(4, 2)& 3 & 12 &  0 &  0 &  0 &        9+5\cr
(4, 1)& 9 &  0 &  0 &  0 &  0 &          5\cr
}
񍀗��� �������� ������ �������� ��~T1, ����� $(3, 12)$---��~T1 �~T2 �~�.~�.
呋� ���� �����������, ������, �� ����� ����~$(3, 2)$, �� "�������������
��������" ����������~$15+9+5$. ��� ��������, ��� �� �������� ������������
������� 15~��������,  ������������ ������� 9~�������� � ������������
������� 5~�������� ����������� ���������� ��������� ��������.
䐓���� �������, $15+9+5$ ��������, �������������� �� ������~3,
�� �������������� � ������� ������ ���� �������.

񋅄����� �������� �������� ��������� ���� �������.

\alg C.(񎐒������ ��������� �������� �� ����������� ��������������.) ����
�������� ������������ ��������� ������� �� ������ ������� �� ��������,
���� ����� ��������� �������� �� �����������. 瀒�� �� ����������, ���
������� ������� �����, �����������, ��� ������� $T\ge 3$~��������������
���������, ��� ���� ������������ ����� �������
$(T-1)\hbox{-�������}$~������� �
�������� ����������� ������� �����������. 녍��~$T$ �����
���� ������������ ��� �������� �����, ��� ��� �� ��� �� �������� �� ����
��������� �������. �������� �������� �� ���������� ���������:
{\let\mypar=\par\ctable{
$#$,\bskip\hfill&$#$:\bskip\hfill&
\vtop{\parindent=0pt \hsize=13cm #\mypar}\cr
|A|[j]    & 1 \le j \le T &
   ������ ������ ��������� �������������, ������� ���� ����������. \cr
|AA|[j]   & 1 \le j \le T &
   򎗍�� ��������� �������������, � �������� �� ���������. \cr
|D|[j]    & 1 \le j \le T &
   ����� ��������� ��������, �������������� ��������������� �� ����������
   �������������� ���������� � �������~$j$. \cr
|M|[j]    & 1 \le j \le T &
   쀊��������� ����� ��������� ��������, ������� ���������� ����� ��
   ���������� �������������� ���������� � �������~$j$. \cr
|TAPE|[j] & 1 \le j \le T &
   펌�� ����������� ��������������� ����������, ����������������
   ����������� ��������������� ���������� � �������~$j$.\cr
}}
%%348
\st[퀗������ ���������.] 󑒀������ $|A|[k]\asg |AA|[k]\asg |D|[k]\asg 0$
���~$2\le k \le T$; ���������� $|A|[1]\asg 0$, $|AA|[1]\asg 1$,
$|D|[1]\asg 1$; ����������~$|TAPE|[k]\asg k$ ���~$1\le k \le T$. 퀊����,
����������~$i\asg T-2$, $j\asg 1$, $k\asg 1$, $l\asg 0$, $m\asg 1$ �
������� � ����~\stp{5} (��� ������� �������� ����� �� �������� ������
������ ��������������� �� ���������� ����� � ��������������� ����������
����������� ����������).

\st[퀗��� ����� �������.] (� ������ ��� �������� ������ �������������.
� ��� ��� ��� ������� �������� ������, �� ���������� ������������� �
���������� ������.) 󂅋�����~$l$ ��~1. 󑒀������~$|A|[k]\asg |AA|[k]$
���~$1\le k \le T$, ����� ����������~$|AA|[T-k]\asg |AA|[T-k+1]+|A|[k]$
���~$k=1$, 2,~\dots, $T-1$ (� ����� �������). 󑒀������ $(|TAPE|[1],
|TAPE|[2],~\ldots, |TAPE|[T-1])\asg (|TAPE|[T-1],~\ldots, |TAPE|[2],
|TAPE|[1])$ � ����������~$|D|[k]\asg |AA|[k+1]$ ���~$1\le k < T$.
퀊����, ����������~$i\asg 1$.

\st[퀗��� ����������~$i$.] 󑒀������~$j\asg i$. (�������~$i$
�~$j$ ������������ "���~$(i,j)$" � �������, �������������� ����� 􅐃�����.)

\st[퀗��� ���~$(i, j)$.] 󑒀������~$k\asg j$ �~$m\asg
|A|[T-j-1]$. 呋�~$m=0$ �~$i=j$, �� ����������~$i\asg T-2$ �
��������� �~\stp{3}; ����~$m=0$ �~$i\ne j$, ��������� �~\stp{2}.
(�������~$m$ ������������ ����� ����� ��������, ������� ������
���� �������� �� �����~$|TAPE|[k]$; $m$~������ �����~0, ������ ����~$l=1$.)

\st[₅��� �� �����~$|TAPE|[k]$.] 瀏����� ���� ������� ��
����� �����~$|TAPE|[k]$ � ���������~$|D|[k]$ ��~1. 瀒��, ����
���� ��������, ���������� ��� ����� � ������� � ����~\stp{7}.

\st[��������.] 󌅍�����~$m$ ��~1. 呋�~$m>0$, ��������� � ����~\stp{5}.
 � ��������� ������ ���������~$k$ ��~1; ����~$k>0$, ����������~$m\asg
|A|[T-j-1]-|A|[T-j]$ � ��������� �~\stp{5}, ����~$m>0$. � ��������� ������
���������~$j$ ��~1;
����~$j>0$, ������� � ����~\stp{4}. � ��������� ������ ���������~$i$
��~1; ����~$i<T<1$, ��������� � ����~\stp{3}. � ��������� ������ �������
�~\stp{2}.

\st[������� � �������.] (� ����� ������� ��������� �������������
���������, � �������~|A|, |AA|, |D| �~|TAPE| ��������� ��������� ����
���� � ������ ������.) 󑒀������~$|M|[k]\asg|AA|[k+1]$ ���~$1\le k < T$ �
����������~$|FIRST|\asg 1$. (�������~|FIRST| ��������� ���������
�������� ������ �� ����� ������� ������� �������.)

\st[ꀑ���.] 呋�~$l=0$, ������������; ���������� ���������, �����
��������� ��~$|TAPE|[1]$. � ��������� ������ ���~$p=T-1$, $T-2$,~\dots, 1
(� ����� �������) ��������� $p\hbox{-�������}$ ������� �
����~$|TAPE|[1]$,~\dots, $|TAPE|[p]$ ��~$|TAPE|[p+1]$ ��������� �������:
%% 349

呋�~$p=1$, �� ������������ ����������� �������
������� ����������~$|TAPE|[2]$ � �������~$|TAPE|[1]\xchg |TAPE|[2]$. �
��������� ������, ����~$|FIRST|=1$ �~$|D|[p-1]=|M|[p-1]$, �� ������������
$p\hbox{-�������}$ �������, ������ ������� $|TAPE|[p]\xchg |TAPE|[p+1]$,
���������~$|TAPE|[p]$ � �����~$M[p-1]$ �� �������~$|D|[1]$,~\dots,
$|D|[p-1]$, $|M|[1]$,~\dots, $|M|[p-1]$. � ��������� ������
�������~$|M|[p-1]$ �� ����~$|M|[1]$,~\dots, $|M|[p-1]$. 瀒�� ����� ��
������ ������� � ������~$|TAPE|[j]$, �����, ���~$1\le j \le p$
�~$|D|[j]\le |M|[j]$; ������� ������� �� �������~$|D|[j]$, ������,
���~$1\le j \le p$ �~$|D|[j]>|M|[j]$, � ��������� �������� �������
��~$|TAPE|[p+1]$. ������� ������, ���� $|TAPE|[p]$ �� ������ ������.
瀒�� ����������~$|TAPE|[p]$ �~$|TAPE|[p+1]$.

\st[������� �� ���� �������.] 󌅍�����~$l$ ��~1,
����������~$|FIRST|\asg 0$, ����������
$(|TAPE|[1],~\ldots, |TAPE|[T])\asg (|TAPE|[T],~\ldots, |TAPE|[1])$. (�
����� ������� ���~|D| �~|M|---���� � �������� ���������.) ⅐������ �~\stp{8}.
\algend

����~C1--C6 ����� ��������� ��������� �������������, ����~C7--C9 ���������
�������; ��� ��� ����� ���������� ���������� ���� �� ������, � ����� ����
�� �������~$|M|[k]$ �~$|AA|[k+1]$ � ����� � ��� �� ������� ������.
\picture{���.~75. ꀑ������ ������� �� ����������� ��������������.}
\section *������ ���������� �������. ꀑ������ ������� ��������� �������
� ������� ������, ��� �����������. � ���� ������ �������� ���������,
��������� �������� ����� ������������� ������. 퀑��������� �����������
���������, �������������� ���������� �����������, ��������������
���������������� ��������� �������������, ������ ��� ������ ������, ���� �����
%%350
����� ��� ����� ��������� �������, ��������� �������---���� ������������! �
������� ����� ���� ���� �� ������ ��������, ������� ������ �������� ��
������ ��������� �����������.

䋟 �������� ���������� ������ ����� ����.  ���� ����� ���������
�������� �������, ������� ���������� �� ������ ������~$T$. 񎎒�������~(1)
�������� � ������ �������� �������:
$$
\eqalignter{
a_n &= a_n &=\perm{0}{0}a_n,\cr
b_n &= a_n-e_{n-1}=a_n-a_{n-2} &=\perm{1}{0}a_n-\perm{2}{2}a_{n-2},\cr
c_n &= b_n-d_{n-1}=b_n-a_{n-2}-b_{n-2} &=\perm{2}{0}a_n-\perm{3}{2}a_{n-2}+\perm{4}{4}a_{n-4},\cr
d_n &= c_n-c_{n-1}=c_n-a_{n-2}-b_{n-2}-c_{n-2} &=\perm{3}{0}a_n-\perm{4}{2}a_{n-2}+\perm{5}{4}a_{n-4}-\perm{6}{6}a_{n-6},\cr
e_n &= d_n-b_{n-1}=d_n-a_{n-2}-b_{n-2}-c_{n-2}-d_{n-2} &=\perm{4}{0}a_n-\perm{5}{2}a_{n-2}+\perm{6}{4}a_{n-4}-\perm{7}{6}a_{n-6}+\perm{8}{8}a_{n-8}.\cr
}
\eqno(4)
$$
������~$A(z)=\sum_{n\ge0} a_n z^n$,~\dots, $E(z)=\sum_{n\ge0}e_n z^n$ �
��������� ����������
$$
\eqalignno{
q_m(z)&=\perm{m}{0}-\perm{m+1}{2}z^2+\perm{m+2}{4}z^4-\cdots=\cr
      &=\sum_{k\ge 0}\perm{m+k}{2k}(-1)^k z^{2k}
        = \sum_{0\le k \le m}\perm{2m-k}{k}(-1)^{m-k} z^{2m-2k}. & (5)\cr
}
$$
���������~(4) ������ ����� ����������� ���,
���~$B(z)-q_1(z)\times A(z)$,~\dots, $E(z)-q_4(z)A(z)$ �������� �
�������� ������, ���������������
��������� ��������, � ������ ���������~$a_{-1}$, $a_{-2}$, $a_{-3}$,~\dots,
������� ���������� �~(4) (��� ���������~$n$), �� �� �~$A(z)$. �����
�������� ���������� ��������� �������, �������� ������������ �����������
� �������� ������� ��� ������������� ������� �� ������~$-8$:
\ctable{
\hfill$#$\bskip&&\hfill\bskip$#$\bskip\cr
\hfill n & \hfill a_n & \hfill b_n & \hfill c_n & \hfill d_n & \hfill e_n \cr
 0 &  1 &   0 &  0 &   0 &  0\cr
-1 &  0 &   0 &  0 &   0 &  1\cr
-2 &  1 &  -1 &  0 &   0 &  0\cr
-3 &  0 &   0 &  0 &  -1 &  2\cr
-4 &  2 &  -3 &  1 &   0 &  0\cr
-5 &  0 &   0 &  1 &  -4 &  5\cr
-6 &  5 &  -9 &  5 &  -1 &  0\cr
-7 &  0 &  -1 &  6 & -14 & 14\cr
-8 & 14 & -28 & 20 &  -7 &  1\cr
}
(䋟 ���� ���� ������� ���� �� �����������, ������ ������ � ���������~$n$
���� �� �������� ������ �� ���� �������.) 򀉍�
������������������~$a_0$, $a_{-2}$, $a_{-4},~\ldots=1, 1, 2, 5, 14,~\ldots$
��������� ������������ ������������ �� �����������, ��� ���
%%351
��� ������������������ ����������� � ����� � ����� ������� �������������
����������� (��������, � ���.~2.2.1-4 � �������~2.3.4.4-13)). 蒀�, ��
������������, ��� � ������ $T$~����
$$
\eqalignrem{
a_{-2n}&=\perm{2n}{n}{1\over n+1} & ��� $0\le n \le T-2$; \cr
a_{-2n-1}&=0 & ��� $0\le n \le T-3$.\cr
}
\eqno(6)
$$
����� ��������� ������������ ����� �������������, ���������� ��������,
���~(6) �~(4) �������� � ���������� ����������� ��� �������~0 �~1. 䋟
������~1 ��� ��������, � ��� ������~0 ��� ���� ���������, ���
$$
\perm{m}{0}a_0-\perm{m+1}{2}a_{-2}+\perm{m+2}{4}a_{-4}-\perm{m+3}{6}a_{-6}+\cdots
=\sum_{k\ge0}\perm{m+k}{2k}\perm{2k}{k}{(-1)^k\over k+1}
=\delta_{m0}
\eqno(7)
$$
���~$0\le m \le T-2$. � �������, ��� ����� ����� ��������� ������������
�������� (��� "������~2", ���� �� �������� �������� � ������ �.~4.2.6).

򅏅�� ����� ��������� ������������~$B(z)-q_1(z)A(z)$ �~�.~�. ����������,
��������, ����������� ���~$z^{2m}$ �~$D(z)-q_3(z)A(z)$. � �����
$$
\eqalign{
\sum_{k\ge0}\perm{3+m+k}{2m+2k}(-1)^{m+k}a_{-2k}
&=\sum_{k\ge0}\perm{3+m+k}{2m+2k}\perm{2k}{k}{(-1)^{m+k}\over k+1}=\cr
&=(-1)^m\left(\perm{2+m}{2m-1}-\perm{3+m}{2m}\right)=\cr
&=(-1)^{m+1}\perm{2+m}{2m}\cr
}
$$
�� ���������� "������~3" �~�.~1.2.6. 򀊈� �������, �� ������ �������
$$
\eqalign{
A(z) &=q_0(z)A(z);\cr
B(z) &=q_1(z)A(z)-q_0(z);\cr
C(z) &=q_2(z)A(z)-q_1(z);\cr
D(z) &=q_3(z)A(z)-q_2(z);\cr
E(z) &=q_4(z)A(z)-q_3(z).\cr
}
\eqno (8)
$$
ꐎ�� ����, �����~$e_{n+1}=a_n$; �������������, $zA(z)=E(z)$ �
$$
A(z)=q_3(z)/(q_4(z)-z).
\eqno (9)
$$

��������� ������� ���� �������� ��� ������ $q\hbox{-�����������}$,
������� �� ����� ����� �������~$q$. � ���� ��������� ������� ���.~1.2.9-15,
��� ��� ��� ���� ��������� � ���������
%%352
����, ������� ����� ���� �������� ���
$$
q_m(z)={((\sqrt{4-z^2}+iz)/2)^{2m+1}+((\sqrt{4-z^2}-iz)/2)^{2m+1}
\over \sqrt{4-z^2}}
\eqno(10) $$
⑅ ����������, ���� ������ ��������~$z=2 \sin\theta$:
$$
\eqalignno{
q_m(2\sin\theta)=&
{(\cos\theta+i\sin\theta)^{2m+1}+(\cos\theta-i\sin\theta)^{2m+1}\over 2\cos\theta}=\cr
&={\cos(2m+1)\theta\over \cos\theta}. & (11)\cr
}
$$
(��� ���������� ���������� ������, ��� ����������~$q_m(z)$ ������
�������� � ����������; � �������������, �������� � ���������������
�������, �����, ���~$q_m(z)$, �� ��������, ��������� �������� ������� ����,
 � ������~$(-1)^m U_{2m}(z/2)$ � ������� ������������.)

򅏅�� ����� ���������� ����� ����������� �~(9):
$q_4(2\sin\theta)=2\sin\theta$ �������� �
$$
\cos 9\theta = 2 \sin \theta \cos \theta = \sin 2\theta.
$$
������� ����� ����������� ��������, ����
������~$\pm9\theta=2\theta+\left(2n-{1\over2}\right)\pi$; ���
�����~$\theta$ ���� ����� ����������� �~(9) ��� �������,
���~$\cos\theta\ne 0$. (呋�~$\cos\theta=0$, ��~$q_m(\pm2)=\pm(2m+1)$,
������� �� �����~$\pm2$.) 񋅄���������, �������� 8~��������� ������:
$$
\displaylines{
q_4(z)-z=0 \qquad \hbox{ ��� }  z=2\sin{-5\over 14}\pi,\quad
2\sin{-1 \over 14}\pi,\quad 2\sin{3 \over 14}\pi, \cr
2\sin{-7 \over 22}\pi,\quad 2\sin{-3 \over 22}\pi,\quad
2\sin{1 \over 22}\pi, \quad 2\sin{5 \over 22}\pi,\quad 2\sin{9 \over 22}\pi.\cr
}
$$
� ���~$q_4(z)$---��������� �������~8, �� ���� ��� �����. ��� ��� ��
���� �������� ����~$q_3(z)=0$, ��� ���~$q_3(z)$ �~$q_4(z)-z$  ����� �����
��������� ��������� ������� �������. ������ ���� ������ ���������
��������������� ���������� �������������~$A(z)$, ���� ���������~(9) �
������������ �����.

���� � ������������ ������ ������ $T$~����,
�������~$\theta_k=(4k+1)\pi/(4T-2)$. ��������� �������~$A(z)$ ���
$T\hbox{-���������}$ ��������� ����� ��������� ���
$$
{4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}{\cos^2\theta_k\over 1-z/(2\sin\theta_k)}
\eqno(12)
$$
(��.~���.~8); �������������,
$$
a_n={4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}\cos^2\theta_k \left({1\over 2\sin\theta_k}\right)^n.
\eqno(13)
$$
%% 353
񎎒�������~(8) �������� ������ � ����������� ��������:
$$
\eqalign{
b_n&={4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}\cos\theta_k\cos3\theta_k\left({1\over 2\sin\theta_k}\right)^n;\cr
c_n&={4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}\cos\theta_k\cos5\theta_k\left({1\over 2\sin\theta_k}\right)^n;\cr
d_n&={4\over 2T-1}\sum_{-T/2<k<\floor{T/2}}\cos\theta_k\cos7\theta_k\left({1\over 2\sin\theta_k}\right)^n\cr
}
\eqno(14)
$$
�~�.~�. � ���.~9 ��������, ��� ��� ��������� ����������� ��� ����~$n\ge0$,
� �� ������ ��� �������~$n$. � ������ ����� ���� �~$k=0$ �����������
����������� ��� ���������, �������� ����~$n$ ���������� ������;
�������������, "��������� �����" ����
$$
{1\over 2\sin\theta_0}={2\over\pi}T-{1\over\pi}+{\pi\over 48T}+O(T^{-2}).
\eqno(15)
$$

ꀑ������ ���������� ������� ���� ����������� �.~�.~ꀐ�����
[Proc.\ IFIP Congress (1962), 62--66], ������� ������� ��������� ����������
��� ��������� ��������~$T$, � 䝂���� 􅐃������
[{\sl CACM,\/} {\bf 7} (1964), 297], ������� ������ ������ ��� ����� �
��������������� ���������~(15)  ��������� �����.
녒�� 1964~�.\ �.~�.~􋎉� ������� ����� ���~$1/(2\sin\theta_0)$
��� ��������� �����, ��� ��� ������ �������
����� ���� ������������ ��� ����~$T$. ㋓����� ������ ��������� ����� ���
���������� �������� �.~�.~𝉍�
[{\sl Canadian J.~Math.,\/} {\bf 18} (1966), 332--349],
������� ��������� �� ��� ���������� ������ �����,
�� ���� ���� � �����������. 𝉍� �������� �������� � �����������
(���.~73) � ����� ����� ������ ���������� ������� ���� �����. 􋎉�
�~𝉍� � ����� ��������������� ����������� � ��������� (��.~���.~6).

\section 쎄�������� ��������� ����������. 呋� ��������� ��� ���� �����,
�� ����� ��� ����� ��������� � ������� ��������� ���������� �����
����������. 퀏�����, �� ����� �������~T1--T5 ��~T7, �����~T1--T4 ��~T6,
�����~T1--T3 ��~T5 (������� � ����� ������� ��� ����������), �����~T1--T2
��~T4 � ������ ��������� ������, ����� ��~T4 ����� ����������
������������ ������� ������. ������������� ����� �������� �����
����������� �� ��������� ����������� ���� ������� ����������
������ (���������� ����������� ��.~�~�.~5.4.6).

񕅌� "�������������� �������", ������� �������� ����������� � ���������
����� ��� ������� ������, ���� ���������� �.~�.~ꍓ��� � [{\sl CACM,\/}
{\bf 6} (1963), 585--587]. ꀆ��� ���� ������� ��~$(T-1)\hbox{-��������}$,
$(T-2)\hbox{-��������}$,~\dots, $P\hbox{-��������}$ �������, ��� $P$---�����
������������� ����� �����~1 �~$T-1$. 呋�~$P=T-1$, �� ���---�����������
�����; ����~$P=1$, ���---������
%%354
��������� �����; ����~$P=2$, ���---��������� ����� ��� ���
�����������. ������ ����� ����� ��� �������� �.~�����
[{\sl IBM Systems J.,\/} {\bf 5} (1966), 226--247] �~�.~�.~ᓐ���
[Proc. IFIP Congress, {\bf 1} (1971), 454---459]. ᓐ� �����
������������ �������~$\sum T_n(x) z^n$ ���
�������~$(P, T)\hbox{-��������������}$ �������,
���������� �����������~(5.4.2-16); ��
�������, ��� ��������� ��������~$P$ (� ����� ������ ����������� �����
�������������� ��������� ��������), ��� ������� ��~$S$
���~$S\to\infty$ (���� ��������������� ������������ ����� �������������
� ���������� �������� ���������), ���� ��������������
$(2, 3, 3, 4, 4, 4, 3, 3, 4)$ ���~$T=(3, 4, 5, 6, 7, 8, 9, 10, 11)$.
��� ��������~$P$ �
������~$T$ ������� ����������� � ������� ����������, � �� ������������
������, � �����������, ��� ������������� ������� ������� �� ������
����������� ����� ����������. � ������ �������, ��� ����������� ������
������� � ������������� ��������� ��������, ��� ������� � �.~5.4.2, ������
����������� ����� ������� ��������� ����� ���� ������������� �������.
� ���������, ����������� ������������� ������������ ������ �����������.

�.~�.~鎍��� [{\sl BIT,\/} {\bf 6} (1966), 129--143] ����������
��������� ����������������� � ������������ �������; �����������
����������������� ������� � ����������� ��������� ���� ����������
�.~㎒��� [Digital Computer User's Handbook, ed.~by.~M.~Klerer
and~G.~A.~Korn (New York: McGraw-Hill, 1967), 1.311--1.312]; �����
����������� ���� � ������ ������ ��������� �����.

\excercises
\ex[10] 葏������ ����.~1, �������� ��������� ������� � ���������
� �.~5.4.2 ������� ������������ ������� � "������������ ����". ꀊ��
����� �����? (␅����� ��������� ����������.)

\rex[22] 񐀂���� ��������� ���������� � ����� �������,
������������ ��������~C, � ����������� ���������� � ����� �������,
������������ ��������~5.4.2D ꀊ�� �������� � �������� �� �a�e���e?

\ex[20] 񎑒����� �������, ������������, ��� ���������� ��� ���������� ��
����� ������ 100~��������� �������� ��� ������ ���������~C.

\ex[�20] (�.~�.~𝉍�.) "ꀑ������ ������������� $n\hbox{-��}$ ������"
���� ���������������, ������������ ��������� ������� (� ������ ����� ����):
$\set{1, 0, 0, 0, 0}$ ���� ��������� ������������� �������� ������;
����~$\set{a, b, c, d, e}$---��������� ������������� $n\hbox{-��}$~������,
��~$\set{a+b+c+d+e, a+b+c+d, a+b+c, a+b, a}$ ����� ���������
�������������� $(n+1)\hbox{-��}$ ������ (� ��� ��������������� ��
�����������, �� �� ������������� ������������� $n\hbox{-��}$~������ �����
���������� ��~5 ��������� ������������� $(n+1)\hbox{-��}$~������.)
(a)~䎊�����, ��� \emph{�����}
���������������~$\set{a, b, c, d, e}$ �� ������� ������� ����� ��������
��������� �������������� $n\hbox{-��}$~������ ��� ���������~$n$.
(b)~䎊�����, ��� �������������, ������������ � ��������� ����������,
\emph{����������} � ��� ������, ��� ����~$\set{a, b, c, d, e}$---�����
������������� $n\hbox{-��}$~������, ������~$a\ge b \ge c \ge d \ge e$, ��
����� �����~$a\le a_n$, $b\le b_n$, $c\le c_n$, $d\le d_n$, $e\le e_n$,
���~$\set{a_n, b_n, c_n, d_n, e_n}$---�������������, ������������ �~(1).

\rex[20] 䎊�����, ��� ��������� �����, ������������ �~(1), �������������
%%355
������
$$
a_k a_{n-k}+b_k b_{n-k}+c_k c_{n-k}+d_k d_{n-k}+e_k e_{n-k}=a_n
\rem{���~$ 0\le k \le n$.}
$$
[\emph{󊀇����:} ��� ������� ��������� ����� ����������� �����������,
������� �������� ��������� ����� ��������� � ������� $k\hbox{-��}$~�������
������ ��������� ����������.]

\ex[�20] 퀉���� $5\times5$-�������~$Q$, �����, ��� ������ ������~$Q^n$
�������� ��������� ����� ��� ����� ����~$a_n b_n c_n d_n e_n$ ���
����~$n\ge 0$.

\ex[�20]  ������� ��� ��������� ������� ����������� �
������� ������������� $a_n$~��������� ��������, ������� ������� ���
�������� ������������� ������, ����� ����������� ����������� �������.

\ex[��23] ⛂����� �������~(12).

\ex[��26] ⛂����� �������~(14).

\rex[�28] ⌅��� �������~(4) ��� �������� ��������� ����� ��������������
� �������� �������� �����������
$$
\eqalignter{
e_n&=a_{n-1}  &= \perm{1}{1}a_{n-1};\cr
d_n&=2a_{n-1}-e_{n-2} &=\perm{2}{1}a_{n-1}-\perm{3}{3}a_{n-3};\cr
c_n&=3a_{n-1}-d_{n-2}-2e_{n-2} &=\perm{3}{1}a_{n-1}-\perm{4}{3}a_{n-3}+\perm{5}{5}a_{n-5}\cr
}
$$
�~�.~�. ����
$$
r_m(z)=\perm{m}{1}z-\perm{m+1}{3}z^3+\perm{m+2}{5}z^5-\ldots,
$$
��������~$A(z)$, $B(z)$ �~�.~�.\ ����� ��� $r\hbox{-����������}$.

\ex[�38] ��
$$
f_m(z)=\sum_{0\le k \le m} \perm{\floor{(m+k)/2}}{k}(-1)^{\ceil{k/2}}z^k.
$$
䎊�����, ��� ������������ �������~$A(z)$ ��� $T\hbox{-���������}$
��������� ����� �����~$f_{T-3}(z)/f_{T-1}(z)$, ������ ��������� �
����������� ����� ��������� �� ����� ����� ���������.

\ex[�40] 䎊�����, ��� ����� ������������� 􅐃����� ���������� � ���
������, ��� ��� ����� ������ ������ ���������� ��������� ��������,
���������������~(2), �� ����� ������� ������� ����� ��������������
�� ������ ��������� ��������, \emph{��� �������} ��� �� ����� �����
������� ������������ ��������� �����~C7--C9.

\ex[40] � ������ ������������ ������� ����� ������� ��������� ���������
����� ���������� �������������� �����. ������������ ��� ����. (퀏�����,
�����, ���������� � ������, �������� �������� ��������� �����~T4;
�� ����� �� ����� ���������~T4 �� ������ ���� ������� ���������� �������?)

\subsubchap{������ ����� � �������� �����������} %% 5.4.4
썎��� �������������� ���������� ��������� ������ ����� � �����������,
��������������� ����, � ������� ��� ������ �� ���. 񕅌� �������, �
�������� �� ����������� �� ��� ���, ������ ���������� ���������� �� �����
� ������ �����������,
%%  356
\bye
