\input style
\hyphenation{��-��-��-��-���}
%% 4
\UDC{681.142.2}
\vfill

򐅒�� ��� ��������� ���������� ������ �� ���������� ������������ ������������ �� 
���������������� �. ꍓ�� (������ ��� ����� � ������������ \rlq{}숐\rrq{} � 1976 �., 
������---� 1977 �.) ������� �� ���� ������: \rlq{}񎐒������\rrq{} � \rlq{}��\rrq{}. � ��� 
�������� ����������� ��������� ��������� ���������� � ������� ����������, ��������� 
������ ������ ���������� � �������� �� ������ ��������� ��� �������������� ������, 
������ ������ ������������� ������������ ����������. ꍈ�� �������� ������� 
����������� ����� � �������� ������ ������� ���������, ����������� ����������� 
�������� �����.

� ������ ���������� �� ���������������� ����� ������� ���������� ���������� 
��������� � ������� ����������� ��������������� ��������. ⌅��� � ��� ��� �������� 
��������� ������� �����. 獀������� � ����� ������� ������ ����������, �� �� 
�����������. ꀆ���, ��� ����� ��������� ���������������� ���������������, ������ � 
��� ����� ���������.

���������� �� ������� ���� �������������.
\vfill
\vfill
\centerline{{\it �������� ���������� �� �������������� ������}}

\line{$�{20204-022\over 041(01)-78}22-78$   \hfill   \copyright\ ���� �� ������� 
����, \rlq{}숐\rrq{}. 1978}
\eject
%% 5
\chapter{����������� ���������� ��������}
�. �. ꍓ� ������ ������ ���������� �������� �� ��������� ���� ������ ����� ��� 
�������� ���������� "葊������ ���������������� ��� ���" � �� ��������� � 
����������. 퀑������ ����� ������������ ����� ������ ��� � ��������� ���������� 
���������� � ������ ����������.

葒�������� ���������� ������� �������� ���������� ����� ������� ��� � �������� 
��������, � �� ����� ���������� ����� ������ ����������� ������ ����������� ���� ���� � 
���� �������. 퀏����� ������ �������, ������, ����������. � ���� � ���� �������� ����� 
�. ꍓ�� ����� ��������. � �������� ��� ������������, � ������� ����� ����� ����� 
�������, ���������� ����������, ������� �� ������, ������� ������� � ���������� 
�������.    

텒 ����� �������� � �������� ����� �������. �������� ���������� � ����� � ��� 
��� ���� ���� ������������ �� ���� �����������; � ���������, ��� ��������� ������� 
������� ������ ������������� ������ ���� �������� ���������� �������������, � ������ � 
����������������� ���� �������. ����, ��� ����������� �������� �����, ����� 
���������� �� ������ ��������� �������������, ������������ ����������� �������� 
���������� � ������ ����������. 쎆�� �������, ��� ���������� ������ ������������� �� 
���� ������� ����� ��� ������� ����� ������ �� ��� ��� ������������ �������� 
��������� ����������������.

ꐎ�� ������������� � ������������ ��������, ����� ����� ������� ������������ 
��������. 썎��� ������ � ������������� ������ ������� �� ��� ����� � �������� �������� 
�� ������ �� �������� ��������������� ��������, �� � �� ������� �� ���������. ������ 
��������� ������� "���������" ���� �������� ����� �������, ��� ����� ����� ������������ 
����������� �� ����� ������ ���������� � ��������� � ��� ��������� ����� 
�������������� ���������������� ��������.

���� �������� �� ������� 1973 �. (������ ��������) � ��������� ������ (����� 700) 
����������� � ����������, ������� ��������������� �������. ������� � 5.1 �� 5.3.2 ����-
������. �. �. ✞�����; ������� � 5.3.3 �� 5.5 � �����������--- �. �. ���������; ����� � 
������� �. �. 》������.
\rightline{�. �. ဟ�������}
\rightline{ �. �. ��������}
%% 6
\chapter{�����������}
\epigraph
꓋������ ����� ����������, ������� ������;\nl
������ ������---����������� ����.
\signed
� 눂��, �� Urbe Condita, XXXIX.vi\nl
(������ ᅐ���, Anatomy of Melancholy, 1.2.2.2)%
\note{1}{ ������ ᅐ��� (1577--1640) --- ���������� ������, �������� � ������.  
{\sl �. ��.\/}}

쀒����� ���� ����� ��������� ���������� �������� �� �������������� ����������, 
���������� � ��. 2, ��������� ����� � ��� ������������� ���������� �������� ����������� 
������� ������� ������������� ������. ��������� "񎐒������ � �����" ����� 
�������� � �����, ��� ��� ����� ������������� ���� ��� ��������� �������������, 
������������ ����������� ������������� �������� ���������� ��� ��������� � �������� 
����������. ��� � ���������������� ������� ���������� � ������ ���� ��� ���������� 
������ ��� ���������� �������� ������ ������ ����� ��������:

ꀊ �������� ������� ���������? 

ꀊ �������� ������ ��������� � ���������? 

ꀊ ����������� ������������� ���������� �������������? 

ꀊ ������� ������� ���� �� ���������� ���������� ��� ������� ���������� ������?

� ����� ������ ����� ��������, ��� ��������� ��������� �������� "���������� �� 
���������"? 

ꀊ ������ ���������� ����������� � ������������� �������������?

ꀊ ���������� ������������ ��������� ���� ������� ������---�����, ��������, 
�����---��� ������� ��� ������?
%% 7
� �����, ��� �� ����� ���� � ��������� ���������� � ������ ����������� ����������� 
\emph{�����} ������ ������ ����������������.

퀑������ ��� ������� �� ��.~5 �~6 ����������. � ��.~5 ��������������� ���������� 
(������������); ��� ����� ������� ����, ��� ������� �� ��� ������� �����---���������� � 
������� ����������. � ��� ����� ������ ����� �������������� �������, ����������� 
��������������� ������ ������������ (\S~5.1) � ������ ����������� ���������� 
���������� (\S~5.3). � ��.~6 �� ����� ���� � ������� ������������� �������� � ������� ��� 
�����; ���������� ���� ����� �������������� �� ������ ����������������� ������, ������ 
������ �� ���������� ������, ������ � �������������� ������� ����, ������ � ������� 
"�����������"; ����� ��������������� ����� ������� ������ ������� �� ��������� ������. 
 ����� ������������ ����� ������������� ����� �����, ����� �� ���������� ������� 
������� ��������. � ���������� � ��. 2 ��������������� ��� ������ ���� �������������� 
��������, � ������ ������������ ������� (�.~5.2.3) � �������� ������, �������������� 
����������� ���������������� �������� (�.~6.2.3).

��������, �� ��������� � ������ ����� ���� ����������, ������������� ���������� � 
��������� ����������� (���������� �), ��� ��� ��������� �� ������������� � ����� 
����������� �� �������� �������������.

��� ����� ��� ������� ����� ��������������� ��������� ���� ������������ ���� � 
�������� �������� �� ������� ����� ������ "񒐓����� ������" ��� ���������
������� � 
������� ������. 쀒����������� ����� ���� �����, �������� \S~5.1,
�.5.2.2, \S~6.3 � 6.4,  ����� �� ��������� ������� �� ������� ����������
��� ��������� ������� � ������� ������.  ꐎ�� ����, �� ������ �.~4.3.3,
4.6.3, 4.6.4, \S~5.3 � �.~5.4.4 ����� ��������� ���� ������ 
"񋎆����� ����������" ��� ���������������.

ᛑ���� �������� ����������� � �������������� ���� ��������� ����� � ���� ���� 
����� ����� �� ��� ����, ��������� ����� ������ ������� ���������� � ������ ������������ 
��������� ����������. � ����� ���������� 퀖���������� �������� �����, ������ 
������-������� ������������, 荑������ �������, ������ IBM � Norges 
Almemitenskapelige Forskningsrad �� ���������� ��������� ����
������������.

%% 8
� ���������� ����� ���� � ������ ��� ������� ������ ������ ����, �������� ������ �. 
ᅍ���, ꋀ�� �. ꐝ��, 䝂�� �. 􅐃����, ������ �. 􋎉�, ������� �. 㐝���, 녎����� 
㞈��, 䆎� ��������, ������ �. ꀐ�, 㝐� �. ꍎ��, 𓄎��� �. ꐓ���, ���� 눍�, 
⎃�� �. ��, 񒅔�� �. ����, ������ �; 񒝍��, �. �. ��� ���  � 䆎� �. ���� ��., � 
����� �������� 񒝍����� � ᅐ���, ������� �������� ������ ������ � ��������.

\line{�, 펐�����, \hfill {\sl �. �. ꍓ�\/} �������� 1972}
\vskip 1 cm
\epigraph
����� ���������� ���������� ������������, � ���������������� �������, 
�������, ��� ������� ��������� �����������. �, �������� � ���� ���������� 
�����, �������� ������ ������������, ��� ��� ��� ������� ����� ������ �������� 
� ����������������%
\note{1}{���� �. �. ������������.---{\sl �. ��.\/}}).
\signed (䆎����� 񂈔�, 񊀇�� �����, �����������, 1704)

%% 9
\chapter{��������� �� �����������}
󏐀������, ���������� � ������ ��������� �����, ������������� 
��� ��� ��������������� ����������, ��� � ��� ����������� �������. 
򐓄��, ���� �� ���������� ������� �������, ������ ����� ������ � �� 
�������� ���������� ���������� ��� ������� ����������� ����� � ��� 
����� �� ��������� ���� ���������� ��, ��� ���� ���������. ꐎ�� ����, 
�� ����� ����� ��������� ��, ��� ���� ��������� ��� ����. ���� 
���������� �������� ������ ����� ������ ������; ���� ����������� 
������������ �������, ����� �������� ����������, � ������� �� 
����������� ��� ����� ������ ���������� � ������� ���� �� ��������� 
������.

� ������ ������ ������ ���������� ������ ���������� � 
������������� ��������. 瀗����� ��� ����� ��������, ��� ��� ����� ���, 
��� ���������� � ������� ������, �������� ����������� ������ 
������������ ����, ������� ������� ����� � ���� �� ��� ������� (����� �� 
����� ����� ������ ����������� ��� ������). ꋀ��������� �������� ����� 
�������� ����� ������� ᅋ����� "䈍��������� ����������������"; ��� 
������ ���������� ������, � ������� � ����� ������ ����� ��� �������� 
"󏐀������ � ����������������� ��������" ������ ����� ��� �����, ��� 
������ � ��������� ��� ����������� ���������� ����������� 
������������� ����������� �������. ㎂����, ��� ������� ���-�� 
������� �-�� ᅋ�����, ��� �������� ���������� �� ����������������� 
�������, � ��� �������: "呋� �� ������ ������ ������, ���---����������; 
� ��������� ������ ���---��������".

