Глава V. Некоторые теоремы о перечислении

Часто говорят, что в основе всех математических действий лежит счет. Великий немецкий математик Герман Вейль как-то сказал, что почти за всеми тождествами математики кроется один неизменный принцип: если двумя разными способами пересчитать одни и те же вещи, то результат окажется одним и тем же.

В предыдущих главах мы часто задавались вопросом о том, сколькими способами можно расположить элементы заданного вида в пределах определенной "доски" или рисунка. И в этой книге, и в математике вообще часто задаются схожим вопросом о числе объектов, обладающих заданными свойствами, например о числе геометрических конфигураций данного типа (мы здесь считаем, что таких конфигураций существует лишь конечное число). Все задачи такого рода называются задачами перечисления; наряду с комбинаторной геометрией, к которой по тематике относится данная книга, они рассматриваются в разделе математики, носящем название комбинаторного анализа. Комбинаторный анализ изучает различные способы подсчета количества всевозможных комбинации чисел или других объектов, обладающих заданными свойствами^*. В последнее время интерес к этому разделу науки повысился, что вызвано все возрастающей ролью электронных вычислительных машин в решении технических задач. Комбинаторный анализ находит множество приложений в таких современных областях науки, как проектирование электрических цепей, передача кодированных сообщений, регулирование транспортных потоков, кристаллография и теория вероятностей.

^* (Ср. с гл. II книги: Ф. Мостеллер, Р. Рурке, Дж. Томас, Вероятность, М., изд-во "Мир", 1969; см. также рассчитанную на учащихся средней школы книгу: Н. Я. Виленкин, Комбинаторика, М., изд-во "Наука", 1969.)

Настоящая глава призвана ввести читателя в комбинаторный анализ, точнее, в ту его часть, которая занимается проблемой перечисления (или подсчета). Несмотря на то что этот материал окажется более трудным и потребует от вас большей концентрации внимания, чем материал предыдущих глав, его изучение полезно, причем не только с точки зрения лучшего понимания последующего. Гораздо важнее другое: проработав материал этой главы, вы впоследствии не встретите затруднений в решении многих задач аналогичного типа, где бы они вам ни попадались. Для тех же, кто предпочтет ограничиться лишь развлекательным аспектом связанных с полимино проблем, рекомендуем опустить эту главу и перейти к более интересному для них материалу последующих глав.