ТГиК-2019-Лекция-02.09.2019

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Тема лекции - Комбинаторика. Правила комбинаторики

О комбинаторике

Комбинаторика — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана с другими областями математики — алгеброй, геометрией, теорией вероятностей и применяется в различных областях знаний (например, в генетике, информатике, статистической физике).

Разделы комбинаторики

  • Перечислительная

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

  • Экстремальные задачи

Требуется найти какие-либо максимальные или минимальные характеристики в заданных условиях, например, найти максимальный размер графа.

Правила комбинаторики

Прежде всего, рассмотрим некоторые вспомогательные понятия.

\( |A| \) - мощность множества А. Для конечных множеств мощность множества - это количество элементов в нём.

\( С=A×B \) - декартово произведение С множеств А и В. По определению \( C = \left \{ <a,b> \mid a\in A, b\in B \right \} \)

Правило сложения

Пусть множества А и В - конечные и не пересекающиеся, т.е. \(A\cap B = \varnothing \). Тогда \(|A\cup B|=|A|+|B|\)

Правило умножения

Пусть множества А и В - конечные. Рассмотрим декартово произведение C=A×B. Тогда \(|C|=|A|*|B|\)

Вывод правила умножения из правила сложения.

1) В декартовом произведении зафиксируем первый элемент пары <a,b>, а второй оставим изменяющимся.

2) Тогда \( \left \{ <a,b>\mid a\in A, b\in B \right \} \) превратится в \( C_1=\bigcup_{a\in A} \left \{ <a,b> \mid b\in B \right \}\)

3) Рассмотрим мощность множества \(С_1\)\[|C_1| = \sum_{a\in A}{|B|} = |A|*|B| \]

Обобщения правил сложения и умножения для n множеств

Обобщение правила сложения для случая n множеств

Пусть \(А_1, А_2, ..., А_n\) - конечные множества, причём \(A_{i}\cap A_{j}\ne \varnothing \Longleftrightarrow i=j \)

Тогда \(|\bigcup^n_{i=1} A_i| = \sum^n_{i=1} |A_i|\)

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

1) Доказательство проведем по индукции. Пусть есть \(А_{n+1}: А_{i}\cap A_{n+1} = \varnothing , \forall i≤n \)

2) \(|\bigcup^n_{i=1} A_i \cup (A_n \cup A_{n+1})| = \sum^{n-1}_{i=1} |A_i| + |A_n \cup A_{n+1}| = \sum^{n+1}_{i=1} |A_i|\)

Замечание: Для правила произведения также есть обобщение, а именно\[|A_1 \times A_2 \times ... \times A_n| = |A_1| \times |A_2| \times ...\times |A_n| = \prod^n_{i=1}|A_i|\]