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

Конкурсная задача №100 (17 баллов)

Пусть S_n множество всех перестановок множества M_n = {1,2,3…,n}

1. Найти и обосновать рекуррентное выражение количества перестановок g из S_n таких, что для всех k из M_n g(k) может отличаться от k:
a) не более, чем на 1;
b) не более, чем на 2.

2. Рассмотрим произвольный элемент из S_n и произвольное a из M_n. Найти вероятность того, что a входит в цикл длины k.

3. Для произвольного элемента g из S_n найти:
a) математическое ожидание количества циклов длины k;
b) математическое ожидание количества циклов;
c) моду циклового вида (учитываются количество и длина циклов);
d) полагая k > n/5, найти вероятность того, что в g будет хотя бы один цикл длины k.

4. Вспомним, что S_n является группой относительно композиции перестановок.
Обозначим s(n,k) = | {g^k | g ∈ S_n} |, q(n,k) = s(n,k)/n!:
a) найти 20 наименьших значений s(n,k);
b) возможно ли равенство q(n,k) = 1/2 для нечетных k.

Решение

1.a.

Этот пункт совсем легкий.
Перестановки, удовлетворяющие условию пункта 1.a будем называть подходящими. Обозначим искомое количество подходящих перестановок через F(n).
Ясно, что F(1) = 1 и F(2) = 2.
Требуемые перестановки, очевидно, представляют собой произведение транзпозиций соседних элементов и «циклов» длины 1. Т. е. их можно получить, приписывая транспозицию (n-1 n) к F(n-2) подходящим перестановкам множества M_n-2 и петли (n) к F(n-1) подходящим перестановкам множества M_n-1.
Поэтому F(n) = F(n-1) + F(n-2), и мы получаем ряд Фибоначчи.

1.b.

Здесь ситуация похитрее.
Теперь подходящими будем называть перестановки, удовлетворяющие условию пункта 1.b. Обозначим искомое количество подходящих перестановок через G(n).
Первые значения G: G(1) = 1, G(2) = 2, G(3) = 6, G(4) = 14. Учитывая, что 0! = 1, положим G(0) = 1.
Пусть теперь n не меньше 5.
i) Из каждой подходящей перестановки множества M_n-1 можно получить подходящую перестановку множества M_n, добавив петлю (n).

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

ii) Заметим, что, если в цикловую запись подходящей перестановки на множестве M_n-1 входит цикл, содержащий (n-1), длина которого больше двух, то в такой цикл можно добавить элемент n единственным способом.

iii) Если цикловая запись перестановки заканчивается петлей (n-1), перед которой идет цикл, содержащий более одного элемента, то такую перестановку также можно продолжить до подходящей, не добавляя новых циклов, единственным способом, заменив петлю (n-1) на транспозицию (n-1 n).

iv) Если цикловая запись перестановки заканчивается двумя петлями (n-2)(n-1), то в каждую из них можно добавить n.

v) Если цикловая запись перестановки заканчивается транспозицией (n-2 n-1), то оба возможных способа добавления элемента n в эту транспозицию ведут к получению подходящих перестановок множества M_n.

vi) Если цикловая запись подходящей перестановки заканчивается выражением (n-3 n-1)(n-2), то элемент n нельзя «впихнуть» в транспозицию (n-3 n-1), но можно добавить в одноэлементный цикл (n-2).

vii) Наконец, если цикловая запись подходящей перестановки заканчивается выражением (n-4 n-2)(n-3 n-1), то добавить элемент n в уже имеющиеся циклы невозможно.

Поэтому G(n) = 2G(n-1) + 2G(n-3) - G(n-5).

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

2.

Ответ к этому пункту: 1/n для всек k ≤ n и 0 при k > n.

В самом деле, произвольный элемент a множества M_n при произвольной перестановке с вероятностью 1/n переходит в себя и образует цикл длины 1. Вероятность его вхождения в цикл длины 2 равна произведению (n-1)/n (вероятности того, что a не перешел в себя) на 1/(n-1) (верояности того, что образ a перешел в a). Итого, вновь имеем верояность 1/n. И т.д.

3.a.

Запишем все n! перестановок в цикловом виде (не опуская одноэлементных циклов). В этой записи будет участвовать ровно n*n! элементов, разбитых на циклы длин 1, 2, … n. Из пункта 2 следует что для каждого k из {1,2,…,n} в этой записи будет ровно n! элементов, входящих в циклы длины k и, значит, n!/k циклов длины k. (Например, для n = 3 имеем: (1)(2)(3),(12)(3),(13)(2),(1)(23),(123),(132).) Но тогда искомое математическое ожидание равно (n!/k)/n! = 1/k.

3.b.

