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

Если задано некоторое множество А, то можно рассматривать новое множество М (А) – множество всех его подмножеств.

Пример 1. Сколько подмножеств имеет множество А={é}?

По свойствам отношения включения, имеем Æ А и А .

Таким образом, одноэлементное множество А={é} имеет 2 подмножества.

Пример 2. Сколько всего подмножеств имеет двухэлементное множество А={а, в}?

По свойствам отношения включения, имеем Æ А и А .

Одноэлементные подмножества: {а}, {в}.

Таким образом, двухэлементное множество А={а, в} всего имеет 4 подмножества.

Пример 3. Сколько всего подмножеств имеет трехэлементное множество А = {, ○, ◊}?

По свойствам отношения включения, имеем Æ А и А .

Одноэлементные подмножества: {}, {○}, {◊}.

Двухэлементные подмножества: {, ○}, {, ◊}, {○, ◊}.

Таким образом, трехэлементное множество А = {, ○, ◊} всего имеет 8 подмножеств.

Пример 4. Сколько всего подмножеств имеет четырехэлементное множество А = {а, в, с, d}?

По свойствам отношения включения, имеем Æ А и А .

Одноэлементные подмножества: {а}, {в}, {с}, {d}. Двухэлементные подмножества: {а, в}, {а, с}, {a, d}, {в, с}, {в, d}, {с, d}. Трехэлементные подмножества: {а, в, с}, {a, в, d}, {а, с, d}, {в, с, d}.

Таким образом, четырехэлементное множество всего имеет 16 подмножеств.

Нетрудно заметить, что с увеличением количества элементов множества А, число всех его подмножеств значительно увеличивается. Возникает вопрос: сколько подмножеств имеет множество из n – элементов?

Ответ на поставленный вопрос дает следующее утверждение.

Теорема 5.Конечное множество, содержащее n элементов, имеет 2^п подмножеств, то есть если А_п = {а₁, а₂, ... , a_п }, то п(М(А_п))=2^п.

 Доказательствопроведем, используя метод математической индукции.

1) Путь п = 1, то есть А₁ = { а₁}. Значит, М(А₁)= {Æ, { а₁}}.

В этом случае п(М(А₁)) = 2¹ = 2 что и доказывает справедливость теоремы при п = 1.

2) Пусть п = к, то есть A_к = { а₁, а₂, ..., a_к }.

Предположим, что п(М(A_к)) = 2 , то есть множество A_к имеет 2  подмножеств.

3) Докажем, что тогда множество A_к+1, имеет 2  подмножеств. В самом деле, если к элементам множества A_к, содержащего к элементов, добавить еще один элемент a_к+1, то к имеющимся 2  подмножествам добавятся еще 2  новых подмножества, и, следовательно, множество A_к+1, содержащее к + 1 элементов, будет иметь 2  + 2  = 2× 2  = 2  подмножеств.

Таким образом, п(М(A_к+1)) = 2 .

На основании метода математической индукции можно сделать вывод, что Теорема.  5 справедлива для любого натурального числа п. Теорема доказана.

Понятие факториала

Название «факториал» происходит от слова «factor» − «множитель». Термин «factorielle» ввёл французский математик Луи Арбогаст (1759–1803) в 1800 году.[13]

Факториал– это функция, определённая на множестве целых неотрицательных чисел , значение которой равно произведению целых неотрицательных чисел от 1 до данного числа n, то есть 1∙2∙3∙ …∙n; Обозначают  символом n!.

По определению 0! = 1, 1! = 1.

Обозначение n! впервые использовал французский математик Христиан Крамп (1760 – 1826 гг.) в 1808 году.

По определению факториала имеем: , .

Пример 1. Вычислим:

Пример 2. Упростим выражение:

Пример 3. Докажем формулу .

ÿ Воспользуемся методом математической индукции.

1) При п=1 имеем,  откуда 1=1, значит для п=1 формула верна.

2) Предположим, что формула верна, для п=к, то есть .

3) Докажем, что формула верна, для п=к+1, то есть

.

Действительно,

= , что и требовалось доказать.

На основании метода математической индукции заключаем, что формула верна для любого натурального числа п.

Пример 4. Найти сумму

Решение.Заменим каждое слагаемое разностью по формуле

.

Имеем,

=  так как все слагаемые в левой части равенства, за исключением второго и предпоследнего взаимно уничтожаются.

Следовательно, =