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

Элементы комбинаторики. Правила комбинаторики

Часто приходится иметь дело с задачами, в которых нужно подсчитать число всех возможных способов осуществления некоторого действия или благоприятствующих исходов для некоторого события. Такого рода задачи называют комбинаторными.

Например:

Пример 1. Найти число всевозможных двузначных чисел, составленных из цифр 1, 2, 3, причем цифры не должны повторяться:

12, 13, 21, 23, 31, 32 – 6 чисел

Пример 2. Найти число всевозможных трехзначных чисел, составленных из цифр 1, 2, 3, причем цифры не должны повторяться.

Для этого надо к каждому числу из примера 1 добавить недостающую цифру

123, 132, 213, 231, 312, 321 – 6 чисел

Пример 3. Даны четыре точки, никакие три из которых не лежат на одной прямой. Провести через каждую пару точек прямые. Найти их число.

Так как прямая определяется двумя точками, то их столько, сколько пар различных чисел можно составить из чисел 1, 2, 3, 4, причем пары (1,2) и (2,1) определяют одну и туже прямую.

(1,2), (1,3), (1,4), (2,3), (2,4), (3,4) – 6 прямых.

Для всех объектов, рассматриваемых в комбинаторных задачах характерно то, что они содержат конечное число элементов.

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

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

Рассмотрим два подхода к определению правила – теоретико-множественный и комбинаторный:

1) Обозначим через N(A) – число элементов во множестве А. Тогда число элементов в объединении находят по формуле

(1)

Формулу (1) можно легко обобщить на случай трех слагаемых:

(2)

Пример 4. Каждый ученик класса – либо девочка, либо блондин, либо любит математику. В классе 20 девочек, из них 12 блондинок и одна любит математику. Всего в классе 24 ученика – блондина, математику из них любят 12, а всего учеников (мальчиков и девочек), которые любят математику –17, из них 6 девочек. Сколько учеников в данном классе?

Решение: Обозначим А – множество девочек класса, В – множество блондинов, С – учеников, которые любят математику. Тогда - искомое число. - множество блондинок, - девочки-математики, -блондины, которые любят математику, - множество блондинок-математиков. Из условия задачи следует, что: , , , . Применяя формулу (2), получим:

= 20+24+17-12-6-12+1 = 32

Если множества А, В, С не пересекаются, то формулы (1) и (2) соответственно примут вид:

2) На языке комбинаторики правило суммы можно сформулировать так: Если некоторый объект X можно выбрать n способами, а объект Y - m способами, то объект «X или Y» можно выбрать m+n способами.

По индукции правило можно распространить на любое количество слагаемых.

Пример 5. На книжной полке стоят 10 книг по математическому анализу, 4 – по алгебре и 6 по геометрии. Сколькими способами можно выбрать одну книгу по математике: N = 10+4+6 = 20.

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

Пусть имеется k-множеств: Х₁, Х₂, … , Х_k. Любой упорядоченный набор

где

назовем кортежем длины к. Совокупность всевозможных кортежей, которые можно составить и элементов множеств Х₁, Х₂, … , Х_к называется декартовым или прямым произведением и обозначается . Имеет место теорема:

Теорема 1. Число элементов в декартовом произведении нескольких множеств равно произведению числа элементов в каждом множестве, т.е.

Сформулируем теорему применительно к задачам комбинаторики. Назовем выборкой любое подмножество, которое выделяется из данного множества. Тогда:

Теорема 2. Пусть имеется r переменных, каждая из которых принимает значения независимо друг от друга. Пусть

1-ая переменная принимает n₁ значение;

2-ая переменная принимает n₂ значений;

… … … …

r-ая переменная принимает n_r значений.

Составим выборки значений данных переменных так, чтобы каждая выборка определялась конкретным значением каждой переменной. Тогда число всевозможных выборок из r переменных равно:

Следствие: Число всевозможных выборок значений r переменных, каждая из которых принимает n значений равно .

Примеры:

1) Сколько всевозможных трехзначных чисел можно составить из цифр множества А=(1,2,3,4,5) так, чтобы:

а) цифры не повторялись;

б) цифры могут повторяться;

Решение: Запишем трехзначное число в систематической форме

Имеем три переменных величины, каждая из которых принимает значения из множества А. Тогда:

а) ; .

б) ; .

2) В комнате 10 ламп. Найти число способов освещенности комнаты.

Решение: Применим следствие из теоремы 2 - каждую лампочку можно рассматривать как переменную величину, принимающую только два значения (горит или не горит). Таких величин 10. Тогда число способов освещенности равно 2¹⁰ = 1024.

Замечание: Часто бывает удобно использовать следующую формулировку теоремы произведения для n = 2:

Если некоторый объект А можно выбрать n способами, а объект В – m способами, то объект «А и В» можно выбрать способами.