������������������� ������ � ������� ������� � ������
�.~�.~���������
� ������ ������������, ��� $\varepsilon_k(n)$ -- ���������� $n$-���������� �������������� ������������� (�. �. ����������� 2) �������� � ������������ ��������� ����� $k$ �� ������, ��� $\min\{{k^{2n}\over (k!)^2}, {(n-k+1)^{2n}\over ((n-k)!)^2}\}$. ����� ������������, ��� $\xi_k(n)$ -- ���������� ������������ ����� �� 1 �� $n$ � ������������ ��������� ���������������������� ����� �� ������ $k$ -- �� ������, ��� ${k^{2n}\over ((k-1)!)^2}.$ ���������� ����� ������� � ������ ����� ������ �������� ��������, ������ �������� ����, �������������� ���������� ��������� � �������������� ��������� �� ������ ����� \cite{Sch61}, \cite{Kn70}. ������� ���������� � ������ \cite{Ges90} ������������ ������� ��� ���������� ������������ ���� ����� $n$ ��� $l$-��������� ��������� $(n \leqslant l)$, � ������ �� ������� �� ������� ������������������ �� $(k+1)$ ����� � ������� ������������������� ��������.
1307.1886.tex
%��� Windows ���������

\documentclass[a4paper,12pt]{article}

%\usepackage{russlh}
%\usepackage{russ}
\usepackage{amssymb}
\usepackage{tipa}
%\usepackage{txfonts}
\usepackage{bbm}

\usepackage[T2A]{fontenc}
\usepackage[cp1251]{inputenc}
\usepackage{amsmath}

\usepackage[dvips]{graphicx}
\usepackage[
russian,
%english
 %replace english and russian for the change of data language
]{babel}

\usepackage{wasysym}

% ��� ��� ���������
%\documentstyle[12pt,amstex,amssymb,russcorr]{article}

%\documentstyle{twoside}
%\usepackage{russcorr,amssymb,amsmath,righttag,amstex,twoside,
%emlines2,disser}%,amsthm,thms2}
%\def\charact{\mathop{\hbox{char}}\nolimits}
%\def\goth{\mathfrak}
%
%\def\LHD{\blacktriangleleft}
%\def\RHD{\blacktriangleright}
%\def\textchi{X}
%\def\AC{\sim}

% ����������� ������ ��� ����� ������.

\def\id{\operatorname{id}}
\def \GK{\operatorname{GK}}
\def\Pid{\operatorname{Pid}}
\def\Var{\operatorname{Var}}
\def\Ht{\operatorname{Ht}}
\def\PI{{\rm PI}}



\topmargin -19mm \oddsidemargin 0.5cm \textwidth 16cm \textheight
24.3cm

%\newtheorem{theorem}{�������}[section]
%\newtheorem{corollary}[theorem]{Corollary}
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{notation}[theorem]{Notation}
%\newtheorem{remark}[theorem]{Remark}
%\newtheorem{construction}[theorem]{Construction}
%\newtheorem{algorithm}[theorem]{Algorithm}
%\newtheorem{ques}[theorem]{Question}
%\newtheorem{definitionhead}[theorem]{Definition}
%\newtheorem{example}[theorem]{Example}

%\newtheorem{proof}{Proof}\def\theproof{}

\newtheorem{theorem}{�������}[section]
\newtheorem{corollary}[theorem]{���������}
\newtheorem{lemma}[theorem]{�����}
\newtheorem{proposition}[theorem]{�����������}
\newtheorem{notation}[theorem]{�����������}
\newtheorem{remark}[theorem]{���������}
\newtheorem{construction}[theorem]{�����������}
\newtheorem{algorithm}[theorem]{��������}
\newtheorem{ques}[theorem]{������}
\newtheorem{problem}[theorem]{��������}
\newtheorem{example}[theorem]{������}
\newtheorem{definitionhead}[theorem]{�����������}
\newenvironment{definition}{\begin{definitionhead}%
\sl}{\end{definitionhead}}
\def\mytheoremstyle{\it}
\newcommand\Proof{\noindent{\bf ��������������. }}
\newtheorem{proof}{��������������.}\def\theproof{}

\hoffset=-1.5cm

\begin{document}



%\title{������������������� ������  � ������� ������� � ������}

