Республиканская олимпиада по математике, 2011 год, 11 класс

Назовем квадратную таблицу бинарной, если в каждой ее клетке записано одно число $0$ или $1$. Бинарная таблица называется регулярной, если в каждой ее строке и в каждом столбце ровно по 2 единицы. Определите количество регулярных таблиц размером $n\times n$ ($n > 1$ — данное фиксированное натуральное число). (Можно считать, что строки и столбцы таблиц пронумерованы: случаи совпадения при повороте, отражения и т.п. считать различными). ( Д. Елиусизов )

Комментарий/решение

Для каждой бинарной регулярной таблицы рассмотрим двудольный граф $G$, $2n$ вершин которого олицетворяют столбцы и строки, мы будем соединять вершину-столбец с вершиной-строкой, если на пересечении соответствующих им строке и столбце написана $1$.

В каждом столбце и строке должно быть по две $1$, это значит что из каждой вершины исходит по 2 ребра. То есть необходимо посчитать количество циклов, проходящих через все вершины ровно по одному разу(при этом граф должен оставаться двудольным).

Представим цикл, как путь лягушки по вершинам, конец и начало которого приходятся на фиксированную вершину. Несложно понять, что есть ровно $n-i$ способов совершить $2i$ый по счёту ход, столько же способов для совершения $2i+1$го хода. Поэтому по правилу произведения количество возможных путей лягушки равно $n!(n-1)!$(для каждого хода от первого до $2n-1$го)

Осталось лишь учесть, что каждый цикл учитывается два раза, поскольку можно повторить тот же путь обратном порядке

Ответ: $\frac{n!(n-1)!}2$