Размещения с повторениями
Задача формулируется следующим образом. Имеются предметы п различных видов a1,a2,…,an . Из них составляют всевозможные расстановки длины k. Например, a2a1a3a3a4a3a2a1- расстановка длины 8. Такие расстановки называются размещениями с повторениями из п по k (элементы одного вида могут повторяться). Найдем общее число расстановок, среди которых две расстановки считаются различными, если они отличаются друг от друга или видом входящих в них предметов, или порядком этих предметов. При составлении указанных расстановок длины k на каждое место можно поставить предмет любого вида. Рассмотрим множества X1,X2,…,Xk такие, что Х1 = Х2 = ... = Xk = { a1,a2,…,an } . Тогда все размещения с повторениями составят множество . По правилу прямого произведения получаем, что общее число размещений с повторениями из п по k равно .
Пример:
Найти количество всех пятизначных чисел.
Решение: Введем пять множеств: А2 = А3 = А4 = А5 = {0, 1,..., 9}, А1 = {1, 2,..., 9}. Тогда все пятизначные числа составят прямое произведение указанных множеств А1 А2 А3 А4 А5. Согласно правилу прямого произведения, количество элементов в множестве А1 А2 А3 А4 А5 равно 9*10*10*10*10 =90000.