Перестановки и сочетания

Производя выборки из совокупности, важно знать, сколько выборок может быть сделано. Для этого мы должны, во-первых, решить влияет ли порядок отбора элементов на результат.

Перестановки: элементы совокупности идентифицированы и порядок, в кото­ром они отобраны имеет большое значение.

□ Пример 1.20. Из пяти букв — А, В, С, Д, Е — нужно составить как можно
больше трехбуквенных сочетаний.

Решение

На первое место можно поставить любую из пяти букв. Для второй позиции остаются вакантными четыре буквы, для третьей — три. Итак, для первых пяти вариантов существуют четыре вторых и три третьих буквы, т.е. общее число перестановок из трех букв равно:

5x4x3 = 60.

Иными словами, количество перестановок пять по три: 5 х 4 х 3 = 60. Возможны следующие сочетания:

■?Я Ч. 1. Принятие решений в условиях недостатка информации

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

Допустим, общее количество элементов п, нужно выбрать три. Тогда на первое место претендуют п элементов, на второе — (п—1), на третье — (п —2) элемента. Число перестановок составит п х (п - 1) х (п - 2). Однако этот метод получения формулы приемлем при выборе группы небольшого объема, в противном случае формула становится громоздкой.

Для краткости перестановка из п элементов по г обозначается как ^ПР_Г. Символ!, будучи помещенным после числа, указывает на факториал. Например:

61 = 6х5х4хЗх2х 1

или

10! = 10х9х8х7хбх5х4хЗх2х1.

В общем виде: n! = n х (п - 1) х (п - 2) х (п - 3) х... х 1.

Особо отметим, что 1! ™ 1 и по определению 01 ■ 1. С небольшими манипуля­циями факториал может использоваться для вычисления перестановок. Вернемся к примеру 1.20. Нужно подсчитать число перестановок из пяти по три. Мы нашли, что ⁵Р₃ = 5 х 4 х 3.

Можем переписать это следующим образом:

5,, _с. о 2x1 5x4x3x2 xl 5! Аналогично

n_D I 44 /- 1ч (П -3) X (П-4) X...X 1П|

Р_ч = п х (п - 1) х (п - 2) х \ ------- -± — I ----- -*-------- - =------- —-.

³ ' (п-3)х(п-4)х...х 1 (п-3)!

Так как мы не будем всегда отбирать по три элемента, то в общем виде эта формула выглядит так:

(п - г)1

Сочетания:

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

Гл. 1. Основы теории вероятностей 29

О Пример 1.21. Сколько существует ^-буквенных сочетаний из литер А, В, С, D, Е? Порядок букв в сочетании не важен.