Размещения без повторений

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

Число всевозможных размещений без повторений из п элементов по т элементов обозначают .

Пример 10. В конкурсе принимает участие 20 человек. Сколькими способами можно присудить первую, вторую и третью премии?

Решение. Не зная формулу для вычисления числа размещений без повторений, можно рассуждать так: присуждение первой премии можно осуществить двадцатью способами. Присуждение второй премии – девятнадцатью, так как один выбор из 20 уже использован, а выбор третьей премии – восемнадцатью способами, так как два выбора из 20 уже использованы.

Отсюда, по правилу произведения, количество выборов присуждения премии подсчитываем по формуле: 20 × 19 × 18 = 6840.

Размещения без повторений.

Сколько можно составить телефонных номеров из 6 цифр каждый, так

чтобы все цифры были различны?

Это пример задачи на размещение без повторений. Размещаются здесь 10

цифр по 6. А варианты, при которых одинаковые цифры стоят в разном

порядке считаются разными.

Если X-множество, состоящие из n элементов, m?n, то размещением без

повторений из n элементов множества X по m называется упорядоченное

множество X, содержащее m элементов называется упорядоченное множество X,

содержащее m элементов.

Количество всех размещений из n элементов по m обозначают

[pic]

n! - n-факториал (factorial анг. сомножитель) произведение чисел

натурального ряда от 1 до какого либо числа n

n!=1*2*3*...*n 0!=1

Значит, ответ на вышепоставленную задачу будет

[pic]

Задача

Сколькими способами 4 юноши могут пригласить четырех из шести девушек на

танец?

Решение: два юноши не могут одновременно пригласить одну и ту же девушку.

И варианты, при которых одни и те же девушки танцуют с разными юношами

считаются, разными, поэтому:

[pic]

Возможно 360 вариантов.

^ Выведем формулу для вычисления

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

Тогда выбор первого элемента таких кортежей можно осуществить п способами. Так как первый элемент выбран, то выбор второго элемента можно осуществить (п – 1) способами, третий элемент можно выбрать (п – 2) способами и т.д. Выбор элемента, стоящего на т месте, будет осуществлен (п – (т – 1)) =
(п – т + 1) способами.

Но выбор упорядоченного набора из т элементов, по правилу произведения, можно осуществить
п (п – 1) (п – 2) … (п – т + 1) способами.

Значит, . (1)

Число размещений без повторений из п элементов по т элементов можно вычислять иначе.

Для этого домножим и разделим правую часть формулы (1) на произведение: 1 × 2 × 3 … (п – т).

(2)

Дата добавления: 2015-07-14