\input style
%%150
��� ����������) ������� ���������� ������������ � ������ �� �������. ␅�� 
�� ������ ���������� ���������������� 
$N^2$, � �� $N\log N$ (��. ���.~25). � ������� �� ������ 
���������� ����������, ������� ��� �����������, �������� Q 
������������ ��������������� �����!

� ���������� ������ ����� ���������� ��� ������� ��������� ��������, 
�������������� �� ������ ������� �������� ������������ ����� $K$, ������� 
��������� �����������. � �� ��� ������������ ������� .� ���, ����� � 
��������� ����� ���� Q2 �������� \emph{���������} ����� ����� $q$ ����� 
$l$ �~$r$; � ���� ���� ����� �������� ���������� "$K\asg K_l$, $R\asg 
R_l$"  ��
$$
K\asg K_q, \quad R\asg R_q, \quad R_q\asg R_l.
\eqno(27)
$$
񎃋���� �������� (25), ����� ��������� ����� ����� �������� ��������� � 
������� ���� $2(N+1)/(M+2)-1$~���, ��� ��� �������������� ����� ������ 
�������������, � ��������� �����---������� ������ �� ��������� ��������� � 
��������� ��������.

⒎��� ����������� ����� ������� � ���, ����� ����������� ��������� 
������� ����� � ����� ������� ��� ���� ������������ ������. 򀊎�� 
������� ���������� �. �. 񈍃���� [{\sl CACM\/}, {\bf 12} (1969), 
185--187], ������� ��������� � �������� $K_q$  ����� ������� ���� ��������
$$
K_l, \quad K_{\lfloor(l+r)/2\rfloor}, \quad K_r.
\eqno(28)
$$

������ 񈍃����� ��������� ����� ��������� � $2N \ln N$ �������� 
�� ${12\over7}N\ln N$ (��. ���. 29). 쎆�� ��������, ���. � ����
������ $B_N$ �������������� ������������ � $C_N/5$, � �� �~$C_N/6$, ��� 
��� ����� ������� ��������� ����������� �����, ������������� �� 
��������� ������, ������� ����� ����� ������ ����������� ��������, �� 
8\%. (������ ������ ��. � ���.56.) ␅�� ������ � ��������� ������ ��� 
��� ������� $N^2$, ������ � ����� ��������� ���������� ��������� ���� �� 
�����-���� �������� ����������� �� ��������.

�.~�.~������� � �.~�.~쀊-ꅋ��� 
[{\sl JACM\/}, {\bf 17} (1970), 496--507] 
���������� ������������� ������������ ������� �������� ������ �� $2^k-1$ 
�������, ��� $k$ ���������� ���, ����� $2^k\approx N/\ln N$. ��� 
������������ ����� ������������� ������� ������� ������� ����������, ����� 
���� �������� ����������� ����� ��������� ������� �� $k$ ���������� ����� 
����� (� ���������� ���� ����� �������� �� $2^k$ ���������, ������������ 
���������� �������������� ������������). � �������������� 
����� ����������� ���������� ��������. 񐅄��� �����, ���������,
 ����������� ����� ���������� "���������� ������������", �������� ����� 
��, ��� � ��� ������ ������� 񈍃�����, ����� $N$
%%151
��������� � ������������ ��������� ��������, �� ��� $N\to\infty$ ��� 
�������������� ������������ � $N\log_2N$.

\section ����� ����������� ����������. � �������� ������ � ������,
 ���������� ��������� �� ���� ���� ����������, ������� ��������������� 
������; � ��� ������������ \emph{�������� �������������} ������, 
�.������ �� ������������ ������������� ��� �������� �����. ⌅��� ���� 
����� ���������� ����� ����� ��� �����, � ���� ������ �����������, ����� 
�� 0 ��� 1 ��������� ���� �����. � ������ ���������� �� �������� 
���������������� �������� ���������� � �� ����� ���� ����� ���������� 
������� ����������. � ��� �� ������� �� �������� �����, 
��������������� � �������� ������� ���������, �� �������� ��� 
"�������� ����������� �����������". � ����� ������ ���� �������� ����� 
������� ��������� �������:
\enumerate
\li ��������������� ����������� \emph{�� �������� ��������� ��������� 
����} ���, ����� ��� �����, ������������ � 0, ��������� ����� ����� 
�������, ������������� � 1. 䋟 ����� ���� ����� ����� ����� ���� $K_i$, 
������������ � 1, � ����� ������ ���� $K_j$, ������������ � 0, ����� ���� 
$R_i$ � $R_j$ �������� �������, � �������  �����������, ���� �� ������ $i>j$.

