\input style
\noindent
%% 41
��� ����� ����� ����������� � ���������� ������������ (12), ���������� $a$,
 ����� ��� $(d\ d\ b\ c\ d\ b\ b\ c\ a)\T \alpha'$, ��� $\alpha'$--- 
��������� ������������. (ㄎ��� ���������� $a$ �� � ������, � � 
����� �����; ��� ���������, ��������� ����� $a$ ������ ����.) ����������,
 ���� �� �� ������������, ��� $\alpha$ �������� ����� $b$, �� ������ ��, 
��� $\alpha=(c\ d\ d\ b) \T \alpha''$, ��� $\alpha''$---��������� ������������.

� ����� ������ ��� ����������� ����������, ��� \emph{���� 
���� �����-������ ���������� $\alpha\T\beta=\pi$, ��� $\alpha$ �������� 
������ ����� $y$, �� ���������� ������������ ���� ����
$$
(x_1\ \ldots\ x_n\ y), \qquad n\ge 0, x_1, \ldots, x_n\ne y,
\eqno(14)
$$
������� �������� ����� ������������ � ���������� ������������ $\alpha$.} 
 �� ���� ����� ��������, ���� $\pi$ � $y$; ��� ����� �������� ����� 
����������� � ���������� ������������ $\pi$, ���������� ����� $y$. ���� �� 
��������� ����� ���������� ����

\proclaim ⅎ���� A. ����� �������� ��������������� $M$ ������� 
����������� ���������� "$<$". ������ ������������ $\pi$ ��������������� 
$M$ ����� ������������ ������������� � ���� ��������������� ������������
$$
\pi=(x_{11}\ldots x_{1n_1}y_1)\T(x_{21}\ldots x_{2n_2}y_2)\T \ldots
(x_{t1}\ldots x_{tn_t}y_t), \quad t\ge 0,
\eqno(15)
$$
��������������� ��������� ���� ��������:
$$
\displaylines{
y_1\le y_2 \le \ldots \le y_t;\cr
\hfill y_i<x_{ij}\hbox{ ��� $1\le j\le n_i$, $1\le i\le t$.}\hfill\llap{\rm(16)}\cr
}
$$
(����� �������, � ������ ����� ��������� ������� ������ ������ �������, � 
��������� �������� ������ �������� ����������� ������������������.)

\proof ��� $\pi=\varepsilon$ ������� ��������� ����������, ������� $t=0$.
 � ��������� ������ ����� $y_1$---����������� ������� $\pi$;
��������� $(x_{11}\ldots x_{1n_1}y_1)$---����� �������� ����� 
����������� ���������� $\pi$, ���������� $y_1$, ��� � ������������� 
�������. ⅏��� $\pi=(x_{11}\ldots x_{1n_1} y_1)\T\rho$, ��� 
$\rho$---��������� ������������;
�������� �������� �� ����� ������������, ����� ��������
$$
\rho=(x_{21}\ldots x_{2n_2}y_2)\T\ldots\T(x_{t1}\ldots x_{tn_t}y_t), t\ge1,
$$
��� ������� (16) ���������. ⅌ ����� �������� ������������� ������ ����������.

������� �������������� ���������� (15), ���������������� �������� (16). 
�, ��� $t=0$ ����� � ������ �����, ����� $\pi$--- ������ ������������ 
$\varepsilon$. ��� $t>0$ �� (16) �������, ��� $y_1$---����������� ������� 
������������ $\pi$ � ��� $(x_{11}\ldots x_{1n_1}y_1$---����� ��������
%%42
����� �����������, ���������� $y_1$. ������� 
$(x_{11}\ldots x_{1n_1} y_1)$
������������ ����������; �������������� �������������� 
������ ������������� ����������� ����������� �������� � ������� ���������� 
(7). 
\proofend

��������, "������������" ���������� ������������ (12), ��������������� 
������ ��������, ������:
$$
(d\ d\ b\ c\ d\ b\ b\ c\ a)\T(b\ a)\T(c\ d\ b)\T(d),
\eqno(17)
$$
���� $a<b<c<d$.

����� ��������, ��� �� ����� ���� � ���� ����������� ����� ��������� 
������ � ����� �������� $\T$, � ��� �� �������� � ���������������! 
������ ���� ������������� ���������� ����������� �� ���������� ���������.
  �� �������, ���� ���������� ��������� � �������� �������������
$$
\pi'=d\ d\ b\ c\ d\ b\ b\ c\ a\ b\ a\ c\ d\ b\ d
$$
������������
$$
\pi=d\ b\ c\ b\ c\ a\ c\ d\ a\ d\ d\ b\ b\ b\ d.
$$
���� � ����������� ������������� $\pi$ ���������� ������� ���� 
$y\atop x$, ��� $x<y$, �� � ��������� � $\pi$ ������������ ������������ 
��������������� ���� �������� ��������� $\ldots y\ x\ldots$.  , � 
����� ������� $\pi$ �������� ��� ������� ���� $d\atop b$, � � $\pi'$ ������
����������� ���� $d\ b$. ������ �� ����� ���������� �������� �������������

\proclaim ⅎ���� B. {����� $M$---���������������. ᓙ������� ������� 
����������� ������������ ����� �������������� $M$, �����, ��� ���� $\pi$ 
������������� $\pi'$, �� ����������� ��������� �������:
\medskip
\item{a)} ������� ����� ������� $\pi'$ ����� �������� ������ 
��������~$\pi$;
\item{b)} ��� ���� ��� ����������� � ������������ ��������� $(x, y)$,
\medskip
\noindent �����, ��� $x<y$, ����� ��������� ������� $y\atop x$ � 
����������� ������������� ������������ $\pi$ ����� ����� �������, ����� � 
������������ $\pi'$ ������� $x$ ������� ��������������� �� $y$.}