\title{
%\ \hbox to \textwidth{\normalsize      % Dirty trick to shift
%16R+05E\hfill} % ��� to the left
\ \hbox to \textwidth{\normalsize
��� 512.54+512.57+512.562+519.1\hfill}\\[1ex]
������ �� ���������� �������������� ������������� ��������\footnote{������ ��������� ��� ��������� ���������� ��������� ����� ��������}}
\author{
�.~�.~���������}
%Mikhail Kharitonov}

\maketitle



\begin{abstract}
� ������ ������������, ��� $\varepsilon_k(n)$ -- ���������� $n$-���������� �������������� ������������� (�. �. ����������� 2) �������� � ������������ ��������� ����� $k$ �� ������, ��� $\min\{{k^{2n}\over (k!)^2}, {(n-k+1)^{2n}\over ((n-k)!)^2}\}$. ����� ������������, ��� $\xi_k(n)$ -- ���������� ������������ ����� �� 1 �� $n$ � ������������ ���������  ���������������������� ����� �� ������ $k$ -- �� ������, ��� ${k^{2n}\over ((k-1)!)^2}.$ ���������� ����� ������� � ������ ����� ������ �������� ��������, ������ �������� ����, �������������� ���������� ��������� � ��������������
��������� �� ������ ����� \cite{Sch61}, \cite{Kn70}. ������� ���������� � ������ \cite{Ges90} ������������ ������� ��� ���������� ������������ ���� ����� $n$ ��� $l$-��������� ��������� $(n \leqslant l)$, � ������ �� ������� �� ������� ������������������ �� $(k+1)$ ����� �
������� ������������������� ��������.
\end{abstract}



%{\small}
%\medskip

{\bf Keywords:} ������������� ����, $k$-�������������, ������� ��������, ������������ �����, ������������ ���������, ��������� ����.

\section{�������� � �������� �������
}


� ������ ����������� ���������� �������������� ������������� ��������.

\begin{definition}
�������� ������������� ��������� $M$ ���������� {\em �������������� �������������,} ���� ������� �� ��� ���� ����������� ���� �������� ��������.
\end{definition}


���������� ������ ��������� ������������ $\pi$ ��������� $1, 2,\dots , n$ (����� ������, $\pi\in S_n$). ��������� ������� $k$-�������������.

\begin{definition}
����� ��� ������������ $\pi\in S_n$ ������� ������������������ ����������� ����� $1\leqslant i_1\leqslant i_2\leqslant\dots\leqslant i_k$ �����, ��� $\pi(i_1)\geqslant\pi(i_2)\geqslant\dots\geqslant\pi(i_k).$ ����� ������������ $\pi(1)\pi(2)\dots\pi(n)$ ���������� $k$-�����������.
\end{definition}

\begin{example}
���������� �� 3-����������� ������������ � ������ $S_n$ ���� $n$-� ����� �������� � ����� ${(2n)!\over n!(n+1)!}$.
\end{example}

\begin{proposition}
���� ����� �������� $k$-�����������, �� ��� ������ $m<k$ ��� ����� �������� $m$-�����������.
\end{proposition}

����� ��� ����������� ����������� ��������� ����.

\begin{definition}
{\em (�����������) ���������� ���� ������� $n$} ���������� �������, � ������� ������� �������� $n$ ��������� ����������� �����, ������ ����� ����� � ������ ������ � ������ ������� ����������, ����� ������� ��� ������ ����� � ���� �������, ������� ���������� � � ������ ������, � � ������ �������.
\end{definition}

\begin{definition}
��������� ���� ���������� {\em ���������� �����} $p = (p_1, p_2,\dots , p_m),$ ���� � �� $m$ ����� � $i$-� ������ ����� ����� $p_i.$
\end{definition}

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

����������� ��� ������ ��������� ���� ����� $p$ ������� �� 1 �� $n$. ����� $h_k$ -- ���������� ������ ��������� ����, �������������
\begin{itemize}
    \item ���� � ����� ������, ���� � ����� ������� � ������� � ������� $k$,
    \item ����������� �� ����� ��� �� ���� ������ � ������� $k$.
\end{itemize}
����� ����� �������� ���� ����� $p$ � ������ ��� ����������� ���������������� ������������� ������������� ������ $S_n$, ����������� �� ``������� ������'' ${n!\over\prod\limits_{k=1}^n h_k}$.

� ������ \cite{Sch61} ��������� ������� ����� �������������� $\pi$ ����� $1, 2,\dots , n$ � ����������� ���� �� ������� ������ �������� ���� $(P, Q)$. ��� ������� � � ��������� ����� ��������� � ����� \ref{sec:main}.