\li �� $F_0$---��������� ���������, ������������ � 0, � $F_1$---��� 
���������. ����� � $F_0$ ����������� ���������� (����� ������ �� 
\emph{�������} ���� �����, � �� �� ��������) �� ��� ���, ���� ��������� 
$F_0$ .�� ����� ��������� �������������; ����� ��������� �� �� � $F_1$.
\enumend

퀏�����, � ����.~3 ��������, ��� ��������� �������� ����������� 
���������� �� ���� 16 ��������� �����, ���������� ������ � ������������ 
������� ���������. � ������ 1 ������� �������� ����; ����� ������� �� 
������� ���� �������� �� ������ ������. � ������ ������ ����������� 
������ ������ �� �������, ����, �� �������---�� �������� ����. (�������� 
������ �������� ������������� ������������ ����� � 10-��������� 
��������.) ꎃ�� �� ����� ���������� �� .���������� ���� ��������� ����� 
������, �� ������������, ��� ������ �� ���������� ����� �������� ����� 
�� ������ ��������,- ��� ��� ��� ����� ����� ����� ������  ��  
�������������. 瀏��� "${}^4[0232\ 0252]$" ��������, ��� ������� $0232\ 
0252$ ��� ��������� ����������� �� ���������� ���� �����. � ���� 
���������� ������ ���������� �� ���������� ���� �� ���� ������ ������; 
����� ��������� ��������, ���������� ��������� �� ������ ����.

⅑� ������� ����������, ���������� � ����.~3, ����������� �� 22 ������; 
��� ��������� ������ ���������������� ����� � ������� ���������� (����.~2).
 ����� �������� ����� 82 ����� ������; �� �� ������, ��� ����� �������� 
����� ��� �������
151
%%152
\picture{򀁋��� 3}
%%153
$N$ � ���������������� ������, ��� ����� ��������� � ������� ����������, � 
������������� � ����������� ������������� ������. �� ����� ������� � 
����.~3 ����� 17, �. �. ������ ��������. 瀌����, ���, ���� ����������� 
10-������� �����, � ������ ������� ��� �������� ����� ������� �� 
���������� ���� ������ �������� ����.

ꀊ � ��� ������� ����������, ��� �������� "���������� � ��������" 
���������, ��������� ����������, ����� ��������������� ������. ⌅��� 
���� ����� ����������� � ������ ������� ���������� �� ���������, ������ 
������ ������������ ����� �������, ��� ��� ������ ����� �. ���� ������ 
������� �� ���������� ����� ����� � ����������� ������. � ���������, 
����������� ����, ������� ����� $(r, b)$ ��������� �� ��, ��� ������� � 
������ �������� $r$ ������� ���������� �� ���� $b$; ����� ������� ����� 
�� ���������� � �����: ��� ������ ������ ������, ��������� � ���� 
��������� ���� ������ �������������� ����� �������.

\alg R.(����� ����������� ����������.) 瀏��� $R_1$, \dots, $R_N$ 
��������������� �� ��� �� �����; ����� ���������� ���������� �� ����� 
����� �����������: $K_1\le \ldots \le K_N$. �����������, ��� ��� 
�����---$m$-��������� �������� ����� $(a_1\ a_2\ \ldots\ a_m)_2$; $i$-� �� 
����������� ��� $a_i$ ���������� 
"��� $i$" �����. 򐅁����� ��������������� ����, ��������� �� 
$m-1$ ���������. ���� ��������, �� ��������, ������� ��������� �������� 
����������� ���������� � ������������, ��������� ����;
�������� ��������� ������������������ � ����� ��������� ������������� (��� 
������� ����� � ������ � � �����������).

