bulgakov

01. Двоичные коды: почему у множества 2ⁿ подмножеств

Главная идея: каждому подмножеству сопоставляем один код, а затем считаем, сколько разных кодов можно составить.

1. Что здесь называется кодом

Возьмём множество из трёх различных элементов:

B={b1,b2,b3}.B=\{b_1,b_2,b_3\}.

Чтобы задать его подмножество, нужно про каждый элемент решить: берём его или не берём. Записываем ответ: 11 — берём, 00 — не берём.

Заранее закрепляем места: первое отвечает за b1b_1, второе — за b2b_2, третье — за b3b_3.

Например:

Элементb1b2b3Берём?101\begin{array}{c|ccc} \text{Элемент}&b_1&b_2&b_3\\ \hline \text{Берём?}&1&0&1 \end{array}

Получили код 101101. Он означает: взяли b1b_1, пропустили b2b_2, взяли b3b_3. Значит,

101⟷{b1,b3}.101\longleftrightarrow\{b_1,b_3\}.

Код — это вся запись целиком, а не отдельная цифра. Здесь 101101 — просто три отметки, а не число «сто один». Нули в начале тоже сохраняем: 001001 означает «взяли только b3b_3».

2. Как посчитать коды: сначала одно место, затем два и три

Одно место. В него можно поставить 00 или 11:

0,1.0,\qquad 1.

Итого 2 варианта.

Два места. К каждому из предыдущих вариантов дописываем справа либо 00, либо 11:

0⟶00, 01;1⟶10, 11.\begin{aligned} 0&\longrightarrow 00,\ 01;\\ 1&\longrightarrow 10,\ 11. \end{aligned}

Было два варианта начала. У каждого — два продолжения. Поэтому:

2⋅2=4 кода.2\cdot2=4\text{ кода}.

Повторения разрешены: например, 1111 означает, что мы выбрали оба соответствующих элемента.

Три места. Теперь к каждому из четырёх вариантов снова дописываем 00 или 11:

Уже записаны два знака Дописываем 00 Дописываем 11
0000 000000 001001
0101 010010 011011
1010 100100 101101
1111 110110 111111

Каждое из четырёх начал получает два продолжения:

4⋅2=8.4\cdot2=8.

Вот почему умножаем: новое место даёт не просто два дополнительных кода, а два продолжения для каждого уже имеющегося варианта.

Все полученные коды различны. У продолжений одного начала разные последние цифры; у продолжений разных начал различаются сами начала. И никакой код не пропущен: его первые два знака обязательно стоят в одной из четырёх строк, а последний знак — либо 00, либо 11.

3. Почему количество кодов равно количеству подмножеств

Нужно проверить, что мы ничего не потеряли и не посчитали дважды.

Любое подмножество можно записать кодом. Просто отмечаем единицами его элементы, а остальные — нулями.

Любой код задаёт ровно одно подмножество. Берём именно те элементы, напротив которых стоят единицы. Например:

000⟷∅,110⟷{b1,b2},111⟷B.000\longleftrightarrow\varnothing, \qquad 110\longleftrightarrow\{b_1,b_2\}, \qquad 111\longleftrightarrow B.

Разные коды задают разные подмножества. Если коды отличаются на каком-то месте, соответствующий элемент в одном подмножестве есть, а в другом отсутствует.

Значит, коды и подмножества можно поставить в пары «один к одному». Поэтому 8 кодов означают ровно 8 подмножеств.

Все восемь соответствий сразу. Вот полный список кодов и подмножеств для B={b1,b2,b3}B=\{b_1,b_2,b_3\}:

Код Что значит Подмножество
000000 не берём b1b_1, не берём b2b_2, не берём b3b_3 ∅\varnothing
001001 не берём b1b_1, не берём b2b_2, берём b3b_3 {b3}\{b_3\}
010010 не берём b1b_1, берём b2b_2, не берём b3b_3 {b2}\{b_2\}
011011 не берём b1b_1, берём b2b_2, берём b3b_3 {b2,b3}\{b_2,b_3\}
100100 берём b1b_1, не берём b2b_2, не берём b3b_3 {b1}\{b_1\}
101101 берём b1b_1, не берём b2b_2, берём b3b_3 {b1,b3}\{b_1,b_3\}
110110 берём b1b_1, берём b2b_2, не берём b3b_3 {b1,b2}\{b_1,b_2\}
111111 берём b1b_1, берём b2b_2, берём b3b_3 {b1,b2,b3}\{b_1,b_2,b_3\}

Каждая строка — один код и ровно одно подмножество; ни один код не пропущен и ни один не повторяется.

4. Переходим от трёх элементов к любому nn

Если элементов nn, в коде тоже nn мест. На каждом месте независимо от остальных разрешены два значения.

Первое место даёт 22 варианта. Каждое следующее место удваивает их количество. Поэтому:

Количество кодов=2⋅2⋅…⋅2⏟n множителей=2n.\text{Количество кодов} = \underbrace{2\cdot2\cdot\ldots\cdot2}_{n\text{ множителей}} =2^n.

Множество всех подмножеств BB обозначают 2B2^B. Его элементы — сами подмножества: например, {b1,b3}\{b_1,b_3\} — один элемент 2B2^B. Это обозначение множества, а 2n2^n — уже число.

Вертикальные черты ∣B∣|B| обозначают число элементов, или мощность конечного множества BB. Здесь ∣B∣=n|B|=n. Каждому элементу 2B2^B соответствует ровно один двоичный код, поэтому:

∣2B∣=2n.\boxed{|2^B|=2^n}.

При n=0n=0 правило тоже верно: у пустого множества одно подмножество — оно само; 20=12^0=1.

Например, для множества из пяти элементов:

2⋅2⋅2⋅2⋅2=32.2\cdot2\cdot2\cdot2\cdot2=32.

Здесь 5 — длина каждого кода, а 32 — количество разных кодов, то есть разных подмножеств.

Проверь себя

1. Сколько подмножеств у множества из 66 элементов? А из 1010?

Решение

Для множества из nn элементов их 2n2^n: 26=642^6=64 и 210=10242^{10}=1024.

2. Пусть B={b1,b2,b3,b4}B=\{b_1,b_2,b_3,b_4\}. Какое подмножество описывает код 01100110? Какой код у подмножества {b1,b4}\{b_1,b_4\}?

Решение

Код 01100110: не берём b1b_1, берём b2b_2, берём b3b_3, не берём b4b_4 — это {b2,b3}\{b_2,b_3\}. Подмножество {b1,b4}\{b_1,b_4\}: берём первый и четвёртый элементы, поэтому код 10011001.

3. Выпишите все коды длины 44, в которых ровно две единицы. Сколько их?

Решение

0011, 0101, 0110, 1001, 1010, 1100 — всего 66. Столько двухэлементных подмножеств у четырёхэлементного множества. Почему именно шесть и как считать такие числа быстро — в главе про сочетания.

Что дальше

Мысль «объект превращаем в код и считаем коды» повторяется во всём курсе: правила суммы и произведения начинают подсчёт, а то, сколько подмножеств каждого размера и почему их сумма равна 2n2^n, объясняет глава про свойства сочетаний.

ПрактикаЗагружаем тест…