Циклы в перестановках

[Jiggy]

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

Никак не получается до конца решить задачу. Состоит она в следующем. Есть множество перестановок $S_n$, нужно найти вероятность того, что в произвольно выбранном элементе из $S_n$ будет хотя бы 1 цикл длины $k$.

На текущем этапе имею:
1) Всего $\frac{n!}{k}$ циклов длины $k$
2) При $\frac{n}{2} < k \leqslant n$ : $p = \frac{1}{k}$. Это очевидно, так как в любой перестановке может быть либо 1 цикл такой длины, либо 0. Больше 1 быть не может, так как не поместятся.
3) А вот если $ k \leqslant \frac{n}{2} $, то возникают проблемы.

На форуме видел эту задачу в разделе марафонских задач. Написано применить метод включений и исключений. Ответ задачи известен. Как именно он получен, я не понял.

Я понимаю, почему происходят изменения при переходе от $\frac{n}{2} < k \leqslant n$ к $\frac{n}{3} < k \leqslant \frac{n}{2}$. Здесь уже получается наличие трех подмножеств перестановок. Первое состоит из перестановок, не содержащих циклы длины $k$, второе состоит из перестановок, содержащих 1 цикл длины $k$, а третье по 2 цикла длины $k$.
Как конкретно применить метод включений-исключений для получения правильного ответа?

Ссылка на исходную тему с задачей: http://dxdy.ru/topic16349-15.html

Всем заранее спасибо.

[VAL]

Jiggy,
Не совсем понятно, что именно Вам непонятно.
Например, для случая $\frac{n}{3} < k \leqslant \frac{n}{2}$ понятно?


PS: Благодаря Вашему вопросу обнаружил и поправил опечатку в последней формуле пункта 3.d задачи ММ100. Так что, и Вам спасибо!

[Jiggy]

VAL
Не понял, если честно.

Понятно, что для этого промежутка вероятность будет : $p = \frac{1}{k} - \frac{1}{2k^2}$
Только почему мы вычли именно $\frac{1}{2k^2}$ не ясно.

В решении написано: "Разобрав случаи одного и двух циклов, получим искомую вероятность $\frac{2k-1}{2k^2}$ "
В общем это я не понял. И для остальных промежутков не понимаю, как конкретно метод включений-исключений используется.

[VAL]

Ну давайте рассуждать.

Пусть $k$ и $n$ таковы, в перестановке укладывается 2, но не 3 цикла.
Посчитаем количество перестановок, в которые входит хотя бы один цикл длины $k$.
Выберем $k$ элементов. Это можно сделать $n\choose k$ способами. Расставить эти элементы в цикл можно $(k-1)!$ способами.
Остальные элементы можно упорядочить $(n-k)!$ способами.
Итого получается ${n\choose k}(k-1)!(n-k)!$ способов.
Эта часть рассуждения совпадает с рассуждением для случая я $\frac{n}2 < k \leqslant n$. Но в нашем случае мы получили не ответ, а оценку сверху. Поскольку среди всевозможных перестановок $n-k$ элементов есть и такие, при которых образуется цикл длины $k$. Поэтому каждая перестановка, содержащая два цикла длины $k$ оказалась сосчитанной дважды. Так что, для получения окончательного ответа надо посчитать количество таких перестановок из вычесть получившееся число из ${n\choose k}(k-1)!(n-k)!$.

Сможете?

[Jiggy]

VAL

${n\choose k}(k-1)!(n-k)! = \frac{n!}{k}$ - количество циклов длины $k$.
Теперь разберемся с 2 циклами. Снова выберем $k$ элементов из $n$, и еще $k$ элементов из $(n-k)$, каждый из циклов можно составить $(k-1)!$ способами. Оставшиеся $(n-2k)$ можно упорядочить $(n-2k)!$ способами. В итоге получается: ${n\choose k}(k-1)!{(n-k)\choose k}(k-1)!(n-2k)! = \frac{n!}{k^2}$. Чуть-чуть не сходится. Где-то ошибся?

[VAL]

Jiggy в сообщении #1245773 писал(а):

${n\choose k}(k-1)!(n-k)! = \frac{n!}{k}$ - количество циклов длины $k$. В перестановке из оставшихся $(n-k)$ элементов нужно сформировать еще цикл из $k$ элементов. Выбрать $k$ элементов из $(n-k)$ можно ${(n-k)\choose k}$ способами. Сформировать цикл из них: $(k-1)!$ способами, а оставшиеся можно упорядочить $(n-2k)!$ способами. Получается: ${(n-k)\choose k}(k-1)! (n-2k)! = \frac{(n-k)!}{k}$ вариантов. Логика такая?

Не совсем.

Я предлагал посчитать посчитать количество перестановок, имеющих по два цикла длины $k$ и вычесть это число из $\frac{n!}{k}$. А Вы принялись формировать второй цикл длины $k$ из оставшихся от первого цикла элементов. При таком подходе (даже если довести его до ума) у Вас циклы не будут равноправны.

PS: Пока набирал, Вы уже что-то поправили. Но ошибка осталась.

[Jiggy]

VAL
Как раз осознал, что нужно посчитать количество перестановок, имеющих по два цикла длины $k$, и принялся исправлять. $2!$ в знаменателе не знаю, как получить. Можно предположить, что нужно разделить на $2!$, так как циклов 2. При наличии 3-х циклов, получается $\frac{n!}{k^3}$, деленный на $3!$, так как циклов 3. И так далее. Но как-то это пока не обоснованно.

[VAL]

Что не обосновано?
У нас есть число $\frac{n!}k$, в котором все перестановки, имеющие по два цикла длины $k$ сосчитаны дважды. Поэтому из данного числа надо вычесть количество таких перестановок.
Давайте еще раз аккуратно их пересчитаем.

[Jiggy]

VAL
Выбираем сначала $k$ элементов из $n$, затем $k$ элементов из $(n-k)$. Осталось $(n-2k)$ элементов. В итоге получается следующее:
${n\choose k}{(n-k)\choose k}(k-1)!(k-1)!(n-2k)! = \frac{n!}{k^2}$
Правильно?

[VAL]

Jiggy в сообщении #1245804 писал(а):

Правильно?

Нет. У Вас опять та же ошибка, на которую я Вам указал. У Вас есть первый цикл длины $k$ и второй цикл длины $k$.
Если циклы поменять местами, получится та же перестановка. А у Вас они считаются разными.

Простейший пример:
Сколькими способами можно разбить 4 элемента на 2 пары. Ясно, что тремя. А вот выбрать 1-ю пару можно 6-ю способами.

[Jiggy]

VAL
Получается, просто разделить еще на $m!$, где $m$ - количество циклов, чтобы одинаковые перестановки убрать.

[VAL]

Jiggy в сообщении #1245819 писал(а):

VAL
Получается, просто разделить еще на $m!$, где $m$ - количество циклов, чтобы одинаковые перестановки убрать.

Да.

Дальше все аналогично:
Если умещается 3 цикла, то мы из числа перестановок, содержащих хотя бы один цикл, вычитаем количество перестановок, содержащих, по крайней мере, по два цикла.
При этом каждая перестановка, содержащая по три цикла, сначала сосчитается трижды, потом вычтется тоже трижды. Значит, надо добавить количество таких перестановок.
И т.д.
Разложение $(1-1)^m$ по формуле бинома гарантирует нам, что в итоге каждая подходящая перестановка будет учтена ровно один раз.

[Jiggy]

VAL

Разобрался. Спасибо вам огромное!