bulgakov

14. Свойства сочетаний: симметрия и сумма 2ⁿ

Выбрать rr элементов — то же самое, что решить, какие n−rn-r оставить: поэтому (nr)=(nn−r)\dbinom nr=\dbinom n{n-r}. А если сложить числа сочетаний по всем возможным размерам k=0,1,…,nk=0,1,\dots,n, получится ровно 2n2^n — число всех подмножеств.

Что пригодится из прошлого: сочетания — формула (nr)=n!r!(n−r)!\dbinom nr=\dfrac{n!}{r!(n-r)!}; двоичные коды и подмножества — число подмножеств равно 2n2^n. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Свойство 1: выбрать rr = оставить n−rn-r

Из пяти букв a,b,c,d,ea,b,c,d,e выбираем две. Каждый такой выбор сразу определяет, какие три буквы остались:

Выбрали 2 Оставили 3
{a, b} {c, d, e}
{a, c} {b, d, e}
{a, d} {b, c, e}
{a, e} {b, c, d}
{b, c} {a, d, e}
{b, d} {a, c, e}
{b, e} {a, c, d}
{c, d} {a, b, e}
{c, e} {a, b, d}
{d, e} {a, b, c}

Таблица читается в обе стороны. Любая пара однозначно задаёт тройку оставшихся букв, а любая тройка — пару оставшихся. Это взаимно однозначное соответствие, поэтому пар и троек поровну:

(52)=(53)=10.\binom52=\binom53=10.

Следствие 1 (из формулы для сочетаний). Для любых 0≤r≤n0\le r\le n

(nr)=(nn−r).\boxed{\binom nr=\binom n{n-r}}.

Ту же формулу видно и в записи: знаменатель r! (n−r)!r!\,(n-r)! не меняется, если поменять rr и n−rn-r местами.

Для чего это нужно. Можно считать меньшее из двух чисел. Например,

(5048)=(502)=50⋅492=1225.\binom{50}{48}=\binom{50}{2}=\frac{50\cdot49}{2}=1225.

Свойство 2: сумма по всем размерам равна 2n2^n

Возьмём множество B={a,b,c,d}B=\{a,b,c,d\} из четырёх элементов. Выпишем все его подмножества, сгруппировав по числу элементов kk. Для каждого подмножества в скобках записан его двоичный код из первой главы:

  • k=0k=0: ∅ (0000) — всего 1
  • k=1k=1: {a} (1000), {b} (0100), {c} (0010), {d} (0001) — всего 4
  • k=2k=2: {a, b} (1100), {a, c} (1010), {a, d} (1001), {b, c} (0110), {b, d} (0101), {c, d} (0011) — всего 6
  • k=3k=3: {a, b, c} (1110), {a, b, d} (1101), {a, c, d} (1011), {b, c, d} (0111) — всего 4
  • k=4k=4: {a, b, c, d} (1111) — всего 1

Всего подмножеств: 16.

Размеры подмножеств — числа 0,1,2,3,40,1,2,3,4, и в каждом пункте стоят подмножества одного размера. Каждое подмножество попало ровно в один пункт, поэтому все подмножества пересчитаны ровно один раз. В первой главе мы выяснили, что всего их 24=162^4=16. Сложим числа по пунктам:

1+4+6+4+1=16=24.1+4+6+4+1=16=2^4.

Следствие 2 (о числе подмножеств). Для любого nn

∑k=0n(nk)=2n.\boxed{\sum_{k=0}^{n}\binom nk=2^n}.

Доказательство. Пусть B={b1,b2,…,bn}B=\{b_1,b_2,\dots,b_n\}. Через 2B2^B обозначим множество всех подмножеств BB (это множество, а 2n2^n — число; запись выбрана потому, что в 2B2^B ровно 2n2^n элементов), а через ∣⋅∣|\cdot| — число элементов. Любому kk-элементному подмножеству BB отвечает сочетание без повторений из элементов BB по kk, и наоборот. Значит, подмножеств с kk элементами ровно (nk)\dbinom nk. Каждое подмножество имеет какой-то размер kk от 00 до nn, поэтому

2n=∣2B∣=∑k=0n∣{A∣A⊆B и ∣A∣=k}∣=∑k=0n(nk).□2^n=|2^B|=\sum_{k=0}^{n}\bigl|\{A\mid A\subseteq B\text{ и }|A|=k\}\bigr|=\sum_{k=0}^{n}\binom nk.\qquad\square

Что значат символы. Знак ∑k=0n\sum_{k=0}^{n} — «сумма по kk от 00 до nn»: слагаемых n+1n+1, от (n0)\dbinom n0 до (nn)\dbinom nn. Выражение в фигурных скобках читается «множество таких AA, что AA — подмножество BB и в AA ровно kk элементов».

Связь с кодами. Подмножество из kk элементов отвечает двоичному коду, где ровно kk единиц. Значит, (nk)\dbinom nk — число двоичных слов длины nn с kk единицами. Это то же число, что P(k,n−k)=n!k!(n−k)!P(k,n-k)=\dfrac{n!}{k!(n-k)!} из главы про перестановки с повторяющимися элементами.

Примеры

1. Все возможные наборы людей. Из 1010 человек можно составить набор любого размера, включая пустой и полный. Число способов: 210=10242^{10}=1024.

2. Начинки для пиццы. Есть шесть начинок; пицца может быть с любым их набором (в том числе без начинок): 26=642^6=64 вариантов.

3. «Не более двух». Сколько подмножеств восьмиэлементного множества содержат не более двух элементов? Складываем непересекающиеся случаи по размеру:

(80)+(81)+(82)=1+8+28=37.\binom80+\binom81+\binom82=1+8+28=37.

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

  • Начинать сумму с k=1k=1. Пустое подмножество (k=0k=0) тоже считается; слагаемых n+1n+1, а не nn.
  • Путать (nk)\dbinom nk и 2n2^n. (nk)\dbinom nk — подмножества одного размера kk; 2n2^n — все подмножества.
  • Применять симметрию с неправильным нижним числом. (nr)=(nn−r)\dbinom nr=\dbinom n{n-r}, а не (nr+1)\dbinom n{r+1}.

Проверь себя

1. Вычислите (3028)\dbinom{30}{28}.

Решение

По симметрии (3028)=(302)=30⋅292=435\dbinom{30}{28}=\dbinom{30}{2}=\dfrac{30\cdot29}{2}=435.

2. Найдите (60)+(61)+⋯+(66)\dbinom60+\dbinom61+\dots+\dbinom66.

Решение

Это сумма по всем размерам подмножеств шестиэлементного множества: 26=642^6=64.

3. Сколько непустых подмножеств у пятиэлементного множества?

Решение

Всего 25=322^5=32 подмножества, из них одно пустое. Непустых 32−1=3132-1=31.

4. При каком r≠5r\ne5 верно (12r)=(125)\dbinom{12}{r}=\dbinom{12}{5}?

Решение

По симметрии r=12−5=7r=12-5=7: (127)=(125)=792\dbinom{12}7=\dbinom{12}5=792.

Итог

  • (nr)=(nn−r)\dbinom nr=\dbinom n{n-r}: выбрать rr — значит определить, какие n−rn-r остаются.
  • ∑k=0n(nk)=2n\sum_{k=0}^{n}\dbinom nk=2^n: подмножества разбиваются по размерам k=0,1,…,nk=0,1,\dots,n.
  • (nk)\dbinom nk — число двоичных слов длины nn ровно с kk единицами.
ПрактикаЗагружаем тест…