Найти все k-элементные подмножества данного множества

Ordm; Понятие множества

Множество A, состоящее из элементов x, y, z, …

A={x, y, z, …}

Множество A, состоящее из элементов x, удовлетворяющих условию P(x)

A={x|P(x)}

Множества называются равными, если они состоят из одних и тех же элементов.

Пример

Множество делителей числа 8

{1, 2, 4, 8}={n∈ ℕ |8n∈ ℕ }.

Множество букв слова " мама"

{" а", " м" }.

Мы придерживаемся принятого в языках программирования соглашения, записывая строковые данные в кавычках. При этом сами кавычки частью строки не являются, а служат только для удобочитаемости.

Элементом множества может быть другое множество, но никакое множество не может быть элементом самого себя. Игнорирование этого правила приводит к известным парадоксам теории множеств.

Пример

Рассмотрим множество A всех множеств. Очевидно, A∈ A т.е. оно является элементом самого себя.

Назовем множество правильным, если оно не является элементом самого себя. Пусть B — множество всех правильных множеств. Очевидно, A∉ B.

Вопрос: является ли B правильным?

Если B является правильным, то оно является элементом самого себя, а значит не является правильным.

Если же B не является правильным, то оно не является элементом самого себя, а значит является правильным.

Пример

Брадобрей в некоторой деревне бреет тех и только тех мужчин, которые не бреются сами. Вопрос: кто бреет брадобрея?

Можно предположить, что брадобрей — женщина. Но как быть, если все-таки брадобрей — мужчина? В этом случае получаем парадокс, аналогичный сформулированному выше.

Пример

Обратите внимание на случай, когда одно множество является элементом другого:

{{1}, {2, 3, 4}, 5}≠ {1, 2, 3, 4, 5}

1∉ {{1}, {2, 3, 4}, 5}

{1}∈ {{1}, {2, 3, 4}, 5}

{1}∉ {1, 2, 3, 4, 5}

Пустое множество ∅ не содержит элементов.

Множество называется конечным, если оно содержит конечное число элементов. Число элементов множества A называется его мощностью и обозначается |A|.

Пример

Мощность пустого множества

|∅ |=0.

Мощность множества простых делителей числа 10

|{2, 5}|=2.

Если множество содержит другие множества в качестве элементов:

|{{1, 2}, {3, 4}, 5}|=3.

Дискретная математика изучает конечные множества с различными структурами. Здесь и далее в курсе дискретной математики мы рассматриваем только конечные множества.

Если из x∈ B следует x∈ A, то множество B называется подмножеством множества A. Обозначение: B⊆ A. Если при этом B не совпадает с A, то пишут B⊂ A.

Пример

Пустое множество является подмножеством любого множества.

Множество букв любого слова является подмножеством множества всех букв.

Множество граждан некоторого государства является подмножеством множества землян.

Если B⊆ A, то очевидно |B|⩽ |A|. Обратное утверждение, разумеется, неверно.

Найти объединение, пересечение, дополнение заданных множеств.

1. Объединение множеств A∪ B — множество, состоящее из элементов, принадлежащих хотя бы одному из множеств A, B. Аналогично определяется объединение любого числа множеств: x∈ ⋃ nAn, если найдется номер n такой, что x∈ An.

Пересечение множеств A∩ B — множество, состоящее из элементов, принадлежащих каждому множеству A, B. Аналогично определяется пересечение любого числа множеств: x∈ ⋂ nAn, если для любого номера n выполняется x∈ An.

Дополнение A\B множества B во множестве A или разность множеств — множество, состоящее из элементов множества A, не принадлежащих множеству B.

Пусть A — множество чисел, делящихся на 2, B — на 3, C — на 5. Тогда A∩ B — множество чисел, делящихся на 6, A∩ C — на 10, B∩ C — на 15, A∩ B∩ C — на 30. Находим:

|A|=[10002]=[500]=500,
|B|=[10003]=[333.3…]=333,
|C|=[10005]=[200]=200,
|A∩ B|=[10006]=[166.6…]=166,
|A∩ C|=[100010]=[100]=100,
|B∩ C|=[100015]=[66.6…]=66,
|A∩ B∩ C|=[100030]=[33.3…]=33.

Поэтому:

|A∪ B∪ C|=500+333+200-166-100-66+33=734
1000-|A∩ B∩ C|=1000-734=266

Рассмотренные операции объединения, пересечения и дополнения могут быть наглядно интерпретированы с помощью так называемых диаграмм Эйлера – Венна:

A B A∪ B A B A∩ B A B A\B
Задача на формулу включения-исключения

Теорема   (Формулы включения-исключения)

|A∪ B|=|A|+|B|-|A∩ B|

|A∪ B∪ C|=|A|+|B|+|C|-|A∩ B|-|A∩ C|-|B∩ C|+|A∩ B∩ C|

|A∩ B|=|A|+|B|-|A∪ B|

|A∩ B∩ C|=|A|+|B|+|C|-|A∪ B|-|A∪ C|-|B∪ C|+|A∪ B∪ C|

Доказательство   Показать

Пример

В группе из 25 студентов каждый изучает хотя бы один инстранный язык. Известно, что 22 человека изучают английский язык, 17 — китайский, 10 — испанский. Причем 15 человек изучают английский и китайский, 7 — английский и испанский, 5 — китайский и испанский. Сколько человек изучают все 3 языка?

