Задача ММ100 утратила статус конкурсной и может обсуждаться в форуме.
=============Юбилейная задача представляет собой по сути целый букет задач, связанных общей тематикой и общими идеями. Часть подзадач - известные (но, с учетом их красоты, на мой взгляд, недостаточно известные) утверждения. Другие - новые (хотелось бы надеяться не только для меня).
ММ100 (17 баллов)
Пусть

множество всех перестановок множества

1. Найти и обосновать рекуррентное выражение количества перестановок

из

таких, что для всех

из

может отличаться от

:
a) не более, чем на

;
b) не более, чем на

.
2. Рассмотрим произвольный элемент из

и произвольное

из

.
Найти вероятность того, что

входит в цикл длины

.
3. Для произвольного элемента

из

найти:
a) математическое ожидание количества циклов длины

;
b) математическое ожидание количества циклов;
c) моду циклового вида (учитываются количество и длина циклов);
d) полагая

, найти вероятность того, что в

будет хотя бы один цикл
длины

.
4. Вспомним, что

является группой относительно композиции перестановок.
Обозначим

:
a) найти

наименьших значений

;
b) возможно ли равенство

для нечетных

.
Решение 1.a.
Этот пункт совсем легкий.
Перестановки, удовлетворяющие условию пункта 1.a будем называть подходящими.
Обозначим искомое количество подходящих перестановок через

.
Ясно, что

и

.
Требуемые перестановки, очевидно, представляют собой произведение транзпозиций соседних элементов и "циклов" длины 1. Т. е. их можно получить, приписывая транспозицию

к

подходящим перестановкам множества

и петли

к

подходящим перестановкам множества

.
Поэтому

, и мы получаем ряд Фибоначчи.
1.b.
Здесь ситуация похитрее.
Теперь подходящими будем называть перестановки, удовлетворяющие условию пункта
1.b. Обозначим искомое количество подходящих перестановок через

. Первые значения

:

. Учитывая, что

, положим

.
Пусть теперь

не меньше

.
i) Из каждой подходящей перестановки множества

можно получить подходящую перестановку множества

, добавив петлю

.
Для того чтобы выяснить, как можно продолжить подходящую перестановку, не добавляя новых циклов, рассмотрим возможные "хвосты" подходящих перестановок.
ii) Заметим, что, если в цикловую запись подходящей перестановки на множестве

входит цикл, содержащий

, длина которого больше двух, то в такой цикл можно добавить элемент

единственным способом.
iii) Если цикловая запись перестановки заканчивается петлей

, перед которой идет цикл, содержащий более одного элемента, то такую перестановку также можно продолжить до подходящей, не добавляя новых циклов, единственным способом, заменив петлю

на транспозицию

.
iv) Если цикловая запись перестановки заканчивается двумя петлями

, то в каждую из них можно добавить

.
v) Если цикловая запись перестановки заканчивается транспозицией

, то оба возможных способа добавления элемента

в эту транспозицию ведут к получению подходящих перестановок множества

.
vi) Если цикловая запись подходящей перестановки заканчивается выражением

, то элемент

нельзя "впихнуть" в транспозицию

, но можно добавить в одноэлементный цикл

.
vii) Наконец, если цикловая запись подходящей перестановки заканчивается выражением

, то добавить элемент n в уже имеющиеся циклы невозможно.
Поэтому

.
(Большинстово подходящих перестановок можно продолжить не менее чем двумя способами. Второе слагаемое учитывает дополнительные подходящие перестановки, возникающие в случаях iv и v, а последнее слагаемое обусловлено случаем vii.)
2.
Ответ к этому пункту:

для всек

и

при

.
В самом деле, произвольный элемент

множества

при произвольной перестановке с вероятностью

переходит в себя и образует цикл длины

. Вероятность его вхождения в цикл длины

равна произведению

(вероятности того, что

не перешел в себя) на

(верояности того, что образ

перешел в

). Итого, вновь имеем верояность

.
И т.д.
3.a.
Запишем все

перестановок в цикловом виде (не опуская одноэлементных циклов). В этой записи будет участвовать ровно

элементов, разбитых на циклы длин

. Из пункта 2 следует что для каждого

из

в этой записи будет ровно

элементов, входящих в циклы длины

и, значит,

циклов длины

.
(Например, для

имеем:

.)
Но тогда искомое математическое ожидание равно

.
3.b.
Для получения ответа к этому пункту достаточно просто просуммировать математические ожидания числа циклов длины

по всем возможным

. Таким образом, математическое ожидание количества циклов в произвольной перестановке n-элементного множества равно

, т.е.

-му гармоническому числу.
3.c.
При

в единственной перестановке множества

есть единственный цикл длины

. При

