Размещение элементов множества

Пусть дано некоторое неупорядоченное n-элементное множество А. Сколько, разных упорядоченных k-элементных подмножеств может иметь множество А? Рассмотрим два возможных варианта этой задачи:

- подмножества имеют k различных элементов;

- подмножества имеют k не обязательно различных элементов. I

Следовательно, в первом варианте задачи подмножества задаются не избыточно, а во втором, – избыточно, однако число всех различных элементов подмножества вместе с числом всех экземпляров каждого из его элементов равно k. Упорядоченное k-элементное подмножество множества А, все элементы ко­торого различны, называется размещением без повторений, а любое упоря­доченное k-элементное подмножество множества А, все k элементов которого не обязательно различны, называется размещением с повторениями. Заме­тим, что в первом случае, причем если k =n, то В этом случае размеще­ние является перестановкой. Во втором случае k не обязательно должно быть меньше n, т. е. возможно, что .

Решение первого варианта задачи.

Поскольку множество А неупорядочено, то любое его k-элементное под­множество может быть упорядочено одним из k! способов, а число всех возможных различных k-элементных подмножеств множества А равно . Следовательно, число всех возможных размещений из n элементов по k равно k! , т. е. имеет место следующая теорема