Принципы сложения и умножения

Пусть Х – конечное множество, состоящее из n элементов. Тогда говорят, что объект х из Х можно выбрать n способами: . Пусть Х ₁, …, Х_k – попарно непересекающиеся множества. Тогда выполняется равенство

.

В комбинаторике этот факт называется правилом суммы. Для k =2 оно формулируется следующим образом:

Если объект х можно выбрать m способами, а объект у – другими n способами, то выбор “либо х, либо у ” можно осуществить m + n способами.

Другим часто применяемым в комбинаторике правилом является правило произведения.

Если объект х можно выбрать m способами и после каждого из таких выборов объект у в свою очередь может быть выбран n способами, то выбор “ х и у ” в указанном порядке можно осуществить mn способами.

Правило произведения также можно обобщить на случай нескольких (трех и более) объектов.