Количество подмножеств в множестве

  X
Введите значения множества (через запятую,)
 

 

Количество подмножеств в множестве

Множество 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}