\input style
%% 161
�������� ���� ����������� �������, ��� ��� ��������� ����� ���� $O(1)$; 
�������������, $U_n-T_n=O(1)$. (�. ���.~47.)

� ��� ��� �� ��� �� ������������ ������� �������, ������� �� 
������������� ���������� �� ������������� �����, ��
\picture{���. 20. ꎍ���� �������������� ��� �������� � �����-���������.}
��� �������� ����~$T_n$ ����������� ����� ����, ���������� �� ������� 
��������� ������ ������� ������������ �����������. 呋� $x$---������������ 
������������� �����, ��
$$
e^{-x}={1\over 2\pi i}\int_{1/2-i\infty}^{1/2+i\infty} \Gamma(z)x^{-z}\,dz=
{1\over 2\pi}\int_{-\infty}^\infty\Gamma\left({1\over2}+it\right)x^{-(1/2+it)}\,dt.
\eqno(42)
$$
䋟 �������������� ����� ��������� ���������� ���� ��������������, 
���������� �� ���.~20(a), ��� $N$, $N'$ � $M$ ������. 獀����� ��������� 
����� ����� ������� ����� ����� ������� ������ �������, � ������
$$
\sum_{0\le k<M} x^{-k}\lim_{z\to-k}(z+k)\Gamma(z)=
\sum_{0\le k<M} x^{-k}{(-1)^k\over k!}.
$$
荒����� �� ������� ����� ������� ���� 
$O\left(\int_{-\infty}^{1/2}\abs{\Gamma(t+iN)}x^{-t}\,dt\right)$,
� � ��� ������� ��������� ������
$$
\Gamma(t+iN)=O(N^{t-1/2} e^{-\pi N/2}) \rem{��� $N\to\infty$.}
$$
[񂎉���� �����-������� ��., ��������, � ����� A.~Erd\'elyi et al., Higher 
Transcendental Functions, 1 (New York: McGraw-Hill, 1953), ��.~1.] ���� 
�������� �� �������� �������
���������� ���: 
$O\left( e^{-\pi N/2}\int_{-\infty}^{1/2} (N/x)^t\,dt\right)$. 
荒����� �� �������
%% 162
������� ����� ���� ����� �� ���������. 䋟 ���������� ��������� �� 
������ ������� ������� ������������� ��� ������, ���
$$
\eqalign{
\Gamma\left({1\over2}+it-M\right)&=
\Gamma\left({1\over2}+it\right)/\left(-M+{1\over2}+it\right)
  \ldots\left(-1+{1\over2}+it\right)=\cr
&=\Gamma\left({1\over2}+it\right) O(1/(M-1)!).\cr
}
$$
񋅄���������, �������� �� ����� ������� ���� 
$O(x^{M-1/2}/(M-1)!)\times
 \int_{-\infty}^\infty\abs{\Gamma\left({1\over2}+it\right)}\,dt$. 
���� ��� $M$, $N$, $N'\to\infty$ ������� ����
�������� �� ������ �������; ��� ����� �������� ��������� (42). � 
���������������� ��������� (42) �������� � ���� � � ��� ������, ���� 
�������� $1\over2$ ����� ������������� ������.

� �� ����� ������������ ����� ��������������� ��� ������ ������ 
�������� �����������, ���������� �����-�������. ⅋����� $x^{-z}$ ����� 
�������� ������� ��������� �� $z$; �����
����� �������� ������ ��������� ��������� $1\over2$. 퀏�����,
$$
{1\over2\pi i}\int_{-3/2-i\infty}^{-3/2+i\infty}\Gamma(z)x^{-z}\,dz
=e^{-x}-1+x,
\eqno(43)
$$
� ���---����������� �������� � ������� (41) ��� $T_n$:
$$
T_n=n\sum_{j\ge1}
{1\over2\pi i}\int_{-3/2-i\infty}^{-3/2+i\infty}\Gamma(z)(n/2^j)^{-1-z}\,dz.
\eqno(44)
$$

񓌌�������� ����� ������ ��� ���� ���������, ��� ��� ���������� ����� 
���������� �������; �����
$$
\sum_{j\le 1}(n/2^j)^w=n^w\sum_{j\le1}(1/2^w)^j=n^w/(2^w-1),
\rem{���� $\Re(w)>0$,}
$$
��� ��� $\abs{2^w} = 2^{\Re(w)} > 1$. ����
$$
T_n={n\over2\pi i}
\int_{-3/2-i\infty}^{-3/2+i\infty}
 {\Gamma(z)n^{-1-z}\over 2^{-1-z}-1}\, dz,