возможные цикловые виды
![$[1]-[1]$ $[1]-[1]$](https://dxdy-03.korotkov.co.uk/f/6/1/c/61c4c46be40a2374fd7470bc4746d2a382.png)
и
![$[2]$ $[2]$](https://dxdy-03.korotkov.co.uk/f/a/5/1/a51017f136e558ba29a2faebc9e2787682.png)
встречаются одинаково часто (по одному разу).
Пусть

.
Из предыдущих пунктов следует, что ровно

перестановок представляют собой цикл длины

. Аналогично, цикловой вид
![$[n-1]-[1]$ $[n-1]-[1]$](https://dxdy-03.korotkov.co.uk/f/e/6/3/e636aee18d2f3e302289f9d6bb093b6e82.png)
имеют

перестановок. Т.е. их больше, чем длинных циклов. Покажем, что
![$[n-1]-[1]$ $[n-1]-[1]$](https://dxdy-03.korotkov.co.uk/f/e/6/3/e636aee18d2f3e302289f9d6bb093b6e82.png)
и есть мода циклового вида.
В самом деле, легко видеть, что престановок циклового вида
![$[n-1]-[1]$ $[n-1]-[1]$](https://dxdy-03.korotkov.co.uk/f/e/6/3/e636aee18d2f3e302289f9d6bb093b6e82.png)
больше, чем престановок циклового вида
![$[n-k]-[k]$ $[n-k]-[k]$](https://dxdy-01.korotkov.co.uk/f/0/3/c/03cb83240efbf84fbf025c67b8ce91f982.png)
при

и

, бОльших

.
Пусть теперь

, где

. Тривиально показывается, что перестановок вида
![$[a+b]-[c]$ $[a+b]-[c]$](https://dxdy-01.korotkov.co.uk/f/4/8/c/48c5af17c9853f65deb3ba9f2cb8313e82.png)
больше чем перестановок вида
![$[a]-[ b ]-[c]$ $[a]-[ b ]-[c]$](https://dxdy-02.korotkov.co.uk/f/9/1/7/9174111879229416b0118c940444312382.png)
.
И т.д.
3.d.
i. Со случаем

мы разобрались в предыдущих пунктах. Искомая вероятность равна

.
ii. При

, разобрав случаи одного и двух циклов, получим искомую вероятность

.
iii. Для остальных случаев удобно воспользоваться формулой включения и исключения. При

имеем

.
iv. При

имеем

.
4.a.
При возведении в степень

цикл длины

распадается на

циклов длины

. Учитывая это соображение и количество подстановок каждого циклового вида в группах

при малых

можно получить следующие

значений

(если значение получается при разных наборах значений

и

, указан один из таких наборов):

(при

)

(при

)

(при

)

(при

)

(при

)

(при

)

(при

)

(при

)

(при

)

(при

)

(при

)

(при

)

(при

)

(при

)

(при

)

(при

)

(при

)

(при

)

(при

)

(при

)
Обоснование того, что приведены наименьшие возможные значения можно посмотреть на
http://www-old.fizmat.vspu.ru/doku.php? ... thon:about4.b.
Покажем, что

.
Для этого заметим, что в

, в отличие от

, нет перестановок с циклами, длины которых кратны

, за исключением перестановок вида
![$[3]-[3]-[3]$ $[3]-[3]-[3]$](https://dxdy-04.korotkov.co.uk/f/3/b/9/3b9b5964745d8725ec642c334360ebfc82.png)
.
В

Имеется:
девятиэлементных циклов -

;
перестановок, содержащих шестиэлементный цикл, -

;
перестановок с ровно двумя трехэлементными циклами, -

;
перестановок с ровно одним трехэлементным циклом, -

.
Учитывая, что

, и суммируя, получим

.
Обсуждение Любопытно, что большинство участников Марафона, получив рекуррентное соотношение для

, никоим образом не отреагировали, что это числа Фибоначчи.
Последовательность

(как, разумеется, и

) есть онлайновой энциклопедии целочисленных последовательностей. Её номер A002524.
Применяя метод включения и исключения, можно получить общую формулу, выражающую вероятность наличия цикла длины

в

-
![$\sum_{i=1}^{[n/k]} \frac{(-1)^{i+1}}{k^i i!}$ $\sum_{i=1}^{[n/k]} \frac{(-1)^{i+1}}{k^i i!}$](https://dxdy-03.korotkov.co.uk/f/2/0/6/206dc5d39d392a0b6dd609156974a6f182.png)
.
Любопытно, 21-е по величине значение

получается при

Это

(

тоже равно

).
С пунктом 4.b. не справился ни один участник. Это оказалось для меня неожиданным. Ведь подходящий пример возникает при совсем не запредельных

и

.
Кстати,

и

тоже равны по

.
Справедливо и более общее утверждение:

, причем это неравенство трансформируется в равенство всякий раз, когда

.
Вызывает интерес доказательство (или опровержение) следующей гипотезы:

.
Награды За правильное решение большинства пунктов задачи 100 участники получают:
Владислав Франк - 15 баллов;
Алексей Волошин - 14 баллов;
Андрей Халявин и Алексей Извалов по 12 баллов.
Эстетическая оценка задачи - 5 баллов