Пусть A — множество студентов, изучающих английский, B — китайский, C — испанский. Тогда |A∪ B∪ C|=25, |A|=22, |B|=17, |C|=10, |A∩ B|=15, |A∩ C|=7, |B∩ C|=5. Подставляем в формулу:

25=22+17+10-15-7-5+|A∩ B∩ C|
|A∩ B∩ C|=3

Задача

Сколько среди чисел 1, 2, …, 1000 не делятся ни на 2, ни на 3, ни на 5?

Решение   Показать

Найти все разбиения данного множества

Разбиением множества A называется его представление в виде объединения

A=A1∪ A2∪ …∪ Ad

непустых попарно непересекающихся множеств A1, A2, …, Ad.

Пример

Перечислим все разбиения множества A={1, 2, 3, 4}:

A={1, 2, 3, 4}
A={1}∪ {2, 3, 4}
A={2}∪ {1, 3, 4}
A={3}∪ {1, 2, 4}
A={4}∪ {1, 2, 3}
A={1, 2}∪ {3, 4}
A={1, 3}∪ {2, 4}
A={1, 4}∪ {2, 3}
A={1}∪ {2}∪ {3, 4}
A={1}∪ {3}∪ {2, 4}
A={1}∪ {4}∪ {2, 3}
A={2}∪ {3}∪ {1, 4}
A={2}∪ {4}∪ {1, 3}
A={3}∪ {4}∪ {1, 2}
A={1}∪ {2}∪ {3}∪ {4}

Число всех разбиений множества A={a1, a2, …, an} зависит только от |A|=n и называется числом Белла Bn. Выражение для Bn довольно сложно и выходит за рамки нашего курса. Вот несколько первых чисел Белла:

Пример

Рассмотрим сложную функцию F(x)=f(g(x)). Из курса математического анализа известна формула для производной сложной функции

Fʹ =fʹ ⋅ gʹ.

Нетрудно получить формулу для 2-ой производной

Fʹ ʹ =fʹ ⋅ gʹ ʹ +fʹ ʹ ⋅ (gʹ)2.

Для дальнейшего нам будет удобнее обозначать производные не штрихами, а индексами, т.е. предыдущую формулу мы будем записывать в виде

F2=f1g2+f2g12.

Аккуратно продифференцировав эту формулу еще 2 раза, получим формулу для производной 4-го порядка:

F4=f1g4+f2(4g3g1+3g22)+f3(6g2g12)+f4g14.

Внимательно сравните полученную формулу с предыдущим примером.

Многочлен, выражающий n-ю производную сложной функции через f1, f2, …, fn и g1, g2, …, gn, называется n-ым многочленом Белла. Сумма коэффициентов многочлена Белла равна соответствующему числу Белла.

Пусть теперь число d фиксировано, т.е. требуется разбить n-элементное множество на d непустых непересекающихся подмножеств. Число таких разбиений называется числом Стирлинга и обозначается S(n, d). Очевидно,

Bn=S(n, n)+S(n, n-1)+…+S(n, 1).

Общую формулу для S(n, d) мы рассматривать не будем, приведем только таблицу нескольких первых значений.

Найти декартово произведение заданных множеств

Декартово произведение множеств A, B есть множество

A× B={(x, y)|x∈ A, y∈ B}.

Т.е. множество всех пар, в которых первый элемент принадлежит первому множеству, а второй — второму.

Аналогично определяется декартово произведение любого числа множеств:

A1× A2× …× AN={(x1, x2, …, xN)|∀ nxn∈ An}.

В частности, декартова степень множества:

AN={(x1, x2, …, xN)|∀ nxn∈ A}.

Пример

{1, 2}× ∅ =∅

{1}× {2}={(1, 2)}

{1, 2}× {2}={(1, 2), (2, 2)}

{2}× {1, 2}={(2, 1), (2, 2)}

{1, 2}2={(1, 1), (1, 2), (2, 1), (2, 2)}

{1, 2}3={(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2), (2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)}

{1, 2, 3}2={(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)}

 
Вычислить мощность декартова произведения

Теорема   (Мощность декартова произведения)

|A× B|=|A|⋅ |B|

|AN|=|A|N

Найти булеан заданного множества

Булеан множества A есть множество B(A) всех его подмножеств

B(A)={S|S⊆ A}.

Булеан B(A) иногда обозначается как 2A. Такое обозначение булеана и обозначение декартовой степени множества как AN имеют общий смысл — мы обсудим его позднее.

Пример

B(∅)={∅ }

B({1})={∅, {1}}

B({1, 2})={∅, {1}, {2}, {1, 2}}

B({1, 2, 3})={∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}

Вычислить мощность булеана заданного множества
Теорема   (Мощность булеана)

|B(A)|=2|A|

Доказательство   Показать

Найти все k-элементные подмножества данного множества

Часто возникает необходимость рассматривать множество подмножеств данного множества A, имеющих данную мощность k

Bk(A)={S|S⊆ A, |S|=k},

где k=0, 1, …, |A|.

Заметим, что для любого A

B0(A)={∅ },   B|A|(A)={A}.

Очевидно, что весь булеан получается как объединение попарно непересекающихся множеств

B(A)=B0(A)∪ B1(A)∪ …∪ B|A|(A)

Пример

B0({1, 2, 3})={∅ }

B1({1, 2, 3})={{1}, {2}, {3}}

B2({1, 2, 3})={{1, 2}, {1, 3}, {2, 3}}

B3({1, 2, 3})={{1, 2, 3}}