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

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

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

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

Примеры.

1. Из элементов можно образовать следующие сочетания с повторениями по 3 элемента:

2. Из элементов с можно образовать следующие сочетания с повторениями по два элемента:

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

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

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

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

Запишем теперь подряд раз цифру 0. Затем перед первым нулем запишем столько единиц, сколько раз элемент а повторяется в комбинации (1), т. е. а единиц, между первым и вторым нулями запишем столько единиц, сколько раз элемент повторяется в комбинации (1), т. е. единиц, наконец, после последнего нуля запишем единиц.

Если какой-либо элемент не входит в сочетание (1), то на соответствующем месте (между нулями, перед первым или после последнего нуля) единицы не пишутся. Так получим символ

Если в сочетание (1) какой-либо из элементов не входит, то в символе (2) нуль будет стоять по крайней мере два раза подряд.

Будем считать символ (2) соответствующим сочетанию (1). Таким образом, всякому сочетанию с повторениями из элементов ставится в соответствие некоторый вполне определенный символ вида (2), в котором цифра 1 встречается раз, а цифра 0 встречается раз. Каждый такой символ является перестановкой с повторениями из элементов 0 и 1, в которой 0 повторяется раз и 1 повторяется раз.

Следовательно, всякому сочетанию с повторениями из элементов по элементов соответствует некоторая вполне определенная перестановка из элементов 0 и 1, в которой 0 повторяется раз и 1 повторяется раз. Наоборот, всякой перестановке с повторениями из элементов 0 и 1, в которой 0 повторяется раз

и 1 повторяется раз, соответствует одно, вполне определенное сочетание с повторениями из элементов по элементов, а именно: сочетание, в котором каждый из элементов повторяется столько раз, сколько единиц стоит на соответствующих местах в перестановке. Следовательно, установленное нами соответствие между сочетаниями и перестановками с повторениями — взаимно однозначное. Поэтому число различных сочетаний с повторениями из элементов по элементов равно числу различных перестановок с повторениями из элементов 0, 1, в каждой из которых 0 повторяется раз, а 1 повторяется раз, т. е.

Пример. Сколькими различными способами можно разделить 20 тетрадей между тремя учениками?

Решение. Если один из учеников получит а тетрадей, второй тетрадей и третий у — тетрадей, то данное распределение можно записать в виде следующего сочетания с повторениями:

и следовательно, число возможных распределений равно числу различных сочетаний с повторениями из 3 элементов по 20, т. е. равно