\st[퀗������ ���������.] ������� ���� � ���������� $l\asg 1$, $r\asg 
N$, $b\asg 1$.

\st[퀗��� ����� ������.] (� ������ �� ������ ������������� �������  
$R_l\le \ldots \le R_r$ �� ���� $b$; �� ������ ��������� $l\le r$.) 呋� 
$l=r$, �� ������� � ���� \stp{10} (��� ��� ����, ��������� �� ������ �����,
 ��� ������������). � ��������� ������ ���������� $i\asg l$, $j\asg r$.

\st[������ $K_i$ �� 1.] ������ ��� $b$ ����� $K_i$.. 呋� �� ����� 1,
 �� ������� � ���� \stp{6}.

\st[󂅋����� $i$.] 󂅋����� $i$ �� 1. 呋� $i\le j$, �� ������������ � 
���� \stp{3}; � ��������� ������ ������� � ���� \stp{8}.

\st[������ $K_{j+1}$ �� 0.] ������ ��� $b$ ����� $K_{j+1}$. 呋� �� 
����� 0, �� ������� � ���� \stp{7}.

\st[󌅍����� $j$.] 󌅍����� $j$ �� 1. 呋�$ i\le j$, �� ������� � ���� 
\stp{5}; � ��������� ������ ������� � ���� \stp{8}.

\st[����� ������� $R_i$, $R_{j+1}$]. ����� ������� 
$R_i\xchg R_{j+1}$, ����� ������� � ���� \stp{4}.

\st[������ ������ ������.] (� ����� ������� ������ ����������
%%154
���������, $i=j+1$, ��� $b$ ������~$K_l$, \dots, $K_j$  �����~$0$, 
� ���~$b$ ������ $K_i$, \dots, $K_r$ �����~$1$.) 󂅋����� $b$ ��~1. 呋� 
$b>m$, ��� $m$---����� ����� ����� � ������, �� ������� � ����~\stp{10}. 
(��� ��������, ��� ������� $R_l$ \dots $R_r$ ������������. 呋� � ����� �� 
����� ���� ������ ������, �� ����� �������� ����� �� ������.) � ��������� 
������, ����~$j<l$ ���~$j=r$, ������������ � ����~\stp{2} (��� 
������������� ���� ��������� ������� ��������������~1 ���~0). 呋� �� 
$j=l$, �� ��������� $l$ ��~1 � ������� � ����~\stp{2} (���������� ������ 
���� ���, ������ 0).

\st[������ � ����.] ������ � ���� ������� $(r, b)$, ����� ���������� 
$r\asg j$ � ������� � ���� \stp{2}.

