\input style
\chapnotrue\chapno=5\subchno=4\subsubchno=2
��� ��� � �����~A3 �~A5 ����������� ������ "�������� �������",
�.~�.\ ����������� ����� 25\% �������.

� ���������������� ����� ���� ��������� ��������� �����������, ����
������ � $F_n$~�������� �� �����~T1 � � $F_{n-1}$~�������� ��~T2,
���~$F_n$ �~$F_{n-1}$---���������������� ����� 䈁������. ����������,
��������, ������~$n=7$, $S=F_n+F_{n-1}=13+8=21$:
{\def\cm{\hfil$-$\hfil}\def\hd#1{\multispan{3}\hfil#1\hfil}\let\f=\hfil\ctable{
#\bskip&
#&#&#\bskip&\bskip#&#&#\bskip&\bskip#&#&#&#\hfil\cr
       &\hd{ᎄ�������~�1}                      & \hd{ᎄ�������~�2}        & \hd{ᎄ�������~T3}       & ���������� \cr
䀇�~1.& 1, 1, 1, 1, &1, 1, 1, 1, &1, 1, 1, 1, 1& 1, 1, &1, 1, 1, 1, & 1, 1 &          &       &       & ��������� �������������\cr
䀇�~2.&             &            &1, 1, 1, 1, 1&       &\cm         &      & 2, 2, 2, & 2,2,  & 2,2,2 & ወ���� 8~�������� ��~T3\cr
䀇�~3.&             &\cm         &             &       &3, 3, 3, 3, & 3    &          &       & 2,2,2 & ወ���� 5~�������� ��~T3\cr
䀇�~4.&             &\f  5, 5, 5 &             &       &\f 3,       & 3    &          & \cm   &       & ወ���� 3~�������� ��~T1\cr
䀇�~5.&             &\f        5 &             &       &\cm         &      &          &\f 8,8 &       & ወ���� 2~�������� ��~T3\cr
䀇�~6.&             &\cm         &             &       &\f 13 \f    &      &          &\f   8 &       & ወ���� 1~������� ��~T2\cr
䀇�~7.&             &\f 21 \f    &             &       &\cm         &      &          &\cm    &       & ወ���� 1~������� ��~T1\cr
}}%
����� "2, 2, 2, 2, 2, 2, 2, 2", ��������, ���������� ������
�������� ������������� �����~2, ���� ������� ������������� ����� �������
���������� ������� ������~1. ����� � ���� ������� ����� 䈁������!

������ ������ �� ������ ������������ ������ ����~1 �~7;
����~2 ������������ ���� $16/21$~������ ����� ��������� ��������,
����~3---����~$15/21$ �~�. �.; ����� �������, ��������� �����
"��������" �����~$(21+16+15+15+16+13+21)/21=5{4\over7}$, ����
������������, ��� ��������� ������� ����� �������� ������
�����. ��� ��������� �������, ��� ������������� ���� ����������
��������� ��������� �� 8~�������� �� ���������� ���� �� ��������� ��������.
�� ������, ��� � ����� ������ ��� ����� 䈁������ ������� ��������������
$1.04\log_2 S+0.99$~��������, ��� ������ �� ��������� �
\emph{����������������} ����������������  ��������, ���� ��� ����������
������ ��� �����.

풓 ���� ����� �������� �� ������ $T$~���� ��� �����~$T\ge 3$, ���������
$(T-1)\hbox{-�������}$~�������. �� ������, ��������, ��� � ������ �������
���� ��������� ������ ����� $0.703\log_2 S+0.96$~�������� �� ������.
���������� ����� ���������� ���������� ����� 䈁������. ����������
��������� ������ � ������ �������:
\ctable{
#\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&$#$\hfil\bskip&\hfil$#$&\hfil$\hbox{}#$\cr
       &       &       &       &       &       &       & \hbox{爑�� �������������� ��������� ��������}\cr
       & T1    & T2    & T3    & T4    & T5    & T6    &                     \cr
䀇�~1.& 1^{31}& 1^{30}& 1^{28}& 1^{24}& 1^{16}& -     & 31+30+28+24+16 =&129\cr
䀇�~2.& 1^{15}& 1^{14}& 1^{12}& 1^8   & -     & 5^{16}&    16\times  5 =& 80\cr
䀇�~3.& 1^7   & 1^6   & 1^4   & -     & 9^8   & 5^8   &     8\times  9 =& 72\cr
䀇�~4.& 1^3   & 1^2   & -     & 17^4  & 9^4   & 5^4   &     4\times 17 =& 68\cr
䀇�~5.& 1^1   & -     & 33^2  & 17^2  & 9^2   & 5^2   &     2\times 33 =& 66\cr
䀇�~6.& -     & 65^1  & 33^1  & 17^1  & 9^1   & 5^1   &     1\times 65 =& 65\cr
䀇�~7.& 129^1 & -     & -     & -     & -     & -     &     1\times 129=&129\cr
}
%%320

����� $1^{31}$~���������� 31~������� ������������� �����~1 �~�.�.;
����� ������������ ����������� �������. 풀 ����� ����� ���� �����������
�.~�.~���������
[Proc.\ AFIPS Eastern Jt.\ Computer Conf., 18 (1960), 143--148],
������� ������ �� ����������� ��������. ዓ��� ���� ���� ��� ����� ������
�.~�.~������ [���������������� �������, Minneapolis-Honeywell Regulator
Co.\ (1956)].

璎�� ��������� ����������� ������� ��������, ��� � ���������� �������,
���������� ����� ������ ���� ����� "������ ������������ �������������"
�������� �� ������. 爒�� ����������� ���� ������� ����� �����, �����
��������, ��� ������ ���� ������ ������������� ������������� ���~$T=6$
���� $\set{1, 0, 0, 0, 0}$, $\set{1, 1, 1, 1, 1}$, $\set{2, 2, 2, 2, 1}$,
$\set{4, 4, 4, 3, 2}$, $\set{8, 8, 7, 6, 4}$, $\set{16, 15, 14, 12, 8}$
�~$\set{31, 30, 28, 24, 16}$. ⅏��� ����� ���� ����� ��������� ������ �������:
\enumerate
\li ����� ������� ������ �� ����� ������� �������������� ���������������?
\li 璎 ������, ����~$S$ �� ������������� ������� ��������������
�������������?
\li ��� ��������� ��������� ������ �������������, ����� �� �������� ������
������������ �������� �� ������?
\li ኎���� "��������" �� ������ ��������� $T\hbox{-���������}$
����������� ������� (��� ������� ��~$S$---����� ��������� ��������)?
\enumend

�� ������� ��� ������ ������� �� �������, ��� ���� ������� ����� "�������
������", � ����� �������� ����� �������� ��������.

⎗��� ������������ ������������� ����� ��������, "�����������"
������������� ����� � �������� �������, ���������� ����������� ����������
����. ��������, ���~$T=6$ ����� ��������� ������������� ��������:
$$
\vcenter{\halign{
\hfil # \hfil &\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\bskip\hfil$#$\bskip&\hfil$#$\hfil\cr
㐎���� & T1 & T2 & T3 & T4& T5 &  \hbox{ᓌ��} & \hbox{����� � ������������� �����������}\cr
0 &   1 &   0&   0&  0 &  0&   1& T1\cr
1 &   1 &   1&   1&  1 &  1&   5& T6\cr
2 &   2 &   2&   2&  2 &  1&   9& T5\cr
3 &   4 &   4&   4&  3 &  2&  17& T4\cr
4 &   8 &   8&   7&  6 &  4&  33& T3\cr
5 &  16 &  15&  14& 12 &  8&  65& T2\cr
6 &  31 &  30&  28& 24 & 16& 129& T1\cr
7 &  61 &  59&  55& 47 & 31& 253& T6\cr
8 & 120 & 116& 108& 92 & 61& 497& T5\cr
\multispan{8}\dotfill\cr
n   & a_n     & b_n     & c_n     & d_n     & e_n & t_n      & T(k) \cr
n+1 & a_n+b_n & a_n+c_n & a_n+d_n & a_n+e_n & a_n & t_n+4a_n & T(k-1)\cr
\multispan{8}\dotfill\cr
}}
\eqno(1)
$$
%%321
(����� ���������� ������������� �����~T6 ������ ����� ������.)

�� ������� �������� �� ������~$n$ � ������~$n+1$ ����, ��� �������
$$
a_n \ge b_n \ge c_n \ge d_n \ge e_n
\eqno (2)
$$
����������� �� ����� ������. � ����� ����, ����� ������ ��~(1), ���
$$
\eqalign{
e_n &= a_{n-1},\cr
d_n &= a_{n-1}+e_{n-1}=a_{n-1}+a_{n-2},\cr
c_n &= a_{n-1}+d_{n-1}=a_{n-1}+a_{n-2}+a_{n-3},\cr
b_n &= a_{n-1}+c_{n-1}=a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4},\cr
a_n &= a_{n-1}+b_{n-1}=a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4}+a_{n-5},\cr
}
\eqno (3)
$$
���~$a_0=1$ � ��� �� ��������~$a_n=0$ ���~$n=-1$, $-2$, $-3$, $-4$.
\def\Fib#1,#2.{F^{(#1)}_{#2}}
\dfn{爑�� 䈁������ $p\hbox{-��}$~�������~$\Fib p, n.$} ������������ ���������
$$
\eqalign{
\Fib p, n. &=\Fib p, n-1.+\Fib p, n-2.+\cdots+\Fib p, n-p. \rem{��� $n\ge p$;}\cr
\Fib p, n. &=0 \rem{��� $0\le n \le p-2$;}\cr
\Fib p, p-1. &=1.\cr
}
\eqno (4)
$$