쎆�� �������� ����� ������� � ������ ����, ��� � ����� ���� ���� 
������ ���� ��� ����������������� ��������, ��� � ����� ������� 
����������, � ��� ���� ����� �������� �� ����������� ������ ������ ��� 
���, ����� ������ ������, � ����� �������, �� ����� "������", ������� 
��������� ������� ��������� ������� ����������. ��� ������ ����� 
��������� ��������:

\halign{
# & \vtop{\hsize=15cm \noindent#\par} \cr
\bf ��� & ������� \cr
00 & ����������� ������ ����������, �� ������� ����� �������� �����   
��, ���� ����� �������� ������, � ������� ����� ������ ����� ������ "� 
���". \cr
%% 10
10 & ���� ������, ������� ���������� ���������� ��� 
����������� ����������, �� �� ������������ ������� 
������ ����������. � ������� ����� ������ ��������� �� 
������ ����� ������; � �������� ������� ����� 
������������ �������� � ������. \cr
20 & 瀄��� ������� ���������, ����������� ���������, ��������� 
������ ����� �����. � �� ����� ���� ������������� �����, ��������� 
�������� 15--20 �����.\cr
30 & 瀄��� ��������� ��������� �/��� ���������, ��� 
������������������� ������� ������� ��������� ������ ���� �����. \cr
40 & �� ������� ��� ���������� ������, �������, ��������, ������� 
�������� � ���� ������������ �������. �����������, ��� ������� ����� 
������ ����� ������, �� ��� ����� ��� ����������� ������������ ������� 
�������; ������ �������� ������������� �������. \cr
50 & 葑�������������� ��������, ������� (��������� ��� ���� �������� 
������ � ������ ���������) ��� �� �������� ������������������� 
�������. 呋� �������� ������ ������� ���� ������, ��� ������������ 
������ ������������ ���; ����� ����, ����� ������ ����� ����� ����� 
�����������, ���� ��� ������� ������� ��� ����� ������� (��� �������, 
��� ��� ���������).\cr
}
荒��������� �� ���� "���������������" �����, ����� ���������, 
��� �������� ����� ������������� ������. 퀏�����, ������ 17 ������� � 
���, ��� ������ ���������� ���� �����, ��� ���������� ������� 
���������. 瀄��� � ������� 50, ���� ��� ����� ������ �����-���� 
���������, � ��������� �������� ������ ����� ����� ����� ��� ������ 
45.

����� ������ �������� ������ ����������� ������, �� ����, ��� 
���������� ������, ������ ����������, ��������� �������� ��� ������ 
�������� ��� ����-�� �������; � ���� �� � ������� �������� ���������� 
������������ ��� �����, ������� �� ������ �������. 퀄����, ��� 
������������ ���� ������ ���� ���������� ������������� � ������� 
��������� �����, �� � ����� �� ����� ������������ ��� ���������������, 
� �� ����������.

��� ����� �������� ��� ��������� ����� ������ �������� 
�������������� ���������� � ������������, ������� ��������� 
���������� ������������� ������ ��� ��������� � �������������� 
�������. 呋� � �����-���� ���������� �������������� ������� ��� 
���������� ������������ ����� ������, ��� ��� ���������� ��� ���, ���� 
� ������ ������� ���������� ���������������� ����������, �� ����� 
������� ������ ���������� �������� ����� \rlq{}�". 呋� ��� ������� 
���������� ��������� ������ ������ ���������� � ������� ������, ��� 
��� ���� � ���������
%%11
�����, �� �������� ����� "��". ���� "��" ������ �� 
�������� �������������� ����, ��� ������ ���������� 
�������.

�� ���������� ������������ ����� ������� "\btr"; ��� ��������, 
��� ������ ���������� �������� ����������� � ��� ������������� 
����������� ���������. 񀌎 ����� ����������, ����� �� �������, ��� 
�������� (��� �������) ����� ������ ��� ������, ������-�� �������� 
�������� �� ��� � ��������. ��� ������ �� ������, ��� ������ ������ �� 
����� ������! ꀆ��� �������� ������ �� ������� ���� ���������� 
������ ��� ������ � ������� 10 � ����; ������� �� ������� �������, ����� 
������ � ����� �������� �������� ������� ������ � ������ �������.

� ����������� ���������� ��������� ������; ��� �������� � 
����������� ������� � ����� �����. �������� ��� �����; � ����� 
�������� ������ ����� ����, ��� �� ��������� ���������� ������, ����� 
������ ������ ��������������, ��� �� ���� ��� ������� ������ ������ � 
��� ��� �������. 呋� ������� ����������� �����, ���� ���� �� 
������������� �������� ������ ������, ������ � ���� ������ �����, 
���������� � �����, ����� ������������ � ��������. ꀊ �������, 
������ � ������� ���������� ����� ������, ����������, ��� ��� 
��������������, ��� �������� ��� ������ ������� ������ ������ 
������������ ������. 荎��� � ����������� ������� ������ ������ 
����������, ��� ������������, ����---��������. ⏎��� ��������, ��� 
���������� ���� ����� �������� ����� ������, ����������� � �����, ��� 
�� ������� ������ � ���� ������; � ����� ������ ����� ��� �� ����� 
������, ���� �� �� ��� ����� ������ �������� �������� ��� �� ����. � 
����������� �������� ��������� ����� ����� �������� ��� 
������������ ������� ������ � ������ ��� ������.

\halign{
# & # \hfill\cr
\span \bf \hfill 񂎄�� �������� ����������� \cr
\btr & ������������� \cr
 �  & � �������������� ������� \cr
�� & 򐅁��� ������ "������ ����������"\cr
 00& 򐅁��� ������������ ������ \cr
10 & ���� (�� ���� ������) \cr
20 & 񐅄��� ��������� (�� �������� ����) \cr
30 & ������� ���������. \cr
40 & 䋟 "�������������" \cr
50 & 葑�������������� ��������\cr
}

\excercises
\rex[00] ��� �������� ������� "�20"?

\ex[10] ꀊ�� �������� ��� �������� ����� ����������, ���������� � 
���������?

\ex[�50] 䎊�����, ��� ���� $n$---����� �����, $n > 2$, �� ��������� 
$x^n+y^n=z^n$ ����������� � ����� ������������� ������ $�$, $�$,$z$.

%% 13
\chapnotrue
\chapno=4
\chapter{񎐒������}

\epigraph
텒 ���� ����� �������� �� �������, ����� ������������� �� ������, 
����� �������� ��� �������������, ��� ������� ����� �������.
\signed 툊���� 쀊�������, "㎑�����" (1513)

\epigraph
"� �� �� ������, ����������� ��� ������ �����������",---�������� 
䐅��. "� ��� � �� ����� ����� ������. . � ������ ���������� �� �� 
������� � ������ ����������".
\signed �� 셉���%
\note{1}{ �� 셉���---����� ����� ����������� ������� ����������� 
������������� �������� ���� 񒅍�� 【�����.--- {\sl �. �����.\/}}. 
� "The Case of Angry Mourner"  (1951)

\epigraph
񎐒������ �������� � �������������� ���.\nl
 ����� �����, "�������� �������" � �������� ������� �� �������� 
����������� ������ ������������ ����� 260 ��������� �������� ���, 
������, ꀍ���, ������� ������, ������� ������� � ������ ��������. 
����� ���������� ������ ������, ���������� ������ �������� �����.
\signed ꀒ���� "Edmund Scientific Company" (1964)

� ���� ����� �� ������ ������, ������� ����� ��������� � 
����������������: �������������� ��������� � ������������ ��� 
��������� �������. ��������, ��������� ������ ���� �� ������������ 
��������, ���� �� ����� � ��� �� ������������� � ���������� �������. 
򎗍� ��� �� �� �������, � ������� �������� �������� � ������ ���, �� 
������ ������� �������� � �������� ����������, ��������������� ��� �� 
���������.

���� � �������� ����� "����������" (sorting) ������������ ��� 
"�������������, ����� �� ������; ������� �� ���������, �����, �������", 
������������ ����������� ���������� ��� ����� � ������� ����� ����� 
������, ��������� �� ���������� ��������� � ������������ ��� 
��������� �������. ���� �������, �������, ��������� �� ������� �� 
�����������, � \emph{�������������} (ordering), �� ������������� ����� 
����� ������� �� � �������� ��-�� ��������������� ���������� ����� 
"�������". ����������, ��������, ��������� �����������: "� ��� 
������ ��� ����� �������������� ���������� � �������, ���� �������� � 
������� � ������� � ������� ������� �������� ��� ��������� ���������, 
����� ����� ���� ������������� ������ ������� ������� �� ��������� 
�������� �������%
\note{2}{� ��������� "Since only two of our tape drives were in working 
order I was ordered to order more tape units in short order, in order to order the 
data several orders of magnitude faster".--- {\sl �. �����.\/}}. 
� �������������� ������������
%% 14
��� ����� ����� ��������� ���������� (������� ������, ������� 
������������, ������� ����� ���������, ��������� ������� � �. �.). 蒀�, 
����� "�������" �������� � �����.

� �������� ����������� ��� �������� ������������ ������������ ����� 
����� "������������"%
\note{1}{� ��������� "sequencing".---{\sl �. �����.\/}}, 
�� ��� �� ������ �������, ��-��������, �� ������ �������� ���� ����, 
�������� ���� ������������ ������ ��������, �, ����� ����, ������ �� 
����������� � ������� ���������. ꎍ����, ����� "����������" � ���� 
����� �������� ����� ��������%
\note{2}{��� � ������� ������� ��������� � ����������� ����� 
"sorting". 焅�� ����� �������� ������: "� was sort of out sorts after sorting 
that sort of data". (� ��� ��� ����� �� � ���� ����� ���������� ������ ����� 
������), ������� � ������� �������� �� ����� �����������.--- {\sl �. 
�����.\/}}, 
�� ��� ������ ����� � ��������������� ������. ���� �� ��� 
���������� ��������� ����� ������������ ����� "����������" � ����� 
������ "���������� �� �������".
\medskip
⎒ ��������� �� �������� ������ ���������� ����������:
\item{a)} ������� ������ "�����������", ����� ����� ������� ������ 
��� �������� � ���������� ��������� ���������� ��������. 䎏�����, 
������� 10000 ���������, ������������� � ��������� �������, ������ 
�������� ������ �� ��� �����; � �����������, ��� ����� 
��������������� ���� ���, ����� �������� � ������� ���������� 
�������� �������� ������� � �����. ���, �� ��������, ������ "����������" 
� ������� ������ �����, � ��� ����� ����� ���� ������ ����� ���������� 
����� � ����� ������ �����, � ������ ������������� ��������� � 
����������� ������� $v_1\le v_2 \le \ldots \le v_{10000}$. 
��������������, ������� ����� ���� ���������� � ���� ���������, � 
����������� ��������� ��������������� ������ ����� "����������".

