\input style
%% 109
\picture{���. 11. 񎎒�������� ����� 2-������������� � ������ �� �������. 
ꓐ����� ������� ����, ��������������� ����� �������� � 2-������������� 
������������.}

�� $A_n$---��������� ����� �������� �� ���� 2-������������� 
������������� ��������� $\{1, 2, \ldots, n\}$. ߑ��, ��� $A_1=0$, $A_2=1$, 
$A_3=2$, � �� ������������ ����� �������
$$
1\ 3\ 2\ 4\quad   1\ 2\ 3\ 4 \quad 1\ 2\ 4\ 3\quad   2\ 1\ 3\ 4\quad   2\ 
1\ 4\ 3   \quad 3\ 1\ 4\ 2
$$
�������, ��� $A_4=1+0+1+1+2+3=8$. ����� ����������� $A_n$ � ����� ������, 
���������� ���������� ��������� �� ���.~11 ��� $n=15$. � ����� ��������� 
2-������������� ������������ ����� ����������� � ���� ���� �� ������� 
����� ������� ����� $(0, 0)$ � ������ ������ ������� ����� $(\ceil{n/2}, 
\floor{n/2})$, ���� ������ $k$-� ��� ���� ������ ��� ���� � ������������ � 
���, ��������� �� $k$ � ������ ��� �������� ������� ������������. ���� 
�������� ������������ ������� ����������� ������������ ����� 
2-�������������� �������������� � $n$-�������� ������ �� ������ ���� 
���������� ��������� � ������. 퀏�����, ������������ �� ������� ���� 
������������� ������������
$$
2\ 1\ 3\ 4\ 6\ 5\ 7\ 10\ 8\ 11\ 9\ 12\ 14\ 13\ 15.
\eqno(1)
$$
䀋��, ������������ �������� ���� ����� ��������� "����", ��� �������� �� 
���������; �������, �������� �� ����� $(i, j)$
%% 110
� ����� $(i+1, j)$ ������������� ��� $\abs{i-j}$. 테���� �������,
�������� �������� � ���, ��� ����� ���� ����� ����� ������� ���� ����� 
����� �������� � ��������������� ������������ (��. ���.~12). �, ��������,
������������ (1) �������� 
$1+0+1+0+1+2+1=6$ ��������.

