§ 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, т. е. равно