������� �������, �� �������� � $p-1$~�����, ����� �����~1, � ������
��������� ����� �������� ������ $p$~���������� �����. ���~$p=2$ ���
������� ������������������ 䈁������; ��� ������� ��������~$p$ ���
������������������ ������� ������, ��-��������, �.~苅���� �
[{\sl El Progreso Matematico,\/} {\bf 4} (1894), 173--174]. 苅���� �����
������������ �������
$$
\sum_{n\ge 0}\Fib p, n. z^n=
{z^{p-1}\over 1-z-z^2-\cdots-z^p}=
{z^{p-1}-z^p \over 1-2z+z^{p+1}}.
\eqno (5)
$$
䎐����~(3) ����������, ��� ����� �������� ��~T1 �
�������� ��������������� ������������ ������� �������� ������ 䈁������
������ �������~$a_n=\Fib 5, n+4.$.

� ����� ������, ���� ��������~$P=T-1$, ������������� � ����������� �������
��� $T$~���� ����� ����������� ������� ��������������� ������ 䈁������
$P\hbox{-��}$~�������. � ������ ������������� $n\hbox{-��}$~������ ��
$k\hbox{-�}$~����� �����
$$
\Fib P, n+P-2. + \Fib P, n+P-3. +\cdots+ \Fib P, n+k-2.
$$
%% 322
��������� �������� ���~$1\le k \le P$, � ����� ���������� ���������
�������� �� ���� ������ �����, �������������, �����
$$
t_n=P\Fib P, n+P-2. + (P-1)\Fib P, n+P-3. + \cdots + \Fib P, n-1. .
\eqno(6)
$$

풎 ������ ������ � "������ ������������� �������������". �� ��� �� ������
������, ����~$S$ �� ����� � ��������~$t_n$ �� ��� �����~$n$? ���
������������� ��������� ������� �� �����?

����~$S$ �� �������� ������ ������ 䈁������ (� ����� 䈁������ �� ���
�� �����), �� ����� �����������, ��� � ����������������
$P\hbox{-�������}$ �������, ��������  "���������
\picture{���.~68. ᎐������� ����������� ��������.}
�������"; ������� ����� �������, ���~$S$, � ����� ������, ����� ������.
���� ��������� �������� ���������� ��������� ��������; �� ��� �� �����,
��� ��� ������� "���������" ��������. � ������ ������� ���������� �����
������������� �������� � ������������ ��������� ��������, ������� ���� �
�� ����� �����������, �� ���� ���������� ������� �, ��-��������,
����� ���� ������ ������� ����� �� ������� ���������.

\alg D.(᎐������� ����������� �������� � ��������������
"���������������" �������������.) 풎� �������� ����� ��������� �������
� ������������ �� ���� �� ������ �� ������, ���� ����� ��������� ��������
�� �����������. ����� �� ����������, ��� ���� ������� �����, ���������
$P\hbox{-�������}$ �������, � �������������, ��� ������� $T=P+1\ge
3$~�������������� ���������. �����~$T$ ����� ������������ ��� ��������
�����, ��� ��� �� ��� �� ������������ �� ������ ���������� �������. �
������ �������� ��������� �������:

%%323
\descrtable{
$|A|[j]$, $1 \le j \le T$:
 & ⎗��� ������������� �������������, � �������� �� ���������. \cr
$|D|[j]$, $1 \le j \le T$:
 & 爑�� ��������� ��������, ������� ��������� ��������������� � ������
 ����� �� ���������� ���������� � �������~$j$.\cr
$|TAPE|[j]$, $1 \le j \le T$:
 & ����� ����������� ��������������� ����������, ���������������� �����������
 ���������� � �������~$j$.\cr
}
(���������, ��� ������ �������� � "�������� ���������� ��������������
���������", ������������ ������� ���������� ����������� �������� �
�������� ���������� ���������.)

\st[��������� ���������.] 㑒�������~$|A|[j]\asg |D|[j]\asg 1$
�~$|TAPE|[j]\asg j$ ���~$1\le j < T$. 㑒�������~$|A|[T]\asg |D|[T]\asg 0$
�~$|TAPE|[T]\asg T$. ����� ����������~$l\asg 1$, $j\asg 1$.

\st[���� �� �����~$j$.] �������� ���� ������� �� �����~$j$
� ���������~$|D|[j]$ ��~1. �����, ���� ���� ��������, ���������� ��� �����
� ������� � ����~\stp{5}.

\st[�����������~$j$.] ����~$|D|[j]<|D|[j+1]$, �� ���������~$j$ ��~1 �
��������� � ����~\stp{2}. � ��������� ������, ����~$|D|[j]=0$, ������� �
����~\stp{4}, � ����~$|D|[j]\ne 0$, ����������~$j\asg 1$ � ��������� �
����~\stp{2}.

\st[��������� �� ���� �������.] 㑒�������~$l\asg l+1$, $a\asg |A|[1]$,
����� ���~$j=1$, 2,~\dots, $P$ (������ � ���� �������)
����������~$|D|[j]\asg a+|A|[j+1]-|A|[j]$ �~$|A|[j]\asg
a+|A|[j+1]$. (�.~(1). �������, ���~$|A|[P+1]$ ������~0. � ����
����� ����� �����~$|D|[1]>|D|[2]>\ldots>|D|[T]$.) ⅏��� ����������~$j\asg 1$
� ��������� � ����~\stp{2}.

\st[ወ����.] ����~$l=0$, �� ���������� ���������, ��������� ���������
��~$|TAPE|[1]$. � ��������� ������ ������� ������� � ����~$|TAPE|[1]$,~\dots,
$|TAPE|[P]$ ��~$|TAPE|[T]$ �� ��� ���, ����~$|TAPE|[P]$ �� ������
������ �~$|D|[P]$ �� ��������� �~$0$. ������� ������� ��� �������
���������� ������� ������ ��������� ��������� �������. ����~$|D|[j]>0$ ���
����~$j$, $1\le j \le P$, �� ���������~$|D|[T]$ ��~1 � ���������
������~$|D|[j]$ ��~1 ���~$1\le j \le P$; � ��������� ������ �������
�� ������ ������� � ������ �����~$|TAPE|[j]$, �����, ���~$|D|[j]=0$, �
���������~$|D|[j]$ ��~1 ��� ���������~$j$. ( �� �������, ���������, ���
��������� ������� ��������� � \emph{������} �����, � �� � �����.)

\st[���������� �� ���� �������.] 㑒�������~$l\asg l-1$. ����������
�����~$|TAPE|[P]$ �~$|TAPE|[T]$. (� ���������������� ���������~$|TAPE|[P]$
����� ���� ������ �� ����~\stp{5} ����� ����� � ��� ���������� �����.)
����� ����������~$(|TAPE|[1],
%%324
|TAPE|[2],~\ldots, |TAPE|[T])\asg (|TAPE|[T], |TAPE|[1],~\ldots,
|TAPE|[T-1])$, $(|D|[1], |D|[2],~\ldots, |D|[T])\asg(|D|[T], |D|[1],~\ldots, |D|[T-1])$
� ��������� � ����~\stp{5}.
\algend

������� �������������, ������� ��� ��������� �������������� � ����~D3
����� ���������, ��������� �� ����������� �������� ����� ���������
�������� �� ������ �����. �������~69 ������������ ������� �������������,
����� �� ��������� �� ������~4 (33~�������) � ������~5 (65~��������) �
���������� � ������ �������; ���� ���� ��, ������, ������ 53~���������
\picture{
���.~69. �������, � ������� ������� �~34-�� ��~65-�
�������������� �� ����� ��� �������� � ������~4 �� �������~5. (�.~�������
������ ������������� �� ���.~320.) �������������� �������
������������� ������ 33~��������, ������� ���� ������������ � �������
���������� ������~4.
}
�������, �� ��� ������� � ��������~54 � ���� ��������������� �� ���
���������. (�� ����� ���� ������� ������������ � ����� �����, �� �������
�������, ��� ��� ������������ � ������, ��� ��� ��������������, ���
��������� ������� ��������� � ������ �����.)

�� ��� ����������� ������ ��� �� ������������ ���� ��������, ��������
�������� ����� "��������" �� ������. ᐀������ ��� �������������� ������
� ��������~(1), �� �����, ��� ��������� ���������� ������������ ���������
�������� ���~$S=t_6$ ����~$a_5t_1+a_4t_2+a_3t_3+a_2t_4+a_1t_5+a_0t_6$,
���� ��������� ��������� ������ �������������. � ���.~4 ���������
%%325
������������ �������
$$
\eqalign{
a(z)&=\sum_{n\ge0}a_nz^n={1\over 1-z-z^2-z^3-z^4-z^5},\cr
t(z)&=\sum_{n\ge1} t_nz^n={5z+4z^2+3z^3+2z^4+z^5\over 1-z-z^2-z^3-z^4-z^5}.\cr
}
\eqno(7)
$$
������ �������, ��� � ����� ������ ����� �������������� ���������
�������� ���~$S=t_n$ ����� ������������ ���~$z^n$ �
������������~$a(z)\cdot t(z)$ ����~$t_n$ (��� ���� ��������� ������
�������������). ⅏��� �� ����� ��������� ��������������� ���������
������������ �������, ��� �������� � ���.~5--7, � �������� ����������,
����������� � ����.~1.

