Математикадан республикалық олимпиада, 2010-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$