Условие
На клетчатой доске 11×11 отмечено 22 клетки так, что на каждой вертикали и на каждой горизонтали отмечено ровно две клетки. Два расположения отмеченных клеток эквивалентны, если, меняя любое число раз вертикали между собой и горизонтали между собой, мы из одного расположения можем получить другое. Сколько существует неэквивалентных расположений отмеченных клеток?
Решение
Рассмотрим двудольный граф, вершинами которого являются строки и столбцы данной доски, причём строка и столбец соединены ребром тогда и только тогда, когда клетка на их пересечении отмечена. Заметим, что перестановки строк и перестановки столбцов исходной таблицы соответствуют перенумерациям вершин в каждой из долей получившегося графа. Это значит, что эквивалентным расположениям соответствуют изоморфные графы, а неэквивалентным – неизоморфные. Таким образом, число неэквивалентных расположений отмеченных клеток равно числу неизоморфных графов, соответствующих каким-нибудь расположениям.
Посмотрим, какие графы соответствуют каким-нибудь расположениям отмеченных клеток. Во-первых, в каждой доле этого графа должно быть по 11 вершин (доля строк и доля столбцов). Во-вторых, степень каждой вершины равна 2, а значит, граф распадается на циклы. Так как граф двудольный, то длины этих циклов чётны. Кроме того, так как в графе нет кратных рёбер, то длина каждого такого цикла не меньше четырёх. Изоморфизм двух таких графов равносилен совпадению у них набора длин циклов. Следовательно, искомое число равно количеству представлений числа 22 в виде суммы чётных слагаемых, каждое из которых не менее четырёх (суммы, отличающиеся лишь порядком слагаемых, считаются одинаковыми), то есть количеству представлений числа 11 в виде суммы слагаемых, каждое из которых не меньше 2. Выписав все эти представления, можно убедиться, что их ровно 14.
Ответ
14 расположений.
Источники и прецеденты использования
