Общие правила комбинаторики

Комбинаторные задачи бывают самых разных видов. Но большинство задач решается с помощью двух основных правил – правила суммы и правила произведения.

Правило суммы: если некоторый объект А можно выбрать способами, а другой объект В можно выбрать способами, то выбор «либо А, либо В» можно осуществить способами.

При использовании правила суммы в последней формулировке надо следить, чтобы ни один из способов выбора объекта А не совпадал с каким-нибудь способом выбора объекта В (или, как мы говорим, чтобы ни одна комбинация не попала сразу в два класса). Если такие совпадения есть, правило суммы утрачивает силу, и мы получим лишь способов выбора, где - число совпадений.

Правило произведения: если объект А можно выбрать способами и если после каждого такого выбора объект В можно выбрать способами, то выбор пары (А, В) в указанном порядке можно осуществить способами.