41. Задача о ладьях

При решении задачи о ферзях основная Трудность состояла в отыскании хотя бы одного нужного Нам Расположения. В аналогичной задаче о ладьях трудность в ином (ладьи бьют по горизонталям и вертикалям). РаССтавить ладьи так, чтобы они не били друг друга, совсем ЛЕгко — достаточно выстроить ИХ по диагонали. ТруднеЕ Узнать, сколькими способами их можно расположить требуемым образом — вообще в одних комбинаторных Задачах трудно найти хотя бы одно решение, а в других решений много, а трудность состоит в их пересчете.

Итак, решим такую ЗАдачу: Найти число способов расстановки восьми ладей на шахматной доске, при которых они не бЬЮт друг друга.

Мы решим сразу более общую задачу:

СколЬКими способами можно расставить п ладЕЙ на -досКЕ, так, чтобы они не били друг Друга?

Каждый способ задается перестановкой П чисел 1, 2,..., П — Указываются номера горизонталей Занятых Полей на первой, второй,..., П-Й вертикалях. Но число таких перестановок равно П! Значит, ладьи можно расставить N! способами. При П = 8 получаем способов.

-доска состоит из одного поля. Поставить на нее одну лАДью можно единственным образом. Поэтому считают, что -доска совсем нЕ имеет поЛЕй, или, как говорят математики, имеет Пустое множество полей. «Поставить» на нее 0 ладей можно лишь одним способом — ничего никуда не ставить (в комбинаторике часто удобно считать и такие способы — иначе пришлось бы делать много лишних оговорок). Значит, надо положить 0! = 1. Возможно, читателя удивит Это равенство. Чтобы уменьшить его удивление, заметим, что для любого П верно соотношение (например, ). Полагая в нем П = 1, получаем, что , а потому . Если ЭТо рассуждение и не является доказательством (соотношение-то было Доказано лишь при П > 1), оно делает более естественным данное выше определение ДЛя 0!

< Предыдущая		Следующая >