14. Свойства сочетаний: симметрия и сумма 2ⁿ
Выбрать элементов — то же самое, что решить, какие оставить: поэтому . А если сложить числа сочетаний по всем возможным размерам , получится ровно — число всех подмножеств.
Что пригодится из прошлого: сочетания — формула ; двоичные коды и подмножества — число подмножеств равно . Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Свойство 1: выбрать = оставить
Из пяти букв выбираем две. Каждый такой выбор сразу определяет, какие три буквы остались:
| Выбрали 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} |
Таблица читается в обе стороны. Любая пара однозначно задаёт тройку оставшихся букв, а любая тройка — пару оставшихся. Это взаимно однозначное соответствие, поэтому пар и троек поровну:
Следствие 1 (из формулы для сочетаний). Для любых
Ту же формулу видно и в записи: знаменатель не меняется, если поменять и местами.
Для чего это нужно. Можно считать меньшее из двух чисел. Например,
Свойство 2: сумма по всем размерам равна
Возьмём множество из четырёх элементов. Выпишем все его подмножества, сгруппировав по числу элементов . Для каждого подмножества в скобках записан его двоичный код из первой главы:
- : ∅ (0000) — всего 1
- : {a} (1000), {b} (0100), {c} (0010), {d} (0001) — всего 4
- : {a, b} (1100), {a, c} (1010), {a, d} (1001), {b, c} (0110), {b, d} (0101), {c, d} (0011) — всего 6
- : {a, b, c} (1110), {a, b, d} (1101), {a, c, d} (1011), {b, c, d} (0111) — всего 4
- : {a, b, c, d} (1111) — всего 1
Всего подмножеств: 16.
Размеры подмножеств — числа , и в каждом пункте стоят подмножества одного размера. Каждое подмножество попало ровно в один пункт, поэтому все подмножества пересчитаны ровно один раз. В первой главе мы выяснили, что всего их . Сложим числа по пунктам:
Следствие 2 (о числе подмножеств). Для любого
Доказательство. Пусть . Через обозначим множество всех подмножеств (это множество, а — число; запись выбрана потому, что в ровно элементов), а через — число элементов. Любому -элементному подмножеству отвечает сочетание без повторений из элементов по , и наоборот. Значит, подмножеств с элементами ровно . Каждое подмножество имеет какой-то размер от до , поэтому
Что значат символы. Знак — «сумма по от до »: слагаемых , от до . Выражение в фигурных скобках читается «множество таких , что — подмножество и в ровно элементов».
Связь с кодами. Подмножество из элементов отвечает двоичному коду, где ровно единиц. Значит, — число двоичных слов длины с единицами. Это то же число, что из главы про перестановки с повторяющимися элементами.
Примеры
1. Все возможные наборы людей. Из человек можно составить набор любого размера, включая пустой и полный. Число способов: .
2. Начинки для пиццы. Есть шесть начинок; пицца может быть с любым их набором (в том числе без начинок): вариантов.
3. «Не более двух». Сколько подмножеств восьмиэлементного множества содержат не более двух элементов? Складываем непересекающиеся случаи по размеру:
Частые ошибки
- Начинать сумму с . Пустое подмножество () тоже считается; слагаемых , а не .
- Путать и . — подмножества одного размера ; — все подмножества.
- Применять симметрию с неправильным нижним числом. , а не .
Проверь себя
1. Вычислите .
Решение
По симметрии .
2. Найдите .
Решение
Это сумма по всем размерам подмножеств шестиэлементного множества: .
3. Сколько непустых подмножеств у пятиэлементного множества?
Решение
Всего подмножества, из них одно пустое. Непустых .
4. При каком верно ?
Решение
По симметрии : .
Итог
- : выбрать — значит определить, какие остаются.
- : подмножества разбиваются по размерам .
- — число двоичных слов длины ровно с единицами.