���� $M$---���������, �� ���, �� ��������, "������������� ������������", 
������������� � ����� �.~1.3.3, � ��������������� �����������. ����� 
����� ��������� ������� B ������� ��� �������� ����� ������������ 
����������� �����, ��������� ����� ����� ������ ������ � �������������, 
����������� �� ����������� �������������, ��� ������������� ������ � 
������������� �� ���� �������� ���������.
%% 43

�.~�.~���-����� ���������� ������ ����� ���� � ����� ���������� ����� 
Combinatory Analysis (Cambridge Univ. Press, 1915), ���~1, ���. 168--186. 
�� ��� �������������� �������������� �������~B � ������� ������, ����� M 
�������� �������� ���� ���� ��������� �����, ������ $a$ �~$b$, ��� 
���������� ��� ����� ������, �� ��������, ��������� � ����������� �����, 
�� ������������ � ���������� ���� ����. ��� ������ ���� ��������� 
��������� $a$, $b$, $c$ ���-����� ��� ������� ���������������� 
�������������� �������~B; ����� ������ ������� ������� 䎀�� � 1965~�.

� �������� �������������� ������� ���������� �������~B ������ ����� 
������� ���� $a$, $b$, $c$, ���������� �����
$$
\eqalign{
A&\hbox{ ��������� ����� $a$;}\cr
B&\hbox{ ��������� ����� $b$;}\cr
C&\hbox{ ��������� ����� $c$;}\cr
k&\hbox{ ��������� ���� ������� ����� ���� $c\ a$;}\cr
l&\hbox{ ��������� ���� ������� ����� ���� $c\ b$;}\cr
m&\hbox{ ��������� ���� ������� ����� ���� $b\ a$;}\cr
}
\eqno(18)
$$
�� ������� �������, ��� ��� �� �� �����, ��� ����� ����� ����������� 
�������� ����
{
\newbox\Abox\newbox\Bbox\newbox\Cbox
\setbox\Abox\hbox{$\displaystyle
\underbrace{
\hbox to 0pt{\hss$\displaystyle\Bigl($}
  \overbrace{
    \matrix{
      a & \ldots & a \cr
      \]& \ldots & \]\cr
    }
  }^A 
}_{A-k-m\hbox{ ���� $a$}}
$}
\setbox\Bbox\hbox{$\displaystyle
\underbrace{
  \overbrace{
    \matrix{
      b & \ldots & b\cr
     \] & \ldots &\]\cr
    }
  }^B
}_{m\hbox{ ���� $a$}}
$}
\setbox\Cbox\hbox{$\displaystyle
\underbrace{
\overbrace{
 \matrix{
   c & \ldots & c \cr
  \] & \ldots &\] \cr
 }
}^C
\hbox to 0pt{$\displaystyle\Bigr)\hss$}
}_{k\hbox{ ���� $a$}}
$}
$$
\underbrace{
 \underbrace{\copy\Abox \copy\Bbox}_{\hbox{$B-l$ ���� $b$}}\;\;
 \underbrace{\copy\Cbox}_{\hbox{$l$ ���� $b$}}
}_{\hbox{$C$ ���� $c$}}
\eqno (19)
$$
}
����� $a$ ����� ����������� �� ������ ������
$$
\perm{A}{A-k-m}\perm{B}{m}\perm{C}{k}
\rem{���������;}
$$
����� ����� ����� $b$ ����� ���������� � ���������� ��������
$$
\perm{B+k}{B-l}\perm{C-k}{l}\rem{���������.}
$$
��������� ��������� ����� ����� ��������� ������� $c$; �������������, 
������� ����� �����
$$
\perm{A}{A-k-m}\perm{B}{m}\perm{C}{k}\perm{B+k}{B-l}\perm{C-k}{l}.
\eqno(20)
$$

%% 44

�������� � ������� � ���������� ���� ���������� ������ ������������. 
ᓙ������� �� ����� ������, ��� "�������" ������������, ������� �� 
����������� �� ���������, �������� �� ��� ����� � $\varepsilon$? 
����������, �������������� ������� A, ���������� �������� � ������ � ���, 
��� \emph{������������ ����� ������� ����� � ������ �����, ����� ��� ���� 
���� ��� ������������� ���������,} ��� ���, ���� ������������ �������� 
����� ������, ���� ����������� ����������, ��� �� ���������� ����� 
����������, ����� $\varepsilon$ � ������ �����. ���� �� ������������ 
�������� ������������� ������� $y$, �� ������ ����� �������� 
������������� ���� � �������� ������ �����������, � ������� ������� 
� ����������� ����� �������.

