02. Основные правила комбинаторики

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

Теорема 2.1. (Правило произведения). Если - конечные множества, то .

Пример. У Пети имеется 3 рубашки и 2 галстука. Он признаёт любое сочетание этих предметов. Сколькими способами Петя может надеть рубашку с галстуком?

Решение. Обозначим символом множество рубашек, . Обозначим символом множество галстуков, . Тогда декартово произведение множеств A и B есть множество всевозможных сочетаний рубашки и галстука:

Для ответа на вопрос задачи надо найти мощность множества . По теореме 2.1 Петя может надеть рубашку с галстуком способами. □

Частным случаем формулы включения и исключения (теорема 1.1) является следующая теорема.

Теорема 2.2. (Правило суммы). Если - конечные Попарно непересекающиеся множества, то .

Пример. Лекции по математике посещают 18 студентов, лекции по дискретной математике – 15 студентов. Сколько студентов посещают указанные лекции, если они проходят в одно время?

Решение. Обозначим символом множество студентов, посещающих лекции по математике, ; символом - множество студентов, посещающих лекции по дискретной математике, . Множество есть множество студентов, посещающих лекции или по математике, или по дискретной математике. По условию задачи лекции проходят одновременно, значит A и B – не пересекающиеся множества. По теореме 2.2 .□

Задачи и упражнения.

2.1. В теннисном клубе состоят 8 юношей и 10 девушек. Сколькими способами можно выбрать одного спортсмена, который будет представлять клуб на соревнованиях?

2.2. В теннисном клубе состоят 8 юношей и 10 девушек. Сколькими способами можно выбрать смешанную команду, которая будет представлять клуб на соревнованиях?

2.3. Из Череповца в Вологду можно добраться поездом и автобусом. Из Вологды в Тотьму можно добраться поездом, автобусом или теплоходом. Сколькими способами можно осуществить путешествие по маршруту Череповец – Вологда – Тотьма?

2.4. У Дюймовочки есть 5 юбочек, 6 блузочек и 3 шляпки. Она признаёт любое сочетание этих предметов. Сколькими способами Дюймовочка может выбрать наряд, состоящий из блузки, юбки и шляпки?

2.5. В отделе «Кофейник» продаются 8 различных чашек, 9 различных блюдец и 6 различных ложечек. Сколькими способами можно купить кофейный набор из чашки с блюдцем и ложечкой?

< Предыдущая		Следующая >