呋� $a\le a'$ �~$b\le b'$, �� ����� ���������� ����� �� $(a, b)$ � 
$(a', b')$ ����� ����� �������� ���������� $a'-a$ ������������ �������� 
� $b'-b$ ���������������, � ������
$$
\perm{a'-a+b'-b}{a'-a}.
$$
񋅄���������, ����� ������������, ��� ������� ��������������� ���� 
�������� ����� ������������ ������� �� $(i, j)$ �~$(i+1, j)$, �����
$$
\perm{i+j}{i}\perm{n-i-j-1}{\floor{n/2}-j}.
$$
󌍎��� ��� �������� �� ��� ������� ������� � �������� �� ���� ��������, ��������
$$
\eqalign{
A_{2n}&=\sum_{0\le i\le n \atop 0\le j\le n}
\abs{i-j}\perm{i+j}{i}\perm{2n-i-j-1}{n-j};\cr
A_{2n+1}&=\sum_{0\le i\le n \atop 0\le j\le n}
\abs{i-j}\perm{i+j}{i}\perm{2n-i-j}{n-j};\cr
}
\eqno(2)
$$
獀�� ���������� �������� � ���� ������ ��������� ��������� ����������, �� 
� ���.~14 ��������, ��� �������� $A_n$ ����� ����������� ������� ���: 
$\floor{n/2}2^{n-2}$. 񋅄���������, ������� ����� �������� � ��������� 
2-������������� ������������ �����
$$
\floor{n/2}2^{n-2}/\perm{n}{\floor{n/2}}.
$$
� ������� 񒈐����� ��� �������� �������������� ������������ � 
$\sqrt{\pi/128}n^{3/2}\approx 0.15 n^{3/2}$. ꀊ ����� ������, 
������������ ����� �������� �����
$$
\perm{\floor{n/2}+1}{2}\approx{1\over8}n^2.
$$
���� ����������� ������������� ����� �������� ����� ���������, 
���������� ������������ �������
$$
\matrix{
 h_1(z)=1, \quad h_2(z)=1+z,\cr
 h_3(z)=1+2z, \quad h_4(z)=1+3z+z^2+z^3, \ldots,\cr
}
\eqno(3)
$$
%% 111
��� � ���. 15. 򀊈� �������, ������, ��� ����������� ���������� ���� 
��������������� $n^{3/2}$, ��� ��� ����� �������� �� ������� ��������� 
������������ ����� ������ �������� ��������. ���������� ������ ����� 
������������� ������ ��������� D, ����� ���� ���������� ����� $h$ �~1.

\proclaim 򅎐��� H. 񐅄��� ����� �������� � $h$-������������� 
������������ ��������� $\{1, 2, \ldots, n\}$ �����
$$
f(n, h)={2^{2q-1}q!q! \over (2q+1)!}\left(\left({h\over2}\right)q(q+1)+
\left({r\over2}\right)(q+1)-{1\over2}\perm{h-r}{2}q\right),
\eqno(4)
$$
��� $q =\floor{n/h}$, $r= n \bmod h$.
��� ������� ����������� 䓃���� ����� [Bachelor's thesis, Princeton 
University (April, 1967)]. 瀌����, ��� ������� ����������� � ��� 
$h\ge n: f (n, h) ={1\over2}\left({n\over2}\right)$.
\proof � $h$-������������� ������������ ���������� 
$r$ ������������� ���������������������� ����� $q+1$ � $h-r$ 
���������������������� ����� $q$. ꀆ��� �������� ���������� 
�� ��������� ���� ��������� ����������������������, � ������ ���� 
��������� ������������� ���������������������� � ��������� 
$h$-������������� ������������ ���������� ��������� 2-������������� 
������������. ���� ������� ����� �������� ����� ����� ������� �������� 
����� �������� �� ���� ����� ��������� ����������������������, � ������
$$
\perm{r}{2}{A_{2q+2}\over\perm{2q+2}{q+1}}
+r(h-r){A_{2q+1}\over\perm{2q+1}{q}}
+\perm{h-r}{2}{A_{2q}\over\perm{2q}{q}}=f(n,h).\;\endmark
$$
\eproofend

\proclaim 񋅄�����. 呋� ������������������ ���������� ������������� �������
$$
h_{s+1}\bmod h_s=0\rem{ ��� $t>s\ge 1$,}
\eqno(5)
$$
�� ������� ����� �������� ����������� � ��������� D �����
$$
\sum_{t\ge s\ge 1}
 (r_sf(q_s+1, h_{s+1}/h_s)+(h_s-r_s)f(q_s, h_{s+1}/h_s)),
\eqno(6)
$$
��� $r_s=N\bmod h_s$, $q_s=\floor{N/h_s}$, $h_{t+1}=Nh_t$, � ������� $f$ 
������������ �������� (4).

\proof ���� $h_s$-���������� ������� �� ���������� �������� ��������� 
$r_s(h_{s+1}/h_s)$-������������� ��������� ����� $q_s+1$ 
�~$(h_s-r_s)$ ����� ��������� ����� $q_s$. ������ �� ������������, ��� 
�������� ������������ �������� � ��� �� �������� ��������, �� �� ������� 
��������� �������, ��� ������ �� ���������---"���������" 
$(h_{s+1}/h_s)$-�������������
%%112
������������ � ��� ������, ��� ��� 
$(h_{s+1}/h_s)$-������������� ������������ �������������.
\proofend

󑋎��� (5) ����� ��������� ������ ����������� ��� \emph{�������������} 
���������� ������� �����, ����� ���� ����� �������������� $h$ �~1. 
�� $q=\floor{N/h}$, a~$r=N\bmod h$, ����� ������� �������� �������� $B$ 
� ��������� D �����
$$
rf(q+1, N)+(h-r)f(q, N)+f(N,h)
={r\over2}\perm{q+1}{2}+{h-r\over2}\perm{q}{2}+f(N,h).
$$
� ������ ����������� ������� $f(n, h)$ ����� $(\sqrt{\pi}/8)n^{3/2}h^{1/2}$;
��. � ������� ������ �� ���.~12. 񋅄���������, ����� ������
\picture{���. 12. 񐅄��� ����� �������� $f(n, h)$ � $h$-������������� 
����� �� $n$ ��������� ��� ������ $n=64$.}
������������� ��������� D �������� ��������������� 
$2N^2/h+\sqrt{\pi N^3h}$. ���� ��������� �������� $h$ ����� 
�������������� $\root 3\of{16N/\pi}\approx1.72\root3\of{N}$; ��� ����� 
������ $h$ ������� ����� ������ ��������������� $N^{5/3}$.

򀊈� �������, ���� �������� ����� ����� � ����� ����� ������, ����� 
����������� ��������� ����� �� ��������� � �������� ���������, � $O(N^2)$ 
��~$O(N^{1.667})$. ߑ��, ��� ����� �������� ������ �����������, ���� 
������������ ������ �����. � ���.~18 ����������� ����������� ����� 
$h_t$,~\dots, $h_1$ ��� �������������~$t$
%%113
� ������, ����� �������� $h$ ���������� 
�������� ���������; ����� ������ ��� ������� $N$ ����������� 
�� $O(N^{1.5+\varepsilon/2}$ ��� $\varepsilon=1/(2^t-1)$. 呋� �� 
���������� ������������ ���� ���������, ������ $N^{1.5}$ ���������� 
����������, ������ ��� ��� ��������� ��������� � ����� �������� ������ �������� �����
$$
f(N, h_2)\approx(\sqrt{\pi}/8)N^{3/2}h_2^{1/2}.
$$

� �������� ������������, ���, ���� ���� $h_t$, \dots, $h_1$ 
\emph{�� �����} ������������� ������� ��������� (5), ����� 
������� ��������. 퀏�����, ��� ���������������� ���������� 8-, 4- � 
2-���������� ���������� �������������� ����� ������� � ������ � �������� 
��������; ������� �� ���� �������������� 1-���������� ��������� 
$O(N^{3/2})$ ��������. � �� �� ����� ��� ���������������� ���������� 7-, 
5- � 3-���������� ���� ��������������� ���, ��� ��� �������������� 
1-���������� �� ����� ����������� ����� $2N$ ��������! (�. ���.~26.) � 
����� ���� ����������� ������������ �������.

\proclaim 򅎐��� �. �� $h$-���������� $k$-������������� ���� �������� $k$-�������������.

򀊈� �������, ����, ������� ��� ������� 7-������������, � ����� 
5-������������, ���������� ������������. 7- � 5-�������������. � ���� �� 
���������� ��� 3-����������, �� ���������� ���� ����� 7-, 5- � 
3-����������. ���� ���������� ����� �������������� �������� ����� ����� 
� ����. 4.
\picture{򀁋��� 4  񎐒������ � ��������� ����� (7, 5, 3, 1)}
\proof � ���.~20 ��������, ��� ��� ������� �������� �� ��������� �����:

%%114

\proclaim 녌�� L. �� $m$, $n$, $r$---��������������� ����� �����, 
� $x_1$, \dots, $x_{m+r}$ �~$y_1$, \dots, $y_{n+r}$---������������ 
������������������ �����, �����, ���
$$
y_1\le x_{m+1}, y_2\le x_{m+2}, \ldots, y_r\le x_{m+r}.
\eqno(7)
$$
呋� ������������������ $x$ �~$y$ ������������� ����������, ��� ��� 
$x_1\le\ldots\le x_{m+r}$ �~$y_1\le\ldots\le y_{n+r}$, �� ����������� (7) 
��������� � ����.

\proof 臂�����, ��� ���, �����, ���� �����, $m$ ��������� 
������������������ $x$, ����������� (�. �. ������ ��� �����) ��������� 
�������� ������������������ $y$, ������ ��������� �������� $x$ 
����������� ��������� �������� $y$. �� $1\le j\le r$. � ��� ����� 
���������� ������� $x_{m+j}$ ����������� $m+j$ ��������� $x$, �� �� 
����������� �� ������� ���� $j$ ��������� $y$, � ������, �� ����������� 
$j$ \emph{����������} ��������� $y$. 񋅄���������, ����� ���������� ����� 
$x_{m+j}\ge y_j$.
\endmark\hskip 1em
%\proofend
\proofend

� ������� � �����, ��� ��� ���������� ���������� ������������ ������� 
�������� ���������� �����, ������ ��������������� �� ��� �� ������� 
������ ������ ����� �����������, ����������� ���������� D. � ��� ����� 
������������ ��������� $\{1, 2, \dots, n\}$, ������������ $h$- � 
$k$-�������������, �� ������ �������� ��������� $n!$, �� �������, ��� 
������� � ��������� ������ �� ���; � ���������� $k$- � $h$-���������� 
��������� $k$- � $h$-������������� ����� ���������� ���� ������. 
ᎋ�� ����, �� ���������� ���������� ������� �������� "��������� ������" 
��� ��������� D ��� ������������ ������������������ ����� ���������� $h_t$,
 \dots, $h_1$. ���� �� ��� ��� ��� ������� ������� ����� ��������� � 
����� ������ ���� ������; �� ��������, ���, ��� ��� ��������,---��� 
������������ ��������������� ��������� ������������� ������� ������ � ��������� �������.

\proclaim 򅎐��� P. 呋� $h_s= 2^s-1$ ��� 
$1\le s\le t=\floor{\log_2 N}$, �� ����� ������ ��������� D ���� $O(N^{3/2})$

\proof 䎑������� ����� ������ $B_s$ ����� ����������� ��� $s$-� ���������,
 �����, ����� $B_t+\cdots+B_1=O(N^{3/2})$. 䋟 ������ $t/2$ ���������� ��� 
$t\le s\ge t/2$ ����� ��������������� ��������� ������� 
$B_s=O(h_s(N/h_s)^2)$, a ��� ����������� ���������� ����� ��������� 
��������� ���.~23: $B_s=O(Nh_{s+2}h_{s+1}/h_s)$. 񋅄���������, 
$B_t+\cdots+B_1=O(N (2 + 2^2 +\cdots+2^{t/2}++2^{t/2}+\cdots+2))=O(N^{3/2})$.
\proofend

��� ������� ����������� �.~�.~������ � �.~�.~񒀑����� [{\sl ����� 
�������� ����������\/}, 1,3 (1965), 81--98].  ���� ������� ������ 
\emph{�������������} ������� ������ ���������, � ��
%%115
\ctable{
\hfill\bskip$#$\bskip\hfill&&\hfill\bskip$#$\bskip\hfill\cr
\noalign{\rightline{\it 򀁋��� 5}}
\noalign{\centerline{\bf ������ ��������� D ��� $N=8$}}
\multispan{3}\hbox{����} & A_{ave} & B_{ave} & S & T & \hbox{����� ������ \MIX}\cr
  &   &1 & 1.718 &14.000 & 1 & 1 & 204.85u\cr
  & 2 & 1& 2.667 & 9.657 & 3 & 2 & 235.91u\cr
  & 3 & 1& 2.917 & 9.100 & 4 & 2 & 220.16u\cr
  & 4 & 1& 3.083 &10.000 & 5 & 2 & 217.75u\cr
  & 5 & 1& 2.601 &10.000 & 6 & 2 & 210.00u\cr
  & 6 & 1& 2.135 &10.667 & 7 & 3 & 206.60u\cr
  & 7 & 1& 1.718 &12.000 & 8 & 2 & 208.85u\cr
4 & 2 & 1& 3.500 & 8.324 & 7 & 3 & 272.32u\cr
5 & 3 & 1& 3.301 & 8.167 & 9 & 3 & 251.60u\cr
3 & 2 & 1& 3.320 & 7.829 & 6 & 3 & 278.50u\cr
}
������ ������ \emph{��������} ������� ������. ���� ��������� �����������,
 ��������� ������������ ����� ������ � ������, ����� ���������� $h$ 
������������� ������� ��������� (5), ����� ������� $N^2$, � � ���.~24 
��������, ��� ���������� $3/2$ ��������� ������.

荒������� ��������� �� ��������� � �������� P ��������� � 1969~�. ⎃�� 
��. \dfn{呋� ��� ���� ���������� ���������� �� ��������� ����� ���� 
$2^p3^q$, ������� $N$, �� ����� ������ ��������� D ����� ������� 
$N (\log N)^2$}. � ���� ������ ����� ����� ������ � �������� ��������� ������������ 
���������. � ���������, ����� ��� ������� ������������ �������� ����� 
����������, ��� ��� ��� �� ������ ������ ������ �����, ���� ������ $N$ �� 
����� ������; ��. ���.~30 �~31.

���������� \emph{�����} ����� ������ ��������� D, 
������ $(9B+10NT+13T-10S-3A+1)u$. � ����.~5 �������� ������� ����� ������ 
��� ��������� ������������������� ����� ��� $N=8$. ꀆ��� ������� ������� 
����� ��������� � ������� ������, ����������� ���� ��� � ���.~19, �� 
����������� �������, ����� ���� ����� $5$ $3$ $1$ � $3$ $2$ $1$; ��� ���� 
���� ������� ���� ��������� ���������� ������������ ���� $8!$ 
������������. 瀌����, ��� ��� ����� ����� �������� $N$ � ����� ������� 
������ ����������� ��������������� ��������, ������� ��������� ���������� 
���������� ��� $t=1$; �������������, ��� $N=8$ ����� ����� ������������ 
�������� ���������. (񐅄��� ����� ������ ��������� S ��� $N=8$ ����� 
����� $191.85u$.) 랁������, ��� ��������� ��������� � ������������� 
��������� ����������� ��� $h_2=6$, ��������� ������� �������� 
5 ����������� ������ ����� ��������~$B$. ���������� ��� ���� $3$ $2$ $1$ 
������������ ������� ����� �����������, �� ��� �� �����
%% 116
������ ������������������ ��� ���� ����������. ᛒ� �����, ��������� 
�������� ��������� "���������" ������������, ��������������� ����� 
�����������, ��� ��� ����� ������ ���������� ����� ������������ �� ��� ��� 
�� ��������:
$$
\matrix{
h_3=5, & h_2=3, & h_1=1: & 8 & 5 & 2 & 6 & 3 & 7 & 4 & 1 & \hbox{(19 �����������)}\cr
h_3=3, & h_2=2, & h_1=1: & 8 & 3 & 5 & 7 & 2 & 4 & 6 & 1 & \hbox{(17 �����������)}\cr
}
$$

� ������ $N$ ����������� ��������� ���� �������. � ����.~6 �������� 
������������ �������� ����� ����������� ��� ��������� 
������������������� ����� ��� $N=1000$. ��� 
��������� ������������������� ������������� ������� ��������� (5), ��� ��� 
����� ��������������� �������� (6); ��� ��������� ������� �������� ��� 
������ ������������������� ����� ����������� ������������ �����. ᛋ� 
������������� ���� ������ �� 1000 ��������� ���������, � ������ ���� 
������������ � ������ ������������������� �����.

��� ������ ��������� ������� ��������� ��������������, �� ��������� 
��������� D ��� ��� �������� �������. ���� ������������� ����������� 
������������ ���� $\floor{N/2}$, $\floor{N/4}$, $\floor{N/8}$, \dots �� 
��� ������������, ���� �������� ������������� ����� $N$ �������� ������� 
������� �����. 뀇���� � ����� [{\sl CACM\/}, {\bf 3} (1960), 20--22] 
���������� ������������, �� ��������, �� �� ������������������, �� 
�������� $1$ ���, ��� ��� ����������, ����� ������� ��� ���� ���������. 
������� 
[{\sl CACM\/}, {\bf 6} (1963), 206--213] ��������� ���� ���� $2^k-1$; 
����� � 񒀑���� ���������� ������������������ $2^k+1$. 񐅄� ������ 
������������ �������������������, �������������� ���. ��������� 
����.~6,---������������������ $(2^k-(-1)^k)/3$, $(3^k-1)/2$ � ����� 􈁎�����.

숍�������� ����� ����������� 6600 ����������� ��� ����� ���� $2^k+1$, 
�� ����� ��������, ��� ���� ��������� �� ������ ����� �����������, ���� 
������ ��� �������������� ���������� � ����� ������� ������. � ��� ����� 
������ ��������� D ����� $9B+10NT+\cdots$ ������, ����, ��� �������� 
������ ��������� �������� ������������ ���������� �����
����������� �� ${10\over9} N$; �� ������ �������� 1100 �����������,
���� �� ���� ����� ������� ���������� ���� ��������. 
���� �������������� ���������� �������� � $h_t$, ��������, ���, 
������, $N/3$, ��������� ������� ��� �� ������ ����� ����������� 
����������� ���������, ����� ��������� ������ ��������.

ᎋ���� ����� ������������� � ���������� D ������� 䆅��� ����� � 
䝂��~�.~������ � 񒝍�������� ������������ � 1971~�.  ����������, ��� ��� 
�������� ����� ����������� $B$ �������
%%117
\picture{򀁋��� 6.}
%%118
\bye
