|
|
 |
Условие
К Ивану на день рождения пришли $3 n$ гостей. У Ивана есть $3 n$ цилиндров с написанными сверху буквами А, Б и В, по $n$ штук каждого типа. Иван хочет устроить бал: надеть на гостей цилиндры и выстроить их в хороводы (один или больше) так, чтобы длина каждого хоровода делилась на $3$, а при взгляде на любой хоровод сверху читалось бы по часовой стрелке АБВАБВ...АБВ. Докажите, что Иван может устроить бал ровно $(3n)!$ различными способами. (Цилиндры с одинаковыми буквами неразличимы; все гости различны.)Решение
Первое решение. Разобьём всех гостей на упорядоченные тройки; первому человеку из тройки наденем цилиндр с буквой А, второму — с буквой Б, третьему — с буквой В. Для этого поставим гостей в шеренгу (это можно сделать $(3n)!$ способами), первых трёх объединим в одну тройку, вторых трёх — в другую и т.д. Поскольку тройки можно переставлять внутри шеренги и получать то же самое разбиение на тройки, то каждое разбиение посчитано $n!$ раз. Таким образом, количество способов разбить гостей на упорядоченные тройки равно $(3n)! / n!$.Теперь для того, чтобы разбить гостей на хороводы, достаточно разбить на хороводы первых $n$ человек из своих троек (эти хороводы могут состоять из одного человека), а затем поставить после каждого человека его тройку, что можно сделать единственным образом. Докажем индукцией по $n$, что количество способов сделать это равно $n!$, что завершит решение.
База для $n = 1$ очевидна. Пусть утверждение верно для $n$, докажем его для $n + 1$. Расставим $n$ человек в хороводы, это можно сделать $n!$ способами. В каждом разбиении на хороводы $n$ человек есть ровно $n + 1$ место, куда можно поставить оставшегося человека: в каждом существующем хороводе из $k$ человек таких мест ровно $k$, а ещё можно выделить этого человека в новый хоровод.
Замечание. Последнее рассуждение можно упростить, если заметить, что каждое разбиение на хороводы соответствует перестановке на множестве из $n$ элементов, представленной в форме циклов, а количество перестановок, как известно, равно $n!$.
Второе решение. Занумеруем людей числами от $1$ до $3n$. Есть как раз $(3n)!$ способов расставить этих людей в ряд, поэтому достаточно установить взаимно однозначное соответствие между такими расстановками и разбиениями на хороводы.
Возьмём любую расстановку, наденем всем цилиндры в порядке АБВАБВ...АБВ слева направо. Мысленно разделим людей подряд на $n$ троек. В первый хоровод берём подряд всех людей от начала и до той тройки включительно, где стоит человек с номером $1$ (и замыкаем в хоровод); во второй хоровод берём следующие тройки подряд до той включительно, где стоит человек с наименьшим из оставшихся номеров (и замыкаем в хоровод), и так далее.
Обратно, по набору хороводов легко восстановить расстановку: берём хоровод, где стоит человек $1$, находим тройку AБВ, в которой он находится, «разрезаем» хоровод сразу за этой тройкой, вытягиваем в линию и ставим в начало расстановки. Далее берём человека с наименьшим номером из оставшихся, находим «его» хоровод, так же разрезаем и подсоединяем к расстановке и т.д.