���� ������������ �� �������, �� �� ����� ��������� �� ��� ������� � 
������� �����, ���� �� ����� �������� ������������ ������� ������������. 
����� ���� ��������, ��� ����� ���������� ����������� � ��������� �� 
������� ������ ������������� ������������.

\proclaim ⅎ���� C. ������ ������������ ��������������� ����� �������� 
� ���� ������������
$$
\sigma_1\T\sigma_2\T\ldots\T\sigma_t, \quad t\ge 0,
\eqno(21)
$$
��� $\sigma_j$---�����, �� ���������� ������������� ���������. 
풎 ������������� ����������� � ��� ������, ��� ����� ��� 
����� ������������� ����� � ��� �� ������������ ����� ������������� ���� 
� ������, ��������������� ����� ������� �������� ���������������� �����.

⅐��� "���������������� �����" ��������� � ������, �� ������� ����� 
���������. � �������� ������� ����� ���������, ��� ������������
$$
\pmatrix{
a & a & b & b & c & c & d\cr
b & a & a & c & d & b & c\cr
}
$$ 
����������� �� ��������� ����� ����� ���������:
$$
\eqalign{
(a\ b)\T(a)\T(c\ d)\T(b\ c) 
&=  (a\ b)\T(c\ d)\T(a)\T(b\ c)=\cr
&=(a\ b)\T(c\ d)\T(b\ c)\T(a)=\cr
&=(c\ d)\T(a\ b)\T(a)\T(b\ c)=\cr
&=(c\ d)\T(a\ b)\T(b\ c)\T(a).\cr
}
\eqno(22)
$$

\proof ����� ����������, ��� ����������� ���������������� � ������� 
�������� ��������������. �������� �������� �� ����� ������������; ����� 
���������� ��������, ��� ���� $\rho$ �~$\sigma$---��� ��������� �����, �� 
���������� ������������� ���������,
%%45
�
$$
\rho\T\alpha=\sigma\T\beta,
$$
�� $\rho$ �~$\sigma$---���������������� �����,  �
$$
\alpha=\sigma\T\theta,\quad \beta=\rho\T\theta,
$$
��� $\theta$---��������� ������������.

����� $y$---������������ ������� ����� $\rho$, ����� � ������ ������ 
����������� � ���������� $\sigma\T\beta$, ����������� ���� ������� $y$, 
����� ����� ����������� $\rho$. ������, ���� $\rho$ �~$\sigma$ ����� ����� 
�������, �� ���� $\sigma$ ������ ���� ������ $\rho$; �������������,
 $\sigma=\rho$ (��� ��� ��� �������), ��� ������������ ������ 
�������������. ዅ����������, ����, ���������� $y$ � �� ������� ����� 
��������� � $\sigma$, ������ ���� ����� ������������ � ���������� $\beta$. 
�������� ������ ���������� (7), �������� ��������������.
\proofend

� �������� ����������� ������� C ���������� ������������ ��������������� 
$M=\{A\cdot a, B\cdot b, C\cdot c\}$, ���������� �� $A$ ���������~$a$, 
$B$ ���������~$b$ �~$C$ ���������~$c$. ����� $N(A, B, C, m)$--- ����� 
������������ ���������������~$M$, ����������� ������������� ������� 
\emph{�� ��������} �������� ���� $a\atop a$, $b\atop b$, $c\atop c$  � ��������
����� $m$ �������� ����~$a\atop b$. ������ �������, ��� ������� 
����� $A-m$~�������� ����~$a\atop c$, $B-m$~�������� ����~$c\atop b$, 
$C-B+m$ �������� ����~$c\atop a$, $C-A+m$~�������� ����$b\atop c$   
�~$A+B-C-m$ �������� ����~$b\atop a$ ; �������������,
$$
N(A, B, C, m)=\perm{A}{m}\perm{B}{C-A+m}\perm{C}{B-m}.
\eqno(23)
$$

ⅎ����~C ���������� ������ ������ ��� �������� ���� ������������: ���� 
����� ������� $a\atop a$, $b\atop b$, $c\atop c$ ���������, �� � 
���������� ������������ ����������� �������� ����� ������� ���������:
$$
(a\ b), (a\ c), (b\ c), (a\ b\ c), (a\ c\ b).
\eqno(24)
$$ 
������ ���� ���� ������ ����� ���� �� ���� ����� �����, ������, ���������� 
�����������. ���� ���� $(a\ b\ c)$ ����������� � ���������� $k$ ���, �� �� 
������ ����������� ������������� �������, ��� $(a\ b)$ ����������� 
$m-k$~���, $(b\ c)$ ����������� $C-A+m-k$~���, $(a\ c)$ ����������� 
$C-B+m-k$~��� �~$(a\ c\ b)$ ����������� $A+B-C-2m+k$~���. ዅ����������, 
$N (A, B, C, m)$
%% 46
\bye
