Пусть M — конечное множество, состоящее из m элементов. Сколько всего в нём подмножеств?

Пусть K – произвольное подмножество множества M, и пусть {0, 1} – множество, состоящее из двух элементов: числа 0 и числа 1. Зададим отображение

M —→ {0, 1}

следующим образом: все элементы подмножества K переведём в число 1, а все остальные элементы – в 0. Таким образом мы задали биекцию между множеством всех подмножеств множества M и множеством всех отображений

M —→ {0, 1}

Следовательно, подмножеств множества M столько же, сколько отображений множества M в {0, 1}, т.е. 2^m.

Сколько подмножеств, состоящих из k элементов, имеется в множестве M?

Пусть K – произвольное множество, состоящее из k элементов. Любое вложение f множества K в множество M задаёт подмножество f(K) множества M и это подмножество состоит из k элементов. Каждое подмножество, состоящее из k элементов, является образом некоторого вложения множества K в M, но разные вложения могут задать одно и то же подмножество. Нам нужно подсчитать, сколько разных вложений K —→ M задают одно и то же подмножество N множества M? Все такие вложения являются вложениями K —→ N, а таких вложений, как уже было подсчитано п. "Отображения", имеется k! = 1*2*… *k. Всего же вложений K в M, как было показано в том же п. "Отображения", имеется m!/(m-k)! Отсюда следует, что подмножеств, состоящих из k элементов, множества M имеется

m!/((m – k)!*k!).