Abstract:
A permutation $\tau$ is called $k+1$-nondecomposible if the following condition holds: if $\{a_1,\dots,a_in\}$ is a set of natural numbers such that $1\le a_1,<\dots,<a_i\le n$ and $\tau(a_1)<\tau(a_2)<\dots<\tau(a_i)$, then $i\le k$. By $f(n,k)$ denote the number of all not $k+1$-nondecomposible permutations. The following statement was proved in this paper: suppose $K(n)=o(\root3\of{n}/\ln n)$; then $f(n,k)=k^{2n-o(n)}$ for every $k \le K(n)$.
Fulltext:
PDF file (227 kB)