В клетчатом квадрате 4 × 4 нужно поставить 5 крестиков так, чтобы в каждой строке и каждом столбце был хотя бы один крестик. Сколько способов это сделать?
Решение.
Из условия следует, что в какой-то строке a и в каком-то столбце b по два крестика (а в остальных строках и столбцах — по одному). И строка a, и столбец b выбираются 4 способами. Далее возможны два случая.
Первый. На пересечении a и b стоит крестик. Ещё по одному крестику из каждой линии выбираем 3 способами. Теперь остались незанятыми две строки и два столбца. На их пересечении оставшиеся крестики расставляются двумя способами. Итак, расстановок первого типа
Второй. На пересечении a и b нет крестика. Тогда по два крестика из каждой из этих двух линий выбираем тремя способами. Теперь остались незанятыми только одна строка и один столбец, на пересечении которых нужно поставить крестик. Итак, расстановок второго типа Всего получается вариантов расстановки 5 крестиков.
Всего получается 
вариантов расстановки 5 крестиков.