Правила суммы и произведения

Основной комбинаторной задачей является подсчет числа (п, r)-выборок при различных условиях. Практический опыт таких подсчетов привел к двум логическим правилам.

Правило суммы

Теоретико-множественная формулировка.

Если даны п-множество М₁ (т.е. |М₁| = n) и т-множество М₂, то при Ø объединение будет (п + т)-множеством.

В более общем случае. Если

Ø , ,

и если М_i есть п_i-множество, то множество М есть -множество.

Комбинаторная формулировка.

Пусть

объект a₁ может быть выбран т₁ способами ;

объект а₂ может быть выбран т₂ способами ;

………………………………………………………..

объект а _k может быть выбран т _k способами .

Тогда выбор объекта а₁ , либо объекта а₂ , … , либо объекта а _k может быть осуществлен т₁ + т₂ + … + т _k способами.

Пример. Фирма направляет специалиста в командировку в другой город, в который в течение суток отправляются 6 поездов, 4 автобуса и 1 самолет. Сколько существует способов добраться до этого города ?

□ По правилу суммы всего существует 6+4+1=11 способов выехать в назначенный город. ■

Правило произведения

Теоретико-множественная формулировка.

Пусть М₁, М₂, … , М _k - конечные множества , М = - их декартово произведение, тогда =

Комбинаторная формулировка.

Пусть

объект а₁ выбирается т₁ способами ;

и после такого выбора

объект а₂ выбирается т₂ способами ;

………………………………………………

и после таких выборов

объект а _k выбирается т _k способами .

Тогда выбор упорядоченного множества объектов может быть осуществлен способами.

Пример. На дискотеку пришли 3 девушки и 2 юноши. Сколько танцующих пар они могут составить ( не одновременно ) ?

□ По правилу произведения можно составить 2 пар. Решение можно представить в виде диаграммы (графа), иллюстрирующего декартово произведение множеств :

■