Количество подмножеств в множестве
Множество A является подмножеством множества B:
A⊂B
если все элементы, принадлежащие A, также принадлежат множеству B.
Пустое множество Ø и само B также включаются в число подмножеств множества B:
Ø⊂B,B⊂B
Количество подмножеств из k элементов у множества из n элементов равно биномиальному коэффициенту, числу сочетаний из n по k:
C_n^k=n!/k!(n-k)!
Соответственно, общее количество подмножеств у множества из n элементов определяется суммой:
C_n^0+C_n^1+C_n^2+⋯+C_n^n
Из комбинаторики известно, что указанная сумма равна 2^n. Таким образом, общее число подмножеств у множества, состоящего из n элементов, составляет 2^n.
Пример
У множества {a,b,c}, состоящего из трех элементов, общее количество всевозможных подмножеств состоит из восьми (2^3=8):
Ø,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}