{\it � ����� ������ �� ���������� ��������� ����������:}

\begin{theorem}\label{th:main}
$\xi_k(n)$ -- ���������� �� $(k+1)$-����������� ������������ $\pi\in S_n$ -- �� ������, ��� ${k^{2n}\over ((k-1)!)^2}$.
\end{theorem}

\begin{theorem}\label{th:main2}
$\varepsilon_k(n)$ -- ���������� $n$-���������� �������������� ������������� �������� � ������������ ��������� ����� $k$ -- �� ������, ��� $\min\{{k^{2n}\over (k!)^2}, {(n-k+1)^{2n}\over ((n-k)!)^2}\}$.
\end{theorem}

\begin{corollary}\label{cor:main}
����� $\digamma$ �������� ���������� ���� �������� �� $l$ ���� � �������� �� ��� ������������������ ��������. ������ {\em ������������} �����, ��� ����� �������� ��������.  ������ ����� {\em $k$-�����������,} ���� � ��� �������� $k$ ���������������� �������, ������ � ������� ������������������� ��������. ����� ���������� ������������ ���� ����� $n$ $(n\leqslant l)$, �� ���������� $(k+1)$-������������, �� ������, ��� ${l!k^{2n}\over n!(l-n)!((k-1)!)^2}$.
\end{corollary}

������ � ������� \ref{th:main} �������� ���������� � ������ \cite{Lat72}. ������� �������, ��� ������ �� $\xi_k(n)$ � ������ \cite{Lat72} ���� �������� ��� �������������� ������� ������, ������ �� � � �������� �� ��������. ������ � ������ \cite{Lat72} ������������ � ������� ������� ��������. ���������� ������� �������� � ��������� ������ ������� ������������� ���� ������� � ������ \cite{BK12}.

� ������ \cite{Ch07} ������������, ��� ��� ��� ����������� ������� $K(n) = o(\sqrt[3]{n}\ln n)$ � �����  $k \leqslant K(n) = o(\sqrt[3]{n}\ln n)$ ����� ��������������� ������ $\xi_k(n) = k^{2n - o(n)}$.

��� ��������� ������������ ������� � ������ \cite{Kn70} ������� ��������� �������:

\begin{definition}
���������� ���������� ���� ����� $(p_1, p_2,\dots  p_m)$, ��� $p_1\geqslant p_2\geqslant\dots\geqslant p_m\geqslant 1$, ���������� ������ $Y$ ������������� ����� $y_{ij}$, ��� $1\leqslant j\leqslant p_i$, $1\leqslant i\leqslant m,$ �����, ��� ����� � ��� ������� �� �������, � � �������� ����������.
\end{definition}

��� ��������� ������������ ������� ���������� ����.

\begin{definition}
����� ��� ������������� ����� $(u_1, v_1), (u_2, v_2),\dots , (u_N, v_N)$ �����, ��� ���� $(u_k, v_k)$ ����������� � ����������� ������������������ �������, ���������� {\em ������� ���� $\alpha(N)$}.
\end{definition}
� ������ \cite{Kn70} ��������������� ������� ����� �������� ���� $\alpha(N)$ � ������ $(P, Q)$ ���������� �������� ���� ������� $N$ (�. �. ��������� �� $N$ �����). ����� ����, ���������� �������-����������� ������������ ����� ���������������� �������� � ���������, � ������� ����� � ������ �� $i$-�� ������ � $j$-�� ������� ����� ���������� ��� $(i, j)$ � ������.
� ������ \cite{Ges90} �� ��������� ������� ���� $s_\lambda$, ������� ����� �������� ������������� ��������� ��� ���������� �������� ����, �������� ������������ ������� ��� $\xi_k(n).$ ������ ��������� ���������� ����� ������� ��� $\xi_k(n)$ ����� ��������������� �� $k$. � �������, $\xi_3(n)= 2 \sum\limits_{ k=0}^n \bigl(\begin{smallmatrix}2k\\ k \end{smallmatrix}\bigr)\bigl(\begin{smallmatrix}n\\ k \end{smallmatrix}\bigr)^2 {3k^2 + 2k + 1 - n - 2kn\over (k + 1)^2(k + 2)(n - k + 1)}$.

\section{�������������� ���������}

