Число подмножеств множества из n элементов

Задача. Сколько подмножеств имеет множество A, состоящее из n элементов?

Решение.

Для начала сделаем вступление о представлении чисел битами.

В памяти компьютера числа задаются с помощью нулей и единиц. Рассмотрим одну ячейку (бит). Там может храниться или 0, или 1 - то есть 2¹ = 2 элемента. Имеем для одной ячейки два состояния. Далее добавим одну ячейку. Имеем две ячейки, в каждой из которых может храниться либо 0, либо 1.Какое общее число состояний в двух ячейках? Допустим в первой ячейке лежит 0. Для 0 в первой ячейке имеем два состояния во второй ячейке: 00 и 01. Теперь предположим, что в первой ячейке 1. Тогда для первой ячейки с 1 мы имеем те же два состояния во второй ячейке: 10 и 11. То есть при добавлении одной ячейки, число состояний увеличилось вдвое, так как для каждого из состояний в первой ячейке мы имеем два состояния во второй.

Число состояний в двух ячейках равно 2² = 4. Это: 00, 01, 10, 11.

Добавим третью ячейку. Теперь для каждого из двух состояний (0 и 1) в первой ячейке, имеется 4 состояния для группы из второй и третьей ячейки. Получается для трех ячеек имеем 2³ = 8 состояний. Видно, что при добавлении одной ячейки к прежней группе, число состояний увеличивается вдвое. Если имеется n ячеек, то число состояний в них равно 2ⁿ.

Пусть множество A состоит из одного элемента a: A={a}, т.е. n = 1. Число подмножеств множества A будет равно 2, так как подмножествами A являются:

- подмножество A={a}, состоящее из единственного элемента множества A, и

- пустого множество ∅.

Можно установить соответствие:

если бит равен 1, то этому состоянию ставим в соответствие существование элемента a;

если бит равен 0, то этому состоянию ставим в соответствие несуществование элемента a.

Теперь рассмотрим множество A={a₁, a₂, ..., a_n}. Подмножества A получаются из множества A удалением одного или более (до n) элементов. Можно поставить в соответствие удаленным элементам 0, а не удаленным 1. Тогда ясно, что число подмножеств множества A равно 2ⁿ.

Поясняющий рисунок: