Примеры комбинаторных конфигураций и задач
Для формулировки и решения комбинаторных задач используют различные модели комбинаторных конфигураций. Примерами комбинаторных конфигураций являются:
- Размещением из n элементов по k называется упорядоченный набор из k различных элементов некоторого n-элементного множества.
- Перестановкой из n элементов (например чисел 1,2,…,n) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n.
- Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.
- Композицией числаn называется всякое представление n в виде упорядоченной суммы целых положительных чисел.
- Разбиением числаn называется всякое представление n в виде неупорядоченной суммы целых положительных чисел.
Примерами комбинаторных задач являются:
- Сколькими способами можно разместить n предметов по m ящикам так, чтобы выполнялись заданные ограничения?
- Сколько существует функций
из m-элементного множества в n-элементное, удовлетворяющих заданным ограничениям?
- Сколько существует различных перестановок из 52 игральных карт?
- Ответ: 52! (52 факториал), то есть, 80658175170943878571660636856403766975289505440883277824000000000000 или примерно 8,0658 × 1067.
- При игре в кости бросаются две кости, и выпавшие очки складываются; сколько существует комбинаций, таких, что сумма очков на верхних гранях равна двенадцати?
- Решение: Каждый возможный исход соответствует функции
(аргумент функции — это номер кости, значение — очки на верхней грани). Очевидно, что лишь 6 6 даёт нам нужный результат 12. Таким образом существует лишь одна функция, ставящая в соответствие 1 число 6, и 2 число 6. Или, другими словами, существует всего одна комбинация, такая, что сумма очков на верхних гранях равна двенадцати.
- Решение: Каждый возможный исход соответствует функции
Для формулировки и решения комбинаторных задач используют различные модели комбинаторных конфигураций. Примерами комбинаторных конфигураций являются:
- Размещением из n элементов по k называется упорядоченный набор из k различных элементов некоторого n-элементного множества.
- Перестановкой из n элементов (например чисел 1, 2, … n) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n.
- Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.
- Композицией числаn называется всякое представление n в виде упорядоченной суммы целых положительных чисел.
- Разбиением числаn называется всякое представление n в виде неупорядоченной суммы целых положительных чисел.
Примеры комбинаторных задач:
- Сколькими способами можно разместить n предметов по m ящикам, чтобы выполнялись заданные ограничения?
- Сколько существует функций F{displaystyle F}
из m-элементного множества в n-элементное, удовлетворяющих заданным ограничениям?
- Сколько существует различных перестановок из 52 игральных карт?
- Ответ: 52! (52 факториал), то есть, 80 658 175 170 943 878 571 660 636 856 403 766 975 289 505 440 883 277 824 000 000 000 000 или примерно 8,0658 ⋅ 1067.
- При игре в кости бросаются две кости, и выпавшие очки складываются; сколько существует комбинаций, в которых сумма очков на верхних гранях равна двенадцати?
- Решение: Каждый возможный исход соответствует функции F:{1,2}→{1,2,3,4,5,6}{displaystyle F:{1,2}to {1,2,3,4,5,6}}
(аргумент функции — это номер кости, значение — очки на верхней грани). Очевидно, что лишь 6 6 даёт нам нужный результат 12. Таким образом, существует лишь одна функция, ставящая в соответствие 1 число 6, и 2 число 6. Или, другими словами, существует всего одна комбинация, при которой сумма очков на верхних гранях равна двенадцати.
- Решение: Каждый возможный исход соответствует функции F:{1,2}→{1,2,3,4,5,6}{displaystyle F:{1,2}to {1,2,3,4,5,6}}
Разделы комбинаторики
Перечислительная комбинаторика (или исчисляющая комбинаторика) рассматривает задачи о перечислении или подсчёте количества различных конфигураций (например, перестановок) образуемых элементами конечных множеств, на которые могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.
Количество конфигураций, образованных несколькими манипуляциями над множеством, подсчитывается согласно правилам сложения и умножения.
Типичным примером задач данного раздела является подсчёт количества перестановок. Другой пример — известная Задача о письмах.
К данному разделу относятся некоторые вопросы теории графов, а также теории матроидов.
Примером этого раздела может служить следующая задача: какова наибольшая размерность графа, удовлетворяющего определённым свойствам.
Теория Рамсея
- в группе из 6 человек всегда можно найти трёх человек, которые либо попарно знакомы друг с другом, либо попарно незнакомы.
- в любом графе с 6 вершинами найдётся либо клика, либо независимое множество размера 3.
Этот раздел отвечает на вопросы вида: какова вероятность присутствия определённого свойства у заданного множества.
Топологическая комбинаторика (англ.) применяет идеи и методы комбинаторики в топологии, при изучении дерева принятия решений, частично упорядоченных множеств, раскрасок графа и др.
Инфинитарная комбинаторика (англ.) — применение идей и методов комбинаторики к бесконечным (в том числе, несчётным) множествам.
Исторический очерк
Джероламо Кардано написал математическое исследование игры в кости, опубликованное посмертно. Теорией этой игры занимались также Тарталья и Галилей. В историю зарождавшейся теории вероятностей вошла переписка заядлого игрока Шевалье де Мерэ с Пьером Ферма и Блезом Паскалем, где были затронуты несколько тонких комбинаторных вопросов.
Блез Паскаль много занимался биномиальными коэффициентами и открыл простой способ их вычисления: «треугольник Паскаля». Хотя этот способ был уже известен на Востоке (примерно с X века), Паскаль, в отличие от предшественников, строго изложил и доказал свойства этого треугольника. Наряду с Лейбницем, он считается основоположником современной комбинаторики.
Сам термин «комбинаторика» придумал Лейбниц, который в 1666 году (ему было тогда 20 лет) опубликовал книгу «Рассуждения о комбинаторном искусстве». Правда, термин «комбинаторика» Лейбниц понимал чрезмерно широко, включая в него всю конечную математику и даже логику[2]. Ученик Лейбница Якоб Бернулли, один из основателей теории вероятностей, изложил в своей книге «Искусство предположений» (1713) множество сведений по комбинаторике.
В этот же период формируется терминология новой науки. Термин «сочетание» (combination) впервые встречается у Паскаля (1653, опубликован в 1665 году). Термин «перестановка» (permutation) употребил в указанной книге Якоб Бернулли (хотя эпизодически он встречался и раньше). Бернулли использовал и термин «размещение» (arrangement).
После появления математического анализа обнаружилась тесная связь комбинаторных и ряда аналитических задач. Абрахам де Муавр и Джеймс Стирлинг нашли формулы для аппроксимации факториала.[3]
Кроме перестановок и сочетаний, Эйлер изучал разбиения, а также сочетания и размещения с условиями.
Литература
- Андерсон Джеймс. Дискретная математика и комбинаторика = 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
- Андерсон, Джеймс. Дискретная математика и комбинаторика = 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.
Ссылки

Эта страница в последний раз была отредактирована 7 мая 2019 в 21:27.