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

 

Определение 1. Пусть Е = {а1, а2, …, аn} – конечное множество. Размещением с повторениями из Е по k элементов называется упорядоченное подмножество из k элементов, принадлежащих Е, причем каждый элемент может входить в это подмножество несколько раз.

Число размещений с повторениями из n элементов по m определяется следующей формулой:

.                                            (1)

Задача 1. Сколько можно написать различных трехзначных чисел с помощью цифр 4 и 5?

Решение. Нетрудно выписать непосредственно различные комбинации 4 и 5: 444, 445, 454, 544, 555, 554, 545, 455. Всего 8 чисел. Но этот результат можно получить и используя формулу (1).

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

Пусть множество Е состоит из k различных элементов, причем 1-ый элемент входит в множество Е m1 раз, 2-ой – m2 раза, . . ., k-ый элемент – mk раз, т. е.

. m1+ m2+. . . + mk=n.

Тогда число перестановок с повторениями из n элементов равно

 .            (2)

Задача 2. Сколько можно написать различных шестизначных чисел только с помощью цифр 5, 3, 1, 5, 5, 1?

Решение. Разделим данные цифры на три группы: 1, 1, 3, 5, 5, 5. По условию задачи можно воспользоваться формулой (2):

.

Определение 3. Сочетанием с повторениями элементов из Е по k называется неупорядоченное подмножество из k элементов, принадлежащих Е, каждый элемент может входить в это подмножество несколько раз.

Число сочетаний с повторениями из n элементов по m определяется следующей формулой:

.                            (3)

Задача 3. В цветочном магазине есть цветы трех видов. Сколькими способами можно составить букет из 7 купленных цветов?

Решение. Ясно, что n=3, m=7. Тогда по формуле (3) имеем:

.