Комбинаторика на Турломе: графы, игры, клетчатые задачи, Дирихле

Через будем обозначать объединение множеств, которые попарно не пересекаются.

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

Таким образом, по сути — количество троек таких, что и

______________________________________________________________________________________________________________________________________________________

Мысль 1. Начнём решение с простого, но важного наблюдения: если то

т.е. если представлено в виде объединения двух непересекающихся множеств, то все тройки, соответствующие способам выбрать и очевидно, разбиваются на тройки по тому, откуда берётся — из или

В частности,

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

______________________________________________________________________________________________________________________________________________________

Мысль 2. Для любых выполнено (а, значит, и Для этого достаточно проверить, что тогда и только тогда, когда Проследим за судьбой какого-то числа при подстановке в Под действием пусть переходит в Тогда Но тогда

Поскольку пока пробегает все числа от до число также пробегает все эти числа, утверждение остаётся верным.

_________________________________________________________________________________________________________________________________________________________________________________

Теперь у нас есть все, чтобы решить задачу. Ранее мы показали, что и Тогда

Используя и получаем, что последнее равно