- •Основные понятия теории множеств. Множества и отношения.
- •Основные операции над множествами. Соотношения между множествами.
- •Диаграммы Эйлера-Венна. Универсальное множество.
- •Перестановки. Бинарные отношения.
- •Высказывания и логические операции над ними. Повествовательные предложения.
- •Основные операции над множествами.
- •Декартово произведение множеств.
- •Числовые множества. Принадлежность.
- •Элементы комбинаторики. Перестановки. Сочетания. Размещения.
- •Представление бинарных отношений графами.
Элементы комбинаторики. Перестановки. Сочетания. Размещения.
Комбинато́рика (Комбинаторный анализ) — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана со многими другими областями математики — алгеброй, геометрией, теорией вероятностей, и имеет широкий спектр применения в различных областях знаний (например в генетике, информатике, статистической физике).
Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».
Примеры комбинаторных конфигураций и задач
Для формулировки и решения комбинаторных задач используют различные модели комбинаторных конфигураций. Примерами комбинаторных конфигураций являются:
Размещением из n элементов по k называется упорядоченный набор из k различных элементов некоторого n-элементного множества.
Перестановкой из n элементов (например чисел 1,2,…,n) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n.
Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.
Композицией числа n называется всякое представление n в виде упорядоченной суммы целых положительных чисел.
Разбиением числа n называется всякое представление n в виде неупорядоченной суммы целых положительных чисел.
Примерами комбинаторных задач являются:
Сколькими способами можно разместить n предметов по m ящикам так, чтобы выполнялись заданные ограничения?
Сколько существует функций F из m-элементного множества в n-элементное, удовлетворяющих заданным ограничениям?
Сколько существует различных перестановок из 52 игральных карт?
Ответ: 52! (52 факториал) то есть 80658175170943878571660636856403766975289505440883277824000000000000 или примерно 8.0658 × 1067.
При игре в кости бросаются две кости и выпавшие очки складываются, сколько существует комбинаций, таких, что сумма очков на верхних гранях равна двенадцати?
Решение: Каждый возможный исход соответствует функции (аргумент функции — это номер кости, значение — очки на верхней грани). Очевидно, что лишь 6+6 даёт нам нужный результат 12. Таким образом существует лишь одна функция, ставящая в соответствие 1 число 6, и 2 число 6. Или, другими словами, существует всего одна комбинация, такая, что сумма очков на верхних гранях равна двенадцати.
Представление бинарных отношений графами.
Под бинарным отношением на множестве M мы понимаем произвольное подмножество EМMxM.
Графом отношения называется ориентированный граф, в котором любая дуга (v,w) существует только в том случае, если элементы v и w, представляемые вершинами v и w, находятся в данном бинарном отношении r, т.е. vrw.
Граф отношения является наглядной формой представления отношения r, так как он полностью перечисляет все упорядоченные пары вершин-элементов, для которых отношение r имеет место. Граф отношения может обладать специальными свойствами: рефлексивностью, симметричностью, антисимметричностью, транзитивностью и т.д., отражающими соответствующие свойства отношения.
(а) Отношение r называется рефлексивным на множестве M, если для всякого aОM верно a ra. Отношение r называется нерефлексивным на множестве M, если ни для какого aОM не выполняется a ra.
(б) Будем говорить, что граф отношения является рефлексивным, если каждая вершина имеет петлю, и антирефлексивным, если ни одна вершина петли не имеет.
(а) Отношение r называется симметричным на множестве M, если для каждой пары a и b элементов M из a rb следует bra. Отношение r называется антисимметричным на множестве M, если для несовпадающих элементов a и b из arb следует не bra.
(б) Будем говорить, что граф отношения является симметричным, если каждой дуге (v,w) соответствует дуга (w,v), и антисимметричным, если каждая дуга (v,w) исключает существование дуги (w,v) (заметим, что антисимметричный граф может как иметь петли, так и не иметь их!).
(а) Отношение r называется транзитивным на множестве M, если для любых трех элементов a,b и g, принадлежащих M, из arb и brg следует arg. Отношение r называется антитранзитивным на множестве M, если для любых трех элементов a,b и g, принадлежащих M, из arrb и brg следует не arg.
(б) Будем говорить, что граф отношения является транзитивным, если существование дуг (v,w) и (w,u) означает существование дуги (v,u), и антитранзитивным, если существование дуг (v,w) и (w,u) означает несуществование указанной дуги. ¦¦¦
Отношение r на множестве M, которое одновременно рефлексивно, симметрично и транзитивно, называется отношением эквивалентности.
Графом отношения эквивалентности называется граф, являющийся рефлексивным, симметричным и транзитивным.
Отношение r называется полным отношением, если для всякой пары a,b несовпадающих элементов множества M имеет место arb, либо bra. Отношение, не являющееся полным, называется неполным.
Граф полного отношения (полный граф) характеризуется наличием хотя бы одной дуги для любой пары вершин. В графе неполного отношения некоторые пары вершин не соединены дугами.
(а) Отношение r называется отношением порядка, если оно анти-симметричное и транзитивное.
Соответственно, графом отношения порядка называется антисим-метричный и транзитивный граф отношения.
(б) Отношение r называется отношением полного порядка (полным порядком), если оно антисимметричное, транзитивное и полное. Отношение r называется отношением неполного порядка (неполным порядком), если оно антисимметричное, транзитивное и неполное.
Графом отношения полного порядка называется антисимметричный, транзитивный и полный граф отношения. Графом отношения неполного порядка называется антисимметричный, транзитивный и неполный граф отношения.
(в) Отношение называется отношением строгого порядка, если оно антирефлексивное, антисимметричное и транзитивное. Отношение называется отношением нестрогого порядка, если оно рефлексивное, антисимметричное и транзитивное.
Графом отношения строгого порядка называется антирефлексивный, антисимметричный и транзитивный граф отношения. Графом отношения нестрогого порядка называется рефлексивный, антисимметричный и транзитивный граф отношения.