Число подмножеств множества из n элементов: формула 2^n

Число подмножеств множества из $n$ элементов - одна из самых частых задач вводного курса дискретной математики: ответ всегда $2^n$, но студентов регулярно сбивает, входят ли в счёт пустое множество и само множество, и как отдельно посчитать подмножества строго заданного размера. Ниже разберём, откуда берётся степень двойки, как треугольник Паскаля объясняет разбиение по размерам и какие формулировки задач встречаются чаще всего. А для проверки своих чисел покрути калькулятор ниже - он мгновенно считает и общее число подмножеств, и число подмножеств заданного размера.

Почему подмножеств ровно $2^n$

Пусть множество $A$ состоит из $n$ элементов. Чтобы построить произвольное подмножество, нужно для КАЖДОГО элемента $A$ независимо решить: включать его в подмножество или нет. У каждого элемента ровно два варианта - «да» и «нет», а всего таких независимых решений $n$ штук. По правилу произведения комбинаторики общее число способов равно произведению $n$ двоек:

$N(n) = \underbrace{2 \cdot 2 \cdot \ldots \cdot 2}_{n} = 2^n.$

Возьмём конкретный пример: множество $A = \{a, b, c\}$ из трёх элементов. Перебором получаем все восемь подмножеств: $\varnothing$, $\{a\}$, $\{b\}$, $\{c\}$, $\{a,b\}$, $\{a,c\}$, $\{b,c\}$, $\{a,b,c\}$. Их действительно $2^3 = 8$, и это ровно те комбинации, которые получаются, если для каждого из трёх элементов независимо решить, попадает он в подмножество или нет.

Почему каждый новый элемент удваивает число подмножеств

Формулу $2^n$ удобно понимать не только как произведение двоек, но и как рекуррентное правило: если у множества из $n-1$ элементов было $N(n-1)$ подмножеств, то при добавлении ещё одного элемента все старые подмножества остаются подмножествами (в них новый элемент просто не включён), и к каждому из них добавляется двойник - то же подмножество, но с новым элементом внутри. Значит, подмножеств становится ровно вдвое больше:

$N(n) = 2 \cdot N(n-1).$

Рассчитать для своей задачи

Именно это удвоение и стоит за степенью двойки: два варианта на первом элементе, ещё удвоение на втором, ещё одно на третьем - и так $n$ раз подряд. Условие $N(0) = 1$ тоже согласуется с этой логикой: у пустого множества (нет элементов вовсе) есть ровно одно подмножество - оно само, то есть $\varnothing$.

Пустое множество и само множество тоже считаются

Частая ошибка - вычесть из $2^n$ пустое множество или само $A$, решив, что «настоящих» подмножеств меньше. По определению подмножества оба граничных случая законны:

• $\varnothing$ - пустое множество является подмножеством любого множества (условие «каждый элемент $\varnothing$ принадлежит $A$» выполняется автоматически, так как элементов там нет);
• само $A$ - множество всегда является подмножеством самого себя.

Оба случая уже включены в формулу $2^n$: пустому множеству соответствует комбинация, где на каждом из $n$ шагов выбрано «нет», а самому $A$ - комбинация, где на каждом шаге выбрано «да». Если задача явно требует посчитать подмножества БЕЗ этих двух крайних случаев, из $2^n$ вычитают именно два, а не одно.

Подмножества заданного размера: биномиальный коэффициент

Иногда нужно не общее число подмножеств, а число подмножеств строго из $k$ элементов. Это классическая задача на сочетания: выбрать $k$ элементов из $n$ без учёта порядка можно

$C_n^k = \binom{n}{k} = \frac{n!}{k!\,(n-k)!}$

способами. Например, у множества из 4 элементов подмножеств из ровно 2 элементов ровно $C_4^2 = 6$. Если просуммировать число подмножеств по всем возможным размерам $k$ от $0$ до $n$, снова получится общее число подмножеств - это и есть биномиальная теорема в частном случае:

$\sum_{k=0}^{n} C_n^k = 2^n.$

Строка коэффициентов $C_n^0, C_n^1, \ldots, C_n^n$ - это как раз $n$-я строка треугольника Паскаля, а формула выше означает, что сумма любой строки треугольника Паскаля равна степени двойки с тем же номером. Подробнее про сумму и произведение вариантов в комбинаторике - в статье про правило суммы и произведения, а про саму формулу сочетаний - в разборе вероятности через сочетания.

Рассчитать для своей задачи

Собственные, несобственные и непустые подмножества

В задачах встречаются термины, которые стоит различать:

