Комбинаторика

Комбинаторика

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

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

Иногда под комбинаторикой понимают более обширный раздел дискретной математики, включающий, в частности, теорию графов.

Содержание

Примеры комбинаторных конфигураций и задач

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

  • Размещением из n элементов по k называется упорядоченный набор из k различных элементов некоторого n-элементного множества.
  • Перестановкой из n элементов (например чисел 1,2,…,n) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n.
  • Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.
  • Композицией числа n называется всякое представление n в виде упорядоченной суммы целых положительных чисел.
  • Разбиением числа n называется всякое представление n в виде неупорядоченной суммы целых положительных чисел.

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

  1. Сколькими способами можно разместить n предметов по m ящикам так, чтобы выполнялись заданные ограничения?
  2. Сколько существует функций F из m-элементного множества в n-элементное, удовлетворяющих заданным ограничениям?
  3. Сколько существует различных перестановок из 52 игральных карт?
    Ответ: 52! (52 факториал), то есть, 80658175170943878571660636856403766975289505440883277824000000000000 или примерно 8,0658 × 1067.
  4. При игре в кости бросаются две кости, и выпавшие очки складываются; сколько существует комбинаций, таких, что сумма очков на верхних гранях равна двенадцати?
    Решение: Каждый возможный исход соответствует функции F: \{1, 2\} \to \{1, 2, 3, 4, 5, 6\} (аргумент функции — это номер кости, значение — очки на верхней грани). Очевидно, что лишь 6+6 даёт нам нужный результат 12. Таким образом существует лишь одна функция, ставящая в соответствие 1 число 6, и 2 число 6. Или, другими словами, существует всего одна комбинация, такая, что сумма очков на верхних гранях равна двенадцати.

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

Перечислительная комбинаторика

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

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

Типичным примером задач данного раздела является подсчёт количества перестановок. Другой пример — известная Задача о письмах.

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

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

Экстремальная комбинаторика

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

Теория Рамсея

Теория Рамсея изучает наличие регулярных структур в случайных конфигурациях элементов. Примером утверждения из теории Рамсея может служить следующее:

в группе из 6 человек всегда можно найти трёх человек, которые либо попарно знакомы друг с другом, либо попарно незнакомы.

В терминах структурной комбинаторики это же утверждение формулируется так:

в любом графе с 6 вершинами найдётся либо клика, либо независимое множество размера 3.

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

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

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

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

Инфинитарная комбинаторика

Инфинитарная комбинаторика (англ.) — применение идей и методов комбинаторики к бесконечным (в том числе, несчётным) множествам.

Открытые проблемы

Комбинаторика, и в частности, теория Рамсея, содержит много известных открытых проблем, подчас с весьма несложной формулировкой. Например, неизвестно, при каком наименьшем N в любой группе из N человек найдутся 5 человек, либо попарно знакомых друг с другом, либо попарно незнакомых (хотя известно, что 49 человек достаточно).[1]

Исторический очерк

См. также

Примечания

  1. Weisstein, Eric W. Числа Рамсея (англ.) на сайте Wolfram MathWorld.

Литература

  • Андерсон Джеймс. Дискретная математика и комбинаторика = 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

Ссылки



Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Полезное


Смотреть что такое "Комбинаторика" в других словарях:

  • КОМБИНАТОРИКА — (лат. ars combinatoria). Наука о законах сочетания известных предметов. Словарь иностранных слов, вошедших в состав русского языка. Чудинов А.Н., 1910. КОМБИНАТОРИКА лат. ars combinatoria. Наука о законах сочетания известных предметов. Объяснение …   Словарь иностранных слов русского языка

  • КОМБИНАТОРИКА — раздел математики, в котором изучаются простейшие соединения . Перестановки соединения, которые можно составить из n предметов, меняя всеми возможными способами их порядок; число ихРазмещения соединения, содержащие по m предметов из числа n… …   Большой Энциклопедический словарь

  • КОМБИНАТОРИКА — КОМБИНАТОРИКА, и, жен. Раздел дискретной математики, изучающий всевозможные сочетания и расположения предметов. | прил. комбинаторный, ая, ое. К. анализ. Толковый словарь Ожегова. С.И. Ожегов, Н.Ю. Шведова. 1949 1992 …   Толковый словарь Ожегова

  • КОМБИНАТОРИКА — раздел математики, где рассматриваются сочетания, размещения, перестановки элементов и связанные с ними задачи. Широко применяется при вероятностном моделировании геол. процессов. Геологический словарь: в 2 х томах. М.: Недра. Под редакцией К. Н …   Геологическая энциклопедия

  • комбинаторика — — [http://www.dunwoodypress.com/148/PDF/Biotech Eng Rus.pdf] Тематики биотехнологии EN combinatorics …   Справочник технического переводчика

  • КОМБИНАТОРИКА — раздел математики, посвящённый решению задач выбора и расположения элементов из некоторого основного (обычно конечного) множества в соответствии с заданными правилами. Простейшими задачами К. являются перестановки, сочетания и размещения …   Большая политехническая энциклопедия

  • комбинаторика — и; ж. [лат. combinare соединять] Раздел математики, изучающий все возможные способы простейших перестановок элементов, цифр, каких л. данных. * * * комбинаторика раздел математики, в котором изучаются простейшие «соединения». Перестановки … …   Энциклопедический словарь

  • Комбинаторика —         1) то же, что математический Комбинаторный анализ. 2) Раздел элементарной математики, связанный с изучением количества комбинаций, подчинённых тем или иным условиям, которые можно составить из заданного конечного множества объектов… …   Большая советская энциклопедия

  • Комбинаторика — ж. Раздел математики, изучающий различного рода соединения элементов: перестановки, сочетания, размещения. Толковый словарь Ефремовой. Т. Ф. Ефремова. 2000 …   Современный толковый словарь русского языка Ефремовой

  • комбинаторика — комбинаторика, комбинаторики, комбинаторики, комбинаторик, комбинаторике, комбинаторикам, комбинаторику, комбинаторики, комбинаторикой, комбинаторикою, комбинаториками, комбинаторике, комбинаториках (Источник: «Полная акцентуированная парадигма… …   Формы слов


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»