bulgakov

16. Сочетания с повторениями: единицы и звёздочки

Выбор rr предметов nn видов с повторениями можно записать цепочкой из rr единиц и n−1n-1 звёздочек: единицы — предметы, звёздочки — перегородки между видами. Цепочек столько же, сколько способов выбрать места для единиц: (nr)~=(n+r−1r)\widetilde{\dbinom nr}=\dbinom{n+r-1}{r}.

Что пригодится из прошлого: выборки — что такое сочетание с повторениями и кратность элемента; сочетания — число способов выбрать места; двоичные коды — приём «превратить объект в слово». Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Пирожные из трёх видов

В кондитерской три вида пирожных: a,b,ca,b,c. Нужно купить два пирожных; порядок покупки не важен, одинаковые пирожные разрешены. Это сочетания с повторениями из трёх элементов по два. Из главы про виды выборок мы знаем, что их шесть: aa,ab,ac,bb,bc,ccaa,ab,ac,bb,bc,cc.

Опишем каждый набор кратностями: сколько пирожных каждого вида куплено. Запишем их через вертикальные черты: код d(a) ∣ d(b) ∣ d(c)d(a)\,|\,d(b)\,|\,d(c). Например, набор abab — это код 1∣1∣01|1|0 (по одному пирожному aa и bb, ни одного cc). Сумма трёх чисел кода всегда равна 22.

От кратностей к слову из единиц и звёздочек

Заменим код словом в алфавите из двух символов: «11» и «∗\ast». Для каждого вида записываем столько единиц, сколько у него кратность, а между видами ставим звёздочку:

11…1⏟d(a1) ∗ 11…1⏟d(a2) ∗ … ∗ 11…1⏟d(an).\underbrace{11\ldots1}_{d(a_1)}\ \ast\ \underbrace{11\ldots1}_{d(a_2)}\ \ast\ \ldots\ \ast\ \underbrace{11\ldots1}_{d(a_n)}.

Единицы — купленные пирожные, а звёздочки — перегородки, отделяющие один вид от другого. Для трёх видов нужны две перегородки.

Набор Кратности Слово
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

Все слова имеют длину 44: две единицы и две звёздочки. Различных слов с двумя единицами и двумя звёздочками (42)=6\dbinom42=6, и все шесть встретились.

Картинка: шарики и коробки

Представьте nn коробок в ряд и rr одинаковых шариков, которые нужно разложить по коробкам. Это то же самое, что набрать rr предметов nn видов: коробка — вид, шарики в коробке — сколько взято. Между nn коробками n−1n-1 перегородок.

Пусть коробок 44, шариков 55, и набор такой: (2,1,0,2)(2,1,0,2).

Схема
коробка 1:  ●●     (d = 2)
коробка 2:  ●      (d = 1)
коробка 3:         (d = 0)
коробка 4:  ●●     (d = 2)

шарики и перегородки в ряд:
  ●●|●||●●
слово (● → 1, | → ∗):
  11∗1∗∗11

Слово 11∗1∗∗1111\ast1\ast\ast11 состоит из 55 единиц и 33 звёздочек, длина 8=4+5−18=4+5-1. Расшифровка однозначна: считаем единицы до первой звёздочки — это кратность первого вида; между первой и второй звёздочками — второго; и так далее.

Теорема и доказательство

Теорема. Число сочетаний с повторениями из nn элементов по rr равно

(nr)~=(n+r−1r)=(n+r−1n−1).\boxed{\widetilde{\binom nr}=\binom{n+r-1}{r}=\binom{n+r-1}{n-1}}.

Доказательство. Каждому сочетанию с повторениями rr элементов из A={a1,…,an}A=\{a_1,\dots,a_n\} сопоставим код d(a1) ∣ d(a2) ∣…∣ d(an)d(a_1)\,|\,d(a_2)\,|\dots|\,d(a_n), где d(ai)d(a_i) — кратность aia_i (d(a1)+⋯+d(an)=rd(a_1)+\dots+d(a_n)=r). Затем по коду однозначно строим слово из единиц и звёздочек, как показано выше.

Каждое такое слово имеет длину n+r−1n+r-1 (все rr единиц и n−1n-1 звёздочек) и содержит ровно rr единиц и n−1n-1 звёздочек. Наоборот, любое слово длины n+r−1n+r-1 с rr единицами и n−1n-1 звёздочками однозначно расшифровывается в набор кратностей. Значит, наборы и слова стоят в соответствии «один к одному», и их поровну.

