Множество-степень

В некоторых случаях необходимо знать не отдельные подмножества некоторого множества, а все подмножества этого множества. Множество всех подмножеств множества A называется множеством-степенью множества A и обозначается символом P (A). Таким образом, P (A) является сокращенным обозначением для «формы от x»

Например, если A = {1, 2, 3}, то

P (A) = { , {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

Интерес вызывает вопрос о мощности множества P (A). Нетрудно заметить, что перечисление всех подмножеств множества A получается перебором всех сочетаний пустого, одно, двух и трехэлементных подмножеств множества A. Если множество A состоит из n элементов, то мощность множества-степени P (A) будет определяться выражением

| P (A)| = (1)

где

(2)

а сочетания и определяют несобственные подмножества множества A (пустое множество и само множество A).

Приведем, может быть, не самое изящное, но одно из самых простых и наглядных доказательств того, что

| P (A)| = . (3)

Вычисление при различных k для наглядности удобно выполнять по так называемому треугольнику Паскаля, который строится следующим образом. В вершине треугольника стоит единица, которая определяется по формуле (2) при n = k = 0. Для n = 1 число k будет принимать два значения: 0 и 1. Поэтому из формулы (2) мы получим два значения числа сочетаний: соответственно 1 и 1. Эти значения будут представлять основание первого треугольника.

Для n = 2 число k будет принимать три значения: 0, 1 и 2. Поэтому получаем три значения числа сочетаний – соответственно 1, 2 и 1. Они будут представлять основание второго треугольника. Аналогично для n = 3 будем иметь четыре значения для числа сочетаний – 1, 3, 3, 1, которые будут представлять основание третьего треугольника и т.д.

По треугольнику Паскаля очень просто вычисляются различные значения сочетаний, не используя формулу (2). Для получения каждого значения числа сочетаний в следующем основании треугольника нужно сложить предыдущее и последующее значения числа сочетаний из основания предыдущего треугольника.

Обобщение всего сказанного представим в виде таблицы 1, в первом столбце которой запишем различные значения n, во втором столбце – числа 2 ⁿ , в третьем столбце представим треугольник Паскаля, в четвертом – числа, получающиеся путем суммирования чисел, стоящих в основаниях соответствующего треугольника Паскаля или, что то же самое, рассчитанные по формуле (2).

Таблица 1

n		Треугольник Паскаля
		1 1
		1 2 1
		1 3 3 1
		1 4 6 4 1
		1 5 10 10 5 1
…	…	…	…

Из приведенной таблицы видим, что второй и четвертый столбцы табл. 1 полностью совпадают, что и доказывает формулу 3.