О нижней оценке количества k + 1-неразбиваемых перестановок

Аннотация

Перестановку т : [1;и] - [1; и] назовем k + 1-неразбиваемой, если для любого набора a1,... ,a_t G [1;n] из условий a_l < a₂ < < a_i и т(a_l) < т(a₂) < < т(ai) следует i < k. Число k + 1-неразбиваемых перестановок на и элементах обозначим через f (u,k). В работе доказано, что для f (u,k) верна асимптотическая оценка f (u,k) = k^2n-o(n), равномерная по всем k <= K (и) = o( y 3/n In и).