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

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

Поясним это на следующем примере. Пусть имеется три элемента: a, b и c. Тогда из этих трёх элементов можно составить шесть сочетаний с повторениями по два элемента: ab, ac, bc, aa, bb, cc.

Таким образом, сочетание с повторениями из n элементов по k элементов (при этом допускается, что m>n) может содержать любой элемент сколько угодно раз от 1 до k включительно или не содержать его совсем, т.е. каждое сочетание с повторениями из n элементов по k элементов может состоять не только из k различных элементов, но и k каких угодно и как угодно повторяющихся элементов.

Следует отметить, что если, например, две комбинации по k элементов отличаются друг от друга только порядком расположения элементов, то они не считаются различными сочетаниями.

Существует специальная формула для вычисления числа сочетаний с повторениями:

(12.1)

Выведем эту формулу. Прежде всего надо занумеровать возможные типы элементов числами от 1 до n (иначе можно оказаться в положении мужа, который никак не мог вспомнить, что ему поручила купить жена: 5 пакетов молока и 2 банки пива или наоборот 2 пакета молока и 5 банок пива). Теперь можно каждую комбинацию зашифровать с помощью последовательности единиц и палочек: для каждого типа с 1-го до n-го по порядку написать столько единиц, сколько предметов этого типа входит в комбинацию, а различные типы отделять друг от друга палочками.

Например, в кондитерском магазине продаются пирожные 4 видов: корзиночки, наполеоны, песочные и эклеры. Если куплено 3 корзиночки (к), 1 наполеон (н), 2 песочных (п) и 1 эклер (э), то получим такую запись:

В этой записи палочки отделяют одну группу пирожных от другой. Если же куплено 2 корзиночки и 5 песочных, то получим запись . Ясно, что разным покупкам соответствуют при этом разные комбинации из 7 единиц и 3 палочек. Обратно, каждой комбинации единиц и палочек соответствует какая-то покупка. Например, комбинациисоответствует покупка 3 наполеонов и 4 песочных (крайние группы отсутствуют).

В результате мы получим столько единиц, сколько предметов входит в комбинацию, т.е. k, а число палочек будет на 1 меньше, чем число типов предметов, т.е. n–1. Таким образом, мы получим перестановки с повторениями из k единиц и n–1 палочек. Различным комбинациям при этом соответствуют различные перестановки с повторениями, а каждой перестановке с повторениями соответствует своя комбинация.

Итак, число сочетаний с повторениями из элементовn типов по k равно числу P(k,n–1) перестановок с повторениями из n–1 палочек и k единиц. А . Поэтому.

Пример 12.1. В кондитерской имеется 3 вида пирожных. Сколькими способами можно купить 9 пирожных?

Решение. В задаче требуется найти число всевозможных групп по 9 элементов, которые можно составить из данных трех различных элементов, причем указанные элементы в каждой группе могут повторяться, а сами группы отличаются друг от друга хотя бы одним элементом. Это задача на отыскание числа сочетаний с повторениями из трех элементов по девять. Следовательно,

Пример 12.2. В почтовом отделении продаются открытки 10 сортов. Сколькими способами можно купить в нем 12 открыток? 8 открыток? Сколькими способами можно купить 8 различных открыток?

Решение. Данная задача на отыскание числа сочетаний с повторениями из 10 элементов по 10. Следовательно,

, .

В случае, когда требуется купить 8 различных открыток, получим сочетания без повторений:

.

Пример 12.3. Сколько всего чисел (не больше 100000) можно составить из цифр 1, 2, 3, 4 и 5 в каждом из которых цифры расположены в неубывающем порядке?

Решение. Это задача о числе сочетаний из пяти цифр по одному, по два, по три, по четыре и по пяти с повторениями в каждом случае. Поскольку ,,,,, то существуетчисел, удовлетворяющих условию задачи.

Упражнения

12.1. Сколькими способами Буратино, кот Базилио и лиса Алиса могут поделить между собой 5 одинаковых золотых монет?

Ответ: .

12.2. В кондитерской имеется пять разных сортов пирожных. Сколькими способами можно выбрать набор из четырёх пирожных?

Ответ: .

12.3. Сколько существует треугольников, длины сторон которых принимают одно из значений 4, 5, 6, 7?

Ответ: .

12.4. Сколько можно построить различных прямоугольных параллелепипедов, длина каждого ребра которых является целым числом от 1 до 10?

Ответ: .