72

Введение в теорию вероятностей

§ 1. Элементы комбинаторики

Определение. Если подмножества, отличающиеся только порядком следования элементов считаются различными, то говорят об упорядоченных подмножествах. В противном случае прилагательное «упорядоченные» опускают.

Например, у множества, состоящего из четырех элементов a, b, c, d имеется 4 трехэлементных подмножества:

abc, abd, bcd, acd

и 24 трехэлементных упорядоченных подмножества:

abc, abd, acd, bcd,

acb, adb, adc, bdc,

bac, bad, cad, cbd,

bca, bda, cda, cdb,

cab, dab, dac, dbc,

cba, dba, dca, dcb.

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

1. Размещения

Определение. Пусть имеется множество, содержащее n элементов. Каждое упорядоченное подмножество, состоящее из k элементов, называется размещением из n элементов по k элементов.

Поскольку n ≥ k ≥ 0, и размещения из n элементов по k элементов – это все k элементные подмножества, отличающиеся составом элементов или порядком их следования.

Для множества, состоящего из 4-х элементов a, b, c, d, все размещения по 3 элемента были рассмотрены выше (их оказалось 24), они отличаются друг от друга либо составом элементов, либо порядком их расположения.

В комбинаторных задачах необходимо уметь подсчитывать число всех размещений из n элементов по k элементов. Для обозначения этого числа применяется специальный символ:

- число размещений из n по k.

А – первая буква французского слова arrangement, что означает размещение, приведение в порядок. Следовательно,

Очевидно, что так как существует только одно подмножество n-элементного множества, не содержащее элементов (пустое множество).

В общем случае на вопрос о числе размещений из n элементов по k элементов дает ответ следующая формула:

или

Таким образом,

Примеры.

1. Вычислить .

Решение:

2. На втором курсе изучается 14 предметов. Сколькими способами можно составить расписание занятий в субботу, если в этот день недели должно быть 5 различных предметов?

Решение: различных способов составления расписания, очевидно, столько, сколько существует пятиэлементных упорядоченных подмножеств у четырнадцатиэлементного множества, т.е.

2. Перестановки

Определение. Размещения из n элементов по nэлементов называются перестановками из n элементов.

Перестановки являются частным случаем размещений. Число перестановок из n элементов обозначают через Р_n. Р – первая буква французского слова permutation – перестановка.

Исходя из вышеизложенного, .

Примеры.

1. Установить n, если

Решение. решая квадратное уравнение получаем n = 11.

2. Сколько шестизначных чисел, кратных пяти, можно составить из цифр 1, 2, 3, 4, 5, 6 при условии, что в числе цифры не повторяются.

Решение. для того, чтобы число, составленное из заданных цифр делилось на 5, необходимо и достаточно, чтобы цифра 5 стояла на последнем месте. Остальные пять цифр могут стоять на оставшихся пяти местах в любом порядке. Следовательно, искомое число шестизначных чисел, кратных пяти, равно