\item{b)} 呋� ��� ��� ����� ����� ������������� � ����� � ��� �� 
�������, �� ����� �������� � ��� ��� ����� �������� �� ���� 
���������������� �������� ���� ������, ��� ���������. ��� ��� ����� 
�������, ������� �������������� �� 셉��� ��� ��������� ���� �� 
�������� (��. �������� � ���� �����). ��������, ���, ��� �������, 
������� ��������� ������������� ������ ���������������, � �� 
������������ � ����� �� ����� ��������� �������, ���� ������ ������ �� 
��������� ���, ��� �� ������� ���������� � ����������� ������. 
񎐒������ ��������� ������������ ���������������� ������ � ������� 
������ � �������� ���������� ������ ������ ���������.

\item{c)} ꀊ �� ������ � ��. 6, ���������� �������� � ��� ������, � �� 
������� ����� ������� ������ ��� ����� �������� ��� ������������� 
����������. � ����� ����, ������� (������������ 
%% 15
������� ��������), ��������������� � ���������� �������, �������� 
�������� ������ �����������, ���� ���� ��������������� �������� 
������ ���� ���������� �������.

���� ���������� ����������� � ������� ������ �������������� ��� 
��������� ������������ ������, �� ����� ���� ��� �������� 
������������, �������� � ����� ������ ���������, � ������� � ��� �� 
������� ��������; � ���. 2.3.2--17 �� �������� �� ���������� ��� 
��������� �������������� ������. 󏐀������, ����������� ����, 
������������ ������������ �������� ���������� ����������.

�� �� ������ ������� ������ ������������ �����������, 
�������������������� ������� ����������� ����������, ��� ���������� 
Larc Scientific Compiler, ������������� ������ Computer Sciences 
Corporation � 1960~�. � ���� �������������� ����������� ��� 
������������ ������� ���������� �������������� ������ ����������, 
��� ��� ��������� ��������� ���������� �������� � ������������ � ��� 
������� �������� ���������, �������������� � ������� 
������������������.  ������ ��������� ������������� ����������� 
������, �. �. ��������� � �������� ��������� ����������� ������ (������), 
������ �� ������� ������������� ���� �������������� (����� 
����������), ���� ���������, ���� ��������� � �. �. ꀆ��� ������� 
�������� ��������� ���������� �������. � ���������� ���������� �� 
������ � ��������������� ���������� ������� ��� ������������� 
������� �������������� ����������� ���������� ������. "��������� 
���������", ��������������� ������������� ��� ��� �������, �������� 
��� ����������� ����������, �������� ������� ������, ������� ��� 
����������� ������� � ������������������ ������, ���������� ����� 
��������������. � ����� ����������� �������� ������������ 
������������ ���������������, ������������� ������ � ������ ���������� 
��������������� � �. �. 񎁐����� ����� ������� ���������� � ������ 
�������������� �������������� � ��������������� �������. ���� �� 
���� ������������� ������� � ����������� ������ "������� ��������", 
���������� �������� �� ���������������. �� ����� ��������� ������� 
����� ������������� �� ������� ����������� ������; � ���������� � 
���������, �� ��������, ���������������� �������������� �������, ���� 
�� ������� ����, ��� �������������� ��������� ����������� ����������� 
� ����� �������, "�������� ����������" �����. 񎐒������ 
�������������� � �� ����������� ����� ����������---��� ���������� 
����������� ������, ��������� � ������� ��������� �� ������� � �. �. 
ꎐ��� ������, ���������� ��� ������� ���, ��� ��� ��������� ������, 
���������� �� ���������, ���������� ����� ���� ����� ���������������. 
����-�� ������ � ���������� ������ ����������� ��������,
%% 16
������� ��������� ������������� ��� ������ ���������� �������� 
���������.

䐓���, ����� ��������� ���������� ���������� ��������� ��� 
�������������� ������, ��� ������ ������ �������� ������. � 
������������ ������ � ���������� ��������� � ����������, ������������� 
������� ���� ���� � ����������� ������. ⑅ ���������� ������ ����� 
������� ������������� (� ��� � ��� ������ � �������� �����������) � 
����� � �������� ������. ��� ���� ����������� ������� ������������ 
������ � ������ ����������������������. 
[�. � �. �. Foster, {\sl Comp. J.\/}, {\bf  11} (1968), 134--137].

������� �������������� ����� �������, ��� � ������� ����� 25\% 
��������� ������� �������������� �������� �� ����������. � ������ 
�������������� �������� �� ��� ������ ������ �������� ��������� 
�������. � ���� ���������� ����� ���������, ��� ���� (i) ���������� 
����� ����� ������ ����������, ���� (ii) �� ����� ���������� ��� �����, 
���� (iii) ����������� � �������� ������������� ��������� ����������. 
�-��������, ������ �� ���� ������������� �������� ���� ������. � 
������ ������ ����, ��� ���������� ����������� ���������� �������� � 
����� ������ �� ������������� �������������.

� ���� ���� �� ���������� ���� ����� ����������, ������� �� ����� 
������ ������ �������� ��! 臎������������ ��������� ���������� 
������� � ���, ��� ��� � ���� �� ���� ��������� ��� ������ ������������. � 
���� ������� ���������� ��������� ������������� ���������� ����� 
������ � ������ ��������� ��� ���������.

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

셒��� ���������� ������ ������������ ������������ ���� 
\emph{ ������� ����������}, �. �. ����, ����������� ��������� ������� 
�������������� ����������, � ������, ������� �������� �����. �������� ��, 
����������� �������. ��������, ������� ���������� � ����������, ������ 
� ���� ����� ������ �������� ������ �������� ������ ���������� � 
������� ������� ������� ������������                                        
%% 17
�����������. � ������ �������, ��������� ��������� ���, ��� ��������, �� 
������� ����� ����������, ����� ������������� ���������� ��������.

��� ��� ��������� ������, ���������� ����� ����� ���������� 
������ � ������ ��������������� ������������. �� ���� ����������� 
$N$ ���������
$$
 R_1, R_2, \ldots, R_N.
$$
퀇���� �� \dfn{��������}, � ��� ������������ N ������� ������� 
\dfn{������}. ꀆ��� ������ $R_j$ ����� \dfn{����} $K_j$, ������� � 
��������� ��������� ����������. ��� �����, ������ ����� ��������� 
��������������, "������������� ����������", ������� �� ������ �� 
����������, �� ������ �������� � ���� ������.

������ ������� "$<$" �� ��������� ������ �������� ����� 
�������, ����� ��� ����� ���� �������� ������ $a$, $b$, $c$ 
����������� ��������� �������:

\item{i)} ����������� ���� � ������ ���� �� ����������� $a<b$, 
$a=b$, $b<a$  (����� ����������);

\item{ii)} ���� $a<b$  � $b<c$, �� $a<c$ (����� ��������������).

��� ��� �������� ���������� �������������� ������� \dfn{��������� 
������������}, ����������� ��� \dfn{����������� �������������}. 랁�� 
��������� � ���������� "$<$", ��������������� ��������� (i) � (ii), 
��������� ���������� ������������ �������, ��������� � ���� �����, ���� 
��������� �� ��� ������� ������ ��� �������� � ��������� ������ � 
������� ���������� �������.

瀄��� ����������---����� ����� ������������ ������� 
$�(1)$ $�(2)$ \dots\ $�(N)$, ����� ������� ����� ������������� �� � 
����������� �������:
$$
K_{� (1)} \le  K_{p (2)} \le \cdots \le K_{p(n)}. \eqno  (1)
$$

񎐒������ ���������� \dfn{����������}, ���� ��� ������������� 
��������������� �������, ��� ������ � ����������� ������� �������� � 
������� �������, �. �. 
$$
p(i)<p(j), \rem{����  $K_{p(i)}=K_{p(j)}$  � $i<j$.} \eqno  (2)
$$

� ���� ������� ����� ������������� ��������� ���������� ������ � 
������ ���, ����� �� �����, ���� �����������; � ������ ������� 
���������� ������� ��������������� �������, ������� ��������� ������� 
��������� ������������ � ������������ ������ � ������� � ������������ � 
�������� �� ������.

텊������ ������ ���������� ������������ ������������� ������� 
"$\infty$" � "$-\infty$" ��� ����� �� ���. ⅋����� "$\infty$" ��������� 
������, � �������� "$-\infty$" ������ ������ �����:
$$
 -\infty < K_j <\infty, \qquad  1\le j \le N. \eqno (3)
$$
%% 18
��� �������� ������������ � �������� ������������� ������, � ����� ��� 
��������� ��������. ��������� � (3), ������ ������, ���������. 呋� �� 
��� ��� �� ����� �����������, ��������� ����� �������������� ���, 
����� ��� ���-���� ��������, ���� ������� ��� ���� �� ��������� � 
������������� ������� ������������.

��� ���������� ������������ �� ��� ������: \emph{����������}, 
����� ��� ������ �������� � ������� ����������� ������, � 
\emph{�������}, ����� ��� ��� ��� �� ����������.  ���������� 
���������� ������� ����� ������ ����������� ��� ���������� �������� 
������ � ������� � ���, ������� �� ����������, ��� ��������� � �������� 
������ ������������� �������.

䎑������� ������� ����� �������� ����������� �� ���������� $N$ 
������� ����� ������� $N \log N$; ��� ���� ��������� ����� $\log N$ 
"��������" �� ������. ꀊ �� ������ � �.~5.3.1, ��� ����������� �����. 
�, ���� ������� ����� �������, �� � ����� ��� ������ ������ �������� 
��������� �������� ����� ��� �����. (� ����� ����, ����� $N$ ��������� � 
$\infty$, �����"������ ��� $N(\log N)^2$, ���� ��� ����� ��������, ��� ��� � 
������� ������ ������������� � ������ $N$; �� ����������� $N$ ������ 
�������� ������������.)