\st[⇟�� �� �����.] 呋� ���� ����, �� ���������� ���������. � 
��������� ������ ���������� $l\asg r+1$, ����� ��. ����� ������� $(r', 
b')$, ���������� $r\asg r'$, $b\asg b'$ � ������������ � ����~\stp{2}.
\algend

\prog R.(����� ����������� ����������.) � ��������� ��������� ��� 
������ \MIX{} ������������, �� ��������, �� �� ����������, ��� � � 
��������� Q. 獀����� ���������: $|rI1|\equiv l-r$, $|rI2|\equiv r$, 
$|rI3|\equiv i$, $|rI4|=j$, $|rI5|\equiv m-b$,  
$|rI6|=\hbox{������ �����}$, ���� �� ������� ����, ��� � ��������� 
�������� (���������� ����) ������ ��������~$|rI3|=i-j$ ���~$|rI4|=j-i$. 
䂎����� �������� ����������� ���������� ����������� ������������� � ���� 
��������� ������ |SRB| (�������� ����� ����������� |AX| ������), |JAE| 
(�������, ���� ���������� |A| �����) � |JAO| (�������, ���� ���������� |A| 
�������), ������������ � �.~4.5.2. �����������, ��� $N\ge 2$.
\code
START& ENT6 & 0         & 1 & R1. 퀗������ ���������. ������� ����.
     & ENT1 &1-N        & 1 & $l\asg 1$.
     & ENT2 &N          & 1 & $r\asg N$.
     & ENT5 &�-1        & 1 & $b\asg 1$.
     & JMP  &1F         & 1 & � R2 (�������� �������� $l=r$).
9H   & INC6 &1          & S & R9. ������ � ����. [$|rI4|=l-j$]
     & ST2  &STACK,6(A) & S
     & ST5  &STACK,6(�) & S & $(r, b)\Rightarrow\hbox{����}$.
     & ENN1 &0,4        & S & $|rI1|\asg l-j$.
     & ENT2 &-1,3       & S & $r\asg j$.
1H   & ENT3 &0,1        & � & R2. 퀗��� ����� ������. [$|rI3|=i-j$]
     & ENT4 &0,2        & A & $i\asg l$, $j\asg r$. [$|rI3|=i-j$]
3H   & INC3 &0,4        & C'& R3. ������ $K_i$ �� 1.
     & LDA  &INPUT,3    & C'&
     & SRB  &0,5        & C'& $\hbox{������� ��� |rA|}\asg\hbox{��� $b$ ����� $K_i$}$.
%%155
       &JAE   &4F       & C'   & � R4, ���� �� ����� 0.
6�     &DEC4  &1,3      & C''+X& R6. 󌅍����� $j\asg j-l$. [$|rI4|=j-i$].
       &J4N   &8F       & C''+X& � R8, ���� $j<i$. [$|rI4|=j-i$]
5�     &INC4  &0,3      & C''  & R5. ������ $K_{j+1}$ �� $0$.
       &LDA   &INPUT+1,4& C''
       &SRB   &0,5      & C''  & $\hbox{������� ��� |rA|}\asg\hbox{��� $b$ ����� $K_{j+1}$.}$
       &JAO   &6�       & C''  & � R6, ���� �� ����� 1.
7�     &LDA   &INPUT+1,4& B    & R7. ����� ������� $R_i$, $R_{j+1}$.
       &LDX   &INPUT,3  & B
       &STX   &INPUT+1,4& B
       &STA   &INPUT,3  & B
4H     &DEC3  &-1,4     & C'-X  & R4. 󂅋����� $i$. $i\asg i+1$. [$|rI3|=i-j$]
       &J3NP  &3B       &C'-X    & � R3, ���� $i\le j$. [$|rI3|=i-j$]
       &INC3  &0,4      &A-X     & $|rI3|\asg i$.
8�     &J5Z   &0F       &A       & R8.  ������ ������ ������. [$|rI4|=\hbox{����������}$]
       &DEC5  &1        &A-G     & � R10, ���� $b=m$, ����� $b\asg b-1$.
       &ENT4  &-1,3     &A-G     &$|rI4|\asg j$.
       &DEC4  &0,2      &A-G     &$|rI4|\asg j-r$.
       &J4Z   &1�       &A-G     & � R2, ���� $j=r$.
       &DEC4  &0,1      &A-G-R   &$|rI4|\asg j-l$.
       &J4N   &1�       &A-G-R   & � R2, ���� $j<l$.
       &J4NZ  &9�       &A-G-L-R & � R9, ���� $j\ne l$.
       &INC1  &1        & K      & $l\asg l+1$.
2�     &J1NZ  &1�       & K+S    & ����, ���� $l\ne r$.
0�     &ENT1  &1,2      & S+1    & R10. ⇟�� �� �����.
       &LD2   &STACK, 6 (A)& S+1
       &DEC1  &0,2      & S+1
       &LD5   &STACK,6 (�)& S+1  & $\hbox{񒅊}\Rightarrow(r, b)$
       &DEC6  &1        & S+1
       &J6NN  &2�       & S+1    & � R2, ���� ���� �� ��� ����.
\endcode
\progend

␅�� ������ ��������� �������� ����������� ���������� ������� ��
$$
\eqalign{
A &=\hbox{����� ������, � ������� $l<r$;}\cr
B &=\hbox{����� ���������;}\cr
C &=C'+C''=\hbox{����� �������� �����;}\cr
G&=\hbox{����� �������, ����� � ���� R8 $b>m$;}\cr
K&=\hbox{����� �������, ����� � ���� R8 $b\le m$, $j=l$;}\cr
L&=\hbox{����� �������, ����� � ���� R8 $b\le m$, $j<l$;}\cr
R&=\hbox{����� �������, ����� � ���� R8 $b\le m$, $j=r$;}\cr
S&=\hbox{����� �������, ����� ���-���� ���������� � ����;}\cr
X&=\hbox{����� �������, ����� � ���� R6 $j<i$.}\cr
}
\eqno(29)
$$
%% 156
� ������ ꈐ����� $S=A-G-K-L-R$, ��� ��� ����� ����� ����������  ����� 
$27A+8B+8C-23G-14K-17L-19R-X+13$ ������. � ���� ���������� ��������� 
����� ��������� �������� ����� �������� ����� (��. ���.~34). ����� 
����������� ���������� ����� ����� ��������, ���� ��� ���������� ����� 
��������� �������� $r-l$ ��������� ������� �������, ��� ��� ������� � 
��������� Q, �� �� �� ����� ������������� �� ����� �������������������.

䋟 ������� ������� ���������� �������� ����������� ���������� 
������������� ��� ���� �������� ������:
\medskip
\item{i)} �� $N=2^m$ � �����, ������� ���� �������������,--- ������ ����� 
$0$, $1$, $2$, \dots, $2^m-1$, ������������� � ��������� �������.

