01. Двоичные коды: почему у множества 2ⁿ подмножеств
Главная идея: каждому подмножеству сопоставляем один код, а затем считаем, сколько разных кодов можно составить.
1. Что здесь называется кодом
Возьмём множество из трёх различных элементов:
Чтобы задать его подмножество, нужно про каждый элемент решить: берём его или не берём. Записываем ответ: — берём, — не берём.
Заранее закрепляем места: первое отвечает за , второе — за , третье — за .
Например:
Получили код . Он означает: взяли , пропустили , взяли . Значит,
Код — это вся запись целиком, а не отдельная цифра. Здесь — просто три отметки, а не число «сто один». Нули в начале тоже сохраняем: означает «взяли только ».
2. Как посчитать коды: сначала одно место, затем два и три
Одно место. В него можно поставить или :
Итого 2 варианта.
Два места. К каждому из предыдущих вариантов дописываем справа либо , либо :
Было два варианта начала. У каждого — два продолжения. Поэтому:
Повторения разрешены: например, означает, что мы выбрали оба соответствующих элемента.
Три места. Теперь к каждому из четырёх вариантов снова дописываем или :
| Уже записаны два знака | Дописываем | Дописываем |
|---|---|---|
Каждое из четырёх начал получает два продолжения:
Вот почему умножаем: новое место даёт не просто два дополнительных кода, а два продолжения для каждого уже имеющегося варианта.
Все полученные коды различны. У продолжений одного начала разные последние цифры; у продолжений разных начал различаются сами начала. И никакой код не пропущен: его первые два знака обязательно стоят в одной из четырёх строк, а последний знак — либо , либо .
3. Почему количество кодов равно количеству подмножеств
Нужно проверить, что мы ничего не потеряли и не посчитали дважды.
Любое подмножество можно записать кодом. Просто отмечаем единицами его элементы, а остальные — нулями.
Любой код задаёт ровно одно подмножество. Берём именно те элементы, напротив которых стоят единицы. Например:
Разные коды задают разные подмножества. Если коды отличаются на каком-то месте, соответствующий элемент в одном подмножестве есть, а в другом отсутствует.
Значит, коды и подмножества можно поставить в пары «один к одному». Поэтому 8 кодов означают ровно 8 подмножеств.
Все восемь соответствий сразу. Вот полный список кодов и подмножеств для :
| Код | Что значит | Подмножество |
|---|---|---|
| не берём , не берём , не берём | ||
| не берём , не берём , берём | ||
| не берём , берём , не берём | ||
| не берём , берём , берём | ||
| берём , не берём , не берём | ||
| берём , не берём , берём | ||
| берём , берём , не берём | ||
| берём , берём , берём |
Каждая строка — один код и ровно одно подмножество; ни один код не пропущен и ни один не повторяется.
4. Переходим от трёх элементов к любому
Если элементов , в коде тоже мест. На каждом месте независимо от остальных разрешены два значения.
Первое место даёт варианта. Каждое следующее место удваивает их количество. Поэтому:
Множество всех подмножеств обозначают . Его элементы — сами подмножества: например, — один элемент . Это обозначение множества, а — уже число.
Вертикальные черты обозначают число элементов, или мощность конечного множества . Здесь . Каждому элементу соответствует ровно один двоичный код, поэтому:
При правило тоже верно: у пустого множества одно подмножество — оно само; .
Например, для множества из пяти элементов:
Здесь 5 — длина каждого кода, а 32 — количество разных кодов, то есть разных подмножеств.
Проверь себя
1. Сколько подмножеств у множества из элементов? А из ?
Решение
Для множества из элементов их : и .
2. Пусть . Какое подмножество описывает код ? Какой код у подмножества ?
Решение
Код : не берём , берём , берём , не берём — это . Подмножество : берём первый и четвёртый элементы, поэтому код .
3. Выпишите все коды длины , в которых ровно две единицы. Сколько их?
Решение
0011, 0101, 0110, 1001, 1010, 1100 — всего . Столько двухэлементных подмножеств у четырёхэлементного множества. Почему именно шесть и как считать такие числа быстро — в главе про сочетания.
Что дальше
Мысль «объект превращаем в код и считаем коды» повторяется во всём курсе: правила суммы и произведения начинают подсчёт, а то, сколько подмножеств каждого размера и почему их сумма равна , объясняет глава про свойства сочетаний.
