Понятие комбинаторики и ее основные разделы

Термин «комбинаторика» происходит от латинского слова «combina», что в переводе на русский означает – «сочетать», «соединять».

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

Из истории комбинаторики

Комбинаторика занимается различного вида соединениями, которые можно образовать из элементов конечного множества. Некоторые элементы комбинаторики были известны в Индии еще во II в. до н. э. Нидийцы умели вычислять числа, которые сейчас называют "сочетания". В XII в. Бхаскара вычислял некоторые виды сочетаний и перестановок. Предполагают, что индийские ученые изучали соединения в связи с применением их в поэтике, науке о структуре стиха и поэтических произведениях. Например, в связи с подсчетом возможных сочетаний ударных (долгих) и безударных (кратких) слогов стопы из n слогов. Как научная дисциплина, комбинаторика сформировалась в XVII в.

Сейчас комбинаторные методы применяются в самой математике, т и вне ее – тория кодирования, планирование эксперимента, топология, конечная алгебра, математическая логика, теория игр, кристаллография, биология, статистическая физика, экономика и т.д.

Математик Лейбниц

Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».

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

Правило суммы:

Если элемент A можно выбрать m способами, а элемент B можно выбрать k способами, то выбор элемента A или B можно осуществить m + k способами.

Правило суммы можно перефразировать на теоретико-множественном языке. Обозначим через | A | число элементов множества A, через A [pic]B - объединение множеств A и B, через AxB - декартово произведение множеств A и B. Тогда для непересекающихся множеств A и B выполняется равенство: | A [pic]B | = | A | + | B |.

Обобщением правила суммы является правило произведения.

Правило произведения:

Если элемент A можно выбрать m способами, а после каждого выбора элемента A элемент B можно выбрать k способами, тогда, упорядоченную пару элементов (A, B) можно выбрать m*k способами.

Правило произведения можно распространить на выбор последовательности (x1, x2, …, xn) произвольной конечной длины n.

На теоретико-множественном языке правило произведения формулируется так: | Aх B | = | A | [pic]| B |

Перестановка

В комбинаторике перестановка- это упорядоченный набор чисел [pic] обычно трактуемый как биекция на множестве[pic] , которая числу i-й элемент из набора.

Число n при этом называется порядком перестановки.

В комбинаторике перестано́вка — это упорядоченный набор чисел обычно трактуемый как биекция на множестве, которая числу i ставит соответствие i -й элемент из набора.

Число n при этом называется порядком перестановки

Размещение

В комбинаторике размещением называется расположение «предметов» на некоторых «местах» при условии, что каждое место занято в точности одним предметом и все предметы различны.

Например, 4-элементное размещение 6-элементного множества {1,2,3,4,5,6}.

В отличие от сочетаний размещения учитывают порядок следования предметов. Так, например, наборы < 2,1,3 > и < 3,2,1 > являются различными, хотя состоят из одних и тех же элементов {1,2,3} (то есть, совпадают как сочетания).

Сочетание

В комбинаторике сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

Примеры комбинаторных соединений:

Нужно расставить 3 книги на полке (например 1-ая; 2-ая; 3-я или 2-ая; 1-ая; 3-я )

Составить пятизначные числа, 1, 2, 3, 4, 5 так, чтобы цифры в числе не повторялись (например 23451; 34521; 12543)

Существуют две схемы выбора элементов:

• Без повторений
• С повторениями

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

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

Структурная комбинаторика

К данному разделу относятся некоторые вопросы теории графов, а также теории матроидов.

Вероятностная комбинаторика

Этот раздел отвечает на вопросы вида: какова вероятность присутствия определённого свойства у заданного множества.

Топологическая комбинаторика

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

Сколько туристов не владеют ни одним языком?

Решение:

10-3=7 человек владеют английским и французским

8-3=5 человек владеют английским и немецким

5-3=2 человека владеют французским и немецким

Немецкий знают 30 человек, но 5+3+2=10 из них владеют и другими языками, следовательно, только немецкий знают 20 человек. Аналогично получаем, что одним английским владеют 13 человек, а одним французским - 30 человек. По условию задачи всего 100 туристов. 20+13+30+5+7+2+3=80 туристов знают хотя бы один язык, следовательно, 20 человек не владеют ни одним изданных языков.