Реферат
По
дисциплине: Математика
„
Комбинаторика “
Комбинаторика
Комбинаторика
(Комбинаторный анализ) — раздел математики,
изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления
элементов) и отношения на них (например, частичного порядка).
Комбинаторика связана со многими другими областями математики —
алгеброй, геометрией, теорией вероятностей
и имеет широкий спектр применения в различных областях знаний (например, в генетике, информатике, статистической физике).
Термин «комбинаторика»
был введён в математический обиход Лейбницем,
который в 1666 году
опубликовал свой труд «Рассуждения о комбинаторном искусстве».
Иногда под
комбинаторикой понимают более обширный раздел дискретной математики,
включающий, в частности, теорию графов.
Примеры
комбинаторных конфигураций и задач
Для формулировки и решения
комбинаторных задач используют различные модели комбинаторных конфигураций.
Примерами комбинаторных конфигураций являются:
· Размещением из n
элементов по k называется упорядоченный набор
из k различных элементов некоторого n-элементного множества.
· Перестановкой из n
элементов (например, чисел 1,2,…,n) называется всякий упорядоченный
набор из этих элементов. Перестановка также является размещением из n
элементов по n.
· Сочетанием из n
по k называется набор k элементов, выбранных из данных n
элементов. Наборы, отличающиеся только порядком следования элементов (но не
составом), считаются одинаковыми, этим сочетания отличаются от размещений.
· Композицией числа
n называется всякое представление n в виде упорядоченной суммы
целых положительных чисел.
· Разбиением числа
n называется всякое представление n в виде неупорядоченной суммы
целых положительных чисел.
Примеры комбинаторных задач:
1. Сколькими
способами можно разместить n предметов по m ящикам, чтобы
выполнялись заданные ограничения?
2. Сколько
существует функций из m-элементного множества в n-элементное,
удовлетворяющих заданным ограничениям?
3. Сколько
существует различных перестановок из 52
игральных карт?
Ответ: 52! (52 факториал), то
есть, 80658175170943878571660636856403766975289505440883277824000000000000 или
примерно 8,0658 × 1067.
4. При
игре в кости
бросаются две кости, и выпавшие очки складываются; сколько существует
комбинаций, в которых сумма очков на верхних гранях равна двенадцати?
Решение: Каждый возможный исход
соответствует функции (аргумент функции — это номер кости,
значение — очки на верхней грани). Очевидно, что лишь 6+6 даёт нам нужный
результат 12. Таким образом, существует лишь одна функция, ставящая в
соответствие 1 число 6, и 2 число 6. Или, другими словами, существует всего
одна комбинация, при которой сумма очков на верхних гранях равна двенадцати.
Разделы
комбинаторики
Перечислительная
комбинаторика
Перечислительная
комбинаторика (или исчисляющая
комбинаторика) рассматривает задачи о перечислении или подсчёте
количества различных конфигураций (например, перестановок)
образуемых элементами конечных множеств, на которые могут накладываться
определённые ограничения, такие как: различимость или неразличимость элементов,
возможность повторения одинаковых элементов и т. п.
Количество
конфигураций, образованных несколькими манипуляциями над множеством,
подсчитывается согласно правилам сложения
и умножения.
Типичным примером задач
данного раздела является подсчёт количества перестановок.
Другой пример — известная Задача о письмах.
Структурная
комбинаторика
К данному разделу
относятся некоторые вопросы теории графов, а
также теории матроидов.
Экстремальная
комбинаторика
Примером этого раздела может
служить следующая задача: какова наибольшая размерность графа, удовлетворяющего
определённым свойствам.
Теория Рамсея
Теория Рамсея изучает
наличие регулярных структур в случайных конфигурациях элементов. Примером
утверждения из теории Рамсея может служить следующее:
в группе из 6 человек всегда можно найти
трёх человек, которые либо попарно знакомы друг с другом, либо попарно
незнакомы.
В терминах структурной комбинаторики
это же утверждение формулируется так:
в любом графе с 6 вершинами
найдётся либо клика, либо
независимое множество размера 3.
Вероятностная
комбинаторика
Этот раздел отвечает на вопросы
вида: какова вероятность присутствия определённого свойства у заданного
множества.
Топологическая
комбинаторика
Топологическая комбинаторика (англ.)
применяет идеи и методы комбинаторики в топологии, при
изучении дерева принятия решений,
частично
упорядоченных множеств, раскрасок графа и др.
Инфинитарная
комбинаторика
Инфинитарная комбинаторика (англ.) —
применение идей и методов комбинаторики к бесконечным (в
том числе, несчётным)
множествам.
Открытые проблемы
Комбинаторика, и в частности,
теория Рамсея, содержит много известных открытых проблем, подчас с весьма
несложной формулировкой. Например, неизвестно, при каком наименьшем N в любой
группе из N человек найдутся 5 человек, либо попарно знакомых друг с другом,
либо попарно незнакомых (хотя известно, что 49 человек достаточно).[1]
Исторический очерк
Джероламо Кардано
написал математическое исследование игры в кости,
опубликованное посмертно. Теорией этой игры занимались также Тарталья и Галилей. В
историю зарождавшейся теории вероятностей
вошла переписка заядлого игрока шевалье де Мерэ с Пьером Ферма и Блезом Паскалем,
где были затронуты несколько тонких комбинаторных вопросов. Помимо азартных
игр, комбинаторные методы использовались (и продолжают использоваться) в криптографии —
как для разработки шифров, так и для их взлома.
Треугольник Паскаля
Блёз Паскаль много
занимался биномиальными
коэффициентами и открыл простой способ их
вычисления: «треугольник Паскаля».
Хотя этот способ был уже известен на Востоке (примерно с X века), Паскаль, в
отличие от предшественников, строго изложил и доказал свойства этого
треугольника. Наряду с Лейбницем,
он считается основоположником современной комбинаторики. Сам термин
«комбинаторика» придумал Лейбниц, который в 1666 году (ему
было тогда 20 лет) опубликовал книгу «Рассуждения о комбинаторном искусстве».
Правда, термин «комбинаторика» Лейбниц понимал чрезмерно широко, включая в него
всю конечную математику и даже логику. Ученик Лейбница Якоб Бернулли, один
из основателей теории вероятностей, изложил в своей книге «Искусство
предположений» (1713)
множество сведений по комбинаторике.
В этот же период
формируется терминология новой науки. Термин «сочетание» (combination)
впервые встречается у Паскаля (1653, опубликован в 1665 году).
Термин «перестановка» (permutation)
употребил в указанной книге Якоб Бернулли (хотя
эпизодически он встречался и раньше). Бернулли использовал и термин «размещение» (arrangement).
После появления математического анализа
обнаружилась тесная связь комбинаторных и ряда аналитических задач. Абрахам де Муавр
и Джеймс Стирлинг
нашли формулы для аппроксимации факториала.
Окончательно
комбинаторика как самостоятельный раздел математики оформилась в трудах Эйлера. Он
детально рассмотрел, например, следующие проблемы:
· задача о ходе коня;
· задача о семи мостах,
с которой началась теория графов;
· построение
греко-латинских квадратов;
· обобщённые перестановки.
Кроме перестановок и
сочетаний, Эйлер изучал разбиения, а
также сочетания и размещения с условиями.
Комбинаторика в
языкознании
Комбинаторика (языкознание) —
это свойство единиц языка и соответствующих им единиц речи вступать в
синтагматические отношения, то есть в отношения сочетаемости.
Литература
· Андерсон
Джеймс. Дискретная математика и комбинаторика = Discrete Mathematics with
Combinatorics. — М.: «Вильямс»,
2006. — С. 960. — ISBN 0-13-086998-8.
· Виленкин
Н.Я. Популярная
комбинаторика. — М.: Наука, 1975.
· Ерош
И. Л. Дискретная математика. Комбинаторика — СПб.: СПбГУАП,
2001. — 37 c.
· Липский
В. Комбинаторика для программиста. —
М.: Мир, 1988. — 213 с.
· Раизер
Г. Дж. Комбинаторная математика. — пер. с англ. — М., 1966.
· Райгородский
А. М. Линейно-алгебраические и вероятностные методы в
комбинаторике. — Летняя школа
«Современная математика». — Дубна, 2006.
· Рейнгольд
Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы.
Теория и практика. — М.: Мир, 1980. — 476 с.
· Риордан
Дж. Введение в комбинаторный анализ — пер. с англ. — М.,
1963.
· Р.
Стенли. Перечислительная комбинаторика = Enumerative
Combinatorics. — М.: «Мир»,
1990. — С. 440. — ISBN 5-03-001348-2.
· Р.
Стенли. Перечислительная комбинаторика. Деревья, производящие функции и
симметрические функции = Enumerative Combinatorics. Volume 2. — М.: «Мир»,
2009. — С. 767. — ISBN 978-5-03-003476-8.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.