Размещения с повторениями

Задача формулируется следующим образом. Имеются пред­меты п различных видов 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.