Схемы и методы комбинаторики

Основные правила перечисления

Предметом комбинаторики являются перечислительные задачи, т. е. подсчет числа: элементов какого-либо множества, объектов с заданными свойствами и пр. Подмножества множества X в комбинаторике часто называют выборками из X. Для подсчета числа различных выборок с заданными свойствами используются следующие правила.

Правило суммы, если число различных выборок со свойством 1 равно щ, и число различных выборок со свойством 2 равно п₂, и все выборки не обладают свойствами 1 и 2 одновременно, то число различных выборок со свойством 1 или со свойством 2 равно п_х + п₂.

Правило произведения: если число различных выборок из X со свойством 1 (из Y со свойством 2) равно п_х (равно п₂), где свойства 1 и 2 могут совпадать, то число различных пар из X х Y таких, что первая выборка пары обладает свойством 1 и вторая выборка нары обладает свойством 2, равно п_хп₂.

Пример 1.5.

Правило суммы. В классе число «отличников» равно 5, число «хорошистов» равно 10. Тогда число школьников, учащихся не ниже, чем на «четыре», равно 15.

Правило произведения и его обобщение, а) Число пар, составленных из «отличника» и «хорошиста», равно 50; б) поскольку число 6-значных телефонных номеров равно 10⁶, то число 7-значных телефонных номеров, не начинающихся с «нуля», равно 910⁶; в) число строк длины п, состоящих из «нулей» и «единиц», равно 2″. >