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

Рассмотрим такую задачу. Пусть из пункта А города Киева в пункт В можно доехать тремя видами транспорта: ((Т) троллейбус, (А) автобус и (М) метро), а из пункта В в пункт С - только двумя видами транспорта: ((Т) троллейбус и (А) автобус). Сколькими способами можно доехать из пункта А в пункт С города Киева? Решение этой задачи сводится, очевидно, к подсчету числа элементов в декартовом произведении множеств {А, Т, М} х {А, Т}. Число таких элементов, как мы знаем, равно произведению числа элементов перво­го множества на число элементов второго множества, т. е. в нашем случае это 3*2 = 6. Следовательно, существует шесть способов доехать из пункта А в пункт С. Оказывается, что за этой простой задачей стоит правило, которое называется основным правилом комбинаторики.

Пусть необходимо выполнить последовательно k действий. Если первое дей­ствие можно выполнить n₁ способами, второе – n₂ способами и так далее до k-го действия, которое можно выполнить n_k способами, то все k действий можно выполнить n₁*n₂*…*n_k способами.

Пример1:

Сколькими способами на первенстве мира по футболу могут распределиться медали, если в финальной части играют 24 команды? Решение. Золотую медаль может получить любая из 24 команд, т. е. имеем 24 возможности. Серебряную медаль может выиграть одна из 23 команд, а бронзовую - одна из 22 команд. По основному правилу комбинаторики общее число способов распределения медалей 24 . 23 . 22 = 12 144.

Пример 2:

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

Цифры могут повторяться.

Решение. Первой цифрой может быть одна из цифр 1,2,3,4,5, по­скольку 0 не может быть первой цифрой, ибо в таком случае число не будет трехзначным. Если первая цифра выбрана, то вторая может быть выбрана шестью способами, как и третья цифра. Следователь­но, общее число трехзначных цифр 5*6*6 = 180.

Ни одна из цифр не повторяется дважды.

Решение. Первой цифрой может быть одна из пяти цифр - 1,2, 3, 4, 5. Если первая цифра выбрана, то второй может быть также одна из пяти цифр (тут уже учитывается 0), а третья может быть выбрана четырьмя способами из четырех цифр, что остались. Следовательно, общее количество таких трехзначных чисел 5*5*4 = 100.

Цифры нечетные и могут повторяться.

Решение. Первой цифрой может быть одна из трех цифр: 1, 3, 5. Второй тоже может быть одна из этих трех цифр. Аналогично и тре­тья цифра может быть выбрана тремя способами. Таким образом, общее количество таких чисел равняется 3*3*3 = 27.

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

Пусть А и В – непустые множества такие, что и . Тогда . Определение: Если элемент можно выбрать m способами, а элемент – n способами, то выбор элемента можно осуществить m+n способами.

Пусть X₁,X₂,…,X_k – попарно непересекающиеся множества, , где , тогда очевидно выполняется неравенство .

5.3. Правило прямого произведения

Пусть А и В – конечные множества, и , тогда

Определение: Если элемент можно выбрать m способами и если элемент

можно выбрать n способами, то выбор пары в указанном порядке можно осуществить способами. В этом случае говорят, что выбор элементов множества А не зависит от способа выбора элементов множества В. Пусть теперь X₁,X₂,…,X_k – произвольные множества, . Тогда

.

Пример:

Найти число маршрутов из пункта М в пункт N через пункт К, если из М в К ведут 5 дорог, а из К в N – 3 дороги.

Решение: Введём два множества: – дороги из М в K, – дороги из K в N можно представить парой (s_i,t_j) где i=1,2,3,4,5; j=1,2,3. Значит, – это множество всех дорог из М в N, количество которых равно .