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

Пусть имеется М = { a ₁, a ₂, …, a_n }. Пустое множество (Æ) входит в это множество как подмножество. Одноэлементные множества тоже входят в это множество как подмножества.

Поставим каждому подмножеству кортеж длиной n, состоящий из 0 и 1. Будем ставить 0, если соответствующий элемент не входит в подмножество, и 1, если входит.

Например, подмножеству { a ₂, a ₄} будет соответствовать кортеж 010100000….0.

Для всех подмножеств получим кортежи (0,0,0, …,0), (1,0,0,…0), (0,1,0,0,...,0)… (1,1,1,…1).

Кортежей столько, сколько подмножеств. Каждый кортеж − это размещения, состоящие из двух элементов (0 и 1) и отличающиеся друг от друга либо элементами, либо их порядком. Это размещения с повторениями из двух по n:

Получим

Ấ = .

Таким образом, мы доказали теорему:

Число подмножеств n -элементного множества равно .

Следствие:

Т.к. число пустых подмножеств С = 1, одноэлементных – С =n, двухэлементных – С , трехэлементных − С , и т.д., n -элементных − С , то сумма С = .

Дата добавления: 2014-01-06