\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[M2I] ������ �������� ����, ��� ������� ��������� Q .�������� �� 
��� ���������, ��� � ���.~25. (�������� ����� ������������� ������ ������.)

%% 166
\bye


