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

Напомним понятие подмножества, введенное в главе 1. Если каждый элемент множества В принадлежит множеству А, то В называется подмножеством множества А: АÊВ или ВÍА.

Считается, что пустое множество Øявляется подмножеством любого множества: Ø Í А. Для всякого множества А имеет место соотношение АÍА. Если В Í А, А Í В, то А = В. Подмножество В множества А называется собственным, если В ≠ А и В ≠Ø.

Если задано некоторое множество А, то можно рассматривать новое множество М(А) - множество всех его подмножеств. Через М _k (А) будем обозначать множество всех подмножеств множества А, которые имеют k элементов:

В Í М _k (А), если |В| = k.

Поставим вопрос: сколько разных подмножеств имеет множество, состоящее из n элементов, сколько разных k -элементных подмножеств имеет это множество. В принятых обозначениях эти вопросы состоят в вычислении

|М(А)| и |М _k (А)|, если |А| = n

Пример. Пусть А = {а,b,с}, тогда

M₀(A) = Ø, M₁(A)={{a},{b},{c}},

M₂(A)={{a,b},{a,c},{b,c}}, M₃(A)={a,b,c}.

Очевидно, что |М₀(А)| = 1, |М₁(а)| = 3, |М₂(а)| = 3, |M₃(a)| = 1, |М(а)| = 8 = 2³.

Покажем, что число всех подмножеств множества из n элементов равно 2ⁿ. Действительно, переномеруем все элементы множества А, построим последовательность длины n из нулей и единиц по следующему принципу: на k -ом месте пишем 1, если элемент с номером k входит в подмножество, и 0, если элемент с номером k не входит в подмножество. Итак, каждому подмножеству соответствует своя последовательность длины n из нулей и единиц. Число всех возможных последовательностей длины n, составленных из нулей и единиц, равно по правилу умножения, 2×2×2×... ×2. Следовательно и число всех подмножеств множества А равно 2ⁿ. Этот результат также очевиден, если представить себе, что процесс набора некоторого подмножества множества А эквивалентен разбиению множества А на две части, тогда для каждого из n элементов множества А есть две возможности: попасть в одну часть (подмножество) или попасть в другую часть (остаться в исходном множестве) и потому всего подмножеств 2ⁿ - число разбиений множества А на две части.

Найдем теперь число всех k -элементных подмножеств множества А, т.е. |М_k(А)|. Чтобы построить k -элементное подмножество множества А, нужно к (k - 1)-элементному подмножеству присоединить один из (n - k + 1) элементов, не входящих в это подмножество.

Поскольку (k - 1)-элементных подмножеств имеется |М_k-1(А)| и каждое из них можно сделать k -элементным (n - k + 1) способами, то таким образом получим (n – k + l) |М_k-1(A)| подмножеств. Но не все они будут разными, так как каждое k -элементное подмножество можно построить k способами. Поэтому полученнок число в k раз больше, чем число k -элементных подмножеств. Следовательно,

k |М_k(А)| = (n - k + 1) |М_к-1(А)|.

Отсюда находим:

|M_k(A)| = |М_k-1(А)| = |М_k-2(А)| = …= |М₁(А)|

В этой формуле |М₁(А)| - число одноэлементных подмножеств множества А, но это число равно количеству элементов в множестве А, то есть n. Подставляя вместо |М₁(А)|число n, получим:

|M_k(A)| = .

Таким образом, мы установили, что число k -элементных подмножеств множества А, состоящего из n элементов, равно числу сочетаний из n по k. Так как все подмножества состоят из всевозможных k -элементных подмножеств множества А, то приходим к уже известной нам формуле:

.

Обобщим теперь рассмотренную задачу о подмножествах следующим образом. Поставим вопрос: сколькими способами можно разложить множество А, состоящее из n элементов, на сумму из m подмножеств:

А = А₁UА₂UА₃U…….UА_m

так, чтобы |А₁| = n ₁, |А₂| = n ₂, …, |А_m| = n _m, n _i > 0, ,

n ₁ + n ₂ + n ₃ +... + n _m = n, множества A_i, , не имеют общих элементов. Очевидно, рассмотренный ранее вопрос о подмножествах множества А есть частный случай рассматриваемой ситуации при m = 2.

Все описанные разбиения множества А на m групп

А₁, А₂, А₃, …….,А_m можно получить так: возьмем произвольное n ₁-элементное подмножество A₁ множества А (это можно сделать способами); среди (n – n ₁) оставшихся элементов возьмем n ₂-элементное подмножество А₂ (это можно сделать способами); и т.д. Общее число способов выбора различных множеств А₁, А₂, А₃, …….,А_m по правилу умножения равно

Такие выражения, как уже было сказано ранее, называются полиномиальными коэффициентами.

Теперь стало возможным ответить и на вопрос о полном числе способов разложения множества на сумму m подмножеств. Очевидно, полное число способов есть сумма по всем возможным способам разложения, то есть по всем n 1, n 2, n 3,..., n m = n, n_i > 0, , таким что n₁ + n₂ + n₃ +... + n_m = n.

Итак, полное число способов разложения множества А, состоящего из n элементов, определяется выражением

При m = 2 мы получаем общее число подмножеств множества А = 2ⁿ.

Упражнения и задачи

Задача 1. На вершину горы ведет 9 дорог. Сколькими способами турист может подняться на гору и спуститься с нее? Дайте ответ на этот же вопрос, если подъем и спуск осуществляются различными путями.

Задача 2. Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5?

Задача 3. Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5, если каждую из этих цифр можно использовать не более одного раза?

Задача 4. Сколько четырехзначных чисел можно написать с помощью цифр 0, 1, 2, 3, 4, 5?