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

Пусть даны различных элементов а, Образуем всевозможные упорядоченные множества, содержащие по элементов, каждый из которых является одним из данных элементов. При в некоторых из этих множеств отдельные элементы будут повторяться несколько раз (конечно, не больше, чем раз).

Все образованные нами множества называются размещениями с повторениями из данных элементов по элементов. Итак, размещением с повторениями из данных элементов элементов называется всякое упорядоченное множество

М, содержащее элементов, каждый из которых является одним из данных элементов. Размещения с повторениями из элементов по называют также размещениями с повторениями из элементов порядка.

Ниже выписаны различные возможные размещения с повторениями из двух элементов по 3 элемента:

Различные размещения с повторениями из данных элементов по элементов, как и размещения без повторений, отличаются одно от другого или самими элементами, входящими в них, или порядком их расположения.

Число различных размещений с повторениями из элементов по элементов обозначают символом а

Теорема. Число различных размещений с повторениями из элементов по равно

Доказательство. Так как при доказательстве теоремы индивидуальные свойства заданных элементов, из которых образуются размещения с повторениями, не играют никакой роли, то будем считать, что заданными элементами являются первые чисел натурального ряда

При теорема верна, потому что заданные элементов образуют различных размещений по одному элементу. Предположим, что теорема верна для размещений с повторениями из элементов по элементов, т. е. что число таких размещений равно и докажем, что тогда она справедлива и для. размещений с повторениями из элементов по элементов. Для этого возьмем любое размещение с повторениями из заданных элементов по элементов (каждое из является одним из чисел Допишем к этому размещению элемент который может равняться любому из чисел получим размещение с повторениями из элементов по элементов: Следовательно, указанным способом из каждого размещения с повторениями из элементов по получаем различных размещений по элементов. Причем из двух различных размещений порядка получим различные размещения порядка. Действительно, в двух различных размещениях порядка:

по крайней мере для одного значения а поэтому всякие два размещения также будут различными.

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

Следовательно, теорема верна при и из предположения, что она верна для размещений порядка, вытекает ее справедливость и для размещения порядка. Значит, в силу принципа математической индукции она верна для всякого натурального числа

Пример. Сколько трехзначных чисел можно записать с помощью девяти цифр 1, 2, 3, 8, 9, если цифры в записи числа могут повторяться?

Решение. Искомое число равно числу размещений с повторениями из девяти элементов по три, т. е.

Из определений перестановки и размещения с повторениями вытекает, что всякое размещение с повторениями, в котором элементы повторяются соответственно является перестановкой с повторениями из элементов а, порядка в которой элементы повторяются соответственно Раз наоборот, всякая перестановка с повторениями из элементов порядка будет размещением с повторениями из элементов по элементов, в котором каждый из элементов повторяется столько же раз, сколько и в перестановке. Поэтому понятие перестановки с повторениями можно определить еще так: перестановкой с повторениями из элементов элементы которой повторяются соответственно раз, называется всякое размещение с повторениями в котором элемент а повторяется а раз, .