� ����.~1 "��������� �����" ���� ������~$\lim_{n\to\infty} t_{n+1}t_n$,
������������, �� ������� �������������� ��� ���������� �����
\htable{ ����~1}%
{������������� ��������� ���������� ����������� ��������}%
{\hfill$#$\bskip&&\bskip\hfill$#$\hfill\bskip\cr
\hbox{�����} &  \hbox{䀇�} &    \hbox{�������}  &  \hbox{�������/����,} & \hbox{���������}\cr
             &              &                    &                       & \hbox{� ��������� �����}\cr
\noalign{\hrule}
 3 & 2.078 \ln S+0.678 & 1.504 \ln S+0.992 & 72 & 1.6180340\cr
 4 & 1.641 \ln S+0.364 & 1.015 \ln S+0.965 & 62 & 1.8392868\cr
 5 & 1.524 \ln S+0.078 & 0.863 \ln S+0.921 & 57 & 1.9275620\cr
 6 & 1.479 \ln S-0.185 & 0.795 \ln S+0.864 & 54 & 1.9659482\cr
 7 & 1.460 \ln S-0.424 & 0.762 \ln S+0.797 & 52 & 1.9835826\cr
 8 & 1.451 \ln S-0.642 & 0.744 \ln S+0.723 & 51 & 1.9919642\cr
 9 & 1.447 \ln S-0.838 & 0.734 \ln S+0.646 & 51 & 1.9960312\cr
10 & 1.445 \ln S-1.017 & 0.728 \ln S+0.568 & 50 & 1.9980295\cr
20 & 1.443 \ln S-2.170 & 0.721 \ln S-0.030 & 50 & 1.9999981\cr
\noalign{\hrule}
}
�������� �� ������ ������. "�������" ���������� ������� ����������
��������� ������ ������, � ������~$(1/S)$, ���������� �� ����� �����
��������� ��������, �������������� � ������� ��� ������������� � �������.
㑒���������� ����� �������� � ��� ����������� � ������ ������ � ���������
��~$O(S^{-\varepsilon})$ ��� ���������~$\varepsilon>0$ ��� �������
������������� ���~$S\to\infty$.

�� ���.~70 ���������� � ���� ������� ��~$S$ ������� ���������� �������
������ ������ ��� ������������� ���������~D � ������ �������� �����.
�������, ��� ��� ������������� ���� ���� ��� ��� ����� ������
������������� ���������� "����" ������������� ���������������, �� ���
������� � ������������ ������� �������� ��� ������� ��� ������� ����� ����.
�������������
%%326
������ ��� ����� ���� ���� ������������ ����� ��������� ��
��������� � ������ ��� ����� �������.

\section *����� ��������� ������������. � ���������������� �������,
 ��������� $k$~��������, ������ ������ �������������� � ���� ����������
����� $k$~���. �� ����������� ��������� �� �������� ����� ���������������:
��������� ������ ����� ��������������
\picture{���.~70.  픔���������� ������������ �������, ������������� ��������~D.}
����� ������� ����� ���, ��� ������, � �� ����� ��������� ��������, ����
��������� �������� ��������� ������� � ����� �������������� �������.

�� ���� ������� ������ ����� �������� ����������� �������������. ������
���� ����� �������������� ������ ������ �������� �� ������ �����, ���
�~(1), �������� ������� ������� ��� \emph{����� �������}---������� ��� ��
�������������� � ������� ����� �������� ����������. ������~(1) ������� ��������� �������:
%%327
$$
\matrix{
\hbox{㐎����} & T1 & T2 & T3 & T4 & T5 \cr
0 & 0 & - & - & - & - \cr
1 & 1 & 1 & 1 & 1 & 1 \cr
2 & 21 & 21 & 21 & 21 & 2\cr
3 & 3221 & 3221 & 3221 & 322 & 32 \cr
4 & 43323221 & 43323221 & 4332322 & 433232 & 4332 \cr
5 & 5443433243323221 & 544343324332322 & 54434332433232 & 544343324332 & 54434332 \cr
\multispan{6}{\dotfill}\cr
n  & A_n & B_n & C_n & D_n & E_n \cr
n+1& (A_n+1)B_n & (A_n+1)C_n & (A_n+1)D_n & (A_n+1)E_n & A_n+1\cr
\multispan{6}{\dotfill}\cr
}
\eqno(8)
$$
����� $A_n$~���� ������� �� $a_n$~��������, �������������� ����� �������
������� ������� ��~$T1$, ���� �� �������� � �������������
$n\hbox{-��}$~������; $B_n$~���� ��������������� ������� ���~T2 �~�.~�.\
�����������~"$(A_n+1)B_n$" ��������: "$A_n$, ��� �������� �������
��������� ��~1, � �� ���~$B_n$".

�������~71~(�), �� ������� "����� �����" ����������~$A_5$, $B_5$, $C_5$,
$D_5$, $E_5$, �������������, ����� ������� ����� ������� ��� �������
������� ���������� �� �����; �������, ��� ������� � ������ ����� �����
����� �������������� 5~���, � �� ����� ��� ������� � �����~T1 �����
�������������� ���� �������.
\picture{���.~71.               ������ ������������ ������������� ������
������ �� ����� ������: (a)---����� �������; (b)---����������� ������� �������������.}
풀 "�������������" ��� ����������� ������� �������� � ����, ��� ���������
������� ����� �������� � ������ �����, � �� � �����. �� ���.~71~(b)
����������� ����������� ������� ������������� �������� ��� ������
�������������� ������������ �������; ������ ����� ������� ���������� �
������� � ���������� �� ���������� ������ �������. �������, ��� ��������~D
%%328
(���.~69) ��������� ����, ��� ��� �� ��������� ���������
�������~"4" �� ����, ��� ��������� ��� �������~"3".
������������ �����������~(8) ����������, ��� ���~$B_n$, $C_n$, $D_n$,
$E_n$ �������� ���������� ������������~$A_n$. � ����������������,
���������~(8), ����� ������� �������
$$
\eqalign{
E_n&=(A_{n-1})+1,\cr
D_n&=(A_{n-1}A_{n-2})+1,\cr
C_n&=(A_{n-1}A_{n-2}A_{n-3})+1,\cr
B_n&=(A_{n-1}A_{n-2}A_{n-3}A_{n-4})+1,\cr
A_n&=(A_{n-1}A_{n-2}A_{n-3}A_{n-4}A_{n-5})+1,\cr
}
\eqno(9)
$$
���������� �����������~(3), ������� ����� ���� ������ � ������� ����
�������. ����� ����, �� ������, ������������  �������~$A$, �������, ���
��������� � ������ ������� ������, � ��������, ���� � �� ��; �����
$$
A_n=n-Q_n,
\eqno(10)
$$
��� $Q_n$~���� ������� �� $a_n$~��������, ������������ �������
$$
\displaynarrow{
Q_n=Q_{n-1}(Q_{n-2}+1)(Q_{n-3}+2)(Q_{n-4}+3)(Q_{n-5}+4) \rem{��� $n\ge 1$},\cr
Q_0=\hbox{'0'}; Q_n=\hbox{(�����)} \rem{��� $n<0$.}\cr
}
\eqno(11)
$$
  ���~$Q_n$ ���������� �~$Q_{n-1}$, �� ����� �����������
\emph{�����������} �������~$Q_\infty$, ������ $a_n$~��������� �������
��������� �~$Q_n$; ��� �������, �� ��������, ��������� ��� ����� ������� �
����������� �������������. � ������ ����� ���� �����
$$
Q_\infty=011212231223233412232334233434412232334233434452334344534454512232\ldots\,.
\eqno  (12)
$$

� ���.~11 ���������� ���������� ������������� ���� �������.

��� ������� ���~$A_n$ ���� �������~$m_1m_2\ldots m_{a_n}$, ���������
�����~$A_n(x)=x^{m_1}+x^{m_2}+\cdots+x^{m_{a_n}}$ ���������������
������������ �������, �����������, ������� ��� ���������� ������  �����
�������; ���������� ������~$B_n(x)$, $C_n(x)$, $D_n(x)$,
$E_n(x)$. ��������, $A_4(x)=x^4+x^3+x^3+x^2+x^3+x^2+x^2+x=x^4+3x^3+3x^2+x$.
 � ���� �����������~(9) ����� ���~$n\ge1$
$$
\eqalign{
E_n(x)&=x(A_{n-1}(x)),\cr
D_n(x)&=x(A_{n-1}(x)+A_{n-2}(x)),\cr
C_n(x)&=x(A_{n-1}(x)+A_{n-2}(x)+A_{n-3}(x)),\cr
B_n(x)&=x(A_{n-1}(x)+A_{n-2}(x)+A_{n-3}(x)+A_{n-4}(x)),\cr
A_n(x)&=x(A_{n-1}(x)+A_{n-2}(x)+A_{n-3}(x)+A_{n-4}(x)+A_{n-5}(x)),\cr
}
\eqno(13)
$$
%%329
���~$A_0(x)=1$ �~$A_n(x)=0$ ���~$n=-1$, $-2$, $-3$, $-4$. ዅ����������,
$$
\sum_{n\ge 0} A_n(x)z^n={1\over 1-x(z+z^2+z^3+z^4+z^5)}=
\sum_{k\ge 0} x^k(z+z^2+z^3+z^4+z^5)^k.
\eqno(14)
$$
������������ ������� �� ���� ������, �������
$$
T_n(x)=A_n(x)+B_n(x)+C_n(x)+D_n(x)+E_n(x), \qquad n\ge 1;
\eqno (15)
$$
��~(13) ���������� ��������
$$
T_n(x)=5A_{n-1}(x)+4A_{n-2}(x)+3A_{n-3}(x)+2A_{n-4}(x)+A_{n-5}(x),
$$
� ������, �
$$
\sum_{n\ge 1} T_n(x)z^n=
{x(5z+4z^2+3z^3+2z^4+z^5)\over 1-x(z+z^2+z^3+z^4+z^5)}.
\eqno(16)
$$

