logo
КЛ

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

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

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

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

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

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

Ø , ,

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

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

Пусть

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

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

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

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

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

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

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

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

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

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

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

Пусть

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

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

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

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

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

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

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

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

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

■