On the lower estimate for $k+1$-nondecomposible permutations

G. R. Chelnokov

Modelirovanie i analiz informacionnyh sistem, Tome 14 (2007) no. 4, pp. 53-56

Résumé

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,$ 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)$.