\excercises  (������ �����)
\ex[�20] 䎊�����, ��� �� ������� ���������� � �������������� 
�������� \emph{��������������} ������������ $�(1)$, $�(2)$, \dots, $�(N)$, 
���� ���������� ���������.

\ex[21] �� ������ ������ $R$. ���������� ����� ����� \emph{���} 
�����: "������� ����" $K_j$ � "����� ����" $k_j$, ������ ��� ��������� 
������ ������� �����������. 򎃄� ����� ������� �������� ������ 
"������������������ �������" �� ��������� ��� ������ $(�, k)$:
$$
(K_i, k_i) < (K_j, k_j),
\rem{ ���� $K_i<K_j$  ��� ���� $K_i=K_j$  � $k_i<k_j$}.
$$

텊�� (������� ��� ������ $�$) ������������ ���� ���� ������� �� 
������� ������, ������� $n$ ����� ������� � ����������� �������� 
������� � ������ ������:
$$
K_{p(1)}=\cdots=K_{p(i_1)}<K_{p(i_1+1)}=\cdots=K_{p(i_2)}<\cdots 
< K_{p(i_{n-1}+1)} = \cdots = K_{p(i_n)},
$$
��� $i_n=N$. 瀒�� ������ ��  $n$ ����� $R_{p(i_{j-1}+1)}$, \dots, 
$R_{p(i_j)}$ �� ������������  �� ����� ������.

� �� �������� ���� ���� ������ $�$ � ������������ ��� ������� �� 
����� ������, � ����� ������������ ���� ������������ �� ������� 
������.

⇟� ��� �� �������� ����, ������ $�$ ������������ ��� ���� ���, 
��������� ������������������ �������� ����� ������ ������ 
$(K_j, k_j)$.

�������. �� � ���� ����� ���� � �� ��?
%% 19
\ex [M25] �� �� ��������� $K_1$, \dots, $K_N$  ���������� ��������� 
$<$, ��� �������� ����� ���������� �����������, � ����� ��������������---
\emph{���}. 䎊�����, ��� � � ���� ������ �������� ���������� ���������� 
�������, �. �. �����, ��� ����������� ������� (1) � (2); �� ����� ���� 
���������� �� ������� ���� ��� ������������ �������, ��������������� 
���� ��������!

\ex[15] 숑��� 򓏈�� (�����������) ������� ������, ��������� �� � 
������ |�| ������ \MIX\ �����, ������� ����� �� ������ |�|, ������� ��� �� 
������ ���. � �������
$$
\eqalign{
&|LDA � |\cr
&|SUB �|\cr
}
 $$
� ����� ��������, ����� ��������� ��������� � |rA|: ������������� �����, 
������������� ��� ����. ꀊ�� ��������� ������ �� �������� � ��� ������ 
��� ���������?

\ex [17] 퀏����� \MIX-������������ ��� ��������� ������, ���������� 
��������� ����, ������ �� ��������� �������:
\ctable{#\hfill\bskip&\hsize=10cm\noindent\vtop{#}\hfill\cr
⛇��: &   |JMP COMPARE| \cr
񎑒����� ��� �����:  &     
$|rI1|=n$; $|CONTENTS|(A+k)=a_k$, $|CONTENTS|(B+k)=b_k$ ��� 
$1\le{} k\le{} n$; ��������������, ��� $n \ge{} 1$.\cr
񎑒����� ��� ������: &      
$|�I|=+1$, ���� $(a_n, \dots, a_1) > (b_n, ..., b_1)$; \cr
 & $|�I|=0$, ���� $(a_n, \dots, a_1) = (b_n, ..., b_1)$;\cr
& $|CI|=-1$, ���� $(a_n, \dots, a_1)< (b_n, ..., b_1)$; \cr
& |rX| � |rI1|, ��������, ����������.\cr
}
焅�� ��������� $(a_n, \dots, a_1) < (b_n, ..., b_1)$ ���������� 
������������������ ������������ ����� �������, �. �. ���������� ������ $j$, 
�����, ��� $a_k=b_k$ ��� $�\ge{} k > j$, �� $�_j < b_j$.

\ex[30] � ������� |A| � |�| ���������� �������������� ����� $�$ �~$b$. 
�����, ��� ����� �������� \MIX-���������, ������� �� ��������� 
$\min (a, b)$ � ���������� ��������� � ������ |�|, \emph{�� ��������� 
��������� ��������.} (\emph{������������:} ��������� �������������� 
������������ ���������� ���������� ��� ������ ��������, ������� ��� 
��������� ���������, ����� ������������ �� ����� ���������� �� ��� ����� 
��������� $�$ �~$b$)

\ex[�27] ꀊ��� ����������� ����, ��� ����� ���������� � ����������� 
������� |N| ����������� ���������� �������������� �� ������� $[0, 1]$ 
��������� ������� $r$-� �� ������ ����� �������� $\le{} x$?

\excercises ���������� (������ �����)
� ������ �� ���� ���������� ���������� ������, � ������� ����� 
����������� �����������. ������� "�������" ������� ������, 
�����������, ��� ������� ������������ ��������� ����������� ������ � 
����� ����������, �������������� ��������� (����� ���������� ���������� 
��� ����������).

\ex[75] 茅���� �����, �� ������� ������� ������� ���� ������. ꀊ 
����������, ������� �� ���� ����� ��������� ����?

\ex[18] ⎎������� ���� � ���� 󏐀������ ���������� ������� 숍���������
�������� ���. � ��������� �������� "��������������" �������� �� 
����������� � ���, �������, ����� ��� ��������� ��������� �����, � 
�������� "���������" �������� �� ��������� ��� �� �� �������. ꀊ �� �� 
����� ���������� �����, ������� �������� �� ��� ���� ����� �������?

%% 20
\ex[�25]{\sl (򐀍������������ �������.)\/} 茅���� ��������� �����, 
���������� ������� ����, ������� ������������ ����� �������� 
$1000\times1000$-�������, ���������� �� �������: $a_{1,1}$ $a_{1,2}$ \dots 
$a_{1,1000}$ $a_{2,1}$ \dots $a_{2,1000}$ \dots $a_{1000, 1000}$. ‘� 
������---�������� �����, �� ������� �������� ���� ������� ���� �� 
�������� �� ��������: $a_{1,1}$ $a_{2,1}$ \dots $a_{1000,1}$ $a_{1,2}$\dots 
$a_{1,2}$\dots $a_{1000,2}$ \dots $a_{1000, 1000}$ (��������� ������� �� 
����� ������ ���������� ������.)

\ex[�26] � ����� ������������ �������� ������� ���� �� $N$ ����. 
ꀊ �� �� ��� "������������" ��������� �������?

 \rex[24] � ����� ������������ �������� ����� 1000 �������������� � 
������� 500 ���������. 񗈒�����, ��� ������ ������������� �������� 
������ �� ������� ���� ���� ���������. ‌ ����� ����������� � ������� 
������ ������������� ������ ������ ���� ���������. � ������������ 
������� �� �������������� 1500 ���������, ��������� ������������ 
������� � ���������� ��������� ����������:

{\it �������� ��������:\/} ������� 1---������; ������� 2--18---������� � 
������������ ���������; ������� 19--20---��������; 
������� 21--23---����� ������� ꎌ�����; 
������� 24--26---����� ������� ��������; \dots; 
������� 78--80--- ����� ���������� �������� (���� �����) ��� �������.

{\it ꎌ�������� ��������:\/} ������� 1---"*"; ������� 2--77---�������� 
��������; ������� 78--80---����� ��������. ꀊ �� ������ �����������? 
(���� ���� ����� ���������� ��������.)

\ex[20] � ��������� � ����� ��������������� ���������, � ������� 
��-������� ����������� ������ (����� � �����). ꀊ ��������� ������ 
��� ����������� ����� � ��������-�������� �����������, 
��������������� ��� ������������� �� ������ ���?

\ex[18] 茅���� �������� ������� ������ �����, ���������� � ���, � 
��������� �����, � ������� ��� ��������. ꀊ ���������� ����� �����, 
���������� � ������ �����? (�����������, ��� �� ���� ������� �� ������ 
� ������ ����� ������ ����.)

\ex[20] ����� ��������� �������� ��������� � ������� ���������, 
���������� �� �������, �� ������ �������� ���������, 
�������������� ������� "������������ ������". ╎����� ������� ��� 
��� ������ ��������� �� �������, � � ���������� ���������� ������� 
�������� ���������, ���������� ���������� ���� ������� ������������ 
������� �������������� (�. �. �����) � ���������. ꀊ �������� ����� 
���������?

