ГЛАВА II. РАЗВИТИЕ МЕТОДОВ ПЕРЕСЧЕТА

§ 11. Введение

Мы ознакомим теперь читателя с наиболее общим методом пересчета, который можно назвать «методом просеивания» или «комбинаторным просеиванием». Принцип его прост: с любым свойством можно связать его расщепление на некотором множестве А, в соответствии с которым А разбивается на две части: подмножество образованное элементами, обладающими свойством и образованное элементами, не обладающими свойством т. е. обладающими свойством 0. Выбирая свойства подходящим образом, можно последовательным просеиванием пересчитать подмножества с наложенными на них теми или иными ограничениями.

Эти методы давно известны, их можно найти в работах математиков Бернулли (XVIII век). Веком позже Сильва указал общие формулы просеивания (или пропускания через решето; в теории чисел этот метод известен под названием «решета Эратосфена»). Но только в работах выдающегося современного математика Пойа подобные методы оказались исключительно плодотворными.

Принцип просеивания применим не только к пересчету, но также к перечислению и оптимизации. Перечисление с помощью латинских прямоугольников — метод, который осуществляет исключение путем разделения. Оптимизация по методу «ветвления и ограничения» и принцип оптимальности Беллмана — Понтрягина также находятся в рамках этих понятий. В последующих главах общность этих методов проявится более четко.