Размещения

ВВЕДЕНИЕ В ТЕОРИЮ ВЕРОЯТНОСТЕЙ

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

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

Например, у множества, состоящего из четырех элементов 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.

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

Размещения

Определение. Пусть имеется множество, содержащее 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 различных предметов?

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