§ 5. Перестановки с повторениями
Предположим, что нам задано множество
в котором элемент а повторяется а раз, элемент
раз,
раз
элемент I повторяется К раз. Пусть
Упорядочив множество
получим перестановку из
элементов, в которой элементы
будут повторяться соответственно
раз. Эта перестановка называется перестановкой с повторениями.
Итак, перестановкой с повторениями из элементов а,
в которой элементы
повторяются соответственно
раз, называется всякое расположение в некотором определенном порядке элементов множества
состоящего из а элементов
элементов 6, у элементов с и
элементов
Если мы образуем все
перестановок с повторениями из заданных
элементов, то, очевидно, некоторые из них будут повторяться.
Число различных перестановок с повторениями из данных элементов будем обозначать символом
Теорема. Число различных перестановок с повторениями из элементов
в которых элементы
повторяются соответственно
раз, равно
Доказательство. Обозначим а элементов а множества
символами
элементов
символами
у элементов с — символами
и
элементов
символами
Из
элементов
множества
образуем всевозможные перестановки. Их будет
Разобьем теперь все эти перестановки на классы следующим образом: к одному классу отнесем те и только те перестановки, которые отличаются одна от другой лишь расположением элементов
а все другие элементы стоят у них на одних и тех же местах. Иначе говоря, к одному классу отнесем все те перестановки, которые можно получить из одной путем перестановки в ней элементов
между собой. Очевидно, что в каждом классе будет столько перестановок, сколько всего перестановок можно образовать из элементов
т. е.
Во всех
перестановках вместо
поставим теперь а.
Тогда все
перестановок одного класса не будут ничем отличаться одна от другой. Следовательно, среди всех
перестановок, образованных из элементов
Повторив изложенные выше рассуждения для этих
разных перестановок и для элементов
входящих в них, мы установим, что среди перестановок, образованных из элементов
различных будет
Рассуждая аналогично и дальше, мы установим, что число различных перестановок, образованных из элементов
равно
Следовательно,
Пример. Сколько семизначных чисел можно записать с помощью цифр 2, 3, 5 при условии, что цифра 2 повторяется в каждом из чисел 3 раза, а цифры 3 и 5 — по два раза?
Решение. Искомое число очевидно, является числом различных перестановок с повторениями из цифр 2, 3, 5, в которых цифра 2 повторяется три раза, а цифра 3 и 5 — по два раза. Потому оно равно