Даны натуральные числа $%n$% и $%k$%, $%k<n$%. Рассмотрим $%P_{n,k} -$% количество перестановок множества $%\left \{ 1,2,...,n \right \}$%, при каких элемент $%i$% перемещается не меньше, чем на $%r$% влево или вправо (то есть для $%i$% и его места в перестановке $%n_i$% выполняется неравенство $%|i-n_i|\ge k$%).

Для разных значений $%n$% и $%k$% получить как можно более точные оценки сверху и снизу для $%P_{n,k}$%. Какие свойства у этой величины.

задан 26 Май '15 14:41

изменен 26 Май '15 14:46

1

Для k=1 это задача о "беспорядках", а для $%k=2$% интересно было бы точную формулу найти. Думаю, это сделать можно. Для других случаев -- пока неясно. Может быть, хотя бы неравенства удастся получить.

(27 Май '15 1:12) falcao
2

Есть идея, как получить асимптотические формулы для любого фиксированного $%k$% при $%n\to\infty$%. У меня получается, что $%P_{nk}/n!\to e^{-(2k-1)}$%. Постараюсь через некоторое время изложить.

(29 Май '15 8:31) falcao
10|600 символов нужно символов осталось
3

Зафиксируем $%k$% и рассмотрим асимптотику величины $%P_{nk}/n!$%. Через $%A_i$% обозначим множество таких подстановок $%\sigma$%, для которых $%|i-\sigma(i)| < k$%. Нас интересует число элементов дополнения объединения $%A_1\cup\cdots\cup A_n$%. Применяя формулу включений и исключений и деля на $%n!$%, имеем $$\frac{P_{nk}}{n!}=\sum\limits_{s=0}^n\frac{(-1)^s}{n!}\sum\limits_{i_1 < \cdots < i_s}|A_{i_1}\ldots A_{i_s}|.$$ Легко видеть, что $%|A_{i_1}\ldots A_{i_s}|\le(2k-1)^s(n-s)!$% за счёт того, что значения $%\sigma(i_j)$%, "близкие" к $%i_j$% в смысле неравенства $%|i_j-\sigma(i_j)| < k$% могут быть выбраны не более чем $%2k-1$% способом, а остальные значения образуют произвольную перестановку. Из этого неравенства, с учётом того, что "внутренняя" сумма имеет $%C_n^s$% слагаемых, получается такая оценка сверху для модуля $%s$%-го члена суммы: $%C_n^s(2k-1)^s(n-s)!/n!=(2k-1)^s/s!$%.

Ряд из таких величин сходится (к $%e^{2k-1}$%), поэтому для любого $%\varepsilon > 0$% можно указать не зависящую от $%n$% константу $%m=m(\varepsilon)$%, что суммы модулей членов с номерами $%s$%, большими $%m$%, меньше $%\varepsilon/2$%. Таким образом, далее мы "урезаем" сумму, меняя верхний предел суммирования на $%m$%.

Пусть $%s\le m$% и $%n\gg m$%. Докажем, что подавляющее большинство наборов индексов вид $%i_1 < \cdots < i_s$% обладает тем свойством, что имеет место равенство $%|A_{i_1}\ldots A_{i_s}|=(2k-1)^s(n-s)!$%. Для этого достаточно, чтобы выполнялись следующие условия: $%i_1\ge k$%, $%i_{j+1}-i_j\ge2k-1$% при $%1\le j < s$%, и $%i_s\le n-k+1$%. Для таких случаев последовательность индексов оказывается "разреженной", то есть выбор элемента $%\sigma(i_j)$% может быть осуществлён $%2k-1$% способом, независимо от выбора соседних значений.

Проверим тот факт, что наборов, для которых нарушается хотя бы одно из неравенств, указанных выше, в некотором смысле "мало". Количество самих неравенств не превосходит $%s+1\le m+1$%, что является величиной порядка $%O(1)$% относительно $%n$%. При фиксированном $%j$% количество пар индексов, для которых $%i_{j+1}-i_j < 2k-1$%, имеет порядок $%O(n)$%. Остальные $%s-2$% индекса выбираются не более чем $%C_n^{s-2}$% способами, а это величина порядка $%O(n^{s-2})$%. Всё вместе даёт $%O(n^{s-1})$%, и это есть $%o(C_n^s)$%, то есть бесконечно малая величина относительно количества всех наборов из $%s$% элементов. Таким образом, мы для каждого $%s\le m$% получаем величину $%s$%-го члена суммы, равную $%(-1)^s(2k-1)^s(1+o(1))/s!$%. Учитывая, что количество членов суммы не зависит от $%n$%, мы можем выбрать достаточно большое $%n$%, при котором все величины порядка $%o(1)$% оказываются меньше $%\varepsilon/(2m+2)$%, и тогда с итоговой погрешностью $%\varepsilon$% мы получим значение суммы, равное $%\sum\limits_{s=0}^n(-1)^s(2k-1)^s/s!$%, что стремится к $%e^{-(2k-1)}$% при $%n\to\infty$%.

ссылка

отвечен 30 Май '15 14:14

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,023

задан
26 Май '15 14:41

показан
352 раза

обновлен
30 Май '15 14:14

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru