Принцип Дирихле (комбинаторика)
- 1 year ago
- 0
- 0
Комбинато́рика — раздел математики , посвящённый решению задач, связанных с выбором и расположением элементов некоторого (чаще всего конечного) множества в соответствии с заданными правилами. Каждое такое правило определяет некоторую выборку из элементов исходного множества, которая называется комбинаторной конфигурацией . Простейшими примерами комбинаторных конфигураций являются перестановки , сочетания и размещения .
Типичные задачи комбинаторики
:Комбинаторика тесно связана со многими другими областями математики — алгеброй , геометрией , теорией вероятностей , теорией чисел и другими . Она применяется в самых различных областях знаний, например, в генетике , информатике , статистике , статистической физике , лингвистике , музыке .
Термин «комбинаторика» был введён в математический обиход в 1666 году Лейбницем в труде «Рассуждения о комбинаторном искусстве».
Для формулировки и решения комбинаторных задач используют различные модели комбинаторных конфигураций . Примерами комбинаторных конфигураций являются:
Примеры комбинаторных задач:
Основные комбинаторные понятия и вычислительные результаты появились в древнем мире . Классическая задача комбинаторики: «сколько есть способов извлечь элементов из возможных» упоминается ещё в сутрах древней Индии (начиная примерно с IV века до н. э.) . Индийские математики, видимо, первыми открыли биномиальные коэффициенты и их связь с биномом Ньютона . Во II веке до н. э. индийцы знали, что сумма всех биномиальных коэффициентов степени равна .
Комбинаторные мотивы можно заметить в символике китайской « Книги Перемен » (V век до н. э.). По мнению её авторов, всё в мире комбинируется из различных сочетаний мужского и женского начал , а также восьми стихий: земля, горы, вода, ветер, гроза, огонь, облака и небо . Историки отмечают также комбинаторные проблемы в руководствах по игре в Го и другие игры. Большой интерес математиков многих стран с древних времён неизменно вызывали магические квадраты .
Античные греки также рассматривали отдельные комбинаторные задачи, хотя систематическое изложение ими этих вопросов, если оно и существовало, до нас не дошло. Хрисипп ( III век до н. э. ) и Гиппарх ( II век до н. э. ) подсчитывали, сколько следствий можно получить из 10 аксиом ; методика подсчёта нам неизвестна, но у Хрисиппа получилось более миллиона, а у Гиппарха — более 100000 . Аристотель при изложении своей логики безошибочно перечислил все возможные типы трёхчленных силлогизмов . Аристоксен рассмотрел различные чередования длинных и коротких слогов в стихотворных размерах . Какие-то комбинаторные правила пифагорейцы , вероятно, использовали при построении своей теории чисел и нумерологии ( совершенные числа , фигурные числа , пифагоровы тройки и др.).
В Средние века комбинаторика также продолжала развиваться, в основном, за пределами европейской цивилизации . В XII веке индийский математик Бхаскара в своём основном труде «Лилавати» подробно исследовал задачи, связанные с перестановками и сочетаниями, включая перестановки с повторениями. Другой индийский математик, (середина IX века), опубликовал формулы для числа перестановок и сочетаний , причём эти формулы, возможно, были знакомы индийским математикам ещё в VI веке н. э. Философ и астроном рабби Авраам ибн Эзра (около 1140 года) подсчитал число размещений с перестановками в огласовках имени Бога . Он же установил симметрию биномиальных коэффициентов . Точную формулу для них обнародовал позже талмудист и математик Леви бен Гершом (более известный как Герсонид) в 1321 году.
Несколько комбинаторных задач содержит « Книга абака » ( Фибоначчи , XIII век). Например, он поставил задачу найти наименьшее число гирь, достаточное для взвешивания любого товара весом от 1 до 40 фунтов.
Блез Паскаль много занимался биномиальными коэффициентами и открыл простой способ их вычисления: « треугольник Паскаля ». Позднее выяснилось, что этот способ был уже известен на Востоке (примерно с X века) и он назывался арифметическим треугольником . Паскаль, в отличие от предшественников, строго изложил и доказал свойства этого треугольника. Арифметический треугольник представляет собой графическую диаграмму, показывающую отношения между биномиальными коэффициентами. Позже, в средневековой Англии, предоставила примеры того, что теперь известно как гамильтоновы циклы в графах Кэли на перестановках.
В эпоху Возрождения , наряду с прочими науками, комбинаторика начала стремительное развитие. Джероламо Кардано написал проницательное математическое исследование игры в кости , опубликованное посмертно. Теорией этой игры занимались также Никколо Тарталья и Галилео Галилей . История теории вероятностей началась с переписки заядлого игрока шевалье де Мерэ с Пьером Ферма и Блезом Паскалем , где были затронуты несколько тонких комбинаторных вопросов. Помимо азартных игр, комбинаторные методы использовались (и продолжают использоваться) в криптографии — как для разработки шифров, так и для их взлома.
Сам термин «комбинаторика» придумал Лейбниц , он считается основоположником современной комбинаторики. В 1666 году (ему было тогда 20 лет) опубликовал книгу «Рассуждения о комбинаторном искусстве». Правда, термин «комбинаторика» Лейбниц понимал чрезмерно широко, включая в него всю конечную математику и даже логику . Ученик Лейбница Якоб Бернулли , один из основателей теории вероятностей, изложил в своей книге «Искусство предположений» (1713) множество сведений по комбинаторике.
В этот же период формируется терминология новой науки. Термин « сочетание » ( combination ) впервые встречается у Паскаля (1653, опубликован в 1665 году). Термин « перестановка » ( permutation ) употребил в указанной книге Якоб Бернулли (хотя эпизодически он встречался и раньше). Бернулли использовал и термин « размещение » ( arrangement ).
После появления математического анализа обнаружилась тесная связь комбинаторных и ряда аналитических задач. Абрахам де Муавр и Джеймс Стирлинг нашли формулы для аппроксимации факториала .
Окончательно комбинаторика как самостоятельный раздел математики оформилась в трудах Эйлера . Он детально рассмотрел, например, следующие проблемы:
Кроме перестановок и сочетаний, Эйлер изучал разбиения , а также сочетания и размещения с условиями.
Работы Паскаля , Ньютона , Якоба Бернулли и Эйлера стали фундаментальными в развитии этой области. В наше время работы Дж. Дж. Сильвестра (конец XIX века) и (начало XX века) помогли заложить основы перечислительной и алгебраической комбинаторики . Теория графов также вызывала растущий интерес, особенно в связи с теоремой о четырёх красках и задачами экономики.
Во второй половине XX века комбинаторика пережила новый бурный рост, что было связано с быстрым развитием дискретной математики, информатики , кибернетики и планирования эксперимента . Частично этот рост был стимулирован обнаруженными связями и приложениями в других областях математики — в алгебре, теорией вероятностей, функциональном анализе , теории чисел и т. д. Эти связи стирают границы между комбинаторикой и другими областями математики, но в то же время приводят к определённой фрагментации комбинаторики.
В начале XX века началось развитие комбинаторной геометрии : были доказаны теоремы Радона , Хелли , Юнга , Бляшке , а также строго доказана изопериметрическая теорема . На стыке топологии, анализа и комбинаторики были доказаны теоремы Борсука — Улама и . Во второй четверти XX века были поставлены проблема Борсука и проблема Нелсона — Эрдёша — Хадвигера . В 1940-х годах оформилась теория Рамсея . Отцом современной комбинаторики считается Пал Эрдёш , который ввёл в комбинаторику вероятностный анализ. Внимание к конечной математике и, в частности, к комбинаторике значительно повысилось со второй половины XX века, когда появились компьютеры . Сейчас это содержательная и быстроразвивающаяся область математики.
Перечислительная комбинаторика (или исчисляющая комбинаторика ) рассматривает задачи о перечислении или подсчёте количества различных конфигураций (например, перестановок ) образуемых элементами конечных множеств, на которые могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.
Количество конфигураций, образованных несколькими манипуляциями над множеством, подсчитывается согласно правилам сложения и умножения .
Числа Фибоначчи являются типичным примером задачи в перечислительной комбинаторике, а также известная Задача о письмах . Двенадцатеричный путь обеспечивает единую структуру для подсчета перестановок , сочетаний и разбиений .
Аналитическая комбинаторика относится к перечислению комбинаторных структур с использованием инструментов из комплексного анализа и теории вероятностей . В отличие от перечислительной комбинаторики, которая использует явные комбинаторные формулы и производящие функции последовательности для описания результатов, аналитическая комбинаторика нацелена на получение асимптотических формул .
Теория разбиения изучает различные перечислительные и асимптотические задачи, связанные с разбиением натуральных чисел , и тесно связана с q-рядами , специальными функциями и ортогональными многочленами . Первоначально она была частью теории чисел и анализа , а теперь рассматривается как часть комбинаторики или самостоятельная область. Она включает в себя биективный подход , различные инструменты анализа и аналитической теории чисел , имеет также связи со статистической механикой .
Графы являются фундаментальными объектами в комбинаторике. Теория графов рассматривает перечисления (например, число вершин с рёбрами графа), существующие структуры (например, гамильтоновы циклы), алгебраические представления (например, имеет ли комбинаторное представление многочлен Татта для заданных графа и двух чисел и ?). Хотя между теорией графов и комбинаторикой существуют очень сильные связи, они иногда рассматриваются как отдельные предметы. В то же время комбинаторные методы применимы ко многим задачам теории графов, эти две дисциплины обычно используются для поиска решений различных типов задач.
Теория схем — это исследование комбинаторных схем , которые представляют собой наборы подмножеств с определёнными свойствами пересечения . Блок схемы — это комбинаторные схемы особого типа. Эта область является одной из старейших частей комбинаторики, например, предложенная в 1850 году задача Киркмана о школьницах . Решение задачи является частным случаем системы Штейнера , системы которой играют важную роль в классификации простых конечных групп . Эта область имеет дальнейшие связи с теорией кодирования и геометрической комбинаторикой.
Конечная геометрия изучает геометрические системы с конечным числом точек. Структуры аналогичны тем, которые встречаются в непрерывной геометрии ( евклидово или проективное пространство), но определены комбинаторно. Эта область является богатым источником примеров для теории схем .
Теория порядка — это изучение частично упорядоченных множеств , как конечных, так и бесконечных. Различные примеры частичных порядков встречаются в алгебре , геометрии, теории чисел и во всей комбинаторике, и теории графов. Известные классы и примеры частичных порядков включают решетки и булевы алгебры .
Теория матроидов абстрагирует часть геометрии . Она изучает свойства множеств (обычно конечных множеств) векторов в векторном пространстве, которые не зависят от конкретных коэффициентов в линейно зависимом отношении. Не только структура, но и перечислительные свойства принадлежат теории матроидов. Теория матроидов была введена Хасслером Уитни и изучалась как часть теории порядка. В настоящее время это самостоятельная область исследований, имеющая ряд связей с другими разделами комбинаторики.
Экстремальная комбинаторика изучает экстремальные вопросы о системах множеств . Типы вопросов, рассматриваемых в этом случае, относятся к самому большому возможному графу, который удовлетворяет определённым свойствам. Например, самый большой граф без треугольников на вершинах — это полный двудольный граф . Часто бывает слишком трудно даже точно найти экстремальный ответ [ уточнить ] и можно дать только асимптотическую оценку .
Теория Рамсея — это ещё одна часть экстремальной комбинаторики. Она утверждает, что любая достаточно большая конфигурация будет содержать некоторый порядок и изучает наличие регулярных структур в случайных конфигурациях элементов. Это расширенное обобщение принципа Дирихле («принцип голубей и ящиков»). Примером утверждения из теории Рамсея может служить следующее:
В терминах структурной комбинаторики это же утверждение формулируется так:
Этот раздел отвечает на вопросы вида: какова вероятность присутствия определённого свойства для случайного дискретного объекта, такого как случайный граф ? Например, каково среднее число треугольников в случайном графе? Вероятностные методы также используются для определения существования комбинаторных объектов с определёнными заданными свойствами (для которых явные примеры может быть трудно найти), просто наблюдая, что вероятность случайного выбора объекта с этими свойствами больше 0 . Этот подход (часто называемый вероятностным методом ) доказал свою высокую эффективность в приложениях экстремальной комбинаторики и теории графов. Тесно связанной областью является изучение конечных цепей Маркова , особенно на комбинаторных объектах. Здесь снова используются вероятностные инструменты для оценки .
Часто ассоциируемая с Палом Эрдёшем , который сделал новаторскую работу по этому предмету, вероятностная комбинаторика традиционно рассматривалась как набор инструментов для изучения задач в других частях комбинаторики. Однако с ростом приложений для анализа алгоритмов в информатике , а также классической теории вероятностей, аддитивной теории чисел и , эта область в последнее время выросла и стала самостоятельной областью комбинаторики.
Алгебраическая комбинаторика — это область математики , которая использует методы абстрактной алгебры , в частности теорию групп и теорию представлений , в различных комбинаторных контекстах и, наоборот, применяет комбинаторные методы к задачам алгебры . Алгебраическая комбинаторика постоянно расширяет свой охват, как в тематических направлениях, так и в методах и может рассматриваться как область математики, где взаимодействие комбинаторных и алгебраических методов особенно сильно и существенно.
Комбинаторика слов имеет дело с формальными языками . Она возникла самостоятельно в нескольких областях математики, в том числе в теории чисел , теории групп и теории вероятности . Она имеет приложения в перечислительной комбинаторике, , теоретической информатике , теории автоматов и лингвистике. Хотя многие приложения являются новыми, классическая иерархия Хомского классов формальных грамматик является, пожалуй, самым известным результатом в этой области.
Геометрическая комбинаторика связана с выпуклой и дискретной геометрией , в частности с комбинаторикой многогранников . Например, она спрашивает, сколько граней каждого измерения может иметь выпуклый многогранник . Важную роль играют также метрические свойства многогранников, например, теорема Коши о жёсткости выпуклых многогранников. Рассматриваются также особые многогранники, такие как перестановочные многогранники , и многогранники Биркгофа . Комбинаторная геометрия — это старомодное название дискретной геометрии.
Топологическая комбинаторика применяет идеи и методы комбинаторики в топологии , при изучении раскрасок графа , справедливого дележа , разбиения , дерева принятия решений , частично упорядоченных множеств , задачи о восстановлении бус и . Её не следует путать с комбинаторной топологией , которая является более старым названием алгебраической топологии .
Арифметическая комбинаторика возникла из взаимодействия между теорией чисел , комбинаторикой, эргодической теории и гармоническим анализом . Она о комбинаторных оценках, связанных с арифметическими операциями (сложение, вычитание, умножение и деление). Аддитивная теория чисел (иногда также называемая аддитивной комбинаторикой) относится к частному случаю, когда задействованы только операции сложения и вычитания. Одним из важных методов арифметической комбинаторики является эргодическая теория динамических систем .
— применение идей и методов комбинаторики к бесконечным (в том числе, несчётным ) множествам. Это часть теории множеств , область математической логики , но использует инструменты и идеи как теории множеств, так и экстремальной комбинаторики.
использовал название непрерывной комбинаторики для описания , поскольку существует много аналогий между подсчетом и мерой.
Комбинаторная оптимизация — это исследование оптимизации дискретных и комбинаторных объектов. Она начиналась как часть комбинаторики и теории графов, но теперь рассматривается как раздел прикладной математики и информатики, связанный с исследованием операций , теорией алгоритмов и теорией сложности вычислений .
Теория кодирования началась как часть теории схем с ранними комбинаторными конструкциями кодов, исправляющих ошибки . Основная идея предмета заключается в разработке эффективных и надежных методов передачи данных. Сейчас это большая область исследований, часть теории информации .
Дискретная геометрия (также называемая комбинаторной геометрией) также началась как часть комбинаторики, с ранними результатами выпуклых многогранников и контактных чисел . С появлением приложений дискретной геометрии в вычислительной геометрии , эти две области частично слились и стали отдельной областью изучения. Остается много связей с геометрической и топологической комбинаторикой, которые сами по себе можно рассматривать как порождения ранней дискретной геометрии.
Комбинаторные аспекты динамических систем — это ещё одна развивающаяся область. Здесь динамические системы могут быть определены комбинаторными объектами. См., например, .
Между комбинаторикой и физикой, в частности статистической физикой , усиливается взаимосвязь. Примеры включают точное решение модели Изинга и связь между с одной стороны, и хроматическими многочленами и многочленами Татте , с другой стороны.
Комбинаторика (в частности, теория Рамсея) содержит много известных открытых проблем , подчас с весьма несложной формулировкой. Например, неизвестно, при каком наименьшем в любой группе из человек найдутся 5 человек, либо попарно знакомых друг с другом, либо попарно незнакомых (хотя известно, что 49 человек достаточно) .
Также есть и другие нерешённые задачи и недоказанные гипотезы:
Комбинаторика (языкознание) — это свойство единиц языка и соответствующих им единиц речи вступать в синтагматические отношения, то есть в отношения сочетаемости.
Для улучшения этой статьи
желательно
:
|