Использование взаимно однозначного соответствия множеств

Пример.

Найти количество всех подмножеств множества из N элементов.

Решение. Обозначим каждое подмножество набором нулей и единиц, всего из N элементов. При этом на позиции номер i стоит 1, если элемент номер i содержится в подмножестве, и 0, если не содержится в нём.

Тогда различных наборов 2^N, поскольку на каждом из N мест может находиться или 0, или 1.

Количество подмножеств равно количеству наборов, поскольку подмножества и наборы нулей и единиц находятся во взаимно-однозначном соответствии.

Итак, количество подмножеств равно 2^N.

Ответ. 2^N.