Спирина, М.С. Дискретная математика

Правило произведения. Правило декартова произведения м но ­ жеств (см. подразд. 1.5) можно распространить и на комбинатори­ ку: если элемент а можно выбрать к способами, а элемент р — т способами, то пару (а, Р) можно выбрать к ■т способами. Так как в декартово произведение входят и элементы первого, и элементы второго множества, то при решении задач важно п о ­ мнить ключевое слово и. Задача 2. В колледже есть три варианта занятий по интересам: творческие объединения (ТО), спортивные секции (СС) и науч­ ное студенческое общество (НСО). Каждое направление содержит по четыре вида коллективов: ТО — театральный, музыкальный, танцевальный и КВН; СС — легкая атлетика, лыжи, спортивные игры и плавание. В состав НСО входят естественно-математиче­ ское, гуманитарное, техническое и информационное направле­ ния. Сколькими способами студенты могут разнообразить свой досуг в колледже после занятий, выбрав коллектив по интересам? Решение. Так как надо учесть и три основных направления, и то, что в каждом из них по четыре коллектива, то для подсчета общего числа вариантов их нужно перемножить: п(А) - 3, п(В) = 4, п ( А х В ) = п(А) ■п(В) = 3 • 4 = 12. Частным случаем правила произведения является число разме­ щений с повторениями Акт = тк для подсчета кортежей длины к, составленных из элементов множества X, мощность которого т. Если п(Х) - т, то п ( Х х X х . . . х Х ) - (п(Х))к =тк. к Перестановки. Рассматривая различные подмножества множе­ ства X, состоящего из п элементов, выделим три принципиально разных вида задач для подсчета числа элементов подмножеств. • Сколькими способами можно переставлять элементы множе­ ства, чтобы получить различные кортежи длины л? • Сколькими способами из всего множества можно выбрать различные кортежи (упорядоченные подмножества) длиной т (т < л)? • Сколькими способами из всего множества можно выбрать различные подмножества длиной т (т < л)? Для решения первой задачи необходимо найти число переста­ новок длины л. Упорядоченные множества (кортежи), состоящие из л различ­ ных элементов, называются перестановками (без повторений). Их число обозначается Рп. Фактически эту задачу можно заменить з а ­ дачей расфасовки л шаров разного цвета в ящик с л свободными местами. Для определения числа полученных кортежей длины л исполь­ зуем правило произведения. Первый из л элементов можно поста­ вить на л свободных позиций, для второго элемента (при фикси ­ 47