Комбинаторика на ИТМО: способы, графы, логика, клетки, комбигео

Будем расставлять в таблицу нули и единицы. Каждый можно поставить четырьмя способами, а — пятью. Заметим, что в каждой строчке чётное количество единиц, потому единиц суммарно в таблице может быть ( быть не может, поскольку в каждой строчке не более двух). Также заметим, что двух единиц быть не может, поскольку тогда бы они стояли в одной строчке и их было бы по одной в столбце. Разберём остальные случаи

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