дискретная-математика — Количество подмножеств
Найдите число таких 6-элементных подмножеств X множества <1,2,…,15>, что никакие два элемента X не отличаются на 1.
Такая задача уже была, но там были просто подмножества, без ограничения на их размер, мне кажется, что это существенно в этой задаче.
задан 19 Дек ’22 16:29
2 ответа
Если рассматривать подмножества произвольного размера, то получаются числа Фибоначчи. Для подмножеств фиксированного размера получатся обычные числа сочетаний. Такая задача (возможно, с другими параметрами) также встречалась.
Пусть мы выбрали 6-элементное подмножество. Упорядочим числа по возрастанию. За каждым из пяти элементов кроме последнего находится не входящее в подмножество число. Вычеркнем его, и останется 10 чисел, среди которых мы выбрали 6. Эти числа можно занумеровать по порядку, и тогда число способов выбора будет равно $%C_<10>^6=C_<10>^4=210$%.
По каждому такому выбору можно однозначно восстановить исходные номера всех чисел. А именно, если слева от числа находится $%k$% выбранных в подмножество, то увеличим его номер на $%k$%.
Пример: пусть из $%\<1,2. 10\>$% выбрали шесть чисел $%2,3,5,7,9,10$%. Тогда по правилу «плюс $%k$%» номера от 1 до 10 превратятся в номера от 1 до 15, а изначально было выбрано $%\<2=2+0,4=3+1,7=5+2,10=7+3,13=9+4,15=10+5\>$%.
Количество подмножеств в множестве
Множество A является подмножеством множества B:
A⊂B
если все элементы, принадлежащие A, также принадлежат множеству B.
Пустое множество Ø и само B также включаются в число подмножеств множества B:
Количество подмножеств из k элементов у множества из n элементов равно биномиальному коэффициенту, числу сочетаний из n по k:
Соответственно, общее количество подмножеств у множества из n элементов определяется суммой:
Из комбинаторики известно, что указанная сумма равна 2^n. Таким образом, общее число подмножеств у множества, состоящего из n элементов, составляет 2^n.
Пример
У множества
Количество подмножеств данного множества
Напомним понятие подмножества, введенное в главе 1. Если каждый элемент множества В принадлежит множеству А, то В называется подмножеством множества А: АВ или ВА.
Считается, что пустое множество Ø 
является подмножеством любого множества: Ø 
А. Для всякого множества А имеет место соотношение АА. Если В А, А В, то А = В. Подмножество В множества А называется собственным, если В ≠ А и В ≠ Ø 
.
Если задано некоторое множество А, то можно рассматривать новое множество М(А) — множество всех его подмножеств. Через Мk(А) будем обозначать множество всех подмножеств множества А, которые имеют k элементов:
В Мk(А), если |В| = k.
Поставим вопрос: сколько разных подмножеств имеет множество, состоящее из n элементов, сколько разных k-элементных подмножеств имеет это множество. В принятых обозначениях эти вопросы состоят в вычислении
|М(А)| и |Мk(А)|, если |А| = n
Пример. Пусть А = <а,b,с>, тогда
Покажем, что число всех подмножеств множества из n элементов равно 2 n . Действительно, переномеруем все элементы множества А, построим последовательность длины n из нулей и единиц по следующему принципу: на k-ом месте пишем 1, если элемент с номером k входит в подмножество, и 0, если элемент с номером k не входит в подмножество. Итак, каждому подмножеству соответствует своя последовательность длины n из нулей и единиц. Число всех возможных последовательностей длины n, составленных из нулей и единиц, равно по правилу умножения, 2×2×2× . ×2. Следовательно и число всех подмножеств множества А равно 2 n . Этот результат также очевиден, если представить себе, что процесс набора некоторого подмножества множества А эквивалентен разбиению множества А на две части, тогда для каждого из n элементов множества А есть две возможности: попасть в одну часть (подмножество) или попасть в другую часть (остаться в исходном множестве) и потому всего подмножеств 2 n — число разбиений множества А на две части.
Найдем теперь число всех 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-элементных подмножеств. Следовательно,
|Mk(A)| = 
|Мk-1(А)| =
|Мk-2(А)| = …= 
|М1(А)|
В этой формуле |М1(А)| — число одноэлементных подмножеств множества А, но это число равно количеству элементов в множестве А, то есть n. Подставляя вместо |М1(А)|число n, получим:
|Mk(A)| = 
.
Таким образом, мы установили, что число k-элементных подмножеств множества А, состоящего из n элементов, равно числу сочетаний из n по k. Так как все подмножества состоят из всевозможных k-элементных подмножеств множества А, то приходим к уже известной нам формуле:
.
Обобщим теперь рассмотренную задачу о подмножествах следующим образом. Поставим вопрос: сколькими способами можно разложить множество А, состоящее из n элементов, на сумму из m подмножеств:
так, чтобы |А1| = n1, |А2| = n2, …, |Аm| = nm, ni > 0, 
,
n1 + n2 +n3 +. + nm = n, множества Ai, 
, не имеют общих элементов. Очевидно, рассмотренный ранее вопрос о подмножествах множества А есть частный случай рассматриваемой ситуации при m = 2.
Все описанные разбиения множества А на m групп
А1, А2, А3, …….,Аm можно получить так: возьмем произвольное n1-элементное подмножество A1 множества А (это можно сделать
способами); среди (n – n1) оставшихся элементов возьмем n2-элементное подмножество А2 (это можно сделать 
способами); и т.д. Общее число способов выбора различных множеств А1, А2, А3, …….,Аm по правилу умножения равно
Такие выражения, как уже было сказано ранее, называются полиномиальными коэффициентами.
Теперь стало возможным ответить и на вопрос о полном числе способов разложения множества на сумму m подмножеств. Очевидно, полное число способов есть сумма по всем возможным способам разложения, то есть по всем n1, n2, n3. , nm = n, ni > 0, 
, таким что n1 + n2 +n3 +. + nm =n.
Итак, полное число способов разложения множества А, состоящего из n элементов, определяется выражением
При m = 2 мы получаем общее число подмножеств множества А = 2 n .
Упражнения и задачи
Задача 1. На вершину горы ведет 9 дорог. Сколькими способами турист может подняться на гору и спуститься с нее? Дайте ответ на этот же вопрос, если подъем и спуск осуществляются различными путями.
Задача 2. Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5?
Задача 3. Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5, если каждую из этих цифр можно использовать не более одного раза?
Задача 4. Сколько четырехзначных чисел можно написать с помощью цифр 0, 1, 2, 3, 4, 5?
Как найти все подмножества множеств
На простом примере напомним, что называется подмножеством, какие бывают подмножества (собственные и несобственные), формулу нахождения числа всех подмножеств, а также калькулятор, который выдает множество всех подмножеств.
Пример 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. Если вам необходимо решение своей задачи, то набираем элементы множества на латинице, через запятую, как показано в примере.