Марковский М.В. Комбинаторика (лекции) Кафедра.36 МИФИ

Комбинаторика Некоторые сведения из теории множеств

Множество – любое собрание объектов, определённых и хорошо различимых нашей интуицией или интеллектом, мыслимое как единое целое (Георг Кантор, 1872 г.).

Множества обозначаются большими буквами, элементы множества – малыми.

Принадлежность. Если x принадлежит множеству S (x является элементом S), то это обозначается xS. Если x не принадлежит S – xS.

Пример: S={a,b,c}, aS, bS, cS, dS.

Подмножество. Отношение включения. Если все элементы множества А принадлежат множеству B, то А – подмножество множества B. Это обозначается так: АB (А не строго включается в B). Если при этом в B есть элементы, не принадлежащие А, то это обозначают АB (А строго включается в B; A – собственное подмножество B).

Универсальное множество – множество всех элементов какого-либо определённого типа.

Пустое множество () – множество, не содержащее ни одного элемента. По определению, пустое множество является подмножеством любого множества. ( S : S).

Мощность множества. Для конечных множеств мощность –количество элементов во множестве. Мощность множества S обозначается |S|. Например, S={a, b, c}, |S|=3.

Множества называются равномощными (эквивалентными), если их мощность равны.

Операции над множествами

Пусть заданы множества A и B.

Объединение множеств A и B – множество АВ={x : xA или xB} (объединение содержит элементы, которые есть или в A, или в B, или в том и другом множестве). (нарисовать с помощью кругов Эйлера). АВ= BA.

Пересечение множеств A и B – множество АВ={x : xA и xB} (пересечение содержит элементы, которые есть одновременно и в A, и в B. (нарисовать). АВ= BA.

Дополнение до универсального множества. Если В – универсальное множество, и АВ, то дополнение ={x : xB и xA}. (нарисовать).

Произведение множеств A и B – множество AxB={<x, y> : xA, yB} (множество всех пар, первый элемент которых принадлежит множеству A, второй элемент – множеству B). Мощность произведения AxB равна произведению мощностей A и B (|AxB|=|A|*|B|). Произведение BxA не равно AxB, но их мощности совпадают (BxA  AxB, но |BxA| = |AxB|).

Пример: A={a, b, c}, B={c, d}, |A|=3, |B|=2.

АВ={a, b, c, d}, АВ={c}, AxB={<a,c>, <a,d>, <b,c>, <b,d>, <c,c>, <c,d>}, BxA={<c,a>, <c,b>, <c,c>, <d,a>, <d,b>, <d,c>}, |AxB|=6, |BxA|=6.

Оператор (функция) – правило, определяющее отображение некоторого множества X в некоторое множество Y. Обозначение: F : XY.

Пример: X={a, b, c, d}, Y={▲, ●, ■}. Возможный вариант функции: f(a)=■, f(b)=●, f(c)=■, f(d)=▲.

X Y

a ▲

b ●

c ■

d

Дискретное множество – множество, состоящее из изолированных точек (т.е. множество, не имеющее предельных точек). Например, множество натуральных чисел – дискретное множество, а множество действительных чисел – непрерывное множество.

Дискретная математика изучает свойства дискретных множеств и определённых на них операторов. Непрерывными множествами занимается математический анализ.

Лекция 1. Проблемы и задачи комбинаторики

Комбинаторика изучает приёмы нахождения числа различных комбинаций, составленных из данных предметов (элементов дискретного множества предметов) при определённых условиях.

Комбинация – некоторое сочетание предметов.

Типы комбинаторных проблем

1. Проблемы существования. Доказывается теоретически, что есть решение или нет.

2. Если решения задачи есть, то сколько их.

3. Выбрать наиболее экономичный способ решения.

Типы комбинаторных задач

1. Задача о маршрутах.

2. Задача о размещении.

3. Задача о покрытии.

4. Задача об укладке.

5. Задача о разбиении.

Все остальные задачи представляют собой объединение, пересечение, произведение указанных типов задач.

Пусть S – множество из n элементов (|S|=n). Говорят, что S – n-множество.

T ₁ T₂

T_n

Задача о покрытии

Найти такие множества T_i, i = 1, 2, …, r, чтобы (чтобы объединение этих множеств «покрыло» S). Например, застелить весь пол в комнате несколькими коврами. Ковры могут накладываться друг на друга (множества могут пересекаться), но незакрытых участков пола быть не должно.

Во многих задачах покрытие должно быть наиболее экономичным (так называемое минимальное покрытие), когда число множеств T_i должно быть минимальным, сами они должны содержать минимально возможное число элементов.

Задача о укладке

Найти такие попарно непересекающиеся множества T_i, i = 1, 2, …, r, (T_i T_j =  при ij) чтобы (чтобы объединение этих множеств вошло в S). (нарисовать)

Например, уложить несколько предметов в одну коробку. Между предметами могут быть пустые промежутки, но сами предметы друг с другом не пересекаются и укладываются в коробку.

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

Задача о разбиении

Найти такие попарно непересекающиеся множества T_i, i = 1, 2, …, r, (T_i T_j =  при ij) чтобы (чтобы объединение этих непересекающихся множеств дало S). (нарисовать)

Например, группы в институте – это разбиение множества студентов института. Группы не пересекаются, а их объединение дает множество всех студентов института.