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) имеем:
.