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

 

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

.

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

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

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

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

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