Общие правила комбинаторики
Комбинаторные задачи бывают самых разных видов. Но большинство задач решается с помощью двух основных правил – правила суммы и правила произведения.
Правило суммы: если некоторый объект А можно выбрать 
способами, а другой объект В можно выбрать 
способами, то выбор «либо А, либо В» можно осуществить 
способами.
При использовании правила суммы в последней формулировке надо следить, чтобы ни один из способов выбора объекта А не совпадал с каким-нибудь способом выбора объекта В (или, как мы говорим, чтобы ни одна комбинация не попала сразу в два класса). Если такие совпадения есть, правило суммы утрачивает силу, и мы получим лишь 
способов выбора, где 
- число совпадений.
Пример 1. Из 12 слов мужского рода и 9 слов женского рода надо выбрать одно слово либо мужского, либо женского рода. Сколькими способами можно это сделать?
Р е ш е н и е. По условию задачи 
. По правилу суммы 
(способов).
Правило произведения: если объект А можно выбрать способами и если после каждого такого выбора объект В можно выбрать способами, то выбор пары (А,В) в указанном порядке можно осуществить 
способами.
Пример 2. Из 12 слов мужского рода и 9 слов женского рода надо выбрать по одному слову каждого рода. Сколькими способами это можно сделать?
Р е ш е н и е. По условию задачи .По правилу произведения 
(способами).
Соединения в комбинаторике
Различные группы, составленные из каких-либо предметов и отличающиеся одна от другой или порядком этих предметов, или самими предметами, называются соединениями.
Предметы, из которых составляются соединения, называются элементами. Элементы обозначаются буквами 
.
Соединения могут быть трёх видов: размещения, перестановки, сочетания без повторений и с повторениями.
Рассмотрим каждый из видов в отдельности.
Размещения без повторений
Определение. Размещениями из 
элементов по 
называются такие соединения, каждое из которых содержит элементов, взятых из данных элементов, и которые отличаются одно от другого или элементами, или порядком элементов и обозначается 
.
Другими словами, если две выборки, отличающиеся только порядком записи символов, считают различными, то говорят о размещении из m элементов по k.
Пусть дано 
элементов: 
. Сначала составим из них все размещения по 1.
Их, очевидно, будет . Значит, 
.
Теперь составим все размещения по 2. Для этого к каждому из ранее составленных размещений по 1 приставим последовательно все оставшиеся 
элементов по 1. Так, к элементу 
приставим последовательно оставшиеся элементы: 
; к элементу 
приставим последовательно оставшиеся элементы: 
и т.д. Получим следующие размещения по 2:
| m строк |
Так как всех элементов , то из каждого размещения по одному элементу мы получим размещений по 2, а всего их будет 
. Значит, 
.
Чтобы составить размещения по 3, берём каждое из составленных сейчас размещений по 2 и приставим к нему последовательно по одному все 
оставшихся элементов. Тогда получим следующие размещения по 3:
| m(m-1) строк |
Так как число всех размещений по 2 равно m(m-1) и из каждого получается m-2 размещения по 3, то всех таких размещений окажется: m(m-1)(m-2). Таким образом 
. Подобно этому получим: 
, и вообще:
Числитель и знаменатель умножим на произведение 
.
Пример 3. Сколькими способами можно составить трёхцветный полосатый флаг, если имеется 5 полос различных цветов?
Р е ш е н и е. 
.