Учебная работа № 1709. Комбинаторные формулы
Пусть имеется множество, состоящее из n элементов. Обозначим его . Перестановкой из n элементов называется заданный порядок во множестве
Примеры перестановок:
1)распределение n различных должностей среди n человек;
2)расположение n различных предметов в одном ряду.
Сколько различных перестановок можно образовать во множестве
Чтобы вывести формулу числа перестановок, представим себе n ячеек, пронумерованных числами
Pn = n(n – 1)(n – 2)…×3×2×1
Число n(n – 1)(n – 2)…×3×2×1, то есть произведение всех натуральных чисел от 1 до n, называется «nфакториал» и обозначается n! Отсюда Pn =n!
По определению считается: 1!=1; 0!=1.
Пример. Сколько существует вариантов замещения 5ти различных вакантных должностей 5ю кандидатами?
Размещениями из n элементов по k элементов будем называть упорядоченные подмножества, состоящие из k элементов множества
Одно размещение из n элементов по k элементов может отличаться от другого как набором элементов, так и порядком их расположения.
Примеры задач, приводящих к необходимости подсчета числа размещений
1) Сколькими способами можно выбрать из 15 человек 5 кандидатов и назначить их на 5 различных должностей?
2) Сколькими способами можно из 20 книг отобрать 12 и расставить их в ряд на полке?
В задачах о размещениях полагается k<n. В случае, если k=n, то легко получить
Для подсчета
n–(k–1) (или n–k+1) способами. Таким образом, все k ячеек заполняются числом способов, равным
Отсюда получаем:
Пример. Сколько существует различных вариантов выбора 4х кандидатур из 9ти специалистов для поездки в 4 различных страны?
Сочетаниями из n элементов по k элементов называются подмножества, состоящие из k элементов множества
Одно сочетание от другого отличается только составом выбранных элементов (но не порядком их расположения, как у размещений).
Число сочетаний из n элементов по k элементов обозначается
Примеры задач, приводящих к подсчету числа сочетаний:
1) Сколько существует вариантов выбора 6ти человек из 15 кандидатов для назначения на работу в одинаковых должностях?
2) Сколькими способами можно из 20 книг отобрать 12 книг?
Выведем формулу для подсчета числа сочетаний. Пусть имеется множество
1) выделим какиелибо k элементов из n элементов множества
2) упорядочим выделенные k элементов, что можно сделать
Пример: 6 человек из 15 можно выбрать числом способов, равным
Несложно понять, что осуществить выбор подмножества из т элементов множества, насчитывающего п элементов, можно, выбрав п–т элементов, которые не войдут в интересующее нас подмножество. Отсюда следует свойство числа сочетаний
Эту формулу можно доказать, используя формулу (1).
Задачи на подсчет числа подмножеств конечного множества называются комбинаторными. Рассмотрим некоторые комбинаторные задачи.
1.Из семи заводов организация должна выбрать три для размещения трех различных заказов. Сколькими способами можно разместить заказы?
Так как из условия ясно, что каждый завод может либо получить один заказ, либо не получить ни одного, и что выбрав три завода, можно поразному разместить среди них заказы, здесь нужно считать число размещений
3.Имеются 7 заводов. Сколькими способами организация может разместить на них три различных производственных заказа? (Заказ нельзя дробить, то есть распределять его на нескольких заводах).
В отличие от условия первой задачи, здесь организация может отдать все три заказа первому заводу или, например, отдать два заказа второму заводу, а один седьмому.
Задача решается так. Первый заказ может быть помещен семью различными способами (на первом заводе, на втором и т.д.). Поместив первый заказ, имеем семь вариантов помещения второго (иначе, каждый способ помещения первого заказа может сопровождаться семью способами помещения второго). Таким образом, существует 7×7=49 способов размещения первых двух заказов. Разместив их какимлибо образом, можем найти 7 вариантов помещения третьего (иначе, каждый способ размещения первых двух заказов может сопровождаться семью различными способами помещения третьего заказа). Следовательно, существуют 49×7=7