Для получения ответа к этому пункту достаточно просто просуммировать математические ожидания числа циклов длины k по всем возможным k. Таким образом, математическое ожидание количества циклов в произвольной перестановке n-элементного множества равно 1 + 1/2 +…+ 1/n, т.е. n-му гармоническому числу.

3.c.

При n = 1 в единственной перестановке множества M_n есть единственный цикл длины 1. При n = 2 возможные цикловые виды [1]-[1] и [2] встречаются одинаково часто (по одному разу).
Пусть n > 2.
Из предыдущих пунктов следует, что ровно (n-1)! перестановок представляют собой цикл длины n. Аналогично, цикловой вид [n-1]-[1] имеют n!/(n-1) перестановок. Т.е. их больше, чем длинных циклов. Покажем, что [n-1]-[1] и есть мода циклового вида.
В самом деле, легко видеть, что престановок циклового вида [n-1]-[1] больше, чем престановок циклового вида [n-k]-[k] при k и n-k, бОльших 1.
Пусть теперь n = a + b + c, где a >= b >= c. Тривиально показывается, перестановок вида [a+b]-[c] больше чем перестановок вида [a]-[b]-[c]. И т.д.

3.d.

i. Со случаем n/2 < k ≤ n мы разобрались в предыдущих пунктах. Искомая вероятность равна 1/k

ii. При n/3 < k ≤ n/2, разобрав случаи одного и двух циклов, получим искомую вероятность (2*k-1)/(2*k²).

iii. Для остальных случаев удобно воспользоваться формулой включения и исключения. При n/4 < k ≤ n/3 имеем (6*k²-3*k+1)/(6*k³).

iv. При n/5 < k ≤ n/4 имеем (24*k³-12*k²+4*k-1)/(24*k⁴).

4.a.

При возведении в степень k цикл длины m распадается на (k,m) циклов длины m/(k,m). Учитывая это соображение и количество подстановок каждого циклового вида в группах S_n при малых n можно получить следующие 20 значений s(n,k) (если значение получается при разных наборах значений n и k, указан один из таких наборов):

1 (при n = 1, k = 1)
2 (при 2 = 1, k = 1)
3 (при n = 3, k = 2)
4 (при n = 3, k = 3)
6 (при n = 3, k = 1)
9 (при n = 4, k = 4)
12 (при n = 4, k = 2)
16 (при n = 4, k = 3)
21 (при n = 5, k = 20)
24 (при n = 4, k = 1)
25 (при n = 5, k = 12)
36 (при n = 5, k = 10)
40 (при n = 5, k = 6)
45 (при n = 5, k = 4)
46 (при n = 6, k = 30)
56 (при n = 5, k = 15)
60 (при n = 5, k = 2)
80 (при n = 5, k = 3)
81 (при n = 6, k = 20)
96 (при n = 5, k = 5)

Обоснование того, что приведены наименьшие возможные значения можно посмотреть в :решении Влада Франка.

4.b.

Покажем, что q(9,3) = 1/2.
Для этого заметим, что в s(9,3), в отличие от S₉, нет перестановок с циклами, длины которых кратны 3, за исключением перестановок вида [3]-[3]-[3]. В S₉ Имеется:
девятиэлементных циклов - 8!;
перестановок, содержащих шестиэлементный цикл, - 9!/6;
перестановок с ровно двумя трехэлементными циклами, - C(9,3)*C(6,3)*2²*|s(3,3)|/2;
перестановок с ровно одним трехэлементным циклом, - C(9,3)*2*|s(6,3)|.
Учитывая, что |s(6,3)| = 400, |s(3,3)| = 4, и суммируя, получим 181440 = 9!/2.

Обсуждение

Любопытно, что большинство участников Марафона, получив рекуррентное соотношение для F(n), никоим образом не отреагировали, что это числа Фибоначчи.

Последовательность G(n) (как, разумеется, и F(n)) есть в онлайн-энциклопедии целочисленных последовательностей. Её номер A002524.

Применяя метод включения и исключения, можно получить общую формулу, выражающую вероятность наличия цикла длины k в S_n -
.

Любопытно, 21-е по величине значение |s(n,k)| получается при n = 8. Это |s(8,420)| = 106 (|s(7,210)| тоже равно 106).

С пунктом 4.b. не справился ни один участник. Это оказалось для меня неожиданным. Ведь подходящий пример возникает при совсем не запредельных n и k. Кстати, q(10,3) и q(11,3) тоже равны по 1/2.
Справедливо и более общее утверждение: q(n,k) ≤ q(n+1,k), причем это неравенство трансформируется в равенство всякий раз, когда (k,n+1) = 1.

Вызывает интерес доказательство (или опровержение) следующей гипотезы:
Для любых натурального k и положительного e найдется n такое, что q(n,k) < e.

Награды

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

Эстетическая оценка задачи - 5 баллов

---