Loading [MathJax]/jax/output/SVG/jax.js

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


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

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

пред. Правка 2   0
1 года 9 месяца назад #

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

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

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

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

Ответ: n!(n1)!2