![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
В некоторых случаях необходимо знать не отдельные подмножества некоторого множества, а все подмножества этого множества. Множество всех подмножеств множества 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 n , в третьем столбце представим треугольник Паскаля, в четвертом – числа, получающиеся путем суммирования чисел, стоящих в основаниях соответствующего треугольника Паскаля или, что то же самое, рассчитанные по формуле (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.
Дата публикования: 2015-01-10; Прочитано: 4499 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!