16. Сочетания с повторениями: единицы и звёздочки
Выбор предметов видов с повторениями можно записать цепочкой из единиц и звёздочек: единицы — предметы, звёздочки — перегородки между видами. Цепочек столько же, сколько способов выбрать места для единиц: .
Что пригодится из прошлого: выборки — что такое сочетание с повторениями и кратность элемента; сочетания — число способов выбрать места; двоичные коды — приём «превратить объект в слово». Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Пирожные из трёх видов
В кондитерской три вида пирожных: . Нужно купить два пирожных; порядок покупки не важен, одинаковые пирожные разрешены. Это сочетания с повторениями из трёх элементов по два. Из главы про виды выборок мы знаем, что их шесть: .
Опишем каждый набор кратностями: сколько пирожных каждого вида куплено. Запишем их через вертикальные черты: код . Например, набор — это код (по одному пирожному и , ни одного ). Сумма трёх чисел кода всегда равна .
От кратностей к слову из единиц и звёздочек
Заменим код словом в алфавите из двух символов: «» и «». Для каждого вида записываем столько единиц, сколько у него кратность, а между видами ставим звёздочку:
Единицы — купленные пирожные, а звёздочки — перегородки, отделяющие один вид от другого. Для трёх видов нужны две перегородки.
| Набор | Кратности | Слово |
|---|---|---|
| aa | (2, 0, 0) | 11∗∗ |
| ab | (1, 1, 0) | 1∗1∗ |
| ac | (1, 0, 1) | 1∗∗1 |
| bb | (0, 2, 0) | ∗11∗ |
| bc | (0, 1, 1) | ∗1∗1 |
| cc | (0, 0, 2) | ∗∗11 |
Все слова имеют длину : две единицы и две звёздочки. Различных слов с двумя единицами и двумя звёздочками , и все шесть встретились.
Картинка: шарики и коробки
Представьте коробок в ряд и одинаковых шариков, которые нужно разложить по коробкам. Это то же самое, что набрать предметов видов: коробка — вид, шарики в коробке — сколько взято. Между коробками перегородок.
Пусть коробок , шариков , и набор такой: .
коробка 1: ●● (d = 2)
коробка 2: ● (d = 1)
коробка 3: (d = 0)
коробка 4: ●● (d = 2)
шарики и перегородки в ряд:
●●|●||●●
слово (● → 1, | → ∗):
11∗1∗∗11
Слово состоит из единиц и звёздочек, длина . Расшифровка однозначна: считаем единицы до первой звёздочки — это кратность первого вида; между первой и второй звёздочками — второго; и так далее.
Теорема и доказательство
Теорема. Число сочетаний с повторениями из элементов по равно
Доказательство. Каждому сочетанию с повторениями элементов из сопоставим код , где — кратность (). Затем по коду однозначно строим слово из единиц и звёздочек, как показано выше.
Каждое такое слово имеет длину (все единиц и звёздочек) и содержит ровно единиц и звёздочек. Наоборот, любое слово длины с единицами и звёздочками однозначно расшифровывается в набор кратностей. Значит, наборы и слова стоят в соответствии «один к одному», и их поровну.
Остаётся посчитать слова: нужно выбрать из мест мест для единиц (остальные займут звёздочки). Это можно сделать способами. Можно выбрать и мест для звёздочек: . Оба числа равны по симметрии (свойство сочетаний).
Проверка по таблице. Для , : — как выше. Для двух видов: : из предметов можно взять штук первого вида, остальные — второго.
Примеры
1. Открытки. Есть пять видов открыток; нужно купить три (одинаковые можно). , : .
2. Конфеты. Нужно набрать конфет четырёх видов. , : .
3. Три одинаковых кубика. Сколько различных результатов у броска трёх неразличимых кубиков (важно только, сколько выпало каждой грани)? Видов , предметов : .
Частые ошибки
- Длина слова вместо . Перегородок на единицу меньше, чем видов: между коробками разделитель.
- Путать с . Если повторения разрешены, ответ ; для сочетаний без повторений — .
- Путать с размещениями. — порядок важен; здесь порядок не важен.
- Взять . Ниже должно стоять либо , либо .
Проверь себя
1. Сколькими способами можно купить открытки, если в продаже видов?
Решение
.
2. Запишите слово из единиц и звёздочек для набора кратностей при . Чему равно ?
Решение
Перед первой звёздочкой единиц нет (), затем три единицы, звёздочка, одна единица, звёздочка, две единицы: . Единиц , поэтому , звёздочек , длина слова .
3. Какой набор кратностей описывает слово ? Сколько здесь видов и сколько предметов?
Решение
Звёздочек три, значит видов . Единицы по блокам: . Всего предметов .
4. Сколько существует различных результатов у броска трёх неразличимых кубиков?
Решение
Шесть граней — шесть «видов», три кубика — три предмета: .
Итог
- Сочетание с повторениями описывают кратности с суммой .
- Кратности записываются словом из единиц и звёздочек длиной ; соответствие взаимно однозначно.
- Число слов — число способов выбрать места: .