ᎎ��������~(16) ����������, ��� ����� ��������� ������������~$T_n(x)$:
$$
\matrix{
 & z &z^2 & z^3 & z^4 & z^5 & z^6 & z^7 & z^8 & z^9 & z^{10} & z^{11} & z^{12} & z^{13} & z^{14} \cr
x & 5 & 4 & 3 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \cr
x^2 & 0 & 5 & 9 & 12 & 14 & 15 & 10 &  6 &  3 &  1 &  0 &  0 &  0 & 0 \cr
x^3 & 0 & 0 & 5 & 14 & 26 & 40 & 55 & 60 & 57 & 48 & 35 & 20 & 10 & 4 \cr
x^4 & 0 & 0 & 0 &  5 & 19 & 45 & 85 & 140 & 195 & 238 & 260 & 255 & 220 & 170\cr
x^5 & 0 & 0 & 0 &  0 &  5 & 24 & 69 & 154 & 294 & 484 & 703 & 918  & 1088
& 1168 \cr
}
\eqno(17)
$$
ᒎ���� ���� ������� ����~$T_n(x)$; ��������, $T_4(x)=2x+12x^2+14x^3+5x^4$.
������ ������� ���� ������� (����� ��������� ������ ������) ��������
������ ���� ���������, ������������� � ���������� ������ ���������������
����� ����.

爑�� �������� � ������ ������������� $n\hbox{-��}$~������ �����~$T_n(1)$,
� ����� ���������� �������������� �������� � �������� �� ������� �����
�����������~$T'_n(1)$. �����,
$$
\sum_{n\ge 1} T'_n(x)z^n=
{5z+4z^2+3z^3+2z^4+z^5\over (1-x(z+z^2+z^3+z^4+z^5))^2};
\eqno(18)
$$
�������~$x=1$ �~(16) �~(18), ��������, ��� ����� ������� ��� �������
������������� �-�� ������ ���� ����������� ���~$z^n$ �~$a(z)t(z)$
[��.~(7)]. 풎 ����������� � ������ ����������� �������������.

䓍����~$T_n(x)$ ����� ������������ ��� ����������� ����������� ������,
����� ��������� ������� ����������� ����������� �������. �����~$\sum_n (m)$
���� ����� ���������� $m$~����� ������� � �������������
$n\hbox{-��}$~������. ��������� �� �������~(17),
%%330
�� ��� ����� �������� ��� �����~$\sum_n(m)$:
{\let\i=\infty
$$\vcenter{\halign{
$#$\bskip&&\bskip\hfill$#$\bskip\cr
\span m=1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 \cr
n=1 & 1 & 2 & 3 & 4 & 5 & \i & \i & \i & \i & \i & \i & \i & \i & \i & \i& \i & \i & \i & \i & \i & \i \cr
n=2 & 1 & 2 & 3 & 4 & � & 8 & 10  & 12 & 14 & \i & \i & \i & \i & \i & \i & \i & \i & \i & \i & \i & \i \cr
n=3 & 1 & 2 & 3 & 5 & 7 & 9 & 11 & 13 & 15 & 17 & 19 & 21 & 24 & 27 & 30 &33 & 36 & \i & \i & \i & \i \cr
n=4 & 1 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 22 & 24 & 26 & 29& 32 & 35 & 38 & 41 & 44 & 47 \cr
n=5 & 1 & 3 & 5 & 7 & 9 & 11 & 13 & 15 & 17 & 19 & 21 & 23 & 25 & 27 & 29& 32 & 35 & 38 & 41 & 44 & 47 \cr
n=6 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 22 & 24 & 26 & 28 & 30 & 33 & 36 & 38 & 42 & 45 & 48 \cr
n=7 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 23 & 26 & 29 & 32 & 35 & 38 & 41 & 44 & 47 & 50 & 53 \cr
}}
\eqno(19)
$$}%
��������, ���� �� ����� ������������� 17~��������, ���������
������������� 3-��~������, �� ����� ���������� �������� ����~$\sum_3
(17)=36$, �� ���� ������������ �������������~4-�� ��� 5-��~������, ��
����� ���������� �������� � �������� ������� �����
������~$\sum_4(17)=\sum_5 (17)=35$. �������� ������������ �������~4,
���� �����~17 ������������� ������� ������������� 3-��~������! � �����
����, ��. ���� �����������~$S$ ����������� ����� ������ �����������
����������� ������, ��� ������������ � ���������~D.

㏐�������~14 ����������, ��� ���������� ����������� ������������������
�����~$M_n$, �����, ��� �������~$n$ ��������� ���~$M_n\le S < M_{n+1}$, ��
�� ���~$S\ge M_{n+1}$. � ������ ����� ���� ������ ��� �����������
�������~$\sum_n (m)$ ����
$$
M_0=0,\quad M_1=2,\quad M_2=6,\quad M_3=10,\quad M_4=14.
$$
���� �� ����� ���� ������ �� ������� ����� ����, ������ ����, ��� �� ��
���� ��������� � ����������� ���������� �~$T$~������� ��� ������~$T\ge3$;
������ � ��������������� ������ ���� ��������~5 ��~$P=T-1$. � ����.~2
���������� ������������������~$M_n$, ���������� ��� ���������
��������~$T$.  ����~3 � ���.~72 ���� ������������� �� �����
���������� �������������� ��������� �������� ����� ����������
������������ ������������� ��������� ��������. (䎐���� �����
����.~3 ������� ��������� � �������������, ��� ��� ��� ����������� ��
������ ���������� ��������� �� �������~$1\le S \le 5000$
($1\le S \le 10\, 000$ ���~$T=3$), ��� �������� � ���������� ����������,
��������� ������ ������� ��������~$S$ �� �������� ��������� ���������� ���
����~$T$. ���~$S\to\infty$ ����� �������������� ��������� �������� �����
������������ ������������ ������������� �������������� �����~$S\log_p S$,
�� ���������� � ����� ���������������� ������� ������ ���������.)

��� ������ ����.~4 ����� �������� ����� ������������� ���������~D �
������������ ������������ �������������, ������������ � ����.~3. �,
��� ��������~D �� ����� ������ � ������������ ��� �������~$S$ �~$T$;
������ ���������, ����� �� ��������� � ���� ������� ����������� �����
���������~D, �� �������� � ������������ �����������, �������� ���� �� ��
%%331
�����~$S$ �������. � �������, ���������� � �������~$S$ ���������� ��������
����� (��.~�.~5.4.6), ��� ��� ��������~D �� �������� �� ��� �� ����, ��
����� ����---���� ������ ������.

������������� ����������� ���������� ������� ���� ����������������
�.~�.~�������� [����.\ IFIP Congress (1962), 62--66].
\picture{���.~72.  픔���������� ������������ ������� � �����������
��������� �������������� (��.~�~���.~70).}

������ �� ����������� ����������� ������������ ������������ ����������
��������� �������� ����������� �.~ᝊ���� �~�.~ል����� [A vector model
for merge sort analisis, ���������������� ������, �������������� ��
���������~ACM �� ���������� (������ 1962), ���.~21]. ������� ᝊ���
��������� �������������� ����� �������������, ������������ �
���������~D; ������� 腋� [{\sl CACM,\/} {\bf 14} (1971), 713--719; {\bf
15} (1972), 28], ���������� ������ ��� ������, ������ ��
�����������~(10) � �������� ������ ��������� ��������� ����������
�������������. ���������� �������� ������������������ � ��������� ����
�������� �������~�.~������ [{\sl JACM,\/} ����� ������������].
%%332
\htable{ ���� 2}%
{爑�� ��������, ��� ������� ������ ������� ���������}
{
\hfill$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\hfill\bskip$#$\bskip&\bskip$#$\hfill\cr
\hbox{㐎����}& T=3 & T=4 & T=5 & T=6 & T=7 & T=8 & T=9 & T=10\cr
\noalign{\hrule}
 1 &  2 &  2 &  2 &  2 &  2 &  2 &  2 &  2 & M_1 \cr
 2 &  3 &  4 &  5 &  6 &  7 &  8 &  9 & 10 & M_2 \cr
 3 &  4 &  6 &  8 & 10 & 12 & 14 & 16 & 18 & M_3 \cr
 4 &  6 & 10 & 14 & 14 & 17 & 20 & 23 & 26 & M_4 \cr
 5 &  9 & 18 & 23 & 29 & 20 & 24 & 28 & 32 & M_5 \cr
 6 & 14 & 32 & 35 & 43 & 53 & 27 & 32 & 37 & M_6 \cr
 7 & 22 & 55 & 76 & 61 & 73 & 88 & 35 & 41 & M_7 \cr
 8 & 35 & 96 &109 &194 & 98 &115 &136 & 44 & M_8 \cr
 9 & 56 &173 &244 &216 &283 &148 &171 &199 & M_9 \cr
10 & 90 &280 &359 &269 &386 &168 &213 &243 & M_{10}\cr
11 &145 &535 &456 &779 &481 &640 &240 &295 & M_{11}\cr
12 &234 &820 &1197&1034&555 &792 &1002&330 & M_{12}\cr
13 &378 &1635&1563&1249&1996&922 &1228&1499& M_{13}\cr
14 &611 &2401&4034&3910&2486&1017&1432&1818& M_{14}\cr
15 &988 &4959&5379&4970&2901&4397&1598&2116& M_{15}\cr
16 &1598&7029&6456&5841&10578&5251&1713&2374&M_{16}\cr
17 &2574&14953&18561&19409&13097&5979&8683&2576&M_{17}\cr
18 &3955&20583&22876&23918&15336&6499&10069&2709&M_{18}\cr
19 &6528&44899&64189&27557&17029&30164&11259&15787& M_{19}\cr
\noalign{\hrule}
}