\item{ii)} �� $m=\infty$ (�������������� ��������) � �����, 
������� ���� �������������,---�����������, ���������� �������������� � 
���������� $[0, 1)$ �������������� �����.
\medskip
\noindent
������ ������~(i) ������������ �����, ������� �� �������� �������� � 
�������� ���������� (��. ���.~35). 񋓗��~(ii) ������������ ������, 
������� �� \emph{�����} �������� ��� ����������. � ��������� ������� 
��������� ������ ������ ����������� ���� � ������� ��������:
$$
\matrix{
\hbox{\bf ⅋�����} & \hbox{\bf 񋓗�� (i)} & \hbox{\bf 񋓗�� (ii)}\cr
A & N & \alpha N\cr
B & {1\over4} N\log_2N & {1\over4}N\log_2 N\cr
C &  N\log_2N & N\log_2N \cr
G &{1\over2} N & 0 \cr
K & 0 & {1\over2} N\cr
L & 0 &  {1\over2} (\alpha-1)N\cr
R & 0 &  {1\over2} (\alpha-1)N\cr
S & {1\over2}N & {1\over2}N\cr
X & {1\over2}N & {1\over4} (\alpha-1)N\cr
}
\eqno(30)
$$
焅�� $\alpha=1/(\ln 2)=1.4427$. 瀌����, ��� ������� ����� �������,
 �������� ����� � ��������� � �����, �� ��������, ��������� � ����� 
�������, �������� ���� �� ��, ��� � ������ (ii) ����� ������ �� 44\% 
������. � ���������� $N$ ��������� � ������ (ii) ���� \MIX-��������� 
�������� � ������� �������������� $14.4N\ln N$ ������ �������. ��� ����� 
����� ���� �� ��������� �������� �� $11.5N\ln N$, ���� ��������������� 
������������ �� ���.~34. 񎎒����������� �������� ��� ��������� Q �����
%% 157
$12.7N \ln N$, �� � �� ����� ��������� ��~$11.7 N \ln N$, ���� 
��������������� ������������ 񈍃����� � �������� ������� �� ���� ������.

� ������ ������������ ������������� ������ �������� ����������� 
���������� �������� � ������� �������� ������� �� �������, ������� � 
������� ����������; ���������� ��� ������ \MIX{} ��� ������� �������, ��� 
������� ����������. � ���.~53 ��������, � ����� ���� ����������� ���� 
������� ��� ������������� �������������.  �� ��������, ��� ���� ��� 
������ ������� �� ������������� � ���. ��� ��� ����� ��������. 
\emph{06������ ����������� ���������� � ��� ����, ��� ��� ������� ����, �� 
����� ����������, ���� ������� ���������� �����,} ��� ��� ��� �������� 
����� ��������� ������, ��������� �������, ������� ��������� ��������� 
���������� ������, ���� $b$ �� ������ $>m$. � ���������� ������ 
��������� ���� ���������� ��������� � ������ � ���.~40.

