Число подмножеств конечного мн-ва

Рассмотрим множество , состоящее из N элементов:

}.

Попробуем закодировать любое его подмножество двоичной последовательностью, состоящей из 0 и 1: если элемент входит в подмножество, то первая цифра последовательности равна 1, если нет – 0. Точно также поступаем для второго элемента, третьего и т.д. Для каждого подмножества получаем свою последовательность из нулей и единиц. Так, в рассмотренном выше примере получим следующие последовательности для каждого из восьми рассмотренных подмножеств:

­ пустое множество – 000;

­ одноэлементные подмножества – 100, 010, 001;

­ двухэлементые подмножества – 110, 011, 101;

­ трехэлементное подмножество – 111.

Таким образом, каждому подмножеству соответствует своя двоичная последовательность длины , а каждой такой последовательности – свое подмножество. Количество двоичных последовательностей длины мы уже считали ранее, когда изучали правило умножения – их будет . Значит, и подмножеств будет ровно столько же:

количество подмножеств N -элементного множества = .