\eqno(45)
$$
� �������� ������� ��������� ��������.

� ���� ��� �������������� ������������ �� �������, ������� ������ 
������� ������, ��� ���������� �� ���. 20(b).
%% 163
荒����� �� �������� ������� ���� 
$O\left(n^{1/2}e^{-\pi M/2} \int_{-3/2}^M N^t\,dt\right)$,
���� $2^{iN}\ne1$, � �������� �� ������� ������� ����� ������������   
���.   荒�����   ��   �������  �������   �����
$O\left( n^{-1-M} \int_{-\infty}^\infty \abs{\Gamma(M+it)}\,dt\right)$. 
􈊑���� $M$ � ��������� $N$, $N'$ �~$\infty$,
����� ��������, ��� $-T_n/n$ ���� $O(n^{-1-M})$ ���� ����� ������� � 
������� $-3/2 < \Re(z)<M$. �� $M\to\infty$, $\Gamma(z)$ ����� ������� 
������ ��� $z=-1$ �~$z=0$, $n^{-1-z}$ �� ����� �������, a~$1/(2^{-1-z}-1)$ 
����� ������� ������ ��� $z=-1+2\pi i k/\ln2$.

퀈������� ��������� ������������ ������� ����� � �����~$z=-1$. 呋� 
$w=z+1$ ����, �� ����� ��������������� ��������� ������������
$$
\Gamma(z+1)
=\exp(-\gamma z+\zeta(2)z^2/2-\zeta(3)z^3/3+\zeta(4)z^4/4-\ldots),
$$
���~$\zeta(s)=1^{-s}+2^{-s}+3^{-s}+\ldots=H_\infty^{(s)}$, ��� ������ 
��������� ����������:
$$
\eqalign{
\Gamma(z)&={\Gamma(w+1)\over w(w-1)}=-w^{-1}+(\gamma-1)+O(w);\cr
n^{-1-z}&=1-(\ln n)w+O(w^2);\cr
1/(2^{-1-z}-1)&=-w^{-1}/\ln2-{1\over2}+O(w).\cr
}
$$
⛗�� � �����~$z=-1$ ����� ������������ ��� $w^{-1}$ � ������������ ���� 
���� ������, � ������ ${1\over2}-(\ln n+\gamma-1)/\ln2$. ������ 
��������� ������, �������� �������
$$
T_n/n={\ln n+\gamma-1\over \ln 2}-{1\over2}+f(n)+{2\over n},
\eqno(46)
$$
���  $f(n)$---������� �������� ���������� ����:
$$
f(n)={2\over\ln 2}
\sum_{k\ge1} \Re(\Gamma(-1-2\pi ik/\ln2)\exp(2\pi i k\log_2n)).
\eqno(47)
$$
瀌����, ��� $f(n)=f(2n)$. 񐅄��� �������� $f(n)$ �����~0, ��� ��� 
������� �������� ������� ���������� ����� 0. (쎆�� �������, ��� 
�������� $(\log_2 n) \bmod 1$ ������������ ����������, �������� �� 
�������� ���������� � ������ � ��������� ������, ���������� � �.~4.2.4.) 
ꐎ�� ����, ��������� 
$\abs{\Gamma(-1+it)}=\abs{\pi/(t(1+t^2)\sinh \pi t)}^{1/2}$, �������� 
��������, ���
$$
f(n)< 0.0000001725;
$$
����� �������, � ������������ ����������� $f(n)$ ����� �������� 
���������. ��� �������� ������, �� ���~$f(n)$ �� �� �����
%%164
�������� ���������������� ���� ��� $U_n$; ������ ������� ��������~$U_n$ 
������������ ������ ��� �������. 
蒀�, �� ��������, ���
$$
U_n=n\log_2n+n\left({\gamma-1\over\ln2}-{1\over2}+f(n)\right)+O(1).
\eqno(48)
$$
䐓��� ������� ���������� ����� ������ �����-������� ����� ����� � 
���.~51--53 � � \S~6.3.

\excercises
\ex[�20] �� $a_1$ \dots $a_n$---������������ ��������� $\{1, \ldots, n\}$, 
� ����� $i$ � $j$ ������, ��� $i<j$ �~$a_i>a_j$. �� $a'_1$ \dots 
$a'_n$---������������, ������� ���������� �� $a_1$ \dots $a_n$, ���� 
�������� ������� $a_i$ � $a_j$. 쎆�� �� � $a'_1$ \dots $a'_n$ ���� ������ 
��������, ��� � $a_1$ \dots $a_n$?

\rex[�25] (a) ꀊ��� ����������� ����� �������, ����������� ��� ����,
 ����� ������������� ������������ 3\ 7\ 6\ 9\ 8\ 1\ 4\ 5? (b) ⎎��� ����� 
���� ������������ $\pi=a_1\ \ldots\ a_n$ ��������� $\{1, \ldots, n\}$, � 
����� 
$\mathop{\rm xch}\nolimits (\pi)$---����������� ����� �������, � ���������� 
������� ������������ $\pi$ ����� ������������� � ������������ �������. 
⛐����� $\mathop{\rm xch}\nolimits (\pi)$, ����� "����� �������" 
�������������� ������������~$\pi$. (�. � ���. 5 2.1--39.)

\ex[10] ߂������ �� ���������� ���������� ������� �������� (�������� B)?

\ex[�23] 呋� � ���� B4 ��������� $t=1$, �� �� ����� ���� ������ 
���������~B ����� ����� �� �����������, ������ ��� � ��������� ���� B2 
�� ���������� ������� �������� ��������. ꀊ��� ����������� ����, ��� 
��� ���������� ��������� ������������ � ���� B4 �������� $t=1$?

\ex[�25] �� $b_1$ $b_2$ \dots $b_n$---������� �������� ������������ $a_1$ 
$a_2$ \dots $a_n$. �����, ��� ����� $r$ ���������� ���������� ������� 
�������� �������� ���������� |BOUND| ����� $\max \{b_i+i \mid b_i\ge 
r\}-r$, ��� 
$0\le r\le \max(b_1, \ldots, b_n)$.

\ex[�22] �� $a_1$ \dots{} $a_n$---������������ ��������� $\{1, \dots, 
n\}$, � ����� $a'_1$ \dots{} $a'_n$---�������� � ��� ������������. �����, 
��� ����� ����������, ����������� ��� ����, ����� ������������� $a_1$ 
\dots{} $a_n$" ������� ��������. ����� $1+\max(a'_1-1, a'_2-2, \ldots, a'_n-n)$.

\ex[�28] ⛗������ ����������� ���������� ����� ���������� 
���������� ������� �������� � �������� ��� ����� $n$ � ������� $P(n)$. [�.
 � ��������� (6) � (7).]

\ex[�24] ⛂����� ������� (8).

\ex[�48] ������������ ����� ���������� � ����� ��������� � ��������� 
������-����������. (\emph{瀌������:} ��������� ���������� ���������� � 
���. 5.4.8--9.)

\ex[�26] �� $a_1$ $a_2$ \dots{} $a_n$---2-������������� ������������ 
���������  $\{1, 2, \ldots, n\}$. (a) ꀊ��� ���������� �������� ����� 
$a_i\hbox{-��}$ 
���� ���������������� ����������� ���� 
(��. � ���.~11)? (b) 䎊�����, ��� ���������/�����
��������� $a_1$: $a_2$, $a_3$, $a_4$, \dots ������������� ����������� ���� ������������
���������, ��� �� ���.~18(b). (�) 䎊�����, ��� ���������/����� ���������
$a_2$: $a_{2+d}$, $a_4$:$a_{4+d}$, \dots{} ������������� ����������� ���� 
������������ �����, 
������������� �� $m$ ������ ���� ���������, ��� �� ���. 18(�), (d) � (e), ����
$d=2m-l$.

\rex[�25] � ����� ������������ ��������� $\{1, 2, \ldots, 16\}$ 
����������� �������� ����� ������� � ��������� ᝒ����?

\ex[24] 퀏����� \MIX-��������� ��� ��������� M, �����������, 
��� \MIX---�������� �������������� ������ � ���������� |AND| � |SRB|. 
񊎋��� ������� ����������� ����� ���������, ����� ������������� 
����������� ������� �� ����.~1?
%%165

