Сочетания с повторением

Теорема 7.4. Общее число сочетаний с повторениями k элементов, взятых из совокупности n различных элементов, равно

. (7.5)

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

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

Таким образом, сведя задачу к случаю сочетания без повторений, мы теперь имеем n «старых» и «новых» (повторяющихся) элементов. Всего: . Далее обращаемся к формуле (7.3), описывающей число сочетаний без повторений, и, подставляя вместо , получаем формулу (7.5).

Пример 7.7. Найти число сочетаний из 5 различных элементов по 3.

1) Если повторение элементов не разрешено: .

2) Если повторение элементов разрешено: .