� 1950 ���� ����� (��. \cite{Sp50}) �������� �������� ������������� ���������� ����������� ������������ ������������� ������ ��� ����� �������������� 0. ������� �������� ������ ��� ������������ ������ ������������ � ���������� ����������� �. �. �������� \cite{Lat77}. ����������� �. �. �������� ������������ �� ���������� ������� �������� ������������� ��������. �. �. ����� (��. \cite{Kem87} �������, ��� ������ ������������ ������������� ������ ������� ���������, ��� ����� ����� �������� ������.

������ ������� ���������� ���������� ������������� ����� ���� �������� �. �. ������� (��. \cite{Bel99}), �. �. �������� (��. \cite{Gr99}) � �. �. ��������� (��. \cite{Shch99}).

����� ������� �������� ������ � ������ �������������� 0 �������� ������, ������������ ���������.

����� ��������� ������� �� ������ ������� ��� �����. ������ {\it �����������} ������������ �����, �������
\begin{itemize}
    \item �������� ����������� (�. �. �������� ����������� ������� ����);
    \item �� ����� ����������� �������;
    \item �� �������� ��������� ������� ������������ ����� ������� �����.
\end{itemize}

\begin{ques}[�������]
����� ��, ��� ���������� ���������� ��� ������������� $T$-������ �������?
\end{ques}

�� �������� �������� �������� ������������ ������ �������� �������� ������������ ��� ������ ��� ����� �������� ��������������. �������� ������ ����������� �������� ���������� $x_n x_{ n-1}\dots x_1$, � ��������� ������ ���������� ��������� �� $n$-����������� ����.

� ����� � ����� ��������� ��������� ��������:

\begin{ques}
����������� ���������� ������������ ����, ���������� ������� ��������� ������ ����������. �������� �������������� ��������������� ������������ �������.
\end{ques}


\section{�������������� �������� �����������}\label{sec:main}

\begin{lemma}[\cite{Sch61}]\label{lem:schlem3}
���������� ����������������� ������������ ����� �������������� $\pi\in S_n$ � ������ $(P, Q)$ ����������� �������� ����, ����������� ������� �� 1 �� $n$ � ������, ��� ����� $P$ ��������� � ������ $Q$.
\end{lemma}

\begin{proof}
����� $\pi = x_1 x_2\dots x_n$. �������� �� ��� ���� �������� ���� $(P, Q)$. ������� �������� ��������� $P$.

��������� �������� $S\leftarrow x$, ��� $S$ -- ��������� ����, $x$ -- ����������� �����, �� ������ �� ������ �� ����� � ��������� $S$.
\begin{enumerate}
\item ���� $x$ �� ������ ������ ������� ����� � ������ ������ $S$ (���� � ��� ��� �����, �� ����� �������, ��� $x$ ������ ������ �� ���), �� ��������� $x$ � ����� ������ ������ ��������� $S$. ���������� ��������� $S\leftarrow x$.
\item ���� ������� �������, ��� $x$, ����� � ������ ������ $S$, �� ����� $y$ -- ���������� ����� � ������ ������, ����� ��� $y > x$. ����� ������� $y$ �� $x$. ����� �������� � $y$ � ������ ������� �� �� ��������, ��� ��������� � $x$ � ������ �������.
\item ���������� ���� ������� ������ �� �������, ���� �����-������ ����� �� ����� ��������� � ����� ������.
\end{enumerate}
�� ���������� $S\leftarrow x$ ��������, ��� ����� ���������� ������� ����� ���������� ����.

����� $P = (\dots ((x_1\leftarrow x_2)\leftarrow x_3)\dots \leftarrow x_n).$ ����� $P$ �������� ���������� ���� � ������������� ������������ $\pi$. ����� ��������� $Q$ ���������� �� ��������� $P$ ���� ������ $x_i$ �� $i$ ��� ���� $i$ �� 1 �� $n$. ����� $Q$ ����� �������� ���������� ����.

����� � ������ \cite{Sch61} ������������, ��� ���������� ���������� ��� �������� ���� $(P, Q)$ �� ������������� $\pi\in S_n$ �����������������.
\end{proof}

�� ���������, ����������� � �������������� ����� \ref{lem:schlem3} �������

\begin{lemma}[\cite{Sch61}]\label{lem:schth1}
���������� ����� � ��������� $P$ ����� ����� ������������ ��������� ��������������������� �������� � $\pi = x_1 x_2\dots x_n$.
\end{lemma}

��������� ������ ��������������� � �������������� ������� \ref{th:main}.

���������� ������������ $\pi = x_1 x_2\dots x_n$. ��� �� $(k+1)$-���������� ����� � ������ �����, ����� � ��������������� �� ���������� $P$ � $Q$ �� ������ $k$ �����.

�������� ����� �� 1 �� $n$ � $k$ ������ ������������ �������. ����� ��������� $k^n$. ���������� ������ ������� (�� ����!), ����������� ��������� �������. ������ ��� ������� $i$ �� 1 �� $k$ �������� � $i$-� ������ �������� ������� ����� $i$-�� ����� � ������������ ������� ���, ����� ���������� ����� � ������ ������ � ������ ������� � ����� ������� � ����� ������ �� ���� ������ ����� (�� ������� ������ ������ ���� �����). ������ ���������� ������� {\it ��������� ���� $\beta (n, k)$}. ����� ����������� � $k$ ������ ����� �� 1 �� $n$ � ��������� ���� $\beta(n, k)$ ���� ������������ �������, �������������, ������ ���� $\beta(n, k)$ ����� ����� $k^n$. �������, ��� ����� ��������� ����, ����������� ������� �� 1 �� $n$ � �� �����, ��� $k$ ��������, ����� �������� ���� $\beta(n, k)$. ����� �������, ��� ������� $A$ � $B$ ���� $\beta(n, k)$ ������������ ($A\sim_\beta B$), ���� ���� �� ������ ����� �������� ��� ������ ������������ �����. ����� ���� � ������� ���� $\beta(n, k)$ �� ������ ����� ������ ������, �� � ��������������� ������ ��������������� ����� ����� $k!$ ���������. ��� ��� � ���������� ���� ����� � �������� ������ ����������� �� �����������, �� � ������ ������ ��������������� ������ ���� $\beta(n, k)$ ����� �� ����� ����� ��������� ����. ���� � ��������� ���� ����� $k$ �����, �� � ��������������� ������� ���� $\beta(n, k)$ �� ����� ������ �����. �������������, �������� ����, ����������� ������� �� 1 �� $n$ � ������� ����� $k$ �����, �� ������, ��� ${k^n\over k!}$.

���� � ��������� ���� $k$ �����, �� � ��� �� ������, ��� $(n-k+1)$ �������. ��������� ����� �� 1 �� $n$ � $(n-k+1)$ ����. ���������� ������ ������� (�� ����!), ����������� ��������� �������. ������ ��� ������� $i$ �� 1 �� $(n-k+1)$ �������� � $i$-� ������� �������� ������� ����� $i$-�� ����� � ������������ ������� ���, ����� ���������� ����� � ������� ������ � ������ ������ � ����� ������� � ����� ������� �� ���� ������ ����� (�� ������� ������ ������ ���� �����). ������ ���������� ������� {\it ��������� ���� $\gamma (n, k)$}. ����� ����������� � $(n-k+1)$ ������ ����� �� 1 �� $n$ � ��������� ���� $\gamma (n, k)$ ���� ������������ �������, �������������, ������ ���� $\gamma (n, k)$ ����� ����� $k^n$. �������, ��� ����� ��������� ����, ����������� ������� �� 1 �� $n$ � $k$ ��������, ����� �������� ���� $\gamma (n, k)$. ����� �������, ��� ������� $A$ � $B$ ���� $\gamma (n, k)$ ������������ ($A\sim_\gamma B$), ���� ���� �� ������ ����� �������� ��� ������ ������������ ��������. ����� � ������� $A$ ����� $t$ ��������� ��������. ����� ������ ���� $\gamma (n, k)$ � $t$ ���������� �������� ����� �� �����, ��� ������ ���� $\gamma (n, n-t+1)$, �. �. �� ����� $t^n$. � ������ ��������������� ������� ���� $\gamma (n, k)$ � $t$ �������� �������� ����� $(\min\{t + 1, n-k+1\})!$ ���������. ��� ���� ������ � $(n-k)$ ��� $(n-k+1)$ �������� ����� �� ����� $(n-k+1)^n$ � � ������ ������ ��������������� ����� ��� ����� $(n-k+1)!$ ���������. ��� ��� � ���������� ���� ����� � ������� ������ ����������� �� �����������, �� � ������ ������ ��������������� ������ ���� $\gamma (n, k)$ ����� �� ����� ����� ��������� ����. �������������, ����� ������ ���� $\gamma (n, k)$ ����� �� ����� ${(n-k+1)^n\over (n-k+1)!} + \sum\limits_{ t=1}^{n-k-1}{t^n\over t!}\leqslant {(n-k+1)^n\over (n-k)!}$ �������� ����.

������, ��� �������� ����, � ������ �� ������� �� $k$ �����, �� ������, ��� $\min\{{(n-k+1)^{2n}\over ((n-k)!)^2}, {k^{2n}\over (k!)^2}\}$. �������������, ���������� �� ������ $\min\{{(n-k+1)^{2n}\over ((n-k)!)^2}, {k^{2n}\over (k!)^2}\}$ ������������ $\pi\in S_n$ � ������ ������������ ��������� ��������������������� ����� $k$.

������ ������������ ������������� � ��������� �� ����������� ���� �������� �������� �� $n$ ���������. ������� � �������������� ������������� ��������� ���� ����������� ���� �������� ��������. ��� ��� � ������ ���� �������� �������� ����� ���� �� �����������, �� �� ������ \ref{lem:schlem3} � \ref{lem:schth1} ���������� �������������� ������������� �������� ������� $n$ � ������������ ��������� ����� $k$  �� ������, ��� $\min\{{(n-k+1)^{2n}\over ((n-k)!)^2}, {k^{2n}\over (k!)^2}\}$. ��� ����� ������� \ref{th:main2} ��������.

\begin{remark}
�������, ��� �� �������������� �������������� ��������� �� ������ ����� ����������, ����� ������ ����� �������� �������� ��� ���������. ��������, ���������� ��������� $\{ p_i \}_{ i=1}^{15}$ � �������� $(p_1>p_2>p_3, p_4>p_5>\dots >p_8, p_9>\dots >p_{15})$. ��� ����� ���� ���������:
\begin{itemize}
\item ����� �������� �������� � ������������� $(p_3>p_4, p_8>p_9)$ � $(p_3<p_4, p_8<p_9)$,
\item ����� �������� �������� � ������������� $(p_3>p_9, p_15>p_1)$ � $(p_3<p_9, p_15<p_1)$.
\end{itemize}

��� 2 ���� �������� �������� �� ��������� ���� �����.
\end{remark}

������ $\beth_k(n)$ -- ���������� �������� ����, ����������� ������� �� 1 �� $n$ � ������� �� ������ $k$ �����.

\begin{lemma}
����� ����������� $\beth_k(n)\leqslant{k^n\over (k-1)!}$.
\end{lemma}
\begin{proof}
��� ������������ �����, ���� � ������� ���� $\beta(n, k)$ �� ������ ����� ������ ������, �� � ��������������� ������ ��������������� ����� ����� $k!$ ���������. �������������, �������� ����, ����������� ������� �� 1 �� $n$ � ������� ���� $(k-1)$, ���� $k$ �����, �� ������ ${k^n\over k!}$. ������, ��� $k < 3$ ����� ��������. ����� ��� �������� ��� $k<t$. ����� ��� $k=t$ ����� $\beth_k(n)\leqslant {k^n\over k!}+\sum\limits_{i=1}^{ k-2}{i^n\over (i-1)!}\leqslant {k^n\over (k-1)!}.$
\end{proof}

������, ��� �������� ���� ������� $n$, � ������ �� ������� ��  $\leqslant k$ �����, �� ������, ��� ${k^{2n}\over ((k-1)!)^2}$. �������������, �� ������ \ref{lem:schlem3} � \ref{lem:schth1} ���������� �� $(k+1)$-����������� ������������ $\pi\in S_n$ ������ ${k^{2n}\over ((k-1)!)^2}$. ��� �����, ������� \ref{th:main} ��������.

������� �� ������� \ref{th:main} ��������� \ref{cor:main}. ��� ������� ������ ���� $a_{ i_1}, a_{ i_2},\dots , a_{ i_n}$ ���������� �� $(k+1)$-����������� ������������ ���� ����� $n$, ������������ �� ����� ������ ����, �� ������, ��� ${k^{2n}\over ((k-1)!)^2}$. ������� ������������� ����� �������� ����� ���� ����� �� $n$ ����. ��� ��� ������� �� $n$ ���� ����� $\bigl(\begin{smallmatrix}l\\ n \end{smallmatrix}\bigr)$, �� ���������� ��  $(k+1)$-����������� ������������ ���� ����� $n$ �� ������, ��� ${l!k^{2n}\over n!(l-n)!((k-1)!)^2}.$ ��� �����, ��������� \ref{cor:main} ��������.

\section{���������� ��������� ���� � �� ������������ �������}

\begin{lemma}[\cite{Kn70}]\label{lem:knuth}
���������� ����������������� ������������ ����� �������� ���� $\alpha(N)$  � ������ $(P, Q)$ ���������� �������� ���� ������� $N$ � ������� ����� $P$ ��������� � ������ $Q$.
\end{lemma}

\begin{proof}
��������� �������� $S\leftarrow x$, ��� $S$ -- ���������� ��������� ����, $x$ -- ����������� �����, ��� ��, ��� � �������������� ����� \ref{lem:schlem3}. ���������� ���������� ������ ���� $\alpha(N)$ �� ��� $(u_1, v_1), (u_2, v_2),\dots (u_N, v_N)$ ��������� ���� $P = (\dots ((v_1\leftarrow v_2)\leftarrow v_3)\dots \leftarrow v_N)$. ����� ��������� $Q$ ���������� �� ��������� $P$ ���� ������ $v_i$ �� $u_i$ ��� ���� $i$ �� 1 �� $N$. ����� $Q$ ����� �������� ���������� ����.

����� � ������ \cite{Kn70} ������������, ��� ���������� ���������� ��� ���������� �������� ���� $(P, Q)$ �� ������� ���� $\alpha$ �����������������.
\end{proof}

\begin{notation}
������������ $\pi\in S_n$ �������� ������� ���� $\alpha(n)$ �� ���//
 $(1, \pi(1)),\dots ,(n, \pi(n))$.
\end{notation}

{\it �������������� �������.}

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

�������� ��������� ������� �� ������ �������������� �������.

{\it ������ �������������� �������} $h_n$ ����� $h_n = \sum\limits_{i_1\leqslant i_2\leqslant\dots\leqslant i_n}x_{i_1}x_{i_2}\dots x_{i_n}.$

����� $\lambda$ -- ����� $(\lambda_1, \lambda_2,\dots ,\lambda_k)$ ��� ���������� ������������ $k$. ����� ����� $|\lambda| = \sum\limits_{i=1}^k \lambda_i$. ����� $\lambda$ ���������� {\it ����������,} ���� $\lambda_1\geqslant \lambda_2\geqslant\dots \geqslant\lambda_k.$

{\it ������� ����} $S_\lambda$ ����� $S_\lambda = \det(h_{\lambda_i + j-i})_{1\leqslant i, j\leqslant k}.$

����� $\lambda$ -- ��������� � �� $\{x_i\}$ ����� ������� $x_1<x_2<\dots <x_i<\dots$ ����� ����������� ����� ������� $P$ ������� $|\lambda|$ � $S_\lambda$ ���� ���������� �������� ���� ����� $(\lambda_1, \lambda_2,\dots ,\lambda_k)$ � ������������� ���������, ������ $P.$

� ������ \cite{Ges90} ������������ ������� $b_i = \sum\limits_{n=0}^{\infty}{x^{2n + i}\over n!(n+i)!}$ � $U_k = \det(b_{\mid i-j\mid})_{1\leqslant i, j\leqslant k}.$

����� �������� ������� $R_k(x, y)$ ��� $R_k(x, y) = \sum\limits_k s_\lambda(x) s_\lambda(y)$, ��� ����� ������ �� ���� ���������� �� �� ����� ��� $k$ ������. ����� ����������� ��� $x_1 x_2\dots x_n y_1 \dots y_n$ � ������� $R_k(x, y)$ ����� $\xi_k(n).$ �� ����� � \cite{Ges90} ���������, ��� $U_k = \sum\limits_{n=0}^{\infty}\xi_k(n){ x^{ 2n}\over (n!)^2}.$

���������� ������������ ���� ����� $n$ ��� $l$-��������� ��������� $(n \leqslant l)$, � ������ �� ������� �� ������� ������������������ �� $(k+1)$ ����� �
������� ������������������� �������� ���� $\bigl(\begin{smallmatrix}l\\ n \end{smallmatrix}\bigr)\xi_k(n)$.

����� �������� ������������� �.�. ������, �.�. �������, �.�. �������� � ���� ���������� �������� ``������ �����'' �� ���������� ������ � ���������� ������.

\begin{thebibliography}{MH1}

\bibitem{Bel99}
�. �. �����. {\it � ����������� �������������.} ���������. � �����. �����., 5:1 (1999), 47�66.
\bibitem{BK12}
�. �. �����, �. �. ���������. {\it ������ ������ � ������ ������� � �� ���������� ���������� ������ �������.} ���������. � �����. �����., 17:5 (2012), 21�54.
\bibitem{Ch07}
�. �. �������� {\it � ������ ������ ���������� k+1-����������� ������������.}
�����. � ������ ������. ������, �. 14, �4, 2007, 53 -- 56.

\bibitem{Ges90}
Ira M. Gessel. {\it Symmetric Functions and P-Recursiveness.} J. Combin. Theory Ser. A 53, 1990, 257 -- 285.
\bibitem{Gr99}
�. �. ������. {\it ������� �� �������� ������������ �-����������� � �-������� � �������������� 2.} ���������. � �����. �����., 5:1 (1999),  101 �- 118.
\bibitem{Kem87}
�. �. ����� {\it �������� ������������ �������� ������������� ������.} ������� � ������, ��� 26, ������ 5, 1987, 597 -- 641.
\bibitem{Kn70}
Donald E. Knuth. {\it Permutations, matrices, and generalized Young tableux.}
Pacific journal of mathematics, Vol. 34, No. 3, 1970, 709 -- 727.

\bibitem{Lat72}
�. �. �������. {\it � ������� ������ � ���������� ���������� ������������ PI-������.} ���, �.27, ������ 4(166), 1972, 213 -- 214.
\bibitem{Lat77}
�. �. �������. {\it ����������� ������������ ����������� ������.} �., ���-�� ����. ��-��, 1977.
\bibitem{Sch61}
Schensted C. {\it Longest increasing and decreasing subsequences.} Canad. J. Math 13, 1961, 179 -- 191.
\bibitem{Shch99}
�. �. �������. {\it ������� ���������� ���������� T-�������.} ���������. � �����. �����., 5:1 (1999),  307 �- 312.
\bibitem{Sp50}
W. Specht. {\it Gesetze in Ringen. I.} Math. Z., 52:557-589, 1950.

\end{thebibliography}

\end{document}

1307.1886.extracted_bib
\begin{thebibliography}{MH1}

\bibitem{Bel99}
�. �. �����. {\it � ����������� �������������.} ���������. � �����. �����., 5:1 (1999), 47�66.
\bibitem{BK12}
�. �. �����, �. �. ���������. {\it ������ ������ � ������ ������� � �� ���������� ���������� ������ �������.} ���������. � �����. �����., 17:5 (2012), 21�54.
\bibitem{Ch07}
�. �. �������� {\it � ������ ������ ���������� k+1-����������� ������������.}
�����. � ������ ������. ������, �. 14, �4, 2007, 53 -- 56.

\bibitem{Ges90}
Ira M. Gessel. {\it Symmetric Functions and P-Recursiveness.} J. Combin. Theory Ser. A 53, 1990, 257 -- 285.
\bibitem{Gr99}
�. �. ������. {\it ������� �� �������� ������������ �-����������� � �-������� � �������������� 2.} ���������. � �����. �����., 5:1 (1999),  101 �- 118.
\bibitem{Kem87}
�. �. ����� {\it �������� ������������ �������� ������������� ������.} ������� � ������, ��� 26, ������ 5, 1987, 597 -- 641.
\bibitem{Kn70}
Donald E. Knuth. {\it Permutations, matrices, and generalized Young tableux.}
Pacific journal of mathematics, Vol. 34, No. 3, 1970, 709 -- 727.

\bibitem{Lat72}
�. �. �������. {\it � ������� ������ � ���������� ���������� ������������ PI-������.} ���, �.27, ������ 4(166), 1972, 213 -- 214.
\bibitem{Lat77}
�. �. �������. {\it ����������� ������������ ����������� ������.} �., ���-�� ����. ��-��, 1977.
\bibitem{Sch61}
Schensted C. {\it Longest increasing and decreasing subsequences.} Canad. J. Math 13, 1961, 179 -- 191.
\bibitem{Shch99}
�. �. �������. {\it ������� ���������� ���������� T-�������.} ���������. � �����. �����., 5:1 (1999),  307 �- 312.
\bibitem{Sp50}
W. Specht. {\it Gesetze in Ringen. I.} Math. Z., 52:557-589, 1950.

\end{thebibliography}