Определение 8: Конечные упорядоченные множества называются размещениями.

Теорема 3: Количество всех размещений из элементов по элементов без повторений вычисляется по формуле:

. (2)

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

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

.

По определению, такие расстановки являются размещениями. Что и требовалось доказать.

Пример 3: Собрание из 25 человек выбирает президиум из 3 человек: 1) председатель, 2) заместитель, 3) секретарь. Сколько возможно вариантов выбора президиума?

Решение. Выбирая трех человек из 25, замечаем, что важен порядок выбора, поэтому количество президиумов будет равно:

.

Замечание: Число размещений без повторений можно также находить по формуле:

. (3)

Если в знаменателе дроби из формулы (3) , то принято считать .

Замечание: Формула (3) отличается компактностью, но при решении задач удобнее использовать формулу (2). Дробь, стоящая в правой части формулы (3), может быть сокращена до целого числа. Это число равно числу из правой части формулы (2).

Пример 4: Сколько можно составить двухбуквенных слов (буквы не повторяются) из 33 букв русского алфавита?

Решение. В данном случае мы имеем дело не со словами в лингвистическом понимании, а с буквенными комбинациями произвольного состава.

Тогда количество различных комбинаций из 2 букв, выбранных из 33 букв алфавита, будет равно:

.

В данном случае важен порядок букв. Если поменять 2 буквы в слове, то получим новое слово.

Замечание: Перестановка без повторений – это частный случай размещений без повторений при . Можно сказать, что перестановка из элементов – это размещение из элементов по элементов:

В некоторых задачах по комбинаторике не имеет значения порядок расположения объектов в той или иной совокупности. Важно лишь то, какие именно элементы ее составляют. В таких ситуациях мы имеем дело с сочетаниями.

 

Сочетания без повторений.

Определение 9: Сочетаниябез повторений из элементов некоторого множества по элементов () – это расстановки, отличающиеся друг от друга составом, но не порядком элементов. Обозначают: (от французского слова combinaison – сочетание).

В данном случае в расстановках важен состав, а не порядок элементов в подмножестве. Если две расстановки отличаются только порядком следования элементов, то с точки зрения сочетаний они не различимы. Элементы в этих расстановках не повторяются.

С точки зрения теории множеств определение сочетаний можно сформулировать иначе.