1.7. ПЕРЕСТАНОВКИ И СОЧЕТАНИЯ

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

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

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

Решение

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

Иными словами, количество перестановок пять по три: Возможны следующие сочетания:

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

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

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

или

В общем виде:

Особо отметим, что и по определению . С небольшими манипуляциями факториал может использоваться для вычисления перестановок. Вернемся к примеру 1.20. Нужно подсчитать число перестановок из пяти по три. Мы нашли, что

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

Аналогично

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

Сочетания:

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

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

Решение.

Вернувшись к решению примера 1.20, видим, что в каждом ряду, в строке перестановок использованы одни и те же буквы. Каждый ряд представляет возможные комбинации из трех букв. Количество комбинаций из 5 букв, взятых по 3, равно 10. Отметим, что число перестановок трех букв равно:

Обозначив число комбинаций из 5 элементов, взятых по получим:

Итак, что же получится если обобщить решение этой задачи, каково число комбинаций элементов, взятых по 3 за раз?

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