{\def\cell#1{\vtop{\hsize=.49\hsize\noindent #1\par}}
 \def\+#1&#2\cr{\line{\cell{#1}\hfil\cell{#2}}\smallskip}
\ex[33] (񎐒������ ���������� ��������.) 񏎑��� ����������� 
���������� ��������� � ������ ����������� ��������� ���������� ���� �� 
�����. � ��������� "����������" ������ ���������� ������������, ������ 
�� ������ ����������� � �������� ���������� �������� ������������ 
������������ ���������� (������, 1942):
\medskip
\+ \centerline{\bf 򅊑� ��������}%
  &\centerline{\bf 瀌������}\cr
\+ R. Accademia nazionale dei Lincei, Rome 
  &� ��������� ����������� (����� ����������) ���������� ����� "royalty" 
   (�����������) ������������\cr
\+ 1812; ein historischer roman.  
  &Achtzehnhundert zw\"olf \cr
\+ Biblioth\`eque d'histoire r\'evolutionnaire. 
  &� ����������� ������  �������� ��������������� ��� ������ \cr
\+ Biblioth\`eque des curiosit\'es.       
  &퀄�������� ����� ������������ \cr
\+ Brown, Mrs. J. Crosby       
  &󊀇���� ��������� (Mrs.) ������������ \cr
\+ Brown, John   
  &􀌈��� � ������ ������� �� ��������� ��� ���~\dots \cr
\+ Brown, John, mathematician   
  &\dots{} ������� ��������������� �� \cr
\+ Brown, John, of Boston
  &������������ ������ \cr
\+ Brown, John, 1715--1766
  &������� ������� ��������������� �� ����� �������� \cr
%% 21
\+ BROWN, JOHN, 1715--1766 
  &������ "� ���" ���� ����� ��� ����� \cr
\+ Brown, John, d. 1811
  &荎��� ��� �������� ������������ �������������� \cr
\+ Brown, Dr. John, 1810--1882 
  &󊀇���� ��������� (Dr.) ������������ \cr
\+ Brown-Williams, Reginald Makepeace
  &䅔�� ��������������� ��� ������ \cr
\+ Brown America. 
  &퀇����� ���� ���� ����� ��������� ������� \cr
\+ Brown \& Dallison's Nevada directory.  
  &\& � ���������� ������ ������������ � "and" \cr
\+ Brownjohn, Alan
  &\cr
\+ Den', Vladimir \'Eduardovich, 1867--
  &�������� � ������ ������������\cr
\+ The den.  
  &������� � ������ ������ ������������\cr
\+ Den lieben s\"ussen m\"adeln. 
  &\dots{} ���� ��������������� ����� � ������������ ������\cr
\+ Dix, Morgan, 1827--1908  
  &􀌈��� ���� ������ ������ ���� \cr
\+ 1812 ouverture.
  &Dix-huit cent douze \cr
\+ Le XIXe si\`ecle fran\c{c}ais.
  &Dix-neuvi\`eme \cr
\+ The 1847 issue of U. S. stamps.
  &Eighteen forty-seven \cr
\+ 1812 overture.
  &Eighteen twelve \cr
\+ I am a mathematician,
  &(by Norbert Weiner)\cr
\+ IBM journal of research and development.
  &������������ ��������������� ��� ��� ������������� ���� \cr
\+ ha-I ha-e\d had.
  &������� � ������ ������ ������������ \cr
\+ Ia; a love story.
  &獀�� ���������� � ��������� ������������ \cr
\+ International Business Machines Corporation
  &\cr
\+ al-Khuw\={a}rizm\={\i}, Mu\d{h}ammad ibn M\={u}s\={a}, {\it fl.\/} 813--846 
  &퀗������ "�l-" � �������� ������ ������������ \cr
\+ Labour; a magazine for all workers. 
  &瀌������� �� "Labor" \cr
\+ Labor research association 
  &\cr
\+ Labour, {\it see\/} Labor
  &񑛋�� �� ������ �������� � ��������� \cr
\+ McCall's cookbook 
  &�������� � ���������� ������ ������������ \cr
\+ McCarthy, John, 1927--
  &Mc = Mac \cr
\+ Machine-independent computer programming. 
  &䅔�� ��������������� ��� ������ \cr
\+ MacMahon, Maj. Percy  Alexander, 1854--1929 
  &󊀇���� ��������� (Maj) ������������ \cr
\+ Mrs. Dalloway. 
  &"Mrs. "= "Mistress" \cr
\+ Mistress of mistresses.
  &\cr
\+ Royal society of London
  &\cr
\+ St. PetersburgerZeitung.
  &"St."= "Saint"   ����  � �������� ������ \cr
\+ Saint-Sa\"ens, Camille, 1835--1921 
  &䅔�� ��������������� ��� ������ \cr
\+ Ste. Anne des Monts, Quebec
  &Sainte \cr
\+ Seminumerical algorithms.
  &\cr
\+ Uncle Tom's cabin.
  &\cr
\+ U.S. Bureau of the census.  
  &"U.S." = "United States" \cr
\+ Vandermonde, Alexander Th\'eophile, 1735--1796
  &\cr
\+ Van Valkenburg, Mac Elwyn, 1921--
  & ��� ����� �������� � �������� ������������ \cr
\+ Von Neumann, John, 1903--1957
  &\cr
\+ The whole art of legerdemain.
  &\cr
%% 22
\+ Who's afraid of Virginia Woolf?
 & �������� � ���������� ������ ������������\cr
\+ Wijngaarden, Adriaan van, 1916--
 & 􀌈���  ������� ��  ���������� � ����� ����� \cr
\medskip
\noindent(� ����������� �� ���� ������ ���� ����������; ����� ����, ���������� 
����� ������ ������, ������� ����� �� ���������.)
\par
}

��������, ��� �������� ����������� ������� ���������� ����� 
�������� � ������� �������������� ������ � ������������ ����������� 
�������� ���������, ������ � ��� ��� ����������� �������� ��� 
����������� ������� ���������� ��������. ꀊ �� �� ������������ 
����������, ����� ��������� �������� ��������� ����� �������� � 
����������?

\ex[�21]\exhead(䈑������� ���������.) �� ��������, ��� 
$p$---(�������� �������) ������� �����, � $a$---������������� ������ �� ������ 
$p$. 񋅄���������, ��� ������ $b$ � ��������� $1\le{} b < p$ ���������� 
������������ $n$, �����, ��� $a^n \bmod p=b$, $1\le{} n < �$. ꀊ �� 
��������� $b$ ����� $n$ ����� ��� �� $�(n)$ �����? [󊀇����. �� 
$m=\lceil\sqrt p\rceil$. �������� ������ ��������� 
$a^{mn_1}\equiv b a^{-n_2} \pmod{p}$  ��� $0 \le{} n_1$, $n_2 < m$.]

\ex[�25] (�. �. ���.) ����� �������� �������������, ��� ���������
$$
u^6+v^6+ w^6 + �^6 + y^6 = z^6
$$
�� ����� ������� (�� ����������� �����������) ����� ����� 
��������������� ����� $u$, $v$, $w$, $x$, $y$, $z$, ����� �� ������� ���� 
������ ���������� ����� ����. ��� �����, �� �����������, ��� 
���������
$$
x_1^n+\cdots+x_{n-1}^n=x_n^n
$$
�� ����� ������������� ������� ��� $n\ge 3$, �� ��� ������������� ���� 
������������: � ������� �������������� ������ ������� ��������� 
$27^5+84^5+110^5+133^5=144^5$; ��. �. �. 띍���, �. �. ��� � �. �. 
񅋔����, {\sl Math. Comp.\/}, {\bf 21} (1967), 446--459. �������, ��� 
����� ���� �� ������������ ���������� ��� ������ ��������, 
������������� ������������� ������ ��� $n=6$.

\rex[24] 􀉋 �������� ������� ���������� 30-��������� �������� ����:
$x_1$, \dots $x_N$. ������� ������� ������ ���������� � ��� ���� 
\emph{��������������} ��� $(x_i, �_j)$. (䂀 ����� ���������� 
���������������, ���� ������ �������� 0 �� ���� ��������, � ������� ���� 1 
� ������ �����, � �������; ����� �������, ��� ������������� ����� � ������ 
�����, ����� �� ����� ����� $(11\ldots1)_2$, ���� ��� ��������������� ��� 
�������� �����.) 

\rex[25] 茅���� ����. ���������� 1000 30-��������� �������� ���� 
$x_1$, \dots, $x_{1000}$. ꀊ �� �� ����� ���������� ������ ���� ��� 
$(x_i, x_j)$, �����, ��� $x_i$ ���������� �� $x_j$  �� ����� ��� � ���� 
��������?

\ex[22] ꀊ �� �� ��������� ��� ��������� ���� ������������� ��������, 
�����, ��� \strong{CARET, CARTE, CATER, CRATE, REACT, 
TRACE; CRUEL, LUCRE, ULCER; DOWRY, ROWDY, WORDY?} [呋� 
�� ��, ������, �������� ������, ���������� �� � ���������� ����� ������ 
�� ������ ��� ����� ��������, ����� ������������� �����:
$$
\vtop{\strong{
APERS, ASPER,PARES,PARSE,PEARS, PRASE, RAPES, REAPS, 
SPARE, SPEAR,
}}
$$
� ������� ����� �������� ��� ����������� ����� \strong{APRES.}]

\ex[�28] �� ���� �������� ������ �������� ����� ������������ 
������. ꀊ�� ����� ����� ������������� \emph{����������} �����? (䂀 
������������ ����� ���������� �����������, ���� ���������� ������� 
����������� ������������ ����� �� ��������� � ������� ����������� 
������������
%% 23
����� �� ������, ������ ��� ������������ ��������� ������������� ������ 
� ���.)

\ex[30] � ��������� ������ �� 4096 ������� ������ ����� ����� 100 
��������. ᛋ ��������� ������ ���� ��� �����, �������� ����� �����. (��� 
��������� �����������, �. �. ���� $�$ ������ � $�$, �� � $�$ ������ � $�$. 
���� ������ �������� �������� 200000 ���.) ������� ��������, 
������� �� �a�a��o�y $k$ ������� �� ��� \emph{�����} �� $k$ �������. 
(ꋈ�� --- ��� ������ �����, � ������� ��� ����� ����� �������.) 
�����������, ��� ������� ������� ���� �� ������.

\ex[30] � �������� ������� � ���������� ������� ���� ������� 
����� ����������� �������� �� 휞-鎐�� �� ꀋ�������. ꀆ���� �� ��� 
���� ������ ������, �� ������� �� ������� ���� ��� � ��� ������ 
���������� ��������� ������. �������, ������������ � ����� �������� 
����� ����, �� �����, ��� ��� ������, � ������� ���� ������. ������ 
2999999 ������� ������� � ������� ������� � ��������� � 퀖��������� 
�����, � ‘������, ����� ꎋ�����. � ���������� ������� ��������� 
������������ � �������� �� ��������� �����.

񏅖������ �� ������ ���������� ���������, ��� ������� ���������� 
���������� ��� �������������� ������ ����� � �������� �������. 
񏅖������ �� ���������������� ����� ������ ������� ��� ����� ��� �� 
1000 ���������� ���� � �������, ��������� ���� ���������������� ������ � 
������ �� ������ � ��������� ���������� ������ � ������������ ��������. 
ꀊ ��� ��� �������?

[䐓���� �������, ���, ���� ������������� ������������ ������� ���� 
$(x_i, x_{i+1})$, $1 \le i < N$, ��� ��� $x_i$ ��������, �������� 
������������������ $x_1$, $x_2$, \dots, $x_N$, �������� ���� ������ 
���������������� ��������� ������, ��������� ��� ������ � ���������� 
�������? ��� ������ ���������� � ������, ����� ������ ����������, ����� �� 
���� ������ ������������ �������; �� ��� ��������� ���� ������ � ���. 
2.2.3--25.]
%% 24

\subchap{* ������������� �������� ������������}
���������� ��������� ��������� ���������� ��������� ������������ 
��� ��������� � ���. ��������� �������� ����� ��� �������� ���������� 
����������, ��� ��� ��� ������ ��� ������������� ��������������� 
�������� ������. ����� ����������� ������������� ��������� ������� 
����������, ����� ����� ������������ ����� ������������, ������� 
��������� ��������� ��������� ��� ��������� ������������ ����� ���. 

�, �������, ��� �� ��� ����������� � �������������� � ��. 1, 2 �~3. 
퀏�����, � �. 1.2.5 ����������� ��� �������� ������������� ������ 
���������� $n!$ ������������ �� $n$ ��������;
� �. 1.3.3 ���������������� ��������� ���������, ��������� � ����������� 
���������� � ������������������ ���������� ������������; � �. 3.3.2 
������� �� ������� ������������. ���� ���������� ���������---������� 
��������� ������ �������� ������������ � ����������� ����� ������, ����� 
����������� ������� ���������� ���������. ���� �� ������ ������ � 
������������� ����������.

񂎉���� ������������ ��������� �������, ��� ������������ � 
��������������� �������. 󄎁�� ����� ���� �� ��������������� ��������� � 
����� �����, � �� ������������ �������� �� ���� �����. ���������, �� 
������� ���������� � ����������, � ����� ���, ��� ������ �������� 
��������� �� ����� ������� ����������, ������������� ������� ����� � 
\S~5.2, ������ ��� ��������� �������� \emph{�����������������} 
��������� � ���������� ����� �� �����.

\subsubchap{*荂�����}
�� $a_1$ $a_2$ \dots\ $a_n$ ---������������ ��������� 
$\{1, 2, \dots, n\}$. 呋� $i < j$, a $a_i>a_j$, �� ���� $(�_i, a_j)$ 
���������� 
��������� ������������; ��������, ������������ 3 1 4 2 ����� ��� ��������: 
$(3, 1)$, $(3, 2)$ � $(4, 2)$. ꀆ��� ��������---��� ���� ���������, 
"���������� �������"; �������������, ������������ ������������, �� 
���������� ��������,---��� ��������������� ������������ 1 2 \dots $n$. 
򀊀� ����� � ����������� � ���� ������� ������� ������ �������� � 
���������, ���� ��� ������� ��� �������������� ���� ��� ������� ��������� 
������������� ������������� ������ (��. ���. 2.2.2--9).
%% 25

���� �������� ���� �. ꐀ��� � 1750 �. [Intr. \`a 1'Analyse des Lignes 
Courbes alg\'ebriques (Geneva, 1750), 657--659; ��. � 򎌀� 있�, �h���� of 
Determinants, 1 (1906), 11--14] � ����� �� ����� ������������� �������� 
������� �������� ���������. � ��������, �� ��������� ����������� 
$n\times n$-������� ��������� �������:
$$
\det\pmatrix{
 x_{11} & x_{12} &\ldots & x_{1n} \cr
\vdots    & \vdots & & \vdots \cr
 x_{n1} & x_{n2} & \ldots & x_{nn} \cr
}=\sum (-1)^{I(a_1 a_2 \ldots a_n)}x_{1a_1}x_{2a_2}\ldots x_{na_n},
$$
��� ����� ������� �� ����  ������������� $a_1$ $a_2$ \dots\ $a_n$, � 
$I(a_1 a_2 \ldots a_n)$---����� �������� � ������������.

\dfn{򀁋���� ��������} ������������ $a_1$ $a_2$ \dots\ $a_n$ 
���������� ������������������ ����� $b_1$ $b_2$ \dots\ $b_n$, 
��� $b_j$---����� ���������, 
\emph{�\'������} $j$ � ������������� \emph{�����} $j$. 
(䐓���� �������, $b_j$---����� ��������, � ������� ������ ������� 
�����~$j$.) 퀏�����, �������� �������� ������������
$$
5\;9\;1\;8\;2\;6\;4\;7\;3 \eqno                     (1)
$$
�����
$$
2\;3\;6\;4\;0\;2\;2\;1\;0,\eqno  (2)
$$
��������� 5 � 9 ����������� ����� 1; 5, 9, 8---����� 2 � �.�., ����� 20 
��������. � �����������
$$
0\le{} b_1\le{} n-1,  0\le{} b_2 \le{} n-2,\ldots ,0\le{} b_{n-1}\le{} 1, 
b_n=0.\eqno (3)
$$

����, �������� ������ ����, ���������� ������������, � 
������������� 쀐������ ������, ��� ��, ��� \emph{������� �������� 
������������ ������� ���������� ��������������� ������������.} [�. 
Proc. Symp. Applied Math., {\bf 6} (American Math. Society, 1956), 203.] � 
����� ������� �������� $b_1$ $b_2$ \dots\ $b_n$, ��������������� �������� 
(3), ����� ���������� ������������ ������������, ������� ��������� 
������ �������, ����� ����������������� ����������� �������������� 
������������ ��������� $n$, $n-1$, \dots, $1$ (� ���� �������). 퀏�����, 
������������, ��������������� (2), ����� ��������� ��������� �������:
������� ����� 9; ��� ��� $b_8=1$, �� 8 ����� ������ 9. ������ 
$b_7=2$, �� 7 ����� ������ 8 �~9. � ��� $b_6=2$, �� 6 ����� ������ ���� 
��� ���������� ���� �����; ����� �������, �����
$$
9\; 8\; 6\; 7.
$$
%% 26
����� ������ 5 �����, ������ ��� $b_5=0$; �������� 4 ����� �� 
�������� �� ��� ���������� �����, 3---����� ����� ���������� ����� (�. �. 
� ������ �����) � ��������
$$
5\;9\;8\;6\;4\;7\;3.
$$
⑒���� ����������� ������� 2 � 1, ������ � (1).

򀊎� ������������ �����, ������ ��� ����� ����� �������� ������, 
���������������� � �������� ������������, ������������� �� �������, 
���������������� � �������� ������ ��������, �������, ��������, �������� 
�����. ����������, ��������, ����� ������� ������: ������� ���������� 
������������ ��������� $\{1, 2, \ldots, n\}$? �� ������ ���� ����� ����� 
������������ ������ ��������, � �� ����� �����������, ��� ��� $b_1$ ����� 
������� $n$ ���������� ���������, $b_2$ ����� ���������� �� $b-1$ 
������� $n-1$ ���������, \dots, $b_n$---����� ��������; ����� 
$�(�-1)\ldots 1=n!$ ��������� ������ ��������. 򀁋��� �������� �����������
�����, 
������ ��� $b$ ����������, � �� ����� ��� $�$ ������ ���� ��� ��������.

� �. 1:2.10 �� ����������� ������ � ����� ��������� ���������� 
������������, ���� ������ �� ������ ������; ����� �������, ����������� 
���������� ���������� ���������, ������ �� ������� ������ ������ �� 
��������� ����� ����. (퀏�����, �������������� ��������� � (1)---��� 9, 
8, 7 � 3.)  ����� ���������� �������� $j$, �����, ��� $b_j=n-j$. � ��� 
$b_1$ ��������� �������� $n-1$ � ������������ $1/n$, $b_2$ (����������) 
��������� �������� $n-2$ � ������������ $1/(n-1)$ � �.�., �� �� ������������ 
�������� ����, ��� ������� ����� ��������������  ���������� �����
$$
{1\over n}+{1\over n-1}+\cdots+1=H_n.    
$$
����������� �������� ����� �������� � ��������������� ������������ 
�������.

䐓��� ���������� ������ �������� ���������� ����� � ���� ����� � ����� 
� ����������� ����������� ����������.

ߑ��, ��� ���� �������� ������� \emph{��������} �������� 
������������, �� ����� ����� �������� ���������� ��� ���������� �� 
�������. � ���. 1 �������� 24 ������������ ��������� $\{1, 2, 3, 4\}$; 
������� ��������� ������������, ������������ ���� �� ����� ���������� 
���� �������� ���������; �������� ����� ����� ����, �� .����������� ����� 
�������� �� �������. 񋅄���������, ����� �������� � ������������ $�$ 
����� ����� ����������� ���� �� 1 2 3 4 � $n$ �� ���.~1; ��� ����� ���� 
������ ����� ���������� �����.

瀌����, ��� ��� ��������� ����� ������������� ��� ���������� ������� 
����---"��������� �������", ������� 8 �������������
%% 27
� 6 ���������� ������. ��� ���� �� ����������� ��������������, ������� 
�������� ������� (��. ���.,10).

\picture{
���. 1. 󑅗����� �������, �� ������� �������� ��������� ����� 
��������, ����� �������� ������� ��� �������� �������� ������������;
}

� ������� ������ "��������" ������������ � ��������� ��������������. 
⑏�����, ��� ������������ ����� ���������� � ���� ���� �����
$$
\pmatrix{
1 & 2 & 3 & \ldots & n \cr
a_1 & a_2 & a_3 & \ldots & a_n \cr
};\eqno (4)
$$
\dfn{��������} � ���� ������������ ���������� ������������ $a'_1$, $a'_2$, 
\dots\ $a'_n$, ������� ����������, ���� � (4) �������� ������� ������, � ����� 
����������� ������� � ������������ ������� �� ������� ���������: 
$$\pmatrix{
a_1 & a_2 & a_3 & \ldots & a_n \cr
1 & 2 & 3 & \ldots & n \cr
}=\pmatrix{
1 & 2 & 3 & \ldots & n \cr
a'_1 & a'_2 & a'_3 & \ldots & a'_n \cr
};
\eqno(5)
$$
퀏�����, �������� � ������������ 5 9 1 8 2 6 4 7 3 ����� ������������
%% 28
3 5 9 7 1 6 8 4 2, ��� ���
$$
\pmatrix{
5 & 9 &1 &8 &2 &6 &4 &7 &3\cr
1 & 2 & 3&4 &5 &6 &7 &8 &9\cr
}=\pmatrix{
1 &2 &3 &4 &5 &6 &7 &8 &9\cr
3 &5 &9 &7 &1 &6 &8 &4 &2\cr
}.
$$
   쎆�� ���� ������ ����������� �������� ������������: $a'_j=k$ ����� � 
������ �����, ����� $�_k=j$.

����� ������������ ������� ���� X. �. ���� [� �.F.~Hindenburg(ed.)., 
Sammlung combinatorisch-analytischer Abhandlungen, 2 (Leipzig, 1800), 
263--305]; �� ������� ���������� ����� ����� ��������� �������������� � 
����������: \emph{�������� ������������ �������� ����� ������� �� 
��������, ������� ��������}. ���� ��� �� ����� ������� �������������� ����� 
�����, �� ��� ����������� � ������ �������� �������. ����� ������� 
������� $n\times n$ � �������� ����� � $j$-� ������ $i$-� ������, ���� 
$a_i=j$. �� ����� ��������� �������� �� ���� �������, ����� �� ������� (� 
��� �� �������) � ������ (� ��� �� ������) ���� �����. 퀏�����, ��� 5 9 1 8 2 
6 4 7 3 ��������� ����� �����:
$$
%%  picture
$$
ꎋ������� ��������� ����� ����� ��������, ��� ��� �������� ������, ��� 
$b_j$ ����� ����� ��������� � $j$-� �������. 呋� �� ������ ������������� 
��������� (������� ������ ������ � �������), �� ������� ��������� ��� 
�������� �� ��������� � �������� ������������; ������, ����� ��������� 
(����� ��������) ��������� � ����� �������. ���� ����������� ���� ���� ��� 
�������������� ����, ��� ����������� ������� �� �������� ��� 
����������������.

䋟 ������� ��������� ���������� ���������� ���������� ����� ����� 
������������ $�$ ���������, ���������� ����� $k$ ��������. ������ ��� 
����� ����� $I_n(k)$; � ����. 1 ��������� ������ ��������� �������� ���� 
�������.
%% 29


\htable{򀁋��� 1}{��������� � $k$ ����������}%
{$#$\bskip\hfill&&\hfill\bskip$#$\bskip\hfill\cr
n & I_n(0) & I_n(1) & I_n(2) & I_n(3) & I_n(4) & I_n(5) & I_n(6) & I_n(7) & I_n(8) & 
I_n(9) & I_n(10) & I_n(11)\cr
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\cr
2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\cr
3 & 1 & 2 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\cr
4 & 1 & 3 & 5 & 6 & 5 & 3 & 1 & 0 & 0 & 0 & 0 & 0\cr
5 & 1 & 4 & 9 & 15 & 20 & 22 & 20 & 15 & 9 & 4 & 1 & 0\cr
6 & 1 & 5 & 14 & 29 & 49 & 71 & 90 & 101 & 101 & 90 & 71 & 49 \cr
}

� ������������ ������� �������� $b_1$ $b_2$ \dots.$b_n$ ����, ��� 
$I_k(0)=1$, $I_n(1)=n-1$  � ��� ����������� �������� ���������:
$$
I_n\left(\left({n \atop 2}\right)-k\right)=I_n(k)\eqno (6)
$$
䀋��, ��� ��� �������� $b$ ����� �������� ���������� ���� �� �����, �� 
�������� ������, ��� ������������ �������
$$
G_n(z)=I_n(0)+I_n(1)z+I_n(2)z^2+\cdots
\eqno (7)
$$
������������� ����������� $G_n(z) = (1 +z+ \cdots +z^{n-1})G_{n-1}(z)$;
�������������, ��� ����� ��������, ������� ���
$$
(1+z+\cdots+z^{n-1})\ldots(1+z)(1)=(1-z^n)\ldots(l-z^2)(l-z)/(l-z)^n.
\eqno(8)
$$
� ������� ���� ������������ ������� ����� ����� ���������� ����. 1 � 
���������, ��� �����, ������������� ��� ����������� ������ � �������, 
������������� �����������
$$
I_n(k)=I_n(k-1)+I_{n-1}(k) \rem{��� $k<n$.}
\eqno(9)
$$
(䋟 ����� \emph{���} ����������� ������ ��� ����������� \emph{��} 
�����������.) ᎋ�� ������� ����������� (��. ���. 14) ����������, ��� �� 
����� ���� ����� ����� �������
$$
\eqalign{
I_n(2)&=\left({ n \atop 2}\right)-1, n \ge{} 2;\cr
I_n(3)&=\left({ n+1 \atop 3}\right) - \left({ n \atop 1}\right), n \ge{} 3;\cr
I_n(4)&=\left({n+2 \atop 4}\right)-\left({ n+1\atop 2}\right), n \ge{} 4;\cr
I_n(5)&=\left({n+3 \atop 5}\right)-\left({ n+2\atop3 }\right)+1, n \ge{} 5.\cr
}
$$
%% 30
�� ������� ��� $I_n(k)$ �������� ����� $1.6\sqrt k$ ���������:
$$
\eqalign{
I_n(k)=&\left({ n+k-2\atop k}\right)-\left({ n+k-3\atop k-2 }\right)+
\left({ n+k-6\atop k-5}\right)+\left({ n+k-8\atop k-7}\right)-\cdots\hfill\cr
&+(-1)^j\left(\left({ n+k-u_j-1\atop k-u_j}\right)+ \left({ n+k-u_j-j-1\atop k-u_j-j}\right) 
\right)+\cdots, \rem{$n\ge k$,}\quad\cr
}
\eqno (10)
$$
��� $u_j=(3j^2-j)/2$ --- ��� ���������� "������������ �����".

�������� $G_n(z)$ �� $n!$, ������� ������������ ������� $g_n(z)$ 
������������� ������������ ����� �������� � ��������� ������������ $�$ 
���������.  ����� ������������
$$
g_n(z)=h_1(z)h_2(z)\ldots h_n(z),\eqno (11)
$$
��� $h_k (z) = (1 + z + z^2 +\cdots + z^{k-1})/k$ --- ������������ ������� 
������������ ������������� ��������� ��������, ����������� ����� 
��������������� ��������, ������� $k$. ���
$$
\eqalignno{
\mean (g_n) &= \mean (h_1) + \mean (h_2) + \cdots + \mean (h_n) =\cr
&=0 +{1\over2}+\cdots+{n-1\over 2}={n(n-1)\over 4}; & (12)\cr 
\var (g_n)& = \var (h_1) + \var (h_2)+ \cdots + \var (h_n)=\cr
&=0 +{1\over 4}+\cdots+{n^2-1\over 12}={n(2n+5)(n-1)\over 72}&(13)\cr
}
$$
򀊈� �������, ������� ����� �������� �������� ������---����� 
${1\over 4}n^2$; ����������� ���������� ����� ������ ������---����� 
${1\over6}n^{3/2}$.

� �������� ����������� ���������� �������� �������� ���������� 
���� ������������� ��������, ������������� 
�. �. 쀊-쀃��� [{\sl Amer. J. Math.,\/} {\bf 35} (1913), 281--322]. 
������ \dfn{������} ������������ $a_1$ $a_2$ \dots $a_n$ ��� ����� 
���� $j$, �����, ��� $�_j>a_{j+1}$, $1 \le < n$. 퀏�����, ������ 
������������ 5 9 1 8 2 6 4 7 3 ����� $2+4+6+8=20$. 荄��� �������� ������ 
� ������ ��������. 呋� ��������� ������ ���� 24 ������������ ��������� 
$\{1, 2, 3, 4\}$, � ������
%% 31
{
\def|{\,\vrule}
\offinterlineskip
\ctable{
\strut\hfill$#$\bskip\hfill&&\hfill$#$\bskip\hfill\cr
\multispan{4}��������� &   荄��� & 荂����� & \multispan{4}���������&    荄��� &荂����� \cr
1 & 2 & 3 & 4 &    0  &    0   & 3| & 1 & 2 & 4 &  1  & 2 \cr
1 & 2 & 4|& 3 &    3  &    1   & 3| & 1 & 4|& 2 &  4  & 3 \cr
1 & 3|& 2 & 4 &    2  &    1   & 3| & 2|& 1 & 4 &  3  & 3 \cr
1 & 3 & 4|& 2 &    3  &    2   & 3| & 2 & 4|& 1 &  4  & 4 \cr
1 & 4|& 2 & 3 &    2  &    2   & 3  & 4|& 1 & 2 &  2  & 4 \cr
1 & 4|& 3|& 2 &    5  &    3   & 3  & 4|& 2|& 1 &  5  & 5 \cr
2|& 1 & � & 4 &    1  &    1   & 4| & 1 & 2 & 3 &  1  & 3 \cr
2|& 1 & 4|& 3 &    4  &    2   & 4| & 1 & 3|& 2 &  4  & 4 \cr
2 & 3|& 1 & 4 &    2  &    2   & 4| & 2|& 1 & 3 &  3  & 4 \cr
2 & 3 & 4|& 1 &    3  &    3   & 4| & 2 & 3|& 1 &  4  & 5 \cr
2 & 4|& 1 & 3 &    2  &    8   & 4| & 3|& 1 & 2 &  3  & 5 \cr
2 & 4|& 3|& 1 &    5  &    4   & 4| & 3|& 2|& 1 &  6  & 6 \cr
}
}
�� �����, ��� \emph{����� ������������, ������� ������ ������ $k$, 
����� ����� ������������, ������� $k$ ��������.}

� ������ ������ ���� ���� ����� ���������� ����� ���������, ������ 
����� ��������� ����������� �� �������� �������� ���� �� �� 
�����������, � �� ����� �������� �������� ������� ��� ��������������. 
쀊-쀃�� ����� ��������� ���������� ��������� ��������������: ����� 
$J(�_1 �_2 \ldots a_n)$---������ ������������ $a_1$ $a_2$ \dots $a_n$, � 
��������������� ������������ ������� ����
$$
H_n(z)=\sum z^{J(a_1 a_2 \ldots a_n)}, \eqno (14)
$$
��� ����� ������� �� ���� ������������� ��������� $\{1, 2, \ldots., �\}$. 
� ������ �� ��������, ��� $H_n(z)=G_n(z)$. 䋟 ����� ��������� 
������� ����������� ������������ ����� $n$-���� 
$(q_1, q_2, \ldots, q_n)$ ��������������� ����� �����, � ����� �������, � 
�������������� ������ $n$-��
$$
((a_1, a_2, \ldots, a_n), (p_1, p_2, \ldots, p_n)),
$$
� ������ �������; ����� $�_1$ $�_2$ \dots\ $a_n$---������������ 
��������� $\{1, 2, \ldots, �\}$ � $p_1\ge p_2\ge \ldots \ge p_n \ge 0$.. ��� 
������������ ����� ������������� �������
$$
q_1+q_2+\cdots+q_n=J(a_1 a_2 \ldots a_n)+(p_1+p_2+\cdots+p_n).
\eqno (15)
$$
��������� ������� $\sum z^{q_1+q_2+\cdots+q_n}$, ��� ����� ������� 
�� ���� $n$-��� ��������������� ����� ����� $(q_1,  q_2, \ldots, q_n)$, 
����� $Q_n (z) =1/(1-z)^z$; � ������������ ������� $\sum 
z^{p_1+p_2+\cdots+p_n}$, ��� ����� ������� �� ���� $n$-��� ����� ����� 
$(�_1, �_2, \ldots p_n)$, �����, ��� $p_1\ge p_2\ge \ldots \ge p_n \ge 0$, �����, 
��� �������� � ���.~15,
$$
P_n(z)=1/(1-z)(1-z^2)\ldots(1-z^n).
\eqno(16)
$$
%% 32
񓙅��������� ������� ������������ ������������, ������� ������������� 
������� (15) � ������� �� ���������� ����������, ���������� ��������� 
$Q_n(z)=H_n(z) P_n(z)$, �.�.
$$
H_n(z)=Q_n(z)/P_n(z)=G_n(z).
$$

򐅁����� ������������ ������������ � ������� ��������� 
"����������". 퀗�� � ������� ������, ��� $k=1$, $2$, \dots, $n$ (� ����� 
�������) ��������� � ���� ������ ����� $q_k$ ��������� �������: ����� 
����� $k-1$ ����� � ������ ���������� ��������
$p_1$, $p_2$, \dots, $p_{k-1}$, ��� $p_1\ge p_2\ge \ldots \ge p_{k-1}$, � 
���������� ������������ $a_1$ $a_2$ \dots $a_n$ ��������� 
$\{n, n-1, \ldots, n-k+2\}$. 
�� $j$---������������ ����� �����, �����, ��� 
$p_j>q_k\ge p_{j+1}$; ���� $q_k\ge p_1$, �� �������� $j=0$, 
� ���� $p_{k-1}>q_k$, �� 
�������� $j=k-1$. ⑒���� ������ $q_k$  � ������ ����� $p_j$ � $p_{j+1}$, 
� ����� ����� $(n-k+1)$---� ������������ ����� $a_j$, � $a_{j+1}$. 
����� ��� ��� ���� $k$, ������� ������������ $a_1$ $a_2$ \dots  $a_n$ 
��������� $\{1,2, \ldots, n\}$ � $n$-�� ����� 
$(p_1, p_2, \ldots, p_n)$, �����, ��� $p_1\ge p_2 \ge \ldots \ge p_n\ge 0$ � 
$$
p_j > p_{j+1}, \rem{���� $a_j>a_{j+1}$.}
$$
퀊����, ��� $1 \le j < n$ ������ ������� �� ���� ����� $p_1$, \dots, $p_j$ 
��� ���� $j$, �����, ��� $a_j>a_{j+1}$. ������� ���� 
$((�_1, �_2, \ldots, �_n), (p_1, p_2, \ldots, p_n))$ ������������� ������� (15).

��, ��������, $n=6$ � $(q_1, \ldots, q_6)=(3, 1, 4, 0, 0, 1).$ 
������� ���������� ��������� �������:
{
\offinterlineskip
\ctable{
\strut\hfil$#$\bskip\hfil&&\hfil$#$\bskip\hfil\cr
k & \multispan{6} $p_1\ldots p_k$\hfill & \multispan{5} $a_1\ldots a_k$\hfill \cr
1 & 3 &   &   &   &   &   & 6 \cr
2 & 3 & 1 &   &   &   &   & 6 & 5 \cr
3 & 4 & 3 & 1 &   &   &   & 4 & 6 & 5 \cr
4 & 4 & 3 & 1 & 0 &   &   & 4 & 6 & 5 & 3 \cr
5 & 4 & 3 & 1 & 0 & 0 &   & 4 & 6 & 5 & 2 & 3 \cr
6 & 4 & 3 & 1 & 1 & 0 & 0 & 4 & 6 & 1 & 5 & 2 & 3 \cr
}
}
�� �������������� ������������� �������� 
$(p_1, \ldots, p_6)=(2, 1, 0, 0, 0,0)$.

텒����� ���������, ��� ���� ������� �������; ����� �������, 
��������� ������������ ����������� � ������� 쀊-쀃��� ��������. 
����������� ������� ����������� ������������ ���������� ��� � �.~5.1.4.
\excercises
\ex[10] ꀊ��� ������� �������� ��� ������������ 2 7 1 8 4 5 9 3 �? ꀊ�� ������������ 
������������� ������� ��������  5  0  1  2  1  2 0  0?

\ex[M15] �������� ������ 莑���, ���������������� � ���. 1.3.2--22, �������� 
������������ ��������� $\{1, 2, \ldots n\}$; ������� ��� ������������ ��� ������� 
$(n=8,m=4)$---������������ 5 4 6 1 3 8 7 2. 񎎒����������� ���� ������������ ������� 
��������---3 6 3 1 0 0 1 0. 퀉���� ������� ������������
%% 33
����������� ��� ��������� $b_1$ $b_2$ \dots $b_n$ ������� 
�������� � ����� ������ 莑��� ��� $n$ �������, ���� ������ ������� $m$-�� 
��������.

\ex[18] �� ������������ $a_1$ $a_2$ \dots $a_n$ ������������� ������� 
�������� $b_1$ $b_2$ \dots $b_n$; ����� ������������ $\bar a_1$ $\bar a_2$ 
\dots $\bar a_n$ ������������� ������� ��������
$$
(n-1-b_1) (n-2-b_2) \ldots  (0-b_n)?
$$

\rex[20] ������� ��������, ������ ��� ���������� �� ���, ������� �� 
������ ������� ��������  $b_1$ $b_2$ \dots $b_n$, ��������������� �������� 
(3), ������ �� ��������������� ������������  $a_1$ $a_2$ \dots $a_n$. 
[{\sl 󊀇����:\/} ��������� ������ ������ �� ��������� �������.]

\ex[35] 䋟 ���������� �� �������� ��� �������� �� ���.~4 ������� �������, 
�������������� ����������������� $n^2$; ����� �� ������� ��������, ����� 
������ �������� ���� �� ����������� ������ $n^2$?

\rex[26] ������� �������� ���������� ������� �������� $b_1$ $b_2$ \dots 
$b_n$, ��������������� ������ ������������ $a_1$ $a_2$ \dots $a_n$ 
��������� $\{1, 2, \ldots, �\}$,, ����� ������ �������� �� �������� ��� 
���� �� ������� $n\log n$.

\ex[20] ��� ������� $b_1$ $b_2$ \dots $b_n$, ������������ � ���� ������,
 �����  ���������� ��������� ������ ���� ������ ��������, ��������������� 
������ ������������ $a_1$ $a_2$ \dots $a_n$ ��������� 
$\{ 1, 2, \ldots, n\}$. � ���� ���������� �� ���������� ��� ������ ���� ������ 
��������, ������� ��������� � �����������.

�� $c_j$---����� ��������, \emph{������} ���������� ������� ����� $j$, 
�.~�. ����� ���������, ������� $j$ � ������������� \emph{������} $j$. 
[��������� (1) ������������� ������� $0$ $0$ $0$ $1$ $4$ $2$ $1$ $5$ 
$7$; ����, ���$ 0\le c_j<j$.] �� $B_j=b_{a_j}$ �~$C_j=c_{a_j}$.

�����, ��� ��� $1 \le j \le n$ ����������� ����������� $0\le B_j<j$ � 
$0\le C_j\le n-j$; �������� �����, ��� ������������ $a_1$ $a_2$ \dots 
$a_n$ ����� ���������� ����������, ���� ������ ��� ������� $c_1$ $c_2$ 
\dots $c_n$, ��� $B_1$ $B_2$ \dots $B_n$, ��� $C_1$ $C_2$ \dots $C_n$.

\ex[�24] 񎕐���� ����������� ���.~7; ����� $a'_1$ $a'_2$ \dots 
$a'_n$---������������, �������� �  $a_1$ $a_2$ \dots $a_n$ � ����� 
��������������� �� ������� ��������--- $b'_1$ $b'_2$ \dots $b'_n$, $c'_1$ 
$c'_2$ \dots $c'_n$, $B'_1$ $B'_2$ \dots $B'_n$  � $C'_1$ $C'_2$ \dots 
$C'_n$. 퀉���� ��� ����� ������ ���������� ����������� ����� $a_j$, $b_j$,
$c_j$, $B_j$, $C_j$, $a'_j$, $b'_j$, $c'_j$, $B'_j$, $C'_j$.

\rex[�21] 䎊�����, ��� � ������������ ���.~7 ������������ $a_1$ $a_2$ 
\dots $a_n$ ������� ����� ���� ����� � ������ �����, ����� $b_j=C_j$ ��� 
$1\le j\le n$.

\ex[��20] ����������� ���.~1 ��� ������������ � ���������� ������������. 
���� ����� ������� ���������� �������� (���������� ����� ��������� 1234 � 
4321), ���� ��� ����� ����� ��������� �����?

\ex[�25] (�) �� $\pi=a_1\ a_2\ldots a_n$---������������ ��������� $\{1, 2,
 \ldots, n\}$, $E(x)=\{(a_i, a_j)\vert i<j, a_i>a_j\}$---��������� �� 
��������, a
$$
\overline{E}(\pi)=\{(a_i, a_j)\vert i>j, a_i>a_j\}
$$
---��������� �� '"����������". 䎊�����, ��� $E(\pi)$ �~$\overline{E}(\pi)$ 
�����������. [썎������ $S$ ������������� ��� ���������� 
\dfn{������������}, ���� ��� ����� $(a, b)$ �~$(b,c)$, ������������� $S$, 
���� $(a, c)$ ����� ����������� $S$.] (b) ����, ����� $E$---����� 
������������ ������������ ��������� 
$T=\{(x, y)\vert 1\le  y < x\le n\}$, ���������� �������� $T\backslash E$ 
�����������. 䎊�����, ��� ���������� ������������ $\pi$, �����, ��� $E(\pi)=E$.

\ex[�28] 葏������ ����������� ����������� ����������, ��������, ��� ���� 
$\pi_1$ � $\pi_2$---������������, � $E$---����������� ������������ ���������,
 ���������� $E(\pi_1)\cup E(\pi_2)$, �� $\overline{E}$---���� ������������ 
���������. [񋅄���������, ���� �� ����� ��������, ��� $\pi_1$ ��������� 
"���" $\pi_2$, ����� 
$E(\pi_1)\subseteq E(\pi_2)$, �� ���������� ������� ������������; 
���������� ������������ "����� ������" ������������, ����������� "���" 
����� ������� ��������������. 䈀������ ������� ���  $n=4$ ������������ �� 
���. 1.]
%% 34

\bye