ꀊ �������� ����������� ����������, ��� � ������� ���������� �������� 
�� ���� ����������. 瀏��� �������� ������� �� ��� ���, ���� ���� �� ����� 
������ �� ��� �����: ����� �������, � ������� ��� ����� $\le K$ ��� 
��������� $K$, � ������ �������, � ������� ��� ����� $\ge K$. � ������� 
���������� � �������� $K$ ���������� �������� ���� �� �����, � �� ����� 
��� � �������� ����������� ����������, �� ��������, ���������� ��������� 
������������� ���� �� ������ �������� �������������. ��� �������� 
������������ ������� ����, �� �������� ����������� ���������� ������� 
�.~������������, �.~葁���, X.~������� � �.~����� [{\sl JACM\/}, {\bf 6} 
(1959), 156--163] �������� �� ��� �� ����������� ������� ����������. 
⎇����� ����� � ������ ����� ����������; ��������, 䆎� 쀊����� ���������
�������� $K\approx{1\over2}(u+v)$, ���� ��������, ��� ��� ����� �����
� ��������� ����� $u$ �~$v$.

噅 ���� ��������� ���������� ��������� �.~�.~���~����� [{\sl CACM\/}, 
{\bf 13} (1970), 563--567]: ������ ���� ����� �������� $K$ �������, �� 
"������", ������ ����� ���� ������� �������� $K$, ����� � �������� 
���������� �� ���������� ������� 
$K'=\max(K_l, \ldots, K_i)$ �~$K''=\min(K_j, \ldots, K_r)$. 쎆�� 
����������� $i$ �� ��� ���, ���� �� ���������� ����, ������� $K'$; ����� 
������  ��������� $j$, ���� �� ���������� ����, ������� $K''$, ����� 
���� �������� �� ������� �/��� �������� ��������~$K'$ �~$K''$. 
������������ ����� ��� ���� ������������ ���������� ����������, ��� ��� 
������� ����� $1.64N\ln N=1.14N\log_2N$ ���������. ��� ������������ �����, 
����������� � ���� �����, ��� ��������� �������� ��� �� ������� 
����������� �������������� ����������.

������ �������� ����������� ���������� �� ������ ������� ��������� � 
����������, ������� 2, ����������� � �.~5.2.5.
%%158

\section * ��������������� ������. ������ ���������� �������� ���������� 
�������� � ��������� �������� ������������ �������������� �������, 
������� ��������� ������ ������ � �������� ����������� ���������������� 
��������� �������. 퀏�����, ��� ������� ������ �������� [������� (9)] �� 
����������� � ��������
$$
W_n={1\over n!}\sum_{0\le r <s\le n} s!r^{n-s}.
\eqno(31)
$$
ꀊ��� �� ��������������� ��������?

쎆�� ����������� ��� ��, ��� ��� ������������ ����� ��������� [������� 
(5.1.4--41)]. ����, ������ ��� ��������� ������, ������� ��� ��� 
����������� ���������� � ����� �.~5.1.4.

葑��������� ������� (31) ����������, ��� ����� ��� $s=n$
������, ��� ����� ��� $s=n-1$, � �. �.; ��� ������� �� ����� � ������ $s$ 
�� $n-s$. � ����� ������, ��� �� ����� ���� ������� ����� ��������� 
����������� $t=n-s+1$, $m=n+1$, � ���������� ������� ������� (31) ������ ���
$$
{1\over m}W_{m-1}={1\over m!}\sum_{1\le t< m}(m-t)!\sum_{0\le r<m-t}r^{t-1}.
\eqno(32)
$$
䋟 ���������� ����� ���������� ������ ��������� ��������������� ���, 
���������� �� ������� ������������ ������:
$$
\eqalign{
\sum_{0\le r<N} r^{t-1} 
&={N^t\over t}-{1\over2}(N^{t-1}-\delta_{t1})+{B_2\over2!}(t-1)(N^{t-2}-\delta_{t2})+\cdots=\cr
&={1\over t}\sum_{0\le j\le k}\perm{t}{j}B_j(N^{t-j}-\delta_{tj})+O(N^{t-k})\cr
}
\eqno(33)
$$

