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

Имеются предметы различных видов. Число элементов каждого вида неограниченно. Сколько существует расстановок длины , если не принимать во внимание порядок элементов? Такие расстановки называют сочетаниями с повторениями, количество и обозначение которых следующее Выведем данную формулу.

Пусть это исходные различные типы элементов, количество которых Рассмотрим произвольное сочетание с повторениями из данных типов элементов. Так как порядок элементов в сочетаниях не учитывается, то расстановку можно записать и так: где элементы каждого из типов упорядочены и завершаются

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

Задача. Трое ребят собрали в саду 63 яблока. Сколькими способами они могут их разделить между собой?

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

Задача. Найти количество целочисленных решений системы

Решение. Рассмотрим следующую интерпретацию решения уравнения. Каждое значение представим как сумму единиц, количество которых Индекс , отмечает ее принадлежность к разложению числа Таким образом, мы ввели типов различных элементов значение каждого из них равно единице. Теперь любое решение исходного уравнения можно представить как сумму, составленную из к произвольных единиц множества Суммируя подобные единицы 1, с одинаковыми индексами, можно составить соответствующие слагаемые решения исходного уравнения. Данное соответствие является взаимно однозначным, откуда и следует, что число решений системы равно числу сочетаний с повторениями