Реферат: Серьёзные лекции по высшей экономической математике

Комбинаторные формулы

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

Примеры перестановок:

1)распределение n различных должностей среди n человек;

2)расположение n различных предметов в одном ряду.

Сколько различных перестановок можно образовать во множестве U_n? Число перестановок обозначается P_n (читается Р из n).

Чтобы вывести формулу числа перестановок, представим себе n ячеек, пронумерованных числами 1,2,...n. Все перестановки будем образовывать, располагая элементы U_n в этих ячейках. В первую ячейку можно занести любой из n элементов (иначе: первую ячейку можно заполнить n различными способами). Заполнив первую ячейку, можно n-1 способом заполнить вторую ячейку (иначе: при каждом способе заполнения первой ячейки находится n-1 способов заполнения второй ячейки). Таким образом существует n(n-1) способов заполнения двух первых ячеек. При заполнении первых двух ячеек можно найти n-2 способов заполнения третьей ячейки, откуда получается, что три ячейки можно заполнить n(n-1)(n-2) способами. Продолжая этот процесс, получим, что число способов заполнения n ячеек равно . Отсюда

P_n = n(n - 1)(n - 2)...321

Число n(n - 1)(n - 2)...321, то есть произведение всех натуральных чисел от 1 до n, называется "n-факториал" и обозначается n!. Отсюда P_n =n!

Пример. .

По определению считается: 1!=1; 0!=1.

Размещениями из n элементов по k элементов будем называть упорядоченные подмножества, состоящие из k элементов, множества U_n - (множества, состоящего из n элементов). Число размещений из n элементов по k элементов обозначается (читается "А из n по k").

Примеры задач, приводящих к необходимости подсчета

1) Сколькими способами можно выбрать из 15 человек 5 кандидатов и назначить их на 5 различных должностей?

2) Сколькими способами можно из 20 книг отобрать 12 и расставить их в ряд на полке?

В задачах о размещениях полагается k<n. В случае, если k=n, то легко получить

Для подсчета используем тот же метод, что использовался для подсчета P_n ,только здесь возьмем лишь k ячеек. Первую ячейку можно заполнить n способами, вторую, при заполненной первой, можно заполнить n-1 способами. Можно продолжать этот процесс до заполнения последней k-й ячейки. Эту ячейку при заполненных первых k-1 ячейках можно заполнить n-(k-1) способами (или n-k+1). Таким образом все k ячеек заполняются числом способов, равным

Отсюда получаем:

Пример. Сколько существует различных вариантов выбора 4-х кандидатур из 9-ти специалистов для поездки в 4 различных страны?

Сочетаниями из n элементов по k элементов называются подмножества, состоящие из k элементов множества U_n (множества, состоящего из n элементов).

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

Число сочетаний из n элементов по k элементов обозначается (читается "C из n по k").

Примеры задач, приводящих к необходимости подсчета числа сочетаний:

1) Сколькими способами можно из 15 человек выбрать 6 кандидатов для назначения на работу в одинаковых должностях?

2) Сколькими способами можно из 20 книг отобрать 12 книг?

Выведем формулу для подсчета числа сочетаний. Пусть имеется множество U_n и нужно образовать упорядоченное подмножество множества U_n, содержащее k элементов (то есть образовать размещение). Делаем это так:

1) выделим какие-либо k элементов из n элементов множества U_n Это, согласно сказанному выше, можно сделать способами;