10. а) Доказать, что множество из n элементов имеет 2ⁿ подмножеств, n=0,1,2,… . б) Сколько подмножеств из k элементов имеет множество из n элементов (0≤k≤n)?

а) Для каждого из n элементов при составлении подмножества есть ровно два независимых выбора: включить элемент или не включить его. По правилу умножения всего получается 2·2·…·2=2ⁿ подмножеств. При n=0 имеется единственное подмножество ∅, что также соответствует 2⁰=1.

б) Чтобы выбрать k элементов из n без учёта порядка, число вариантов равно числу сочетаний:

\(\binom{n}{k}=\frac{n!}{k!(n-k)!}\).