Перестановки без повторений

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

Пример: Пусть . Упорядочим его элементы:

1) (a,b.c), 2) (a,c,b), 3) (b,a,c), 4) (b,c,a), 5) (c,a,b), 6) (c,b,a).

Получили 6 кортежей длины 3. Все они содержат одни и те же элементы, однако отличаются друг от друга порядком следования элементов.

Определение: Всякое упорядоченное n – элементное множество называется перестановкой без повторений из n элементов.

Теорема: Число перестановок без повторений из n элементов равно произведению n последовательных натуральных чисел от 1 до n.

Доказательство:

При упорядочивании элементов множества А, содержащего n элементов, первый элемент можно выбрать n способами; второй – (n-1) способами; третий – (n-2) способами и т.д.; n-ый элемент можно выбрать 1 способом. Тогда n-ку ( по правилу произведения можно выбрать способами.

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

В задаче речь идет о перестановках без повторений: (способа).

Пример: Сколько различных пятизначных чисел можно составить из цифр: 1, 2, 3, 4, 5 так, чтобы цифры в числе не повторялись?

Цифр всего 5 и число должно быть пятизначным, т.е. в образовании числа должны быть задействованы все цифры. Известно, что значение числа зависит от того, какое место в числе занимает та или иная цифра. Налицо все характерные признаки перестановок без повторений. Следовательно, таких чисел будет: .

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

Задача 3: Сколько различных трехзначных чисел можно составить из цифр: 1, 2, 3, 4, 5 так, чтобы цифры в числе не повторялись?

В этой задаче в отличие от предыдущей для образования трехзначного числа необходимо задействовать лишь три цифры, а выбрав три цифры из пяти, их нужно упорядочить, чтобы получить различные трехзначные числа. Например, выберем цифры: 2, 3, 5. С их помощью можно получить числа: 235; 253; 523; 532; 325; 352. Выбрав другую тройку цифр, получим другие трехзначные числа и т.д.

Таким образом, мы из множества, содержащего n элементов, образуем упорядоченные k – элементные подмножества.

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

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

Теорема: Число размещений без повторений из n элементов по k равно

Тогда решение нашей задачи будет выглядеть так:

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

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

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

Теорема: Число сочетаний без повторений из n элементов по k определяется по формуле:

Доказательство:

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

Задача: Из 12 человек нужно выбрать 3 человека для участия в соревнованиях. Сколькими способами это можно сделать ?

При выборе трех человек из 12 для участия в соревнованиях порядок выбора не важен. следовательно, в задаче речь идет о сочетаниях без повторений из 12 по 3: (способов).

Задача: Сколькими способами из 12 человек можно составить команду для участия в эстафете?

Здесь при выборе тройки человек важен порядок, в котором побегут спортсмены, поэтому решение задачи будет таким: =1320