• несобственное подмножество - само множество $A$ (единственное такое подмножество);
• собственное подмножество ($A' \subsetneq A$) - любое подмножество, кроме самого $A$; их число $2^n - 1$;
• непустое подмножество - любое подмножество, кроме $\varnothing$; их тоже $2^n - 1$;
• непустое собственное подмножество - отличается и от $\varnothing$, и от $A$; таких $2^n - 2$.

Для множества из 3 элементов: всего подмножеств 8, собственных - 7 (все, кроме $\{a,b,c\}$), непустых - тоже 7 (все, кроме $\varnothing$), а непустых собственных - 6 (исключены и $\varnothing$, и $\{a,b,c\}$).

Как решать типовые задачи

Задача 1. Сколько подмножеств у множества из 6 элементов? Прямая подстановка: $2^6 = 64$.

Задача 2. Сколько подмножеств из ровно 3 элементов у множества из 8 элементов? Это сочетания: $C_8^3 = \frac{8!}{3!\,5!} = 56$.

Задача 3. Известно, что множество имеет 128 подмножеств - сколько в нём элементов? Нужно решить $2^n = 128$: поскольку $2^7 = 128$, ответ $n = 7$. Такие задачи «в обратную сторону» удобно проверять просто подбором степени двойки - таблица степеней $2^0, 2^1, 2^2, \ldots$ растёт быстро, и нужное $n$ обычно находится за несколько шагов.

Задача 4. Сколько собственных непустых подмножеств у множества из 5 элементов? $2^5 - 2 = 30$.

Задача 5. Множество состоит из 10 элементов. Сколько у него подмножеств, содержащих не более 2 элементов? Здесь нужно не одно значение $C_n^k$, а сумма трёх слагаемых - для размеров 0, 1 и 2: $C_{10}^0 + C_{10}^1 + C_{10}^2 = 1 + 10 + 45 = 56$. Такой приём - сложить несколько соседних строк биномиальных коэффициентов - часто встречается в задачах «не более $m$ элементов» или «хотя бы $m$ элементов», где вместо перебора всех размеров удобнее посчитать дополнение: например, «хотя бы 8 из 10» проще найти как $2^{10}$ минус сумма подмножеств размером 0-7.

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

• Забывают, что пустое множество и само множество тоже входят в $2^n$, и вычитают их без явного требования задачи.
• Путают «число подмножеств размера $k$» ($C_n^k$) с «общим числом подмножеств» ($2^n$) - это разные величины, и вторая получается суммированием первой по всем $k$.
• Считают число подмножеств через перестановки ($n!$) вместо сочетаний - перестановки учитывают порядок элементов внутри подмножества, а порядок в множестве не важен.
• При решении «обратной» задачи ($2^n =$ известное число) пытаются логарифмировать в столбик вместо того, чтобы быстро подобрать степень двойки.
• Путают собственное подмножество ($A' \ne A$) с непустым подмножеством ($A' \ne \varnothing$) - это разные ограничения, совпадающие по количеству ($2^n-1$), но не по составу.

FAQ

Считается ли пустое множество подмножеством само по себе? Да, $\varnothing$ - подмножество любого множества, в том числе самого себя. Оно уже учтено в формуле $2^n$.

Чем отличается число подмножеств от числа сочетаний? Число подмножеств $2^n$ - это сумма числа сочетаний по всем размерам $k$ от 0 до $n$. Число сочетаний $C_n^k$ - только подмножества фиксированного размера $k$.

Как быстро посчитать $2^n$ для больших $n$ без калькулятора? Удобно удваивать по шагам: $2^{10} = 1024$, дальше домножать на 2 столько раз, сколько осталось до нужного $n$, либо раскладывать показатель на сумму степеней десятки, которые легко запомнить.

Можно ли множество с одинаковыми элементами? Нет - по определению множества все его элементы различны; если в условии задачи встречаются «повторы», их считают один раз при подсчёте $n$.

Как связаны число подмножеств и число бинарных строк длины n? Напрямую: каждому подмножеству множества из $n$ элементов соответствует ровно одна двоичная строка длины $n$, где единица на $i$-й позиции означает «$i$-й элемент включён», а ноль - «не включён». Поэтому число подмножеств $2^n$ совпадает с числом всех различных двоичных строк длины $n$ - это одна и та же комбинаторная задача в двух формулировках.

Коротко

Число подмножеств множества из $n$ элементов равно $2^n$, потому что для каждого элемента есть независимый выбор «включать или нет», и оно уже включает и пустое множество, и само множество. Подмножества фиксированного размера $k$ считаются через биномиальный коэффициент $C_n^k$, а сумма всех $C_n^k$ по $k$ от 0 до $n$ снова даёт $2^n$ - это и есть строка треугольника Паскаля. Собственные и непустые подмножества отличаются от общего числа на единицу-две в зависимости от того, какие крайние случаи исключены условием задачи.