Как найти все подмножества множеств
На простом примере напомним, что называется подмножеством, какие бывают подмножества (собственные и несобственные), формулу нахождения числа всех подмножеств, а также калькулятор, который выдает множество всех подмножеств.
Пример 1. Дано множество А = <а, с, р, о>. Выпишите все подмножества
данного множества.
Решение:
Несобственные: <а, с, р, о>, Ø.
Всего: 16 подмножеств.
Пояснение. Множество A является подмножеством множества B если каждый элемент множества A содержится также в B.
• пустое множество ∅ является подмножеством любого множества, называется несобственным;
• любое множество является подмножеством самого себя, также называется несобственным;
• У любого n-элементного множества ровно 2 n подмножеств.
Последнее утверждение является формулой для нахождения числа всех подмножеств без перечисления каждого.
Вывод формулы: Допустим у нас имеется множество из n-элементов. При составлении подмножеств первый элемент может принадлежать подмножеству или не принадлежать, т.е. первый элемент можем выбрать двумя способами, аналогично для всех остальных элементов (всего n-элементов), каждый можем выбрать двумя способами, и по правилу умножения получаем: 2∙2∙2∙ . ∙2=2 n
Для математиков сформулируем теорему и приведем строгое доказательство.
Теорема . Число подмножеств конечного множества, состоящего из n элементов, равно 2 n .
1. Для n = 1 (база индукции) (и даже для n = 2, 3) теорема доказана.
2. Допустим, что теорема доказана для n = k, т.е. число подмножеств множества, состоящего из k элементов, равно 2 k .
3. Докажем, что число подмножеств множества B, состоящего из n = k + 1 элемента равно 2 k+1 .
Выбираем некоторый элемент b множества B. Рассмотрим множество A = B \ . Оно содержит k элементов. Все подмножества множества A – это подмножества множества B, не содержащие элемент b и, по предположению, их 2 k штук. Подмножеств множества B, содержащих элемент b, столько же, т.е. 2 k
штук.
Следовательно, всех подмножеств множества B: 2 k + 2 k = 2 ⋅ 2 k = 2 k+1 штук.
Теорема доказана.
В примере 1 множество А = состоит из четырех элементов, n=4, следовательно, число всех подмножеств равно 2 4 =16.
Если вам необходимо выписать все подмножества, или составить программу для написания множества всех подмножеств, то имеется алгоритма для решения: представлять возможные комбинации в виде двоичных чисел. Поясним на примере.
Пример 2. Eсть множество , в соответствие ставятся следующие числа:
000 = <0>(пустое множество)
001 =
010 =
011 =
100 =
101 =
110 =
111 =
Калькулятор множества всех подмножеств.
В калькуляторе уже набраны элементы множества А = , достаточно нажать кнопку Submit. Если вам необходимо решение своей задачи, то набираем элементы множества на латинице, через запятую, как показано в примере.
Научный форум dxdy
Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".
Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.
Не ищите на этом форуме халяву , правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.
Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.
Теория множеств
Пожалуйста, подскажите, как одолеть следующие доказательства?
3) Пусть множество А содержит n элементов, а его подмножество В содержит k элементов. Сколько существует множеств С, для которых 
?
Я размышлял так (может, неправильно). Зафиксируем множество В. Тем самым мы зафиксируем некоторые k элементов из n. Соответственно n-k останется, и каждый из них может поучаствовать в формировании множества С. Рассмотрим множества, получаемые из множества В присоединением одного из n-k элементов. Таких множеств может быть создано 
и 
?
Число различных k-элементарных подмножеств n-элементарного множества
где сокращение п! = п * (п — 1) * . * 3 * 2 * 1 называется факториалом числа n (читается n-факториал). Причем 0! = 1. А сокращение .
Доказательство.Чтобы построить k-элементное подмножество множества А, необходимо к (k — 1)-элементному множеству присоединить один из п — k + 1 элементов, которые не входят в это подмножество. Поскольку число (k — 1)элементных подмножеств равно , И каждое из этих подмножеств можно сделать k-элементным п — k + 1 способами, по основному правилу комбинаторики получаем число * (n — k + 1) подмножеств. Однако не все эти подмножества будут различными, поскольку любое k-элементарное подмножество можно также построить k способами. Следовательно,
Поскольку – число одноэлементных подмножеств множества А – равно n, то
Произвольное k-элементное подмножество множества А называется комбинацией, или выборкой, а число – числом комбинаций или сочетаний из n элементов по k элементов.
Биномиальные коэффициенты имеют интересную геометрическую интерпретацию. Пусть имеем прямоугольную шахматную доску размером m на n, размещенную на координатной плоскости. Эта доска состоит из m*n элементарных квадратов, разделенных n — 1 горизонтальной линией и m — 1 вертикальной. Определим, сколькими разными самыми короткими путями можно попасть из точки (0, 0) в точку (m, n)на этой доске.
Каждый самый короткий путь, ведущий из точки (0, 0) в точку (m,n), состоит, очевидно, из m + n сторон элементарных квадратов, среди которых m горизонтальных и n вертикальных. Эти пути отличаются между собой только 1 числом вертикальных и горизонтальных сторон. Значит, общее количество путей равно числу способов, какими из т + n сторон можно выбрать n вертикальных, т.е. это число равно .
Заметим, что можно было бы вести подсчет не по вертикальным сторонам,
а по горизонтальным. То есть, существует различных самых коротких путей и, следовательно, справедливо равенство:
Данное равенство имеет название «формула симметрии».
Из этой формулы имеем следствие:
имеющее название «формула сложения». Докажем данное следствие.
Доказательство:
Пример:
Сборная команда университета по волейболу насчитывает 15 человек. Сколько разных вариантов должен рассмотреть тренер перед игрой, чтобы заявить список игроков на игру?
Решение:Число игроков волейбольной команды равно шести. Значит, число всех возможных вариантов — это число различных подмножеств, состоящих из шести элементов в множестве из пятнадцати элементов. Следовательно, по теореме 2 имеем