(��. ���. 1.2.11.2--4). 񋅄���������, ���� ������ �������� � �������� 
���� ����
$$
{1\over m!}\sum_{1\le t<m} (m-t)!(m-t)^t\,t^k, \quad k\ge-1.
\eqno(34)
$$
ꀊ � � �.~5.1.4, ����� ��������, ��� ��� ��������� $t$, �\'������ 
$m^{1/2+\varepsilon}$, ����� ����� ������������ ����: 
$O(\exp(-n^\delta))$. 獀���, ����� �������� $t =O(m^{1/2+\varepsilon})$ � 
�������� ���������� �� ������� 񒈐�����
$$
{(m-t)!(m-t)^t\over m!}=
\sqrt{1-{t\over m}}
\exp\left({t\over12m^2}-\left({t^2\over2m}+{t^3\over3m^2}+{t^4\over4m^3}+{t^5\over5m^4}\right)
+O(m^{-2+6\varepsilon})\right).
$$
򀊈� �������, ��� ���������� ��������������� �������� �����
$$
r_k(m)=\sum_{1\le t<m} e^{-t^2/2m}t^k, \quad k\ge-1.
\eqno(35)
$$
%%159
(񓌌�������� ����� ����� ����� ���� �� �������������� �� ���� �������� 
$1\le t<\infty$, �� ������� ��� ���� ���������������� �������� �����, 
���������, ��� ������� ����, �������� � ����� �������� ��� 
$t>m^{1/2+\varepsilon}$ ������������ ����.)

�� $g_k(x)=x^ke^{-x^2}$ �~$f_k(x)=g_k(x/\sqrt{2m})$. � ������� 
������������ ������ ���~$k\ge 0$
$$
\eqalign{
\sum_{0\le t<m} f_k(t)&=\int_0^m f_k(x)\,dx
+\sum_{1\le j\le p}{B_j\over j!}(f_k^{(j-1)}(m)-f_k^{(j-1)}(0))+R_p,\cr
R_p&={(-1)^{p+1}\over p!}\int_0^m B_p(\{x\})f_k^{(p)}(x)\,dx=\cr
   &\left({1\over\sqrt{2m}}\right)^p 
O\left(\int_0^\infty\abs{g_k^{(p)}(y)}\,dy\right)
=O(m^{-p/2});\cr
}
\eqno(36)
$$
�������������, ��� ������, �� ��������, ��� �� �������, ��� � ������, 
����� �������� ��������������� ��� ���~$r_k(m)$, ���� ������ $k\ge 0$. � 
��� $k=-1$ ���� ����� �� �������, ��� ��� �������� $f_{-1}(0)$ �� 
����������; ������ ����� ������ �������������� ��~$1$ ��~$m$, ��� ��� 
���������� ����� �� ���� ��������� ��������~$m$, ���� ������ ������ 
�����~$1$. (茅��� � ���� ���� ����, �, ������ ��� ��������� ������, 
�������� ������ ��������� � ���, ��� �� ������ ����� ������.)

����� ��������� ��� �������, ����� �������� �� ����������� 
$g_{-1}(x)=(e^{-x^2}-1)/x$, $f_{-1}(x)=g_{-1}(x/\sqrt{2m})$; ����� 
$f_{-1}(0)=0$ � $r_{-1}(m)$ �������� �������� 
��~$\sum_{0\le t< m} f_{-1}(t)$. 󐀂����� (36) ����������� ������ � 
���~$k=-1$, � ���������� �������� ��� "������ ������" (��. ���. 43):
$$
\eqalign{
{2\over\sqrt{2m}}\int_0^m f_{-1}(x)\,dx&=
   2\int_0^m{e^{-x^2/2m}-1\over x}\,dx=\int_0^{m/2}{e^{-y}-1\over y}\,dy=\cr
&=\int_0^1{e^{-y}-1\over y}\,dy+\int_1^{m/2}{e^{-y}\over y}\,dy-\ln(m/2)=\cr
&=-\gamma-\ln(m/2)+O(e^{-m/2}).\cr
}
$$