\ex [10] 󑒎����� �� ���������� ᝒ����?

\ex [�21] �� $c(N)$---����� ��������� ������, ������������ ��� 
���������� $N$ ��������� ������� ᝒ����; ��� ����� ����� ���������� 
���� M4.
(a) �����, ��� ��� $t\ge 1$ $c(2^t)=2c(2^{t-1}+(t-1)2^{t-1}+1.$
(b) 퀉���� ������� ��������� ��� $c(2^t)$ ��� ������� ��~$t$. 
(\emph{󊀇����:} ����������� ������������������ $x_t=c(2^t)/2^t)$.

\ex[�38] 񎄅������ ����� ����������---������ ������� $c(N)$ �� ���.~14
� ���������� ������� ��� $c(N)$, ���� $N=2^{e_1}+2^{e_2}+\cdots+2^{e_r}$, 
$e_1>e_2>\ldots>e_r\ge0$. (a) �� $a(N)=c(N+1)-c(N)$. 䎊�����, ��� 
$a(2n)=a(n)+\floor{\log_2(2n)}$, $a(2n+1)=a(n)+1$;  ������
$$
a(N)=\perm{e_1+1}{2}-r(e_1-1)+(e_1+e_2+\cdots+e_r).
$$
(b) �� $x(n)=a(n)-a(\floor{n/2})$,  � �����  
$a(n)=x(n)+x(\floor{n/2})+x(\floor{n/4})+\cdots$. �� 
$y(n)=x(1)+x(2)+\cdots+x(n)$, � 
�����~$z(2n)=y(2n)-a(n)$, $z(2n+1)=y(2n+1)$.  䎊�����, ��� 
$c(N+1)=z(N)+2z(\floor{N/2})+4z(\floor{N/4})+\cdots$. (c) 䎊�����,��� 
$y(N)=N+(\floor{N/2}+1)\times(e_1-1)-2^{e_1}+2$. (d) 򅏅�� �������� ��� 
������ � ������� ��������� $c(N)$ ����� ���������� $e_j$ ��� ������������� 
�������� $r$.

\ex[��46] 퀉���� ��������������� �������� �������� ����� ������� � ������,
 ����� �������� ᝒ���� ����������� � $N=2^t$ ��������� ���������, 
������������� � ��������� �������.

\rex[20] ㄅ � ��������� Q ������������ ��, ��� $K_0$ �~$K_{N+1}$ 
�������� ����������, ���������������� ������������� (13)?

\rex[20] ������, ��� �������� �������� Q � ������, ����� ��� ����� � 
�������� ����� �����. ��� ����������, ���� � ����� Q3 � Q5 �������� ����� 
"$<$" �� "$\le$"?

\ex[15] ᓄ�� �� �������� Q ��-�������� �������� ���������, ���� ������ 
����� (��������� ����������---������ �����������) ��������������� �������� 
(������ ����������---������ �����������)?

\ex[�20] ⛐����� ���������� ����� ���������, ������� ����� ������������ 
��������� � ����� �� ����� ������ ��������� Q, � ���� ������� ��~M �~$N$.

\ex[20] ������, ������ ���� ���������� � ��������� Q ������� ��� ��� 
������ ����� ���������, ��������� � �. �., ��� ��� ������� � (17).

\ex[�25] �� $p_kN$---����������� ����, ��� ��������~$A$ � (14) 
����� �����~$k$, ���� �������� Q ����������� � ��������� ������������ ���������
$\{1, 2, \ldots, N\}$, � �����~$A_N(z)=\sum_k p_kN^{z^k}$---��������������� 
������������ �������.   䎊�����,   ���~$A_N(z)=1$   ���~$N\le M$,   
�~$A_N(z)= z(\sum_{1\le s\le N} A_{s-1}(z)A_{N-s}(z))/N$ ���~$N>M$. 
퀉���� ����������� ������������ �����������, ������������ ������ 
������������� ������������ $B_N(z)$, $C_N(z)$, $D_N(z)$, $E_N(z)$, 
$L_N(z)$, $X_N(z)$.

\ex[�24] �� $A_N$, $B_N$, $D_N$, $E_N$, $L_N$, $X_N$---������� �������� 
��������������� ������� � (14) ��� ���������� ��������� 
������������-��������� $\{1, 2, \ldots, N\}$. 퀉���� ��� ���� ������� 
������������ �����������, ����������� (18), ����� ��������� ��� 
����������� � �������� ������� (25).

\ex[�21] �����, � ��������� Q ������������ ��������� ������ ���������, 
��� ��� ����������, ������ ��� � ����� Q3 � Q5 ����� ���������, ��� $i=j$ 
��� ���� $i>j$. 񊎋��� ��������� $G_N$ ������������� �� � �������, ���� 
�� ����������� ��� ��������� ��� $i\ge j$?

\ex[�20] ���� ����� ������ �������� ������� $A$, $B$, $C$, $D$, $E$, $L$, 
$X$ ��� ��������� Q � ������, ����� �������� ����� ������������ ����� 
������������� ����� ����� $1$, $2$, \dots, $N$ � �������������, ��� $N>M$? 

\rex[M21] ������ �������� ����, ��� ������� ��������� Q �������� �� 
��� ���������, ��� � ���.~25. (�������� ����� ������������� ������ ������.)

%% 166
\ex[�23] ꀊ�� �������� ���� ����� \emph{���������} ��� 
���������~Q? 퀉���� ��������������� �������� �������~$A$, $B$, $C$, $D$, 
$E$, $X$ ��� ����� ������.

\ex[M26] 퀉���� ������������ �����������, �����������~(20), 
�������� ������������� ������� ����� ��������� � ���������~Q, 
���������������� 񈍃������ (�.~�.\ ����� � ��������~$s$ ���������� 
��~$s=K_1$, � ������� ��~$\set{K_1, K_{\floor{(N+1)/2}}, K_N}$).

\ex[��40] 퀉���� ��������������� �������� ����� ��������� � ��������� 
񈍃����� "������� �� ����" (��.~���.~28).

\ex[25] (�.~��������.)  ���������� \emph{������ ������ � ��������� 
����} ������ ��������� ��� ����� ����������� �� ���� ����, ��� ���� 
������������ � �������������� ���������, ��������� ��� ����������� 
����������� ������������������� ������� ������ ��� ����� ������ ������ 
��������� �������� ��������� ��� ���� (��.~���.~5-5). 􀉋�, ������� 
����������� �� ��������, ����� �������� ����� ������ �����, � ��� 
������� ����� ������� ���������� �� ������� ����������.

򀊎� ����������� ����������� ��� ���������~Q, �� �� ��� ���������~R,
��������� ��� ������ ��� ����������� ������ ���� ��� (���� 
����������� ������ � ����� ������ ������ ����� ������ ��������� ����� 
������ ���������~R �� ������ ��������).

������, ��� ����� ����������������� ��������~Q, ����� �������� ����� 
�����������; � ��������, � ������� ��������, ��� ������� $k$~���� �� ���� 
������ �������� ���������� ��������, ������� ��������� ���� 
$(k+1)\hbox{-�}$~����� ������.

\rex[20] (�.~�.~�.~����) ��������, ��� ��� ����� �� ������������� ����, � 
���� ���������� $m\hbox{-�}$ ���������� �� �������� ������� �� 
��������� ��������� $n$~���������. �����, ��� "������� ����������" 
����� ������������ ��� ���� ����, ������� ������������ ����� ����������, 
����������� ��� ������ ����������.

\ex[�40] 퀉���� ������� ��������� "� ��������� ����" 
���~$C_{nm}$---�������� ����� ��������� ������, ����������� ��� ��������� 
$m\hbox{-��}$~����������� �� $n$~��������� �� ������ ���.~31. (䋟 
�������� ����� ���������� ��� ��������� �~$i\ge j$, ��� � ���.~24.) ꀊ��� 
��������������� ��������� ��������~$C_{(2m-1)m}$---�������� ����� ���������, 
����������� ��� ���������� ������� �� $2m-1$~��������� ������� �����?

\rex[20] ������������ �������� �������������� ����� � ��������� �������� 
������� ����� �������, ����� ��� ������������� �������� �������������� 
�������������. �������� �� ����� ��������� �����������:
���������� ������ �������� ������������� ����� �� �������������. 
‘ �������� ������ ����������� ���������� ��������� ����� �������.

\ex[20] ꀊ ����� �������� ����� �������� ����� � �������� ����������� 
���������� (���� ��~R3 ��~R6)?

\ex[�23] ������������ �������������� ��������������~$A$, $B$, $C$, $G$,
$K$, $L$, $R$, $S$ �~$X$, ������� ���������� ��� �������� ����������� 
���������� ��� "�������� ������ ����~(i)".

\ex[�27] 䋟 ����� ������ ������������������ �����~$\< a_n >=a_0$, $a_1$,
$a_2$,~\dots{} ��������� �� \dfn{������������-��������������} 
$\<\hat a>_n=\hat a_0$, $\hat a_1$, $\hat a_2$,~\dots{} ��������
$$
\hat a_n = \sum_k \perm{n}{k} (-1)^k a_k.
$$
(a)~䎊�����, ���~$\<\hat {\hat a}_n>=\< a_n>$. (b)~퀉���� ������������ 
�������������� �������������������~$\<1>$; $\<n>$; $\<\perm{n}{m}>$ ��� 
�������������~$m$; $\<a^n>$ ��� �������������~$a$; $\<\perm{n}{m}a^n>$ ��� 
�������������~$a$ �~$m$. (c)~ �������, ���
%% 167
������������������~$\<x_n>$ ������������� �����������
$$
x_n=a_n+2^{1-n}\sum_{k\ge 2} \perm{n}{k}x_k 
\rem{���~$n\ge 2$, $x_0=x_1=a_0=a_1=0$,}
$$
��������, ���
$$
x_n=\sum_{k\ge 2}\perm{n}{k}(-1)^k{2^{k-1}\hat a_k \over 2^{k-1}-1}=
a_n+\sum_{k\ge 2}\perm{n}{k}(-1)^k{\hat a_k \over 2^{k-1}-1}.
$$

\ex[M28] ������� ��� ����� ������������������~$\< a_n>$, 
���~$\<\hat a_n>=\<a_n>$ � ������ ���.~36.

\rex[M30] 퀉����~$A_N$, $B_N$, $C_N$, $G_N$, $K_N$, $L_N$, $R_N$, 
�~$X_N$---������� �������� �������~(29)---� ������, ����� ����������� 
���������� ������������ "�������� ������ ����~(ii)". ⛐����� ���� ������ 
�����~$N$ � �������
$$
U_n=\sum_{k\ge 2}\perm{n}{k}{(-1)^k \over 2^{k-1}-1},\qquad
V_n=\sum_{k\ge 2}\perm{n}{k}{(-1)^k k \over 2^{k-1}-1}=n(U_n-U_{n-1}).
$$
[\emph{󊀇����:} ��.~���.~36.]

\ex[20] ����������~(30) ����������, ��� ����������� �������� ����������, 
����������� � ��������� ������� ������, ������� ����� $1.44$~������. 
䎊�����, ��� ������� ���������� ������� �� ������� ����� $N$~������, � 
���������, ������ ��� �������� ����������� ���������� ����� 
������ ���������� ����� $N$~������.

\ex[21] ������, ��� ����� �������� ��������~R, ����� �� 
������� ���������� ���������� � �����, ����� ����������� ����� �������� 
����� ������ ������.

\ex[23] 䀉�� ������ �������� ��������� "������������ �������� 
����������" ‍ ������.

\ex[�43] ������������ �������� ������������ �������� ���������� �� ���.~41.

\ex[��21] 䎊�����, 
���~$\int_0^1 y^{-1}(e^{-y}-1)\,dy +\int_1^\infty y^{-1}e^{-y}\,dy=-\gamma$. 
[\emph{󊀇����:} �����������~$\lim_{a\to 0+} y^{a-1}$.]

\ex[��24] ⛂����� �������~(37), ��� ��� ���������� � ������ ���������� ������.

\ex[��20] ������, ������ ���~$x>0$ ����������� ���������~(43).

\ex[��20] ꀊ��� �������� 
���������~$(1/2\pi i) \int_{a-i\infty}^{a+i\infty}\Gamma(z) n^{s-z}\,dz/(2^{s-z}-1)$
��� �������, ���~$s$---����� ������������� ����� �~$0<a<s$?

\ex[��21] 䎊�����, ���~$\sum_{j\ge1} (n/2^j) e^{-n/2^j}$---������������ 
������� ��~$n$.

\ex[��24] 퀉���� ��������������� �������� ��������~$V_n$, ������������ 
� ���.~38, ��� ������ �������, ����������� ���, �������� � 
������ ���������� ������ ������������� ��������~$U_n$, � �������� ����� ��~$O(1)$.

\ex[��24] ������� ��������������� �������~(47) ���~$U_n$ �� ������ �������~$O(n^{-1})$.

\ex[��24] 퀉���� ��������������� �������� �������
$$
U_{mn}=\sum_{k\ge 2}\perm{n}{k}(-1)^k{1\over m^{k-1}-1},
$$
���~$m$---������������ ������������� �����, �������~1. (��� �������� 
���~$m$~����� �������~$2$ ����������� ��� ������������ ��������� ��������
�����������
%%168
����������, � ����� ��� �������� ���������� ������ � 
"������� ������" � \S~6.3.)

\rex[��28] �����, ��� ��� ������ ���������������� ����������~$r_k(m)$ 
����� ��������������� ������� ������������ ��������������� ����� ��� 
������ �����-������� ������ ������� ������������ ������ (��.~�~(35)). ��� 
���� ��� ������������� ������ ��������~$r_k(m)$ ��� ����~$k$, �� 
��������� �� ����� "�����", ��� �������� �������~$g_{-1}(x)=(e^{-x^2}-1)/x$.

\ex[��35] (�.~�.~��~ᐅ��.) ꀊ��� ��������������� ��������� �����
$$
S_n=\sum_{t\ge 1} \left({2n \over n+t}\right) d(t),
$$
���~$d(t)$---���������� ��������� �����~$t$? (�, $d(1)=1$, $d(2)=d(3)=2$,
 $d(4)=3$, $d(5)=2$ �~�.~�. ���� ������ ��������� � ����� � �������� 
��������� ����������� ������; ���.~2.3.1-11.) 퀉���� �������� 
��������~$S_n/\perm{2n}{n}$ �� ������ �������~$O(n^{-1})$.

\ex[��42] ������������ ����� �������� ����� � ����� �������,
����������� ��� �������� ����������� ����������, ���� ��������� 
������� ������ �������� ����� � ����������� ��������� �� ����������~$[0,1)$,
������ ��� ������� ���������� ��������� ��������~$1$ � 
������������~$p$. (� �������� ������ ������ ���������� ���� 
������~$p={1\over 2}$; ������������� ������ ����� �������� �� ������ 
�������������~$p$.) ����������� ����� ������~$p=1/\phi=.61803\ldots\,$.

\ex[��24] (�.~�.~����.) �����, ���~$U_n$ ����� �������� � ����
$$
U_n=(-1)^n {n!\over 2\pi i} \oint_C {dz \over z(z-1)\ldots(z-n)}{1\over 
2^{z-1}-1},
$$
���~$C$---��������� ������, ������������ ������� ����� �����~$2$, $3$,~\dots,
$n$. � ���������� ������~$C$ �� ����������� ������� ���������� � 
������� � ������ ��������� �������� ���������� ���
$$
U_n=n(H_{n-1}-1)/(\ln 2)-{1\over 2}n +2+{2\over \ln 2}\sum_{m\ge 1}\Re(B(n+1, -1+ibm)),
$$
���~$b=2\pi/(\ln 2)$ 
�~$B(n+1, -1+ibm)=\Gamma(n+1)\Gamma(-1+ibm)/\Gamma(n+ibm)=n!/\prod_{0\le k \le n}(k-1+ibm)$.

\rex[22] �����, ��� ����� �������� ���������~Q, ����� � ��������
������������ �������� ���������� ������� �� ���� ������~(28).

\ex[�44] ������������ � ������� ��������� �������, �� ������� ������� 
����� ������ ���������~Q, ���� ��������� �������� ���, ��� ��� �������� 
������� �� ���� ���������, ��� � ���.~55. [(�.~���.~29.)]

\rex[��24] 퀉���� ��������������� �������� ����� 
�������������� ����������, ������������� ��� ���������� ��������� � 
��������� ������� (�������~(5.2.1-11)), ����~$M=N/\alpha$ ��� 
�������������~$\alpha$ �~$N\to\infty$. 
⛏������ ���������� �� ������ �������~$O(N^{-1})$ � �������� ��� ����� 
����� ������������ ������������� �������~$E_1(z)=\int_z^\infty e^{-t}\,dt/t$.

%% 169

\bye


