Перестановки, РАзмещения и сочетания

 

Пусть имеется набор из n различных объектов.

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

Количество перестановок из n элементов:

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

 

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

Установить справедливость этой формулы легко, если применить рассуждения аналогичные рассуждениям, приведенным при выводе формулы для перестановок из n элементов.

 

Выборки k элементов из набора в n элементов, когда различными считаются только выборки, имеющие разный состав, называются сочетаниями из n элементов по k . Их количество обозначается , и при этом : .

Замечание: при вычислении количества сочетаний мы иногда сталкиваемся с необходимостью вычислить 0! . Чтобы не записывать для этих случаев отдельные формулы, условились считать, что: . Оказалось, что такая договоренность не приводит к неприятностям, а позволяет вычислять и в тех случаях, когда в знаменателе стоит 0!.

 

Примеры:

  1. Каково количество различных вариантов расположения команд в итоговой турнирной таблице футбольного чемпионата , если в нем принимают участие 16 команд? Ответ: Таких способов: .
  2. Каково количество различных вариантов распределения призовых мест (золото, серебро, бронза)? Ответ: При распределении призовых мест важным является не только то кто из участников стал призером, но и каким именно.

Поэтому, получаем :

.

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

Поэтому, получаем :

.