򅏅�� � ��� ���������� ������ � ������ ��� ����, ����� ������� ������� 
�����, ������� �����, ��� �������� � ������ � ���~ 44,
$$
W_n={1\over2}m\ln m+{1\over2}(\gamma+\ln2)m-{2\over3}\sqrt{2\pi m}
+{31\over36}+O(n^{-1/2}), \quad m=n+1.
\eqno(37)
$$
���� ����������� ������ ������ ��������.

%% 160

����� ���������������� �������� ����������� ����������, ���������� ����� 
��������������� ��������� ��� $n\to\infty$ �������� �����
$$
U_n=\sum_{k\ge2}\perm{n}{k}(-1)^k{1\over 2^{k-1}-1}.
\eqno(38)
$$
���� ������ ����������� ������� ������� ������ ����� �� ��������������� 
���������, � �������� �� ������������ �� ��� ���;
������������ ������ ���������� � ��������� ����, ������� ������������ 
������ � �. �. ����� ���������. 񋅄����� ����� ��� ��������� �.~�.~��~ ᐅ����.

����� ���������� � ������� (38) �� ������������ �������
������� ���������� $\perm{n}{k} (-1)^k$, �� ������ � ����, ��� ��������� 
����� � ���� ������������ ����:
$$
U_n=\sum_{k\ge2}\perm{n}{k}(-1)^k\sum_{j\ge1}\left({1\over2^k-1}\right)^j=
\sum_{j\ge1}(2^j(1-2^{-j})^n-2^j+n).
\eqno(39)
$$

呋� �������� $x=n/2^j$, �� ���� ���� ��������� � ����
$$
2^j(1-2^{-j})^n-2^j+n=
{n\over x}\left(\left(1-{x\over n}\right)^n-1+x\right).
$$
 $x\le n^\varepsilon$ �����
$$
\left(1-{x\over n}\right)^n=\exp\left(n\ln\left(1-{x\over n}\right)\right)
=\exp(-x+x^2O(n^{-1})),
\eqno(40)
$$
� ��� ������� �� ����� � ���, ����� ���������� (39) �����
$$
T_n=\sum_{j\ge1}(2^je^{-n/2^j}-2^j+n).
\eqno(41)
$$
����� ��������� ��� �����������, ���������� �������� 
$U_n-T_n=X_n+Y_n$, ���
$$
\eqalignno{
X_n&=
\sum_{\scriptstyle j\ge1\atop\scriptstyle 2^j<n^{1-\varepsilon}}
    (2^j(1-2^{-j})^n-2^je^{-n/2^j})=
    &\rem{[�.�. ��������� ��� $x>n^\varepsilon$]}\cr
&=\sum_{\scriptstyle j\ge1\atop\scriptstyle 2^j<n^{1-\varepsilon}} 
    O(ne^{-n/2^j})=
    &\rem{[��� ��� $0<1-2^{-j}<e^{-2^{-j}}$]}\cr
&=O(n\log n e^{-n^\varepsilon})
    &\rem{[��� ��� ������� $O(\log n)$���������];}\cr
Y_n&=
\sum_{\scriptstyle j\ge1\atop\scriptstyle 2^j\ge n^{1-\varepsilon}}
    (2^j(1-2^{-j})^n-2^je^{-n/2^j})=
    &\rem{[��������� ��� $x\le n^{-\varepsilon}$]}\cr
&=\sum_{\scriptstyle j\ge1\atop\scriptstyle 2^j\ge n^{1-\varepsilon}}
    \left(e^{-n/2^j}\left({n\over2^j}\right)O(1)\right)
    &\rem{[�� ������� (40)]}\cr
}
$$
%% 161

\bye