Число сочетаний с повторениями

Обозначим через С" ¹ число всех сочетаний с повторениями из п по т.

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

Рассмотрим «-элементное множество и занумеруем его элементы: S={a, a₂, …, я"}. Будем перебирать все сочетания с повторениями. Так как порядок записи элементов неважен, то вначале запишем все элементы а|, затем все аг и т. д. Элементы разделяем вертикальной чертой: a…ct]a2…ct2…a»…a_n. Такую комбинацию можно отождествить с набором нулей и единиц вида I… 101… 10…01… I, в котором п-1 нулей (нуль играет роль разделительной черты) и т единиц, так как сочетание содержит т элементов. Таким образом, число сочетаний будет равно числу перестановок, в которых цифра 0 имеет кратность («-1), а цифра 1 — кратность т. Число таких перестановок равно.

Пример 11.3.1. В примере 11.1.1 были рассмотрены все сочетания с повторениями из 3 по 3. Приведем их коды в соответствии с рассмотренной идеей, полагая ai=2, я₂=3, Яз=4:

• 2,2,2<-«11 100
• 2,2,3<-«11 010 2,2,411 001
• 2,3,3<-«10 110 2,3,4<-«10 101 2,4,410 011
• 3,3,301 110 3,3,401 101 3,4,4<-«1 011 4,4,400 111 •

Итак, подсчет числа сочетаний с повторениями можно свести к подсчету числа сочетаний без повторений с помощью формулы:

Пример 11.3.2. В магазине продают 4 сорта пирожных: заварное, белковое, «Грибок», «Ночка». Сколькими способами можно купить 8 пирожных?

Рассмотрим множество S = {з, б, г, //}, в котором каждый элемент кодирует название пирожного по первой букве. Любой выбор 8 пирожных порождает комбинацию элементов множества 5, при этом порядок записи элементов нс имеет значения. Например, выбрав 2 заварных пирожных, 4 белковых и по одному пирожному остальных сортов, имеем комбинацию ззббббгн, являющуюся сочетанием с повторениями из 4 по 8. Наоборот, любое такое сочетание однозначно даст некоторый набор пирожных. Значит, число способов купить указанное число пирожных равно С₄ =С,⁸_] =С,³, = 165.

Отметим, что можно было произвести подсчет не по формуле (6), а непосредственно применив процедуру, описанную при выводе этой формулы. Каждый набор из 8 пирожных можно закодировать последовательностью из 8 нулей и 3 единиц. Например, набору ззббббгн соответствует последовательность 11 011 110 101, а набору ггггнннн последовательность 111 101 111 (заварных и белковых пирожных не выбрали ни одного). Последовательность 11 110 011 011 однозначно определяет следующий набор пирожных: заварных — 4 штуки, «Грибков».

2 штуки, «Ночки» — 2 штуки, белковых нет. Итак, 8 пирожных можно выбрать ,(8,3) = 165 числом способов. •.

Пример 11.3.3. В условиях предыдущего примера найдем, сколькими способами можно купить 8 пирожных при дополнительном условии: требуется купить хотя бы по одному пирожному каждого сорта.

Дополнительное условие означает, что в выборке элементов множества S заведомо должны быть элементы з, б, г, п. Уберем из выборки по одному элементу каждого типа. После этого получим сочетание, содержащее только 4 элемента из тех же 4 сортов. Число таких сочетаний С₄⁴ = С⁴ = С³ = 35 .•.

Отождествление набора объектов с последовательностью из нулей и единиц является важной идеей при решении комбинаторных задач. Этот прием часто называют 0−1 кодированием.

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

Так как карандаши одинаковые, то различные способы распределения карандашей между детьми будут отличаться лишь количеством карандашей у каждого ребенка. Применим идею 0−1 кодирования. Изобразим каждый карандаш цифрой 1. Получим набор из 6 единиц. Для того чтобы распределить их между тремя детьми, добавим в набор две цифры 0, что разобьет 6 единиц на три группы. Полученный набор взаимно однозначно распределяет карандаши между детьми. Например, набор 11 101 011 означает, что первый ребенок получил три карандаша, второй — один карандаш, а третий — два карандаша. Осталось сосчитать число наборов из двух нулей и шести единиц, число которых равно Pg (2,6) или С₈², то есть 28.

Указанные в примере распределения карандашей также определяют сочетания с повторениями. О каких сочетаниях идет речь? Подумайте. •.

Упражнение. Найдите число способов распределить шесть одинаковых карандашей между тремя детьми так, чтобы каждый ребенок получил хотя бы один карандаш.

Для того чтобы распределить шесть карандашей между тремя детьми, нам пришлось представить число 6 в виде суммы трех целых неотрицательных чисел. Обобщим эту идею.

Так как сочетание с повторениями определяется только составом элементов, то каждому сочетанию из п по т соответствует ровно одна упорядоченная л-ка (к₉к₂,…,к"), сумма координат которой равна т, где i-я координата показывает, сколько раз в сочетании встречается соответствующий элемент. При этом некоторые координаты могут равняться О, так как в сочетании могут присутствовать не все элементы исходного множества. Указанное соответствие взаимно однозначно. Поэтому число сочетаний С" равно числу способов представить натуральное число т в виде суммы п целых неотрицательных чисел: т = к+к₂ + … + к". Важно, что порядок следования слагаемых здесь существенен. Например, представления числа 7 в виде 2+3+2 и в виде 2+2+3 считаются различными.

Другими словами, число С™ равно числу решений уравнения *!+…+jc" = т в целых неотрицательных числах.

Пример 11.3.5. Сколько решений в целых неотрицательных числах имеет уравнение jC|+jc2+*3+jc₄=9?

Каждое решение можно отождествить с последовательностью из 9 единиц и 3 нулей (разбивающих единицы на четыре группы). Например, решению (2,3,2,2) соответствует код 110 111 011 011. Общее количество решений равно числу сочетаний с повторениями из 4 по 9:

С₄⁹=С?₂ = С?₂ = 220 .

Пример 11.3.6. Сколько решений в натуральных числах имеет уравнение *i+Ar₂+*3⁺*4⁼9?

Здесь можно применить идею, рассмотренную в примере 11.3.5. Заметим вначале, что каждой упорядоченной четверке (а, b, с, d) натуральных чисел соответствует четверка целых неотрицательных чисел (я-1,6 —1,с-1, </ —1), сумма координат которых равна 9−4=5. Это соответствие взаимно однозначно, при обратном соответствии надо прибавить к каждой координате по 1. Таким образом, требуется представить число 5 в виде суммы четырех целых неотрицательных слагаемых, что можно сделать С₄⁵ = С^ = CJ =56 способами. •.

Во всех рассмотренных выше примерах задач данного пункта требовалось сосчитать число сочетаний с повторениями. Как было доказано, это число можно найти по формуле (6). Тем не менее вместо того, чтобы переводить задачу на язык сочетаний, можно напрямую воспользоваться идеей 0−1 кодирования, что было продемонстрировано в ряде примеров. В некоторых случаях задачу можно решить, не прибегая к идее кодирования или формуле (6).

Пример 11.3.7. Среди азартных игр распространена игра в домино. Кость домино представляет собой комбинацию двух чисел, образованную из 7 элементов: 0, 1,2, 3, 4, 5, 6. Комбинации чисел неупорядоченные (1:2 и 2:1 — это одна и та же кость), при этом возможны повторения чисел (0:0, 1:1, 2:2, … — так называемые дубли). Сосчитаем, сколько всего существует костей домино.

Нетрудно видеть, что кость — это сочетание с повторениями из 7 по 2. Их число можно найти по формуле С~ =С$ = 28.

Найдем это число другим способом. Вначале переберем все дубли: их.

7. Сосчитаем количество костей, не являющихся дублями. Их число равно числу сочетаний (без повторений) из 7 по 2, то есть =21. Всего имеем 7+21=28 костей домино. •.

Упражнение. Используя принцип сложения, вычислите число С₇³. Отдельно найдите число всех сочетаний без повторений и число сочетаний, в которых есть повторяющиеся элементы.