Остаётся посчитать слова: нужно выбрать из n+r−1n+r-1 мест rr мест для единиц (остальные займут звёздочки). Это можно сделать (n+r−1r)\dbinom{n+r-1}{r} способами. Можно выбрать и n−1n-1 мест для звёздочек: (n+r−1n−1)\dbinom{n+r-1}{n-1}. Оба числа равны по симметрии (ab)=(aa−b)\dbinom ab=\dbinom a{a-b} (свойство сочетаний). □\square

Проверка по таблице. Для n=3n=3, r=2r=2: (3+2−12)=(42)=6\dbinom{3+2-1}{2}=\dbinom42=6 — как выше. Для двух видов: (2+r−1r)=(r+1r)=r+1\dbinom{2+r-1}{r}=\dbinom{r+1}{r}=r+1: из rr предметов можно взять 0,1,…,r0,1,\dots,r штук первого вида, остальные — второго.

Примеры

1. Открытки. Есть пять видов открыток; нужно купить три (одинаковые можно). n=5n=5, r=3r=3: (5+3−13)=(73)=35\dbinom{5+3-1}{3}=\dbinom73=35.

2. Конфеты. Нужно набрать 1010 конфет четырёх видов. n=4n=4, r=10r=10: (1310)=(133)=286\dbinom{13}{10}=\dbinom{13}{3}=286.

3. Три одинаковых кубика. Сколько различных результатов у броска трёх неразличимых кубиков (важно только, сколько выпало каждой грани)? Видов n=6n=6, предметов r=3r=3: (83)=56\dbinom{8}{3}=56.

Частые ошибки

  • Длина слова n+rn+r вместо n+r−1n+r-1. Перегородок на единицу меньше, чем видов: между nn коробками n−1n-1 разделитель.
  • Путать (nr)~\widetilde{\dbinom nr} с (nr)\dbinom nr. Если повторения разрешены, ответ (n+r−1r)\dbinom{n+r-1}{r}; для сочетаний без повторений — (nr)\dbinom nr.
  • Путать с размещениями. [n]~r=nr\widetilde{[n]}_r=n^r — порядок важен; здесь порядок не важен.
  • Взять (n+r−1n)\dbinom{n+r-1}{n}. Ниже должно стоять либо rr, либо n−1n-1.

Проверь себя

1. Сколькими способами можно купить 33 открытки, если в продаже 55 видов?

Решение

(5+3−13)=(73)=35\dbinom{5+3-1}{3}=\dbinom73=35.

2. Запишите слово из единиц и звёздочек для набора кратностей (0,3,1,2)(0,3,1,2) при n=4n=4. Чему равно rr?

Решение

Перед первой звёздочкой единиц нет (d=0d=0), затем три единицы, звёздочка, одна единица, звёздочка, две единицы: ∗111∗1∗11\ast111\ast1\ast11. Единиц 0+3+1+2=60+3+1+2=6, поэтому r=6r=6, звёздочек 3=n−13=n-1, длина слова 9=4+6−19=4+6-1.

3. Какой набор кратностей описывает слово 11∗∗1∗11111\ast\ast1\ast111? Сколько здесь видов и сколько предметов?

Решение

Звёздочек три, значит видов n=4n=4. Единицы по блокам: 2,0,1,32,0,1,3. Всего предметов 2+0+1+3=62+0+1+3=6.

4. Сколько существует различных результатов у броска трёх неразличимых кубиков?

Решение

Шесть граней — шесть «видов», три кубика — три предмета: (6+3−13)=(83)=56\dbinom{6+3-1}{3}=\dbinom83=56.

Итог

  • Сочетание с повторениями описывают кратности d(a1),…,d(an)d(a_1),\dots,d(a_n) с суммой rr.
  • Кратности записываются словом из rr единиц и n−1n-1 звёздочек длиной n+r−1n+r-1; соответствие взаимно однозначно.
  • Число слов — число способов выбрать места: (nr)~=(n+r−1r)=(n+r−1n−1)\widetilde{\dbinom nr}=\dbinom{n+r-1}{r}=\dbinom{n+r-1}{n-1}.
ПрактикаЗагружаем тест…