{\def\m#1#2{\matrix{\hfill #1\cr\hfill #2\cr}}
\htable{ ����~3}%
{爑�� ��������� ��������, �������������� ��� ����������� \nl ����������� �������}%
{\hfill$#$\bskip&&\hfill\bskip$#$\bskip\cr
   S&  T=3 &  T=4 &  T=5 &  T=6 &  T=7 &  T=8 &  T=9 & T=10\cr
\noalign{\hrule}
  10&    36&    24&    19&    17&    15&    14&    13&    12\cr
  20&    90&    60&    49&    44&    38&    36&    34&    33\cr
  50&   294&   194&   158&   135&   128&   121&   113&   104\cr
 100&   702&   454&   362&   325&   285&   271&   263&   254\cr
1000& 10371&  6680&  5430&  4672&  4347&  3872&  3739&  3632\cr
5000& 63578& 41286& 32905& 28620& 26426& 23880& 23114& 22073\cr
\multispan{2} \hfil$
\displaystyle
S\left\{\matrix{
\hfill  (1.51\cr
\hfill +(-.11\cr
}\right.
$ &
\m{0.951}{+.14} & \m{0.761}{+.16} & \m{0.656}{+.19} & \m{0.589}{+.21} &
\m{0.548}{+.20} & \m{0.539}{+.02} &
\multispan{2}
\hfill\bskip$\displaystyle\vcenter{\halign{\hfil$#$&$\hbox{}#$\hfil\cr
0.488)&\cdot S \ln S \cr
+.18)&\cdot S \cr
}}$
\cr
\noalign{\hrule}
}}
������������ �������~(16) ���� ������� ����������� �.~������
[����. IFIP Congress (1971), I, 454--459].

\qsection � ��� ������� ���� � �������� ���������? �� ��� ��� ��
������������ "�������������� ��������� �������" ��� ������������ ����
������������� ��� ��������� ��������� ���������� �������. �� �����
������ �� ���~2--6 � �������� � ������ ����� ������ ��� ������ �������
��������� ���� ����;
��� ���������� �������� �����, ��� � ����� ������� ��������
%%333
\htable{ ����~4}%
{爑�� ��������� ��������, �������������� ��� ����������� \nl ����������� �������}%
{\hfill$#$\bskip&&\hfill\bskip$#$\bskip\cr
   S&  T=3 &  T=4 &  T=5 &  T=6 &  T=7 &  T=8 &  T=9 & T=10\cr
\noalign{\hrule}
  10&    36&    24&    19&    17&    15&    14&    13&    12\cr
  20&    90&    62&    49&    44&    41&    37&    34&    33\cr
  50&   294&   194&   167&   143&   134&   131&   120&   114\cr
 100&   714&   459&   393&   339&   319&   312&   292&   277\cr
1000& 10730&  6920&  5774&  5370&  4913&  4716&  4597&  4552\cr
5000& 64740& 43210& 36497& 32781& 31442& 29533& 28817& 28080\cr
\noalign{\hrule}
}
����� ������ ���� ���������� � ������, ������ ��� ������ �����������
��������� ����. 풎 ����� ������� ������������ ��������, ��� ��� � �����
������ ���������� �������� ����� �������� ������������ ������� �����������
������� (��. ������� "�������/����" � ����.~1). �������, ����� ���
����������� �� ����� �������� ���������, ����� ��� ����� ���� ��,
��������� ���� ����� �������, ��������� �������� ������ � ���������� �������.

풓 ������ ������ ������� ����������� ����������� ���������, ���� ���
������� �� ����� ���� ���� [��.~����������� �.~ᅇ��� (Univ.~of~Paris
(1968), 25--27), ��� ��� ���� ������������� ��.~�������]. ������ ����
����� ������� �������  ������� � $(T-3)$~���� �� ��������� ������ �����, �
�� ����� ��� ���������� ��� ����� ��������������.

����������, ��������, ������ ����� ���� � 49~��������� ��������. �
��������� ������� ������~$R$ �������� �����, ���������������� �� �����
������ ����; ��������������, ��� $T5$~�������� �������������� �������:
\ctable{
\hfill$#$\bskip&&\bskip\hfill$#$\hfill\bskip\cr
\omit\hfill 䀇�\hfill & T1 & T2 & T3 & T4 & T5 & T6 & \omit\hfill ����� ������  \hfill & \omit\hfill ����� ��������� \hfill \cr
 1&1^{11}&1^{17}&1^{13}& 1^8& -   & (R)   & 49           & 17\cr
 2&   (R)&   1^9&   1^5&   -& R   & 3^8   & 8\times  3=24& 49-17=32\cr
 3&   1^6&   1^4&   -  &   R& 3^5 &  R    & 5\times  3=15& \max(8,24)\cr
 4&   1^2&     -&    R & 5^4& R   & 3^4   & 4\times  5=20& \max(13,15)\cr
 5&   -  &     R&   7^2&   R& 3^3 & 3^2   & 2\times  7=14& \max(17,20)\cr
 6&    R &  11^2&     R& 5^2& 3^1 & -     & 2\times 11=22& \max(11,14)\cr
 7&  15^1&     R&   7^1& 5^1& -   & R     & 1\times 15=15& \max(22,24)\cr
 8&  R   &  11^1&   7^0&   -& R   & 23^1  & 1\times 23=23& \max(15,16)\cr
 9& 15^1 &  11^1&     -&   R& 33^0& R     & 0\times 33= 0& \max(20,23)\cr
10&(15^0)&     -&     R&49^1& (R) & (23^0)& 1\times 49=49& 14\cr
}
����� ��� ���������, �� ��������, ���������; �� ����������� ����~9
("��������� ����", ������� �������������� ������������� �������) �
��������� ����� ��������� ���� ������������� (����� �������������� ���
�����). ���� $t$~���� �����, �����������
%%334
��� ������� ������ ���������� �������, ����� ���������� � �����
��������� �������, � $r$---����� ��������� �� ���� ��������� �������, ��
���� ������� ������ �����~$182t+40r$ ���� ����� ���������� ������������� �
����������� ���������. ᎎ������������ ��������� ��� ������������
������������ ������, ������������� ��������~D, ����~$140t+104r$, ���
��������� ����, ����~$r={3\over 4}t$, � ��������� �����, ����~$r={1\over2}t$.

��� ��������� � ����������� ����������� ������ ��������� � ������������
������ �������; ��������, ������������������~$a_n$ ������ �������������
������������� �����������
$$
a_n=a_{n-2}+a_{n-3}+a_{n-4}
\eqno  (20)
$$
������~(3). 爒����� ����� ������� ���������������� ���� ����� ����� ��
�������, ��� �� ������������� ����������� �����������, ��� ��� ���
������� ��������� ����� ������� (��., ��������, ���.~19 �~20).

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

풎 ����� ��������, ��������������, ���� �� �� ������, ��� \emph{�������
������� ������� �� ����������� �������� ����������� ����������.} �
�������� �������� ���������� ������, ����� �� �����~T1 ����������
1~������� � $n$~��������---��~T2, T3,
\htable{ ���� 5}%
{��������������� ��������� ������������ ������� �������}%
{
\hfill$#$\bskip&&\bskip\hfill$#$\hfill\bskip\cr
\hbox{�����} & \hbox{䀇�} & \hbox{�������} & \hbox{�������/����,} & \hbox{���������}\cr
             &             &                & \hbox{� ���������}   &
\hbox{�����} \cr
\noalign{\hrule}
 5& 3.566 \ln S +0.158 & 1.463 \ln S + 1.016 & 41 & 1.3247180\cr
 6& 2.616 \ln S -0.166 & 0.951 \ln S + 1.014 & 36 & 1.4655712\cr
 7& 2.337 \ln S -0.472 & 0.781 \ln S + 1.001 & 33 & 1.5341577\cr
 8& 2.216 \ln S -0.762 & 0.699 \ln S + 0.980 & 32 & 1.5701473\cr
 9& 2.156 \ln S -1.034 & 0.654 \ln S + 0.954 & 30 & 1.5900054\cr
10& 2.124 \ln S -1.290 & 0.626 \ln S + 0.922 & 29 & 1.6013473\cr
20& 2.078 \ln S -3.093 & 0.575 \ln S + 0.524 & 28 & 1.6179086\cr
\noalign{\hrule}
}
T4, T5; ���� �� ����� ���������� ��������� ������� ��~T6 �~T1, ���� T2, T3,
T4, T5 �� ������ �������, �� ����� ��������� ����� �����
$(2n^2+3n)$~������ ��������� ��������, �.~�., �� ��������,
���������������~$S^2$, � ��~$S\log S$, ���� ��� ����� ������������
����������� �������.

%%335

\section ����������� ����. 픔�������� ���������� �������
��������� �������� ���������, ����������� �� ������ �����������, � ��
������ � ����������; ���������� ����� ������, ������� ����� ����� ����
�����������. ���������� ����������� �������, ������� ���������� �����
��������� �������:
\ctable{
#\bskip\hfill&&\bskip#\bskip\hfill\cr
      &\omit\hfill T1 \hfill&\omit\hfill T2 \hfill\cr
䀇�~1& �����~1   & \omit\hfill $-$ \hfill \cr
      & ��������� & \omit\hfill $-$ \hfill \cr
䀇�~2& ����~1    & �����~2\cr
      & ��������� & ���������\cr
䀇�~3& �����~3   & ����~2\cr
      & ��������� & ���������\cr
䀇�~4& ����~3    & �����~4\cr
      & ��������� & ���������\cr
}
� �. �., ��� "�����~$k$" �������� ������ � $k$-� �������� ����, �
"����~$k$" �������� ��� ������. ����� ��������� ����� ���������, ����
������������ ��� �����, ��� ���� ���������� �.~���������
[{\sl CACM,\/} {\bf 5} (1962), 102]:
\ctable{
#\bskip\hfill&&\bskip#\bskip\hfill\cr
      &\omit\hfill T1 \hfill&\omit\hfill T2 \hfill& \omit\hfill T3 \hfill\cr
䀇�~1 & �����~1.1 & \omit\hfill $-$ \hfill & \omit\hfill $-$ \hfill\cr
       & �����~1.2 & \omit\hfill $-$ \hfill & \omit\hfill $-$ \hfill\cr
       & ��������� & �����~1.3 & \omit\hfill $-$ \hfill\cr
䀇�~2 & ����~1.1  & �����~2.1 & \omit\hfill $-$ \hfill\cr
       & ����~1.2  & ��������� & �����~2.2\cr
       & ��������� & ����~1.3  & �����~2.3\cr
䀇�~3 & �����~3.1 & ����~2.1  & ���������\cr
       & �����~3.2 & ��������� & ����~2.2\cr
       & ��������� & �����~3.3 & ����~2.3\cr
䀇�~4 & ����~3.1  & �����~4.1 & ���������\cr
       & ����~3.2  & ��������� & �����~4.2\cr
       & ��������� & ����~3.3  & �����~4.3\cr
}
�~�.~�. ����� "�����~$k.j$" �������� ������ $j\hbox{-�}$~�����
$k\hbox{-��}$~��������� �����, � "����~$k.j$" �������� �� ������. � �����
������ ����� ��������� ��� ����� ���������, ���� ��������� �� �������
���� ����� ������� ������/������. �������� ���������, � ������� ����� �
������ ���� ����������� ����� �������, ���������� "������������ ����".

�.~���-�������� [{\sl CACM\/}, {\bf 7} (1964), 158--159] �������,
��� ����������� ���� �������� � ������������ ������ ���������� �������
��������� � ����������� �������. ��� ����� ����� ������������ � ��������
��� ������� ����������� ����, � �� ������������ $(T-2)\hbox{-�������}$~�������.

%%336

����������� �����, ��� � ��� ���� ����� ���� � ���������� ��������� �����
�������, ������� �������� ��������� �������, ��������� ����� �� ������
������ (�����~I, � �~R ���������� �������������� ����, ����� � ���������):
$$
\vcenter{\halign{
\hfil$#$\hfil&\bskip\hfill # \hfill\bskip&\bskip\hfill #
\hfill\bskip&\bskip\hfill # \hfill\bskip&\bskip\hfill #
\hfill\bskip&\bskip\hfill # \hfill\bskip&\bskip\hfill # \hfill\bskip&\bskip\hfill$#$\hfill\bskip\cr
        &    &    &    &    &    &    & \hbox{爑�� ���������}\cr
㐎���� & T1 & T2 & T3 & T4 & T5 & T6 & \hbox{��������}\cr
7 & I & I & I & I & R & O & u_7 \cr
  & I & I & I & I & O & R & v_7 \cr
6 & I & I & I & R & O & I & u_6 \cr
  & I & I & I & O & R & I & v_6 \cr
5 & I & I & R & O & I & I & u_5 \cr
  & I & I & O & R & I & I & v_5 \cr
4 & I & R & O & I & I & I & u_4 \cr
  & I & O & R & I & I & I & v_4 \cr
3 & R & O & I & I & I & I & u_3 \cr
  & O & R & I & I & I & I & v_3 \cr
2 & O & I & I & I & I & R & u_2 \cr
  & R & I & I & I & I & O & v_2 \cr
1 & I & I & I & I & R & O & u_1 \cr
  & I & I & I & I & O & R & v_1 \cr
0 & I & I & I & R & O & I & u_0 \cr
  & I & I & I & O & R & I & \cr
}}
\eqno (21)
$$
璎�� ��������� ������ � ����� �������� �� �4 � ������� ���������� �������,
�� ������ �����
$$
\eqalign{
v_0 &= 1,\cr
u_0+v_1&= 0,\cr
u_1+v_2 &= u_0+v_0,\cr
u_2+v_3 &= u_1+v_1+u_0+v_0,\cr
u_3+v_4 &= u_2+v_2+u_1+v_1+u_0+v_0,\cr
u_4+v_5 &= u_3+v_3+u_2+v_2+u_1+v_1+u_0+v_0,\cr
u_5+v_6 &= u_4+v_4u_3+v_3+u_2+v_2+u_1+v_1,\cr
}
$$
�~�.~�.; � ����� ������ ���������, �����
$$
u
_n+v_{n+1}=u_{n-1}+v_{n-1}+u_{n-2}+v_{n-2}+u_{n-3}+v_{n-3}+u_{n-4}+v_{n-4}
\eqno (22)
$$
��� ����~$n\ge 0$, ���� �������~$u_j=v_j=0$ ��� ����~$j<0$.

� ���� ��������� ��� ������������� �������; � ����� ����, ���� ��������
���~$u$ ������� ����, �� ������� ������� �����������, �������, ������
���� ����� ����� ������! �� ����
%%337
�������~$u_n\approx v_{n+1}$,  �� ����� ��������� ����� �����������������
���������.

���-�������� ��������� �����~$u_n=v_{n-1}+v_{n-2}+v_{n-3}+v_{n-4}$,
$v_{n+1}=u_{n-1}+u_{n-2}+u_{n-3}+u_{n-4}$, ��� ��� ������������������
$$
\<x_0, x_1, x_2, x_3, x_4, x_5, \ldots > = \<v_0, u_0, v_1, u_1, v_2, u_2, \ldots>
$$
������������� ����������� ������������� �����������
$$
x_n=x_{n-3}+x_{n-5}+x_{n-7}+x_{n-9}.
$$
���������, ������, ��� ����� ��������
$$
\eqalign{
v_{n+1} &= u_{n-1}+v_{n-1}+u_{n-2}+v_{n-2},\cr
u_n &= u_{n-3}+v_{n-3}+u_{n-4}+v_{n-4}.\cr
}
$$
풀 ������������������ �� ������ ������� ����� �� ������� �������, ��
������� ������������ � ���, ��� ��������������� ����� ������� �����
���������������� �������������. [������� ���-��������� ��� �������
������ ������, ������ ��� � ����� ���� ����� ����������� ������� ������
�����; �� ������, ��� ������ �� ����� ��������� ���~(23).]

����� ������� ����� �������� �� ������ ����� �� ������ ������, ��������
����� �� �����~(21); �� �������� ��������� ����� ����������:
{\def\m#1{\displaystyle\matrix{#1}}\ctable{
\hfil#\hfil&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip&\bskip$#$\hfil\bskip&\bskip\hfil$#$\hfil\bskip\cr
㐎���� &  T1 & T2 & T3 & T4 & T5 & T6 & \hbox{����� ������} & \hbox{�����  ���������}\cr
       & 1^{23} & 1^{21} & 1^{17} & 1^{10} & -  & 1^{11}    & 82 & 23\cr
7      & 1^{19} & 1^{17} & 1^{13} & 1^6    & R  & 1^{11}4^4 & 4\times 4=16  & 82-23\cr
       & 1^{13} & 1^{11} & 1^7    & -      & 4^6& R         & 6\times 4=24  & 25 \cr
6      & 1^{10} & 1^8    & 1^4    & R      & 4^9& 1^84^4    & 3\times 4=12  & 10 \cr
       & 1^6    & 1^4    & -      & 4^4    & R  & 1^44^4    & 4\times 4=16  & 36 \cr
5      & 1^5    & 1^3    & R      & 4^47^1 & 4^8& 1^34^4    & 1\times 7=7   & 17 \cr
       & 1^2    & -      & 7^3    & R      & 4^5& 4^4       & 3\times 7=21  & 23 \cr
4      & 1^1    & R      &7^3 13^1& 4^37^1 & 4^4& 4^3       & 1\times 13=13 & 21 \cr
       & -      & 13^1   & R      & 4^27^1 & 4^3& 4^2       & 1\times 13=13 & 34 \cr
3      & R      & 13^1 19^1& 7^2 13^1 & 4^1 7^1 & 4^2 & 4^1 & 1\times 19=19 & 23 \cr
       & 19^1   & R      & 7^1 13^1 & 7^1  & 4^1& -         & 1\times 19=19 & 32 \cr
2      & 19^1 31^0& 13^1 19^1 & 7^1 13^1 & 7^1 & 4^1 & R    & 0\times 31=0  & 25 \cr
       & R      & 19^1   & 13^1 & 7^0 & - & 31^1 & 1\times 31=31 & 19 \cr
$\m{ 1\cr \cr 0\cr}$ &
\m{ 19^1 31^0 \cr
    19^1 31^0 \cr
    19^1 31^0 \cr}&
\m{ 19^1 \cr
    19^1 \cr
    19^1 \cr } &
\m{13^1 \cr
   13^1 \cr
   13^1 \cr } &
\m{ 7^0 \cr
    - \cr
    R \cr } &
\m{ R \cr
    52^0 \cr
    52^0 82^0 \cr } &
\m{ 31^1 52^0 \cr
    R \cr
    31^1 52^0 \cr } &
\left.\m{ 0\times 52 = 0 \cr
          0\times 52 = 0 \cr
          0\times 82 = 0 \cr } \right\} \max(36, 31, 23)\span\cr
 & (31^0) & (19^0) & - & 82^1 & (R) & (52^0) & 1\times 82 = 82 & 0\cr
}}
������������� ��������� ����������� ������ ��� ��������� ������� �����~T5
(82~�������), � ������� ������ �������� ���� ������� ������ (25~������) �
� ������� ������������� ��� "���������� �������" �� �������~1 �~0 (36
������).  ��
%% 338
�������, ����� ������ ����� ������� ���������~$273t+143r$;
��� ���������~D ��������������� ��������~$268t+208r$ ����� ������ ����.

�������� ������ (��.~���.~23), ��� ����� ��������, ��������� �� �����
������ ����, ���� ���������������
$$
4, 4, 7, 13, 19, 31, 52, 82, 133, \ldots
\eqno(24)
$$
��� ���� ������������������~$\< t_1, t_2, t_3,~\ldots>$ ������������� ������
$$
t_n=t_{n-2}+2t_{n-3}+t_{n-4},
\eqno(25)
$$
���� �������~$t_n=1$ ���~$n \le 0$. ����� �����
���������������� ����������� ���������� ��������� ��������, ����������
������ ����� �������, ��� �� ������ ��� ������������ ������������ ������ [��.~�~(8)]:
$$
\vcenter{\halign{
\hfill$#$\hfill&&\bskip\hfill$#$\hfill\bskip\cr
               &    &    &    &    &    & \hbox{�������������} \cr
\hbox{㐎����} & T1 & T2 & T3 & T4 & T6 & \hbox{����� �� �����}\cr
  1 & 1         & 1        & 1      & 1    & -    & T5 \cr
  2 & 1         & 1        & 1      & -    & 1    & T4 \cr
  3 & 21        & 21       & 2      & 2    & 1    & T3 \cr
  4 & 2221      & 222      & 222    & 22   & 2    & T2 \cr
  5 & 23222     & 23222    & 2322   & 23   & 222  & T1 \cr
  6 & 333323222 & 33332322 & 333323 & 3333 & 2322 & T6 \cr
\multispan{7}\dotfill\cr
  n & A_n  & B_n & C_n & D_n  & E_n & T(k) \cr
n+1 & (A''_n E_n+1)B_n & (A''_nE_n+1)C_n & (A''_n E_n+1)D_n & A''_nE_n+1 & A'_n & T(k-1)\cr
\multispan{7}\dotfill\cr
}}
\eqno(26)
$$
���~$A_n=A'nA''_n$ �~$A''_n$ ������� �� ��������� $u_n$~�����
�������~$A_n$. ����������� ���� ������� �������� � ������~$n$ ��
�������~$n+1$ ����������� ��� \emph{�����} �����, ���������������~(22).
���� �� ����������~$u$ �~$v$ �����������~(23), �� ������~$A_n$,~\dots,
$E_n$ ����� �������� � ���������, �������� ������� ���� [��.~�~(9)]:
$$
\eqalign{
A_n &= (W_{n-1}W_{n-2}W_{n-3}W_{n-4})+1,\cr
B_n &= (W_{n-1}W_{n-2}W_{n-3})+1,\cr
C_n &= (W_{n-1}W_{n-2})+1,\cr
D_n &= (W_{n-1})+1,\cr
E_n &= (W_{n-2}W_{n-3})+1,\cr
}
\eqno(27)
$$
���
$$
\eqalign{
W_n &= (W_{n-3}W_{n-4}W_{n-2}W_{n-3})+1 \rem{��� $n>0$;}\cr
W_0 &=\hbox{'0'}\hbox{ � } W_n = \hbox{(�����)} \rem{ ��� $n<0$.}\cr
}
\eqno(28)
$$
%%339
������ �� ���� �����������, ����� �������� ���������������� ������ ����� ����.

� ����� ������, ���� ������� $T\ge 5$~����, ��
�������~$P=T-2$ � ��������� ������������������~$\<u_n>$, $\<v_n>$ �� ��������
$$
\eqalign{
v_{n+1}&= u_{n-1}+v_{n-1}+\cdots+u_{n-r}+v_{n-r};\cr
u_n &= u_{n-r-1}+v_{n-r-1}+\cdots+u_{n-P}+v_{n-P}
\rem{��� $n\ge 0$,}\cr
}
\eqno(29)
$$
���~$r=\floor{P/2}$, $v_0=1$ �~$u_n=v_n=0$ ���~$n<0$. ����~$w_n=u_n+v_n$,
 �� �����
$$
\eqalign{
w_n &= w_{n-2}+\cdots+w_{n-r}+2w_{n-r-1}+w_{n-r-2}+\cdots+w_{n-P},
\rem{$n>0$,}\cr
w_0&=1 \hbox{ � } w_n=0 \rem{��� $n<0$.}\cr
}
\eqno(30)
$$
��� ��������� ������������� ��� ������~$n+1$ �� �����~$k$ ����������
$w_n+w_{n-1}+\cdots+w_{n-P+k}$~�������� ���~$1\le k \le P$
�~$w_{n-1}+\cdots+w_{n-r}$--- �� �����~$T$; �����~$T-1$ ������������ ���
�����. ����� $u_n$~�������� ��������� �� �����~$T$, � �� ����� ���
�����~$T-1$ ��������������; $v_n$~�������� ��������� ��~$T-1$, ����~$T$
��������������; $u_{n-1}$~��������---��~$T-1$, ���� $T-2$~��������������, �~�.~�.
\htable{ ����~6}
{��������������� ��������� ������������ ������� � ������������ ����}%
{\hfill$#$\hfill&&\hfill\bskip$#$\bskip\hfill\cr
\hbox{�����} & \hbox{����} & \hbox{�������} &
\hbox{�������/����} & \hbox{���������}\cr
      & & & \hbox{� ���������} & \hbox{�����}\cr
\noalign{\hrule}
 4 & 2.885\ln S+0.000 & 1.443\ln S+1.000 & 50 & 1.4142136\cr
 5 & 2.078\ln S+0.232 & 0.929\ln S+1.022 & 45 & 1.6180340\cr
 6 & 2.078\ln S-0.170 & 0.752\ln S+1.024 & 34 & 1.6180340\cr
 7 & 1.958\ln S-0.408 & 0.670\ln S+1.007 & 34 & 1.6663019\cr
 8 & 2.008\ln S-0.762 & 0.624\ln S+0.994 & 31 & 1.6454116\cr
 9 & 1.972\ln S-0.987 & 0.595\ln S+0.967 & 30 & 1.6604077\cr
10 & 2.013\ln S-1.300 & 0.580\ln S+0.94l & 29 & 1.6433803\cr
20 & 2.069\ln S-3.164 & 0.566\ln S+0.536 & 27 & 1.6214947\cr
\noalign{\hrule}
}
 ����~6 ���������� ��������������� ��������� ���� ���������, �����~$S$
�� ������� ����. ᒎ���� "�������/����" �������� ���������, ����� �����
����� ����� �������������� �� ����� ������ �������� ���� � ����� �����
����� ������������ �� ����� ������ ������ ����. \emph{����� �����������
���� ����������� ����������� ����������� �� ����� ��� ����� ������} �,
��������; ����� �� ���� ������, �� ������� ���� ��� �������~$S$.

����~$T=4$, �� ��������� ��������� ����� ��, �� ��������, �������������
����������������� ������������ ������� \emph{���} ���������� �������
���������, ��� ���~$w_{2n+1}$ ���� �� �����~$0$
%$390
��� ����~$n$. ������� �������� ����.~6 ���~$T=4$ ���� �������� �����������
��������� �����������, ��������� � ���, ��� ����������
$$
\displaylines{
v_2=0, u_1=1, v_1=0, u_0=0, v_0=1\hbox{ � } v_{n+1}=u_{n-1}+v_{n-1},\cr
u_n=u_{n-2}+v_{n-2}\rem{��� $n \ge 2$.}\cr
}
$$
풎 �������� � ����� ���������� ����� ���������� (��.~���.~25 �~26).
\excercises
\ex[16] �� ���.~69 ������ �������, � ������� ��������~D ������������ ��
���� ������ ������� �~34-�� ��~65-�; � ����� �������
�������������� ������� �~1-�� ��~33-�?

\rex[21] ����� ��, ��� ����� ���� ��� ������� � ���������~D,
�.~�.~����� �� �� ������ ��� ��������� ����~D6, ��� ��������� ������� ��������?

\rex[22] ��������, ��� �� ��������� ����~D4 ������ ���������
������� $|D|[1]\ge |D|[2] \ge \ldots \ge |D|[T]$. ���������, ��������
����� ������� ��� ���������� ������ ��������� �����~D2 �~D3.

\ex[�20] �������� ������������ �������~(7).

\ex[��26] (�.~�.~�����~��., 1960.) ��������, ��� ��� ����~$p\ge 2$
���������~$f_p(z)=z^p-z^{p-1}-\cdots-z-1$ ����� $p$~��������� ������, ��
������� ����� ���� �����������~1 �� ���������� ��������. [\emph{㊀�����:} ����������� ���������~$z^{p+1}-2z^p+1$.]

\ex[��24] 態� ����� ����������---����������� ������ ����������� ����.~1, 5
�~6. �����������, ��� ������� ����� �������, �������� ������� ���������
������� ��������������� ������������~$p(z)$ �~$q(z)$: (1)~爑�� ���������
�������� � "������ �������������", ��������� $n$~��� �������,
����� ������������ ���~$z^n$ �~$p(z)/q(z)$. (2)~爑�� ��������� ��������,
�������������� � ������� ���� $n$~��� �������, ����� ������������
���~$z^n$ �~$p(z)/q(z)^2$. (3)~� ����������~$q(z^{-1})$ ���� "�������
������"~$\alpha$, �����, ���~$q(\alpha^{-1})=0$, $q'(\alpha^{-1}) \ne 0$,
$p(\alpha^{-1})\ne 0$, � ��~$q(\beta^{-1})=0$ �������, ���~$\beta=\alpha$ ���~$\abs{\beta}<\abs{\alpha}$.

��������, ��� ����������~$\varepsilon > 0$, �����, ��� ���� $S$~�����
����� �������� � ������ �������������, ��������� $n$~��� �������, � ��
����� ���� ��� �������������� $\rho S$~��������, ��~$n=a\ln
S+b+O(S^\varepsilon)$,
$\rho=c\ln S+d+O(S^{-\varepsilon})$, ���
$$
\displaylines{
a=(\ln \alpha)^{-1},\quad  b= -a\ln\left({p(\alpha^{-1})\over
-q'(\alpha^{-1})}\right)-1,
\quad c=a{\alpha\over -q'(\alpha^{-1})},\cr
d={(b+1)\alpha-p'(\alpha^{-1})/p(\alpha^{-1})+q''(\alpha^{-1})/q'\alpha^{-1}
\over -q'(\alpha^{-1})}.\cr
}
$$

\ex[��22] �����~$\alpha_p$---������� ������ ����������~$f_p(z)$ �� ���.~5.
������ ��������������� ���������~$\alpha_p$ ���~$p\to\infty$?

\ex[�20] (�.~�����, 1901.) �����~$N^{(p)}_m$ ���� ����� ��������
��������~$m$ � ���� ������������� ����� ����� �����~$\set{1, 2,~\ldots,
p}$. ��������, ����~$p=3$ �~$m=5$, �� ������� 13~��������:
$1+1+1+1+1=1+1+1+2=1+1+2+1=1+1+3=1+2+1+1 =1+2+2=
1+3+1=2+1+1+1=2+1+2=2+2+1=2+3=3+1+1=3+2$. ��������, ���
$N^{(p)}_m$~�������� ����������� ������� 䈁������.

\ex[�20] �����~$K^{(p)}_m$---����� ������������������� �� ����� � ������,
�����, ��� � ��� ��� $p$~���������������� ������. ��������, ����~$p=3$
�~$m=5$, ������� 24~��������: $00000$, $00001$, $00010$, $00011$, $00100$,
$00101$, $00110$, $01000$, $01001$,~\dots, $11011$. ��������, ���
$K^{(p)}_m$~�������� ����������� ������� 䈁������.

%%341
\ex[�27]\exhead(ሑ���� ��������� � ����������� ������� 䈁������.)
��������, ��� ������ ��������������� �����~$n$ ����� ������������ �������������
� ���� ����� ��������� ����� 䈁������ $p\hbox{-��}$~�������~$F^{(p)}_j$
���~$j\ge p$, ��������������� �������, ��� �� ������������ �������
$p$~���������������� ����� 䈁������.

\ex[�24] ��������, ��� $n\hbox{-�}$~������� �������~$Q_\infty$ �~(12)
����� ���������� ��������� ����� 䈁������ � ������������� ��������
$n-1$~������� 䈁������ ������ ������� (��.~���.~10).

\rex[M20] ������� ����������� ����� ��������� �������
$$
\pmatrix{
0 & 1 & 0 & 0 & 0 \cr
0 & 0 & 1 & 0 & 0  \cr
0 & 0 & 0 & 1 & 0 \cr
0 & 0 & 0 & 0 & 1 \cr
1 & 1 & 1 & 1 & 1 \cr
}
$$
� ������ ������������� �������������� �~(1).

\rex[22] �������� ��������� ���������� �������� ������
������������� �������������: ���� ������������� ����� ����������� �� �����
�����~$T$, �� ����� �������� �� ���� ������ ������ \emph{��������,} ����
������������� ����� ����������� �� ��������� �����, �������� ��~$T$, ��
����� �������� ����� \emph{��������} �� ���� ����� � \emph{������} ��
��������� [��.~(1)].

\ex[�35] �����~$T_n(x)=\sum_{k\ge0} T_{nk}x^k$, ��� $T_n(x)$---����������,
������������ �~(16). (a)~��������, ��� ��� �������~$k$ ����������
�����~$n(k)$, �����, ���~$T_{1k}\le T_{2k} \le \ldots \le T_{n(k)k} >
T_{n(k)+1,k}\ge\ldots\,$.. (b)~��� ������� ���~$T_{n'k'}<T_{nk'}$ �~$n'<n$,
 ��������, ���~$T_{n'k}\le T_{nk}$ ��� ����~$k\ge k'$. (c)~��������, ���
���������� ����������� ������������������~$\< M_n >$, �����,
���~$\sum_n(S) =\min_{j\ge 1} \sum_j (S)$ ���~$M_n\le S < M_{n+1}$,
��~$\sum_n(S)>\min_{j\ge 1}\sum_j(S)$ ���~$S\ge M_{n+1}$. [�.~(19).]

\ex[�43] ����� ��, ���~$\sum_{n-1}(m) < \sum_n (m)$
������~$\sum_n(m)\le\sum_{n+1}(m)\le \sum_{n+2}(m) \le \ldots?$ ( ��
��������� ������ �������� �� ���������� ����.~2.)

\ex[M43] ���������� ��������������� ��������� ������������ ������� �
����������� �������������� ��������� ��������.

\ex[32] ����� ��, ��� ������� ��� ������������ ������������
������������� ����� ���������� ����� �������, ��� �������������
$S+1$~��������� �������� ���������� ����� ���������� ������ ������� (��
��������������� �����) � ������������� $S$~��������� ��������?

\ex[30] ����� ��, ��� ����������� ����������� ������������� ���� ���������
��������� ����� ������� � ��� ������, ��� ��������� ����������
�������������� ��������� �������� ����������, ���� ���������,
����� ��������� ������� ����������� �� �����, ��� �� $T-1$~������?
(�������� ��������� ����������.)

\ex[21] ᎑������ �������, �����������~(1), ��� ������������
������ ���������� ������� ��� ����� ����.

\ex[�24] ����� ������������ ������� ��� ������������
����������� ���������� �� ����� ������ �������������~(7) �~(16)? �����
�����������, �����������~(9) �~(27), ���������� ������ ����� �������?

\ex[11] 璎 ������ ��������� �� ������~7 �~(26)?

\ex[M21] ������ ���� ������������������~(24) �������������� ����� �����
���� ����������. ����������� �� ��� ������� ��� ���������
������ ������������������? ᔎ���������� � �������� �������
�~$t_n-t_{n-1}-t_{n-2}$.

\rex[29] ����� ��������� ���� ���� �� ������� �~(25), (27) � (28), ���� ��
(23)~���������� ��~$v_{n+1}=u_{n-1}+v_{n-1}+u_{n-2}$, $u_n=v_{n-2}+u_{n-3}+v_{n-3}+u_{n-4}+v_{n-4}$?
%%342
\ex[��41] ��������� ��������������� ��������� ����������� ��������� �
������������ ����, ���� �������~$v_{n+1}$ ��������� ��� ����� ������$q$
������~$u_{n-1}+v_{n-1}+\cdots+u_{n-P}+v_{n-P}$ ��� ���������~$P=T-2$
�~$0\le q \le 2P$. (� ������ ��������������� ������
������~$q=2\floor{P/2}$; ��.~�~���.~23.)

\ex[19] �����������������, ��� ����������� ������� � ������������ ����,
���������� � ����� ����� ������, ����������� �� 32~���������
�������. (����� ������ ���� �� �����, ��� ��� ������� � ������ � ������� �
82~��������� � 6~�������.)

\ex[�21] ��������������� ��������� ������������ ������� � ������������
���� �� ������� ������ ���~$S=2^n$ � ���~$S=2^n+2^{n-1}$ (��.~���.~25).

\ex[23] ���� ��������� ������� ������������ �� ������ � ������������ �
������ ��������������, �� ����������� ��������� ������������ ������ �
"������� �� �����������". �� ������� ������� �� ���� ��������
������� ����, ���� ���� �� ��� �� ������ ������, ����� �� ���������� ���
����� ��� ��������� ��������, � ���������� �������� ����� ���������� ���
�������.

����� ��, ��� ��� ��������� "������� �� �����������" ������
��������� ���������� ���������� �� ����, ��� ������������ ���������
�������, ��� ������� ��� �� ������������ �� �� ������� ���� �� ��� �����
(���� �����, �������, ����� ��������� ������, ����� ��� ����� �������
������ �������� ������).
\edef\exref{\the\excerno}
\ex[�26] ���������� ���������� ���������� ������ ������� ��������� ����
�������. ��������, ��� ����������� ����� \emph{���������} �� ��� �
��������� ������: ���� ������� ����� ���� � �� ������������� ����� ����
��������� �������������~$(a, b, c, d, e)$, �����, ��� ��������� "�������
�� �����������" �������~$n$ ��� ������ ��� ��� ����������,
��~$a+b+c+d+e\le t_n$, ���~$t_n$---��������������� ����� ��� ����������� ����������~(1).

\ex[�47] ㏐.~\exref{} ����������, ��� ����������� �������������
���������� ����� ���� ���� "������� �� �����������" � ������ �������������
����� ���. �� �������� �� ��� ����������� ����� � ������ ������������� ����� ��������?

����� �����~$a$ �~$b$ ������� �������, � �����������, ��� $a+b$~����
����� 䈁������~$F_n$. ����� �� ��������� �������������, ����������� �.~�.~������:
����� ��������� ��������, �������������� ������ "������� �� �����������",
 ������������ � �������������~$(a, b)$, ������ ���
�����~$((n-5)F_{n+1}+(2n+2)F_n)/5$? (㊀������ �������� �����������,
�����~$a=F_{n+1}$, $b=F_{n-2}$.)

\ex[42] ᎑������ �������, ����������� ����.~2, ��� ������������ �������
� ������������ ����.

\subsubchap{��������� �������}%5.4.3
������ �������� �����, ���������� "��������� ��������", �� ����� ���� ����
������� ������ ����������� [�.~�.~���� �~�.~�.~������, ACM Nat'1
Conference, {\bf 14} (1959), Paper~14]. ���� � ������� ���� ������
�������������� ��� 6~���� �~190~��������� �������� � ��������������
����������� �� �.~5.4.2:
\ctable{
#\hfil\bskip&\bskip\hfil$#$\bskip\hfil&\bskip\hfil$#$\bskip\hfil
&\bskip\hfil$#$\bskip\hfil&\bskip\hfil$#$\bskip\hfil
&\bskip\hfil$#$\bskip\hfil&\bskip\hfil$#$\bskip\hfil&#\hfil\cr
          & T1     & T2      & T3     & T4     & T5     & T6    & ���������� ������������ ��������� ��������\cr
������~1. & 1^{55} & 1^{50}  & 1^{41} & 1^{29} & 1^{15} & -     & 190 \cr
������~2. & -      & {1^5}_* & 2^9    & 3^{12} & 4^{14} & 5^{15}& 190 \cr
������~3. & 15^5   & 14^4    & 12^3   & 9^2    & {5^1}_*& -     & 190 \cr
������~4. & -      & {15^1}_*& 29^1   & 41^1   & 50^1   & 55^1  & 190 \cr
������~5. & 190^1  & -       & -      & -      & -      & -     & 190 \cr
}
%%343

\bye
