В § 1 уже рассмотрен вопрос о числе размещений с повторениями. Для полноты картины, рассмотрим еще перестановки и сочетания с повторениями.

1. Перестановки с повторениями.Перестановкой с повторениями порядка n и состава из элементов -множества называется упорядоченная n‑ка, в которой элементы встречаются соответственно раз, причем . Понятно, что две перестановки с повторениями одинакового порядка и состава могут отличаться друг от друга лишь порядком компонент. Например, и различные перестановки с повторениями порядка 7 и состава . Решим следующую комбинаторную задачу: найти число перестановок с повторениями порядка n, имеющих состав . Все такие перестановки можно получить следующим образом. Составим все перестановки без повторений из различных элементов, включающих элементы . Напомним, что их число равно . Если , то выберем произвольно элементов, не входящих в множество , и отождествим их с во всех перестановках. Легко понять, что таким образом получим перестановки с повторениями порядка и состава , где единица записана раз. Но различных среди них будет меньше во столько раз, сколько можно образовать перестановок без повторений из элементов, т.е. в раз. Таким образом, получим перестановок. Если , то переходим к . Если , то выберем произвольно элементов, не входящих во множество , и отождествим их с во всех перестановках. Легко понять, что таким образом получим перестановок с повторениями порядка и состава , где единица записана раз. Продолжая этот процесс, приходим к выводу о справедливости следующего утверждения:

Т е о р е м а 1.Число перестановок с повторениями порядка n, имеющих состав , вычисляется по формуле

= . (1)

Пример 1. Буквы слова «Математика» можно переставлять способами.

Из формулы (1) вытекает, что букв и букв можно переставлять способами. Но это число равно . Значит, число перестановок с повторениями состава равно :

= . (2)

Формула (2) позволяет записать формулу бинома Ньютона в следующем виде:

= + +…+ + … + ,

или в краткой форме

= ,

где суммирование распространено на все наборы такие, что .

С помощью индукции по числу слагаемых нетрудно убедится в справедливости следующего утверждения:

Т е о р е м а 2.Длялюбых натуральных чисел , и любых действительных чисел справедлива формула

= , (3)

где суммирование распространено на все наборы такие, что .

Пример 2. = = .

2. Сочетания с повторениями.Найдем теперь число различных составов, которые могут иметь наборы длины , состоящие из элементов ‑множества . Каждый такой состав является упорядоченным набором, состоящим из чисел таких, что . Его можно записать в виде набора из нулей и единиц, заменив каждое число соответствующим числом единиц и поставив нуль после каждой группы единиц, кроме последней. Например, вместо набора можно написать , а вместо набора – набор . Число единиц, входящих в полученные наборы, равно , а число нулей равно . Поэтому число различных наборов такого вида равно числу перестановок с повторениями из n единиц и нулей, т.е.. . Но ввиду формулы (2) = .

Таким образом, мы доказали, что число составов наборов длины , компоненты которых принадлежат данному k‑множеству, равно .