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

Пусть дано множество А, содержащее 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 – элементные подмножества.

Дата добавления: 2014-01-11