Комбинаторика: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
imported>LGB
imported>Vklimin
исправление (скрытый символ)
 
imported>LGB
отмена правки 151471684 участника 109.252.136.89 (обс.)
 
Строка 1: Строка 1:
{{wikipedia}}
'''Комбинато́рика''' — раздел [[Математика|математики]], посвящённый решению задач, связанных с выбором и расположением элементов некоторого (чаще всего конечного) [[Множество (математика)|множества]] в соответствии с заданными правилами. Каждое такое правило определяет некоторую выборку из элементов исходного множества, которая называется ''комбинаторной конфигурацией''. Простейшими примерами комбинаторных конфигураций<ref name=ME>{{книга |автор=Сачков В. Н. |часть=Комбинаторный анализ |страницы=974—979 |заглавие=Математическая энциклопедия (в 5 томах) |место=М. |страниц=1104 |том=2 |год=1979 |издательство=[[Большая Российская энциклопедия (издательство)|Советская Энциклопедия]]}}</ref>{{sfn |БРЭ}} являются [[Перестановка|перестановки]], [[Сочетание|сочетания]] и [[Размещение|размещения]]{{переход|Примеры комбинаторных конфигураций и задач}}.
= {{-ru-}} =
{{Лексема в Викиданных|L118603}}


=== Морфологические и синтаксические свойства ===
Типичные задачи<ref name=ME/> комбинаторики{{переход|Примеры комбинаторных конфигураций и задач}}:
{{сущ ru f ina 3a
* определить количество комбинаторных конфигураций, соответствующих заданным правилам (в частности, доказать или опровергнуть их существование);
|основа=комбинато́рик
* найти практически пригодный алгоритм их полного построения;
|слоги={{по-слогам|ком|би|на|то́|ри|ка}}
* определить свойства заданного класса комбинаторных конфигураций.
}}


{{морфо-ru|комбин|-атор|-ик|+а|и=т}}
Комбинаторика тесно связана со многими другими областями математики — [[Алгебра|алгеброй]], [[Геометрия|геометрией]], [[Теория вероятностей|теорией вероятностей]], [[Теория чисел|теорией чисел]] и другими{{переход|Связанные области}}. Она применяется в самых различных областях знаний, например, в [[Генетика|генетике]], [[Информатика|информатике]], [[Статистика|статистике]], [[Статистическая физика|статистической физике]], [[Лингвистика|лингвистике]], [[Музыка|музыке]].


=== Произношение ===
Термин «комбинаторика» был введён в математический обиход в [[1666 год в науке|1666 году]] [[Лейбниц]]ем в труде «Рассуждения о комбинаторном искусстве».
{{transcription-ru|комбинато́рика|}}


=== Семантические свойства ===
== Примеры комбинаторных конфигураций и задач ==
Для формулировки и решения комбинаторных задач используют различные модели '''комбинаторных конфигураций'''. Примерами комбинаторных конфигураций являются:
* [[Размещение]]м из <math>n</math> элементов по <math>k</math> называется [[упорядоченный набор]] из <math>k</math> различных элементов некоторого <math>n</math>-элементного множества.
* [[Перестановка|Перестановкой]] из <math>n</math> элементов (например чисел 1, 2, … <math>n</math>) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из <math>n</math> элементов по <math>n</math>.
* [[Сочетание]]м из <math>n</math> по <math>k</math> называется набор <math>k</math> элементов, выбранных из данных <math>n</math> элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.
* [[Композиция (теория чисел)|Композицией числа]] <math>n</math> называется всякое представление <math>n</math> в виде упорядоченной суммы целых положительных чисел.
* [[Разбиение числа|Разбиением числа]] <math>n</math> называется всякое представление <math>n</math> в виде неупорядоченной суммы целых положительных чисел.


==== Значение ====
Примеры комбинаторных задач:
# {{матем.|ru}} [[раздел]] [[математика|математики]], изучающий дискретные [[объект]]ы, множества (сочетания, перестановки, размещения и перечисления) и отношения на них {{пример|В этой главе подробно освещены комбинаторные числа, производящие функции, теорема Пойа, и другие темы {{выдел|комбинаторики}}.}}
# Сколько имеется способов разместить <math>n</math> предметов по <math>m</math> ящикам, чтобы выполнялись заданные ограничения?
# {{разг.|ru}} совокупность сочетаний, перестановок, размещений элементов какого-либо множества {{пример|}}
# Сколько существует функций <math>F</math> из <math>m</math>-элементного множества в <math>n</math>-элементное, удовлетворяющих заданным ограничениям?
#
# Сколько существует различных [[Перестановка|перестановок]] из 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,
::: или примерно <math>8{,}0658 \cdot 10^{67}.</math>
# <li value="4"> При [[Игра в кости|игре в кости]] бросаются две кости, и выпавшие очки складываются; сколько существует комбинаций, в которых сумма очков на верхних гранях равна двенадцати?
#: Решение: Каждый возможный исход соответствует функции <math>F: \{1, 2\} \to \{1, 2, 3, 4, 5, 6\}</math> (аргумент функции — это номер кости, значение — очки на верхней грани). Очевидно, что лишь 6 + 6 даёт нам нужный результат 12. Таким образом, существует всего одна комбинация, при которой сумма очков на верхних гранях равна двенадцати.


==== Синонимы ====
== История ==
# —
{{main|История комбинаторики}}
#
#


==== Антонимы ====
=== Древность и средние века ===
# —
Основные комбинаторные понятия и вычислительные результаты появились в [[Древний мир|древнем мире]]. Классическая задача комбинаторики: «сколько есть способов извлечь <math>m</math> элементов из <math>N</math> возможных» упоминается ещё в [[сутра]]х [[История математики в Индии|древней Индии]] (начиная примерно с IV века до н. э.)<ref name="India">''Amulya Kumar Bag''. [http://repository.ias.ac.in/70374/ Binomial theorem in ancient India.] {{Wayback|url=http://repository.ias.ac.in/70374/ |date=20210803171018 }} Indian J. History Sci., 1:68-74, 1966.</ref>. Индийские математики, видимо, первыми открыли [[биномиальные коэффициенты]] и их связь с [[Бином Ньютона|биномом Ньютона]]<ref name="India"/>. Во II веке до н. э. индийцы знали, что сумма всех биномиальных коэффициентов степени <math>n</math> равна <math>2^n</math>. Индийский математик Нарайяна Пандита впервые предложил алгоритм порождения всех перестановок.
#
#


==== Гиперонимы ====
Комбинаторные мотивы можно заметить в символике китайской «[[Книга Перемен|Книги Перемен]]» (V век до н. э.). По мнению её авторов, всё в мире комбинируется из различных сочетаний [[Инь и ян|мужского и женского начал]], а также восьми стихий: земля, горы, вода, ветер, гроза, огонь, облака и небо{{sfn |Виленкин Н. Я.|1975|с=7}}. Историки отмечают также комбинаторные проблемы в руководствах по игре в [[Го]] и другие игры. Большой интерес математиков многих стран с древних времён неизменно вызывали [[магические квадраты]].
# [[математика]]
#
#


==== Гипонимы ====
Античные греки также рассматривали отдельные комбинаторные задачи, хотя систематическое изложение ими этих вопросов, если оно и существовало, до нас не дошло. [[Хрисипп]] ([[III век до н. э.]]) и [[Гиппарх]] ([[II век до н. э.]]) подсчитывали, сколько следствий можно получить из 10 [[Аксиома|аксиом]]; методика подсчёта нам неизвестна, но у Хрисиппа получилось более миллиона, а у Гиппарха — более 100000{{sfn |Виленкин Н. Я.|1975|с=9|name=V9}}. [[Аристотель]] при изложении своей логики безошибочно перечислил все возможные типы трёхчленных [[Дедуктивное умозаключение|силлогизмов]]. [[Аристоксен]] рассмотрел различные чередования длинных и коротких слогов в [[Стихотворный размер|стихотворных размерах]].<ref name=V9/> Какие-то комбинаторные правила [[пифагорейцы]], вероятно, использовали при построении своей [[Теория чисел|теории чисел]] и [[нумерология|нумерологии]] ([[совершенные числа]], [[фигурные числа]], [[пифагоровы тройки]] и др.).
# —
#
#


=== Родственные слова ===
В [[Средние века]] комбинаторика также продолжала развиваться, в основном, за пределами [[Европейская культура|европейской цивилизации]]. В XII веке индийский математик [[Бхаскара II|Бхаскара]] в своём основном труде «Лилавати» подробно исследовал задачи, связанные с перестановками и сочетаниями, включая перестановки с повторениями. Другой индийский математик, {{iw|Махавира (математик)|Махавира||Mahāvīra (mathematician)}} (середина IX века), опубликовал формулы для числа [[Перестановка|перестановок]] и [[Сочетание|сочетаний]], причём эти формулы, возможно, были знакомы [[История математики в Индии|индийским математикам]] ещё в VI веке н. э. Философ и астроном рабби [[Авраам ибн Эзра]] (около 1140 года) подсчитал число размещений с перестановками в огласовках [[Имена Бога в иудаизме|имени Бога]]<ref>Краткий комментарий к Исход, 3:13.</ref>. Он же установил симметрию [[Биномиальный коэффициент|биномиальных коэффициентов]]. Точную формулу для них обнародовал позже [[талмуд]]ист и математик [[Леви бен Гершом]] (более известный как Герсонид) в 1321 году.
{{родств-блок
|имена-собственные=
|существительные=комбинат, комбинатор, комбинаторность, комбинаторша, комбинация
|прилагательные=комбинаторный, комбинаторский, комбинационный
|глаголы=комбинировать
|наречия=
}}


=== Этимология ===
Несколько комбинаторных задач содержит «[[Книга абака]]» ([[Фибоначчи]], XIII век). Например, он поставил задачу найти наименьшее число гирь, достаточное для взвешивания любого товара весом от 1 до 40 фунтов.
Происходит от {{этимология:комбинаторика|да}}


=== Фразеологизмы и устойчивые сочетания ===
=== Новое время ===
*
[[Файл:PascalTriangleAnimated2.gif|thumb|251px|[[Треугольник Паскаля]]]]
[[Паскаль, Блез|Блез Паскаль]] много занимался биномиальными коэффициентами и открыл простой способ их вычисления: «[[треугольник Паскаля]]». Позднее выяснилось, что этот способ был уже известен на Востоке (примерно с X века) и он назывался ''арифметическим треугольником''. Паскаль, в отличие от предшественников, строго изложил и доказал свойства этого треугольника. Арифметический треугольник представляет собой графическую диаграмму, показывающую отношения между биномиальными коэффициентами. Позже, в средневековой Англии, [[кампанология]] предоставила примеры того, что теперь известно как [[Гамильтонов цикл|гамильтоновы циклы]] в [[Граф Кэли|графах Кэли]] на перестановках.


=== Перевод ===
В эпоху [[Возрождение|Возрождения]], наряду с прочими науками, комбинаторика начала стремительное развитие. [[Джероламо Кардано]] написал проницательное математическое исследование [[Кости (игра)|игры в кости]], опубликованное посмертно. Теорией этой игры занимались также [[Никколо Тарталья]] и [[Галилео Галилей]]. [[История теории вероятностей]] началась с переписки заядлого игрока шевалье де Мерэ с [[Ферма, Пьер|Пьером Ферма]] и [[Блез Паскаль|Блезом Паскалем]], где были затронуты несколько тонких комбинаторных вопросов. Помимо азартных игр, комбинаторные методы использовались (и продолжают использоваться) в [[Криптография|криптографии]] — как для разработки шифров, так и для их взлома.
{{перев-блок|раздел математики
|abq=
|ab=
|av=
|ave=
|agh=
|aja=
|ady=
|az=[[kombinatorika]]
|ay=
|ain=
|ain.kana=
|ain.lat=
|sq=[[kombinatorika]]
|gsw=
|ale=
|alt=
|am=[[ሥነ ጥምረት]]
|en=[[theory of combinations]]; [[combinatorics]]
|ar=[[توافقيات]]
|an=
|arc.jud=
|arc.syr=
|arn=
|hy=[[կոմբինատորիկա]]
|asm=
|ast=
|af=
|bar=
|bm=
|eu=[[konbinatoria]]
|ba=
|be=[[камбінаторыка]] {{f}}
|bn=
|bg=[[комбинаторика#Болгарский|комбинаторика]]
|bs=[[kombinatorika]]
|br=
|bua=
|cy=
|wa=
|hu=[[kombinatorika]]
|vep=
|hsb=
|vot=
|vo=
|wo=
|vro=
|vi=
|gag=
|haw=
|ht=
|gl=[[combinatoria]] {{f}}
|ze=
|kl=
|el=[[συνδυαστική]] {{f}}
|ka=[[კომბინატორიკა]]
|gn=
|gu=
|gd=
|dar=
|prs=
|da=[[kombinatorik]]
|dv=
|ang=
|grc=
|sgs=[[kuombėnatuorėka]]
|zza=
|zu=
|he=[[קומבינטוריקה]]
|yi=
|io=[[kombinatoriko]]
|inh=
|id=[[kombinatorika]]
|ia=
|iu=
|ik=
|ga=
|is=[[talningarfræði]]
|es=[[combinatoria]]
|it=[[calcolo combinatorio]]
|yo=
|kbd=
|kk=
|xal=
|kn=
|kaa=
|krc=
|krl=
|ca=[[combinatòria]] {{f}}
|csb=
|qu=
|ky=
|zh=[[组合数学]]
|zh-tw=
|zh-cn=
|kom=
|koi=
|kok=
|kw=
|ko=[[조합론]]
|co=
|xh=
|crh=
|kum=
|ku=
|ckb=
|km=
|lad=
|lbe=
|lo=
|la=[[calculus coniunctionibus]]; [[ars combinatoria]]
|lv=[[kombinatorika]] {{f}}
|lez=
|li=
|ln=
|lt=[[kombinatorika]] {{f}}
|lmo=
|lb=
|mk=[[комбинаторика#Македонский|комбинаторика]]
|mg=
|ms=[[kombinatorik]]
|ml=
|mt=
|mi=
|chm=
|mdf=
|mo=
|mn=
|gv=
|nv=
|gld=
|nah=
|na=
|nio=
|nap=
|new=
|de=[[Kombinatorik]]
|yrk=
|nl=[[combinatoriek]]; [[combinatieleer]]
|dsb=
|no=[[kombinatorikk]]
|oc=
|os=
|pa=
|pap=
|fa=
|pl=[[kombinatoryka]] {{f}}
|pt=[[combinatória]] {{f}}
|ps=
|pms=
|rap=
|rm=
|ro=[[combinatorică]] {{f}}
|sjd=
|sa=
|sc=
|se=
|sr=[[комбинаторика#Сербский|комбинаторика]] {{f}}
|sr-l=
|scn=
|si=
|sd=
|sk=[[kombinatorika]] {{f}}
|sl=
|slovio-c=
|slovio-l=
|so=
|chu.cyr=
|chu.glag=
|sw=
|tab=
|tl=[[kombinatorika]]
|tg=
|ty=
|th=
|ta=[[சேர்மானவியல்]]
|tt=[[комбинаторика#Татарский|комбинаторика]]
|tt.lat=
|ttt=
|te=
|bo=
|tir=
|art=
|tpi=
|kim=
|tn=
|tyv=
|tr=[[kombinatorik]]
|tk=[[kombinatorika]]
|udm=
|ug=
|uz=
|uk=[[комбінаторика]] {{f}}
|ur=
|fo=
|fi=[[kombinatoriikka]]
|fr=[[théorie des combinaisons]]; [[combinatoire]] {{f}}; [[analyse combinatoire]]
|fy=
|fur=
|kjh=
|ha=
|hi=
|hr=[[kombinatorika]]
|rom=
|ce=
|cs=[[kombinatorika]] {{f}}
|cv=[[комбинаторика#Чувашский|комбинаторика]]
|sv=[[kombinatorik]]
|cjs=
|sco=
|ewe=
|myv=
|eo=[[kombinatoriko]]
|et=[[kombinatoorika]]
|jv=
|sah=[[комбинаторика#Якутский|комбинаторика]]
|ja=
}}


=== Библиография ===
Сам термин «комбинаторика» придумал [[Лейбниц, Готфрид Вильгельм|Лейбниц]], он считается основоположником современной комбинаторики. В 1666 году (ему было тогда 20 лет) опубликовал книгу «Рассуждения о комбинаторном искусстве». Правда, термин «комбинаторика» Лейбниц понимал чрезмерно широко, включая в него всю [[Дискретная математика|конечную математику]] и даже логику{{sfn |Виленкин Н. Я.|1975|с=19}}. Ученик Лейбница [[Якоб Бернулли]], один из основателей теории вероятностей, изложил в своей книге «Искусство предположений» (1713) множество сведений по комбинаторике.
*


<!-- Служебное: -->
В этот же период формируется терминология новой науки. Термин «[[сочетание]]» (''combination'') впервые встречается у [[Паскаль, Блез|Паскаля]] (1653, опубликован в 1665 году). Термин «[[перестановка]]» (''permutation'') употребил в указанной книге Якоб Бернулли (хотя эпизодически он встречался и раньше). Бернулли использовал и термин «[[размещение]]» (''arrangement'').
{{improve|ru|примеры|семантика|переводы}}
{{Категория|язык=ru|Комбинаторика}}
{{длина слова|13|ru}}


= {{-bg-}} =
После появления [[Математический анализ|математического анализа]] обнаружилась тесная связь комбинаторных и ряда аналитических задач. [[Муавр, Абрахам де|Абрахам де Муавр]] и [[Стирлинг, Джеймс|Джеймс Стирлинг]] нашли формулы для аппроксимации [[факториал]]а<ref name="O'Connor">{{cite web
|url        = http://www-history.mcs.st-andrews.ac.uk/Biographies/De_Moivre.html
|title      = Abraham de Moivre
|accessdate  = 2010-05-31
|last        = O'Connor
|first      = John
|coauthors  = Edmund Robertson.
|work        = The MacTutor History of Mathematics archive
|archiveurl  = https://www.webcitation.org/67EMJ4eNF?url=http://www-history.mcs.st-andrews.ac.uk/Biographies/De_Moivre.html
|archivedate = 2012-04-27
}}</ref>.


=== Морфологические и синтаксические свойства ===
Окончательно комбинаторика как самостоятельный раздел математики оформилась в трудах [[Эйлер, Леонард|Эйлера]]. Он детально рассмотрел, например, следующие проблемы:
{{сущ bg |слоги={{по-слогам|комбинаторика}}|основа=|основа1=}}
* [[задача о ходе коня]];
* [[задача о семи мостах]], с которой началась [[теория графов]];
* построение [[Греко-латинский квадрат|греко-латинских квадратов]];
* [[Числа Эйлера I рода|обобщённые перестановки]].


{{морфо|прист1=|корень1=|суфф1=|оконч=}}
Кроме перестановок и сочетаний, Эйлер изучал [[Разбиение числа|разбиения]], а также сочетания и размещения с условиями.


=== Произношение ===
=== Современное состояние ===
{{transcriptions|||}}
Работы [[Паскаль, Блез|Паскаля]], [[Ньютон, Исаак|Ньютона]], [[Бернулли, Якоб|Якоба Бернулли]] и [[Эйлер, Леонард|Эйлера]] стали фундаментальными в развитии этой области. В наше время работы [[Сильвестр, Джеймс Джозеф|Дж. Дж. Сильвестра]] (конец XIX века) и {{iw|Макмэн, Перси|Перси Макмэна||Percy Alexander MacMahon}} (начало XX века) помогли заложить основы [[Перечислительная комбинаторика|перечислительной]] и [[Алгебраическая комбинаторика|алгебраической комбинаторики]]. [[Теория графов]] также вызывала растущий интерес, особенно в связи с [[Теорема о четырёх красках|теоремой о четырёх красках]] и задачами экономики.


=== Семантические свойства ===
Во второй половине XX века комбинаторика пережила новый бурный рост, что было связано с быстрым раз­ви­ти­ем дис­крет­ной ма­те­ма­ти­ки, [[Информатика|ин­фор­ма­ти­ки]], [[Кибернетика|ки­бер­не­ти­ки]] и [[Планирование эксперимента|пла­ни­ро­ва­ния экс­пе­ри­мен­та]]. Частично этот рост был стимулирован обнаруженными связями и приложениями в других областях математики — в алгебре, теории вероятностей, [[Функциональный анализ|функциональном анализе]], [[Теория чисел|теории чисел]] {{итд}} Эти связи стирают границы между комбинаторикой и другими областями математики, но в то же время приводят к определённой фрагментации комбинаторики.
{{илл|lang=bg|}}


==== Значение ====
В начале XX века началось развитие [[комбинаторная геометрия|комбинаторной геометрии]]: были доказаны теоремы [[Теорема Радона|Радона]], [[Теорема Хелли|Хелли]], [[Теорема Юнга|Юнга]], [[Теорема Бляшке|Бляшке]], а также строго доказана [[Изопериметрическое неравенство|изопериметрическая теорема]]. На стыке топологии, анализа и комбинаторики были доказаны теоремы [[Теорема Борсука — Улама|Борсука — Улама]] и {{iw|Теорема Люстерника — Шнирельмана|Люстерника — Шнирельмана||Lusternik–Schnirelmann theorem}}. Во второй четверти [[XX век]]а были поставлены [[Гипотеза Борсука|проблема Борсука]] и [[проблема Нелсона — Эрдёша — Хадвигера]]. В [[1940-е|1940-х]] годах оформилась [[теория Рамсея]]. Отцом современной комбинаторики считается [[Пал Эрдёш]], который ввёл в комбинаторику вероятностный анализ. Внимание к конечной математике и, в частности, к комбинаторике значительно повысилось со второй половины XX века, когда появились [[компьютер]]ы. Сейчас это содержательная и быстроразвивающаяся область математики.
# {{матем.|bg}} [[комбинаторика#Русский|комбинаторика]] {{пример||перевод=}}
#


==== Синонимы ====
== Методы и разделы комбинаторики ==
#
#


==== Антонимы ====
=== Перечислительная комбинаторика ===
#
{{Основная статья|Перечислительная комбинаторика}}
#
[[Файл:Catalan 4 leaves binary tree example.svg|мини|290x290пкс|Пять двоичных деревьев с 4 листьями, пример чисел Каталана]]
'''[[Перечислительная комбинаторика]]''' (или '''исчисляющая комбинаторика''') рассматривает задачи о ''перечислении'' или ''подсчёте количества'' различных конфигураций (например, [[Перестановка|перестановок]]) образуемых элементами конечных множеств, на которые могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.


==== Гиперонимы ====
Количество конфигураций, образованных несколькими манипуляциями над множеством, подсчитывается согласно правилам [[Правило сложения (комбинаторика)|сложения]] и [[Правило умножения (комбинаторика)|умножения]].
#
#


==== Гипонимы ====
[[Числа Фибоначчи]] являются типичным примером задачи в перечислительной комбинаторике, а также известная [[Задача о письмах]]. [[Двенадцатеричный путь]] обеспечивает единую структуру для подсчета [[Перестановка|перестановок]], [[Сочетание|сочетаний]] и [[Разбиение множества|разбиений]].
#
#


=== Родственные слова ===
=== Аналитическая комбинаторика ===
{{родств-блок
{{Основная статья|{{iw|Аналитическая комбинаторика|Аналитическая комбинаторика|en|Symbolic method (combinatorics)}}}}
|умласк=
Аналитическая комбинаторика относится к перечислению комбинаторных структур с использованием инструментов из [[Комплексный анализ|комплексного анализа]] и [[Теория вероятностей|теории вероятностей]]. В отличие от перечислительной комбинаторики, которая использует явные комбинаторные формулы и [[Производящая функция последовательности|производящие функции последовательности]] для описания результатов, аналитическая комбинаторика нацелена на получение [[Асимптотический анализ|асимптотических формул]].
|имена-собственные=
[[Файл:Partition3D.svg|мини|Плоское разбиение]]
|существительные=
|прилагательные=
|числительные=
|глаголы=
|наречия=
}}


=== Этимология ===
=== Теория разбиения ===
От {{этимология:|bg}}
{{Основная статья|Разбиение числа}}
Теория разбиения изучает различные перечислительные и асимптотические задачи, связанные с [[Разбиение числа|разбиением натуральных чисел]], и тесно связана с [[Q-символ Похгаммера|q-рядами]], [[Специальные функции|специальными функциями]] и [[Ортогональные многочлены|ортогональными многочленами]]. Первоначально она была частью [[Теория чисел|теории чисел]] и [[Анализ (раздел математики)|анализа]], а теперь рассматривается как часть комбинаторики или самостоятельная область. Она включает в себя [[Биективное доказательство|биективный подход]], различные инструменты анализа и [[Аналитическая теория чисел|аналитической теории чисел]], имеет также связи со [[Статистическая механика|статистической механикой]].
[[Файл:Petersen1 tiny.svg|мини|Граф Петерсена]]


=== Фразеологизмы и устойчивые сочетания ===
=== Теория графов ===
*
{{Основная статья|Теория графов}}
Графы являются фундаментальными объектами в комбинаторике. Теория графов рассматривает перечисления (например, число <math>n</math> вершин с <math>k</math> рёбрами графа), существующие структуры (например, гамильтоновы циклы), алгебраические представления (например, имеет ли комбинаторное представление [[многочлен Татта]] <math>T_G(x,y)</math> для заданных графа <math>G</math> и двух чисел <math>x</math> и <math>y</math>?). Хотя между теорией графов и комбинаторикой существуют очень сильные связи, они иногда рассматриваются как отдельные предметы. В то же время комбинаторные методы применимы ко многим задачам теории графов, эти две дисциплины обычно используются для поиска решений различных типов задач.


=== Библиография ===
=== Теория схем ===
*
{{Основная статья|Комбинаторная схема}}
Теория схем — это исследование [[Комбинаторная схема|комбинаторных схем]], которые представляют собой наборы подмножеств с определёнными свойствами [[Пересечение множеств|пересечения]]. [[Блок-дизайн|Блок-схемы]] — это комбинаторные схемы особого типа. Эта область является одной из старейших частей комбинаторики, например, предложенная в 1850 году [[задача Киркмана о школьницах]]. Решение задачи является частным случаем [[Система Штейнера|системы Штейнера]], системы которой играют важную роль в [[Классификация простых конечных групп|классификации простых конечных групп]]. Эта область имеет дальнейшие связи с [[Теория кодирования|теорией кодирования]] и геометрической комбинаторикой.


<!-- Служебное: -->
=== Конечная геометрия ===
{{improve|bg|морфо|транскрипция/мн|пример|синонимы|гиперонимы|этимология}}
{{Основная статья|Конечная геометрия}}
{{Категория|язык=bg|Комбинаторика||}}
Конечная геометрия изучает геометрические системы с конечным числом точек. Структуры аналогичны тем, которые встречаются в непрерывной геометрии ([[Евклидово пространство|евклидово]] или [[Проективное пространство|проективное]] пространство), но определены комбинаторно. Эта область является богатым источником примеров для [[Комбинаторная схема|теории схем]].
{{длина слова|13|bg}}
[[Файл:Hasse diagram of powerset of 3.svg|мини|Диаграмма Хассе, булеан — <math>\{x, y, z\}</math>, упорядоченный по включению]]


= {{-mk-}} =
=== Теория порядка ===
{{Основная статья|Отношение порядка}}
Теория порядка — это изучение [[Частично упорядоченное множество|частично упорядоченных множеств]], как конечных, так и бесконечных. Различные примеры частичных порядков встречаются в [[Алгебра|алгебре]], геометрии, теории чисел и во всей комбинаторике, и теории графов. Известные классы и примеры частичных порядков включают [[Решётка (алгебра)|решетки]] и [[Булева алгебра|булевы алгебры]].


=== Морфологические и синтаксические свойства ===
=== Теория матроидов ===
{{сущ mk |слоги={{по-слогам|комбинаторика}}|основа=|основа1=}}
{{Основная статья|Матроид}}
Теория матроидов абстрагирует часть [[Геометрия|геометрии]]. Она изучает свойства множеств (обычно конечных множеств) векторов в векторном пространстве, которые не зависят от конкретных коэффициентов в [[Линейная независимость|линейно зависимом]] отношении. Не только структура, но и перечислительные свойства принадлежат теории матроидов. Теория матроидов была введена [[Уитни, Хасслер|Хасслером Уитни]] и изучалась как часть теории порядка. В настоящее время это самостоятельная область исследований, имеющая ряд связей с другими разделами комбинаторики.


{{морфо|прист1=|корень1=|суфф1=|оконч=}}
=== Экстремальная комбинаторика ===
{{Основная статья |{{iw|Экстремальная комбинаторика|Экстремальная комбинаторика|en|Extremal combinatorics}}}}
Экстремальная комбинаторика изучает экстремальные вопросы о [[Множество|системах множеств]]. Типы вопросов, рассматриваемых в этом случае, относятся к самому большому возможному графу, который удовлетворяет определённым свойствам. Например, самый большой [[граф без треугольников]] на <math>2n</math> вершинах — это [[полный двудольный граф]] <math>K_{n,n}</math>. Часто бывает слишком трудно даже точно найти экстремальный ответ{{уточнить}} <math>f(n)</math> и можно дать только [[Асимптотический анализ|асимптотическую оценку]].


=== Произношение ===
=== Теория Рамсея ===
{{transcriptions|||}}
{{main|Теория Рамсея}}


=== Семантические свойства ===
'''Теория Рамсея''' — ещё одна часть экстремальной комбинаторики. Она утверждает, что любая достаточно большая конфигурация будет содержать некоторый порядок и изучает наличие регулярных структур в случайных конфигурациях элементов. Это расширенное обобщение принципа Дирихле («принцип голубей и ящиков»). Примером утверждения из теории Рамсея может служить следующее:
{{илл|lang=mk|}}
: ''в группе из 6 человек всегда можно найти трёх человек, которые либо попарно знакомы друг с другом, либо попарно незнакомы.''
В терминах структурной комбинаторики это же утверждение формулируется так:
: ''в любом графе с 6 вершинами найдётся либо [[Задача о клике|клика]], либо независимое множество размера 3.''
[[Файл:Self avoiding walk.svg|мини|Самонепересекающаяся прогулка по решетке]]


==== Значение ====
=== Вероятностная комбинаторика ===
# {{матем.|mk}} [[комбинаторика#Русский|комбинаторика]] {{пример||перевод=}}
{{Основная статья|Вероятностный метод}}
#
Этот раздел отвечает на вопросы вида: какова вероятность присутствия определённого свойства для случайного дискретного объекта, такого как [[случайный граф]]? Например, каково среднее число треугольников в случайном графе? Вероятностные методы также используются для определения существования комбинаторных объектов с определёнными заданными свойствами (для которых явные примеры может быть трудно найти), просто наблюдая, что вероятность случайного выбора объекта с этими свойствами больше ''0''. Этот подход (часто называемый [[Вероятностный метод|вероятностным методом]]) доказал свою высокую эффективность в приложениях экстремальной комбинаторики и теории графов. Тесно связанной областью является изучение конечных [[Цепь Маркова|цепей Маркова]], особенно на комбинаторных объектах. Здесь снова используются вероятностные инструменты для оценки {{iw|время смешивания цепи|времени смешивания|en|Markov chain mixing time}}.


==== Синонимы ====
Часто ассоциируемая с [[Эрдёш, Пал|Палом Эрдёшем]], который сделал новаторскую работу по этому предмету, вероятностная комбинаторика традиционно рассматривалась как набор инструментов для изучения задач в других частях комбинаторики. Однако с ростом приложений для [[анализ алгоритмов|анализа алгоритмов]] в [[Информатика|информатике]], а также классической теории вероятностей, [[Аддитивная теория чисел|аддитивной теории чисел]] и [[вероятностная теория чисел|вероятностной теории чисел]], эта область в последнее время выросла и стала самостоятельной областью комбинаторики.
#
[[Файл:Young diagram for 541 partition.svg|мини|Диаграмма Юнга формы (5, 4, 1)]]
#


==== Антонимы ====
=== Алгебраическая комбинаторика ===
#
{{Основная статья|Алгебраическая комбинаторика}}
#
Алгебраическая комбинаторика — это область [[Математика|математики]], которая использует методы [[Общая алгебра|абстрактной алгебры]], в частности [[Теория групп|теорию групп]] и [[Теория представлений|теорию представлений]], в различных комбинаторных контекстах и, наоборот, применяет комбинаторные методы к задачам [[Алгебра|алгебры]]. Алгебраическая комбинаторика постоянно расширяет свой охват, как в тематических направлениях, так и в методах и может рассматриваться как область математики, где взаимодействие комбинаторных и алгебраических методов особенно сильно и существенно.
[[Файл:Morse-Thue sequence.gif|мини|Демонстрация создания последовательности Морса — Туэ.]]


==== Гиперонимы ====
=== Комбинаторика слов ===
#
{{Основная статья|{{iw|Комбинаторика слов |Комбинаторика слов|en|Combinatorics on words}}}}
#
Комбинаторика слов имеет дело с [[Формальный язык|формальными языками]]. Она возникла самостоятельно в нескольких областях математики, в том числе в [[Теория чисел|теории чисел]], [[Теория групп|теории групп]] и [[Теория вероятностей|теории вероятности]]. Она имеет приложения в перечислительной комбинаторике, {{iw|фрактальный анализ|фрактальном анализе|en|Fractal analysis}}, [[Теоретическая информатика|теоретической информатике]], [[Теория автоматов|теории автоматов]] и лингвистике. Хотя многие приложения являются новыми, классическая [[иерархия Хомского]] классов [[Формальная грамматика|формальных грамматик]] является, пожалуй, самым известным результатом в этой области.
[[Файл:Icosahedron.svg|мини|Выпуклый [[правильный икосаэдр]]]]


==== Гипонимы ====
=== Комбинаторная геометрия ===
#
{{основная статья|[[Комбинаторная геометрия]]}}
#
Геометрическая комбинаторика связана с [[Выпуклая геометрия|выпуклой]] и [[Комбинаторная геометрия|дискретной геометрией]], в частности с [[Комбинаторика многогранников|комбинаторикой многогранников]]. Например, она спрашивает, сколько граней каждого измерения может иметь [[выпуклый многогранник]]. Важную роль играют также [[Метрическое пространство|метрические]] свойства многогранников, например, [[Теорема Коши о многогранниках|теорема Коши]] о жёсткости выпуклых многогранников. Рассматриваются также особые многогранники, такие как [[Перестановочный многогранник|перестановочные многогранники]], {{iw|ассоциаэдр|ассоциаэдры|en|Associahedron}} и [[Многогранник Биркгофа|многогранники Биркгофа]]. [[Комбинаторная геометрия]] — это старомодное название дискретной геометрии.
[[Файл:Collier-de-perles-rouge-vert.svg|мини|Пример ожерелья, разделённого на <math>k = 2</math> (то есть между двумя участниками дележа) и <math>t = 2</math> (то есть два типа бусин, имеется 8 красных и 6 зелёных). Показаны 2 разреза — один из участников получает большую секцию, а другой получает оставшиеся два куска.]]


=== Родственные слова ===
=== Топологическая комбинаторика ===
{{родств-блок
{{Основная статья|Топологическая комбинаторика}}
|умласк=
[[Топологическая комбинаторика]] применяет идеи и методы комбинаторики в [[Топология|топологии]], при изучении [[Раскраска графов|раскрасок графа]], [[Справедливый делёж|справедливого дележа]], [[Разбиение множества|разбиения]], [[Дерево принятия решений|дерева принятия решений]], [[Частично упорядоченное множество|частично упорядоченных множеств]], [[Задача о восстановлении бус|задачи о восстановлении бус]] и {{iw|дискретная теория Морса|дискретной теории Морсе|en|Discrete Morse theory}}. Её не следует путать с [[Комбинаторная топология|комбинаторной топологией]], которая является более старым названием [[Алгебраическая топология|алгебраической топологии]].
|имена-собственные=
|существительные=
|прилагательные=
|числительные=
|глаголы=
|наречия=
}}


=== Этимология ===
=== Арифметическая комбинаторика ===
От {{этимология:|mk}}
{{Основная статья|Арифметическая комбинаторика}}
Арифметическая комбинаторика возникла из взаимодействия между [[Теория чисел|теорией чисел]], комбинаторикой, [[Эргодичность|эргодической теории]] и [[Гармонический анализ|гармоническим анализом]]. Она о комбинаторных оценках, связанных с арифметическими операциями (сложение, вычитание, умножение и деление). [[Аддитивная теория чисел]] (иногда также называемая аддитивной комбинаторикой) относится к частному случаю, когда задействованы только операции сложения и вычитания. Одним из важных методов арифметической комбинаторики является [[Эргодичность|эргодическая теория]] [[Динамическая система|динамических систем]].


=== Фразеологизмы и устойчивые сочетания ===
=== Инфинитарная комбинаторика ===
*
{{Основная статья|{{iw|Инфинитарная комбинаторика|Инфинитарная комбинаторика|en|Infinitary combinatorics}}}}
{{Не переведено|Инфинитарная комбинаторика||en|Infinitary combinatorics}} — применение идей и методов комбинаторики к [[Бесконечное множество|бесконечным]] (в том числе, [[Несчётное множество|несчётным]]) множествам. Это часть [[Теория множеств|теории множеств]], область [[Математическая логика|математической логики]], но использует инструменты и идеи как теории множеств, так и экстремальной комбинаторики.


=== Библиография ===
{{iw|Рота, Джан-Карло|Джан-Карло Рота|en|Gian-Carlo Rota}} использовал название непрерывной комбинаторики для описания {{iw|геометрическая вероятность|геометрической вероятности|en|Geometric probability}}, поскольку существует много аналогий между подсчетом и мерой.
*


<!-- Служебное: -->
== Связанные области ==
{{improve|mk|морфо|транскрипция/мн|пример|синонимы|гиперонимы|этимология}}
[[Файл:Kissing-3d.png|мини|Контактное расположение сфер связано как [[теория кодирования]] с [[Комбинаторная геометрия|дискретной геометрией]]]]
{{Категория|язык=mk|Комбинаторика||}}
{{длина слова|13|mk}}


= {{-sr-}} =
=== Комбинаторная оптимизация ===
[[Комбинаторная оптимизация]] — это исследование оптимизации дискретных и комбинаторных объектов. Она начиналась как часть комбинаторики и теории графов, но теперь рассматривается как раздел прикладной математики и информатики, связанный с [[Исследование операций|исследованием операций]], [[теория алгоритмов|теорией алгоритмов]] и [[Теория сложности вычислений|теорией сложности вычислений]].


=== Морфологические и синтаксические свойства ===
=== Теория кодирования ===
{{сущ sr |слоги={{по-слогам|комбинаторика}}|основа=|основа1=}}
[[Теория кодирования]] началась как часть теории схем с ранними комбинаторными конструкциями [[Корректирующий код|кодов, исправляющих ошибки]]. Основная идея предмета заключается в разработке эффективных и надежных методов передачи данных. Сейчас это большая область исследований, часть [[Теория информации|теории информации]].


{{морфо|прист1=|корень1=|суфф1=|оконч=}}
=== Дискретная и вычислительная геометрия ===
[[Комбинаторная геометрия|Дискретная геометрия]] (также называемая комбинаторной геометрией) также началась как часть комбинаторики, с ранними результатами [[Выпуклый многогранник|выпуклых многогранников]] и [[Контактное число|контактных чисел]]. С появлением приложений дискретной геометрии в [[Вычислительная геометрия|вычислительной геометрии]], эти две области частично слились и стали отдельной областью изучения. Остается много связей с геометрической и топологической комбинаторикой, которые сами по себе можно рассматривать как порождения ранней дискретной геометрии.


=== Произношение ===
=== Комбинаторика и динамические системы ===
{{transcriptions|||}}
Комбинаторные аспекты динамических систем — это ещё одна развивающаяся область. Здесь динамические системы могут быть определены комбинаторными объектами. См., например, [[динамическая система графов]].


=== Семантические свойства ===
=== Комбинаторика и физика ===
{{илл|lang=sr|}}
Между комбинаторикой и физикой, в частности [[Статистическая физика|статистической физикой]], усиливается взаимосвязь. Примеры включают точное решение [[Модель Изинга|модели Изинга]] и связь между {{iw|модель Поттса|моделью Поттса|en|Potts model}} с одной стороны, и [[Хроматический многочлен|хроматическими многочленами]] и [[Многочлен Татта|многочленами Татте]], с другой стороны.


==== Значение ====
== Открытые проблемы ==
# {{матем.|sr}} [[комбинаторика#Русский|комбинаторика]] {{пример||перевод=}}
Комбинаторика (в частности, теория Рамсея) содержит много известных [[Открытые математические проблемы|открытых проблем]], подчас с весьма несложной формулировкой. Например, неизвестно, при каком наименьшем <math>N</math> в любой группе из <math>N</math> человек найдутся 5 человек, либо попарно знакомых друг с другом, либо попарно незнакомых (хотя известно, что 49 человек достаточно)<ref>{{MathWorld|RamseyNumber|Числа Рамсея}}</ref>.
#


==== Синонимы ====
Также есть и другие нерешённые задачи и недоказанные гипотезы:
#
#


==== Антонимы ====
* '''Гипотеза Адамара (1893):''' для каждого натурального <math>n</math>, делящегося на 4, существует вещественная [[матрица Адамара]] порядка <math>n</math>. '''Пояснение:''' известно, что делимость на 4 является лишь необходимым условием существования матрицы Адамара. Существуют различные методы построения вещественных матриц Адамара порядка <math>n=4k</math> для некоторых бесконечных серий натуральных чисел, делящихся на 4, однако они не позволяют доказать гипотезу Адамара. Наименьшим порядком, кратным 4, для которого матрица Адамара неизвестна, является <math>n=668</math><ref>{{Статья|ссылка=http://ej.kubagro.ru/2017/02/pdf/33.pdf|автор=|заглавие=МАТРИЦЫ АДАМАРА|год=|язык=|издание=|тип=|месяц=|число=|том=|номер=|страницы=|issn=|archivedate=2022-01-21|archiveurl=https://web.archive.org/web/20220121055802/http://ej.kubagro.ru/2017/02/pdf/33.pdf}}</ref>.
#
* Существование конечной [[Проективная плоскость|проективной плоскости]] натурального порядка, не являющегося степенью простого числа.
#
* '''Гипотеза Эрдёша — Реньи.''' Если <math>k</math> — фиксированное целое число <math>k \geqslant 3</math>, то <math>\lim\;\inf(per(A))^{\frac{1}{n}}>1</math> для <math>A</math> из <math>\Lambda_n^k</math>. Здесь <math>per(A)</math> — [[перманент]] матрицы <math>A, \Lambda_n^k</math> — множество всех <math>(0,1)</math> — матриц порядка <math>n</math> c <math>k</math> единицами в каждой строке и каждом столбце<ref>{{Книга|автор=Минк X.|заглавие=Перманенты.|ответственный=|год=1982|издание=Мир|место=|издательство=|страницы=|страниц=211|isbn=}}</ref>.
* [[Числа Рамсея]] <math>N(q_1,q_2,...,q_t;r)</math> для случая <math>t>2</math> почти не изучены{{sfn |Рыбников|1972|с=96}}.
* Задача нахождения минимума [[перманент]]а [[Дважды стохастическая матрица|дважды стохастической матрицы]] в общем случае не решена{{sfn |Рыбников|1972|с=110}}.
* Не известны необходимые и достаточные условия, при которых существует общая [[трансверсаль]] для трёх семейств подмножеств<ref>{{Книга|автор=Капитонова Ю. В., Кривой С. Л., Летичевский А. А.|заглавие=Лекции по дискретной математике|ответственный=|год=2004|издание=|место=СПб|издательство=БХВ-Петербург|страницы=530|страниц=624|isbn=5-94157-546-7}}</ref>.
* Задача о числе [[Монотонная булева функция|монотонных булевых функций]] от <math>n</math> аргументов{{sfn|Шень|с=8|2017}}.


==== Гиперонимы ====
== Комбинаторика в языкознании ==
#
Комбинаторика (языкознание) — это свойство единиц языка и соответствующих им единиц речи вступать в синтагматические отношения, то есть в отношения сочетаемости.
#


==== Гипонимы ====
== Примечания ==
#
{{примечания}}
#


=== Родственные слова ===
== Литература ==
{{родств-блок
* {{книга
|умласк=
|автор = Андерсон, Джеймс
|имена-собственные=
|заглавие = Дискретная математика и комбинаторика
|существительные=
|оригинал = Discrete Mathematics with Combinatorics
|прилагательные=
|ссылка =  
|числительные=
|издание =  
|глаголы=
|место = М.
|наречия=
|издательство = [[Вильямс (издательство)|«Вильямс»]]
|год = 2006
|страниц = 960
|isbn = 0-13-086998-8
}}
}}
 
* {{книга |автор=[[Виленкин, Наум Яковлевич|Виленкин Н. Я.]]|заглавие=Популярная комбинаторика|ссылка=http://ilib.mccme.ru/djvu/combinatorika.htm|место=М. |издательство=Наука |год=1975|ref=Виленкин Н. Я.}}
=== Этимология ===
* ''[[Вялый, Михаил Николаевич|Вялый М. Н.]]'' [https://mccme.ru/free-books/dubna/vyalyi.pdf Линейные неравенства и комбинаторика]. М.: МЦНМО, 2003. 32 с.
От {{этимология:|sr}}
* ''Ерош И. Л.'' Дискретная математика. Комбинаторика — СПб.: СПбГУАП, 2001. — 37 c.
 
* ''[[Леонтьев, Владимир Константинович|Леонтьев В. К.]]'' Избранные задачи комбинаторного анализа. — М. : Изд-во МГТУ им. Н. Э. Баумана, 2001. — 179, [3] с.; 20 см; ISBN 5-7038-1862-1
=== Фразеологизмы и устойчивые сочетания ===
* ''Леонтьев В. К.'' Комбинаторика и информация : учеб. пос. … по направлению … «Прикладные математика и физика». — Москва : МФТИ, 2015. — 21 см; ISBN 978-5-7417-0518-6
*  
* ''Леонтьев В. К., Гордеев Э. Н.'' [http://www.mou.mipt.ru/AddDiscAn.pdf Комбинаторные аспекты теории информации]. М.: МФТИ, 2019.
 
* {{книга |автор=Липский В.|заглавие=Комбинаторика для программиста |место=М. |издательство=Мир |год=1988 |ссылка= |страниц=213}}
=== Библиография ===
* {{книга |автор=[[Райгородский, Андрей Михайлович|Райгородский А. М.]]|заглавие=Линейно-алгебраические и вероятностные методы в комбинаторике |издание=[[Летняя школа «Современная математика»]] |место=Дубна |год=2006 |ссылка=http://www.mccme.ru/dubna/2006/notes/raygorodsky.pdf}}
*  
* {{книга |автор=Райзер Г. Дж.|заглавие=Комбинаторная математика |издание=пер. с англ |место=М. |год=1966}}
 
* {{книга |автор=Рейнгольд Э., Нивергельт Ю., Део Н.|заглавие=Комбинаторные алгоритмы. Теория и практика |место=М. |издательство=Мир |год=1980 |страниц=476}}
<!-- Служебное: -->
* {{книга |автор=Риордан Дж.|заглавие=Введение в комбинаторный анализ |издание=пер. с англ |место=М. |год=1963}}
{{improve|sr|морфо|транскрипция/мн|пример|синонимы|гиперонимы|этимология}}
* {{Книга|автор=Рыбников К. А.|заглавие=Введение в комбинаторный анализ |ref=Рыбников |год=1972 |место=М. |издательство=МГУ|страницы=96|страниц=308}}
{{Категория|язык=sr|Комбинаторика||}}
* {{книга
{{длина слова|13|sr}}
|автор = Стенли Р.
 
|заглавие = Перечислительная комбинаторика
= {{-tt-}} =
|оригинал = Enumerative Combinatorics
 
|ссылка =  
=== Морфологические и синтаксические свойства ===
|издание =  
{{сущ tt |слоги={{по-слогам|комбинаторика}}|основа=|основа1=}}
|место = М.
 
|издательство = [[Мир (издательство)|«Мир»]]
{{морфо|прист1=|корень1=|суфф1=|оконч=}}
|год = 1990
 
|страниц = 440
=== Произношение ===
|isbn = 5-03-001348-2
{{transcriptions|||}}
 
=== Семантические свойства ===
{{илл|lang=tt|}}
 
==== Значение ====
# {{матем.|tt}} [[комбинаторика#Русский|комбинаторика]] {{пример||перевод=}}
#
 
==== Синонимы ====
#
#
 
==== Антонимы ====
#
#
 
==== Гиперонимы ====
#
#
 
==== Гипонимы ====
#
#
 
=== Родственные слова ===
{{родств-блок
|умласк=
|имена-собственные=
|существительные=
|прилагательные=
|числительные=
|глаголы=
|наречия=
}}
}}
 
* {{книга
=== Этимология ===
|автор = Стенли Р.
От {{этимология:|tt}}
|заглавие = Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции
 
|оригинал = Enumerative Combinatorics. Volume 2
=== Фразеологизмы и устойчивые сочетания ===
|ссылка =  
*
|издание =  
 
|место = М.
=== Библиография ===
|издательство = [[Мир (издательство)|«Мир»]]
*  
|год = 2009
 
|страниц = 767
<!-- Служебное: -->
|isbn = 978-5-03-003476-8
{{improve|tt|морфо|транскрипция/мн|пример|синонимы|гиперонимы|этимология}}
{{Категория|язык=tt|Комбинаторика||}}
{{длина слова|13|tt}}
 
= {{-cv-}} =
 
=== Морфологические и синтаксические свойства ===
{{сущ cv |слоги={{по-слогам|комбинаторика}}|основа=|основа1=}}
 
{{морфо|прист1=|корень1=|суфф1=|оконч=}}
 
=== Произношение ===
{{transcriptions|||}}
 
=== Семантические свойства ===
{{илл|lang=cv|}}
 
==== Значение ====
# {{матем.|cv}} [[комбинаторика#Русский|комбинаторика]] {{пример||перевод=}}
#
 
==== Синонимы ====
#
#
 
==== Антонимы ====
#
#
 
==== Гиперонимы ====
#
#
 
==== Гипонимы ====
#
#
 
=== Родственные слова ===
{{родств-блок
|умласк=
|имена-собственные=
|существительные=
|прилагательные=
|числительные=
|глаголы=
|наречия=
}}
}}
* {{книга|заглавие=Начала теории множеств|автор=[[Верещагин, Николай Константинович|Н. К. Верещагин]], [[Шень, Александр Ханиевич|А. Х. Шень]]|место=М.|издательство=МЦНМО|год=2017|isbn=978-5-4439-0943-1|страниц=112|ref=Шень|ссылка=https://old.mccme.ru//free-books/shen/shen-logic-part1-5ed.pdf}}
{{wiktionary|комбинаторика}}


=== Этимология ===
== Ссылки ==
От {{этимология:|cv}}
* ''Белешко Д''. [https://web.archive.org/web/20100507072030/http://rain.ifmo.ru/cat/view.php/theory/combinations/combinations1-2004 Комбинаторика]. 2004.
 
* {{БРЭ |статья=Комбинаторный анализ |автор=Сачков В. Н. |ref=БРЭ|ссылка=https://old.bigenc.ru/mathematics/text/2622055 |архив=https://web.archive.org/web/20230103215121/https://bigenc.ru/mathematics/text/2622055 |архив дата=2023-01-03 }}
=== Фразеологизмы и устойчивые сочетания ===
* [http://www.mathelp.spb.ru/book2/tv3.htm Теория вероятностей. 3. Элементы комбинаторики]
*
 
=== Библиография ===
*  


<!-- Служебное: -->
{{rq|
{{improve|cv|морфо|транскрипция/мн|пример|синонимы|гиперонимы|этимология}}
{{стиль статьи|дата=2022-11-19}}
{{Категория|язык=cv|Комбинаторика||}}
{{проверить факты|дата=2022-11-19}}
{{длина слова|13|cv}}
 
= {{-sah-}} =
 
=== Морфологические и синтаксические свойства ===
{{сущ sah |слоги={{по-слогам|комбинаторика}}|основа=|основа1=}}
 
{{морфо|прист1=|корень1=|суфф1=|оконч=}}
 
=== Произношение ===
{{transcriptions|||}}
 
=== Семантические свойства ===
{{илл|lang=sah|}}
 
==== Значение ====
# {{матем.|sah}} [[комбинаторика#Русский|комбинаторика]] {{пример||перевод=}}
#
 
==== Синонимы ====
#
#
 
==== Антонимы ====
#
#
 
==== Гиперонимы ====
#
#
 
==== Гипонимы ====
#
#
 
=== Родственные слова ===
{{родств-блок
|умласк=
|имена-собственные=
|существительные=
|прилагательные=
|числительные=
|глаголы=
|наречия=
}}
}}
{{вс}}
{{Разделы математики}}


=== Этимология ===
[[Категория:Комбинаторика|*]]
От {{этимология:|sah}}
 
=== Фразеологизмы и устойчивые сочетания ===
*  
 
=== Библиография ===
*
 
<!-- Служебное: -->
{{improve|sah|морфо|транскрипция/мн|пример|синонимы|гиперонимы|этимология}}
{{Категория|язык=sah|Комбинаторика||}}
{{длина слова|13|sah}}
{{multilang|}}

Текущая версия от 09:14, 1 февраля 2026

Комбинато́рика — раздел математики, посвящённый решению задач, связанных с выбором и расположением элементов некоторого (чаще всего конечного) множества в соответствии с заданными правилами. Каждое такое правило определяет некоторую выборку из элементов исходного множества, которая называется комбинаторной конфигурацией. Простейшими примерами комбинаторных конфигураций<ref name=ME>Шаблон:Книга</ref>Шаблон:Sfn являются перестановки, сочетания и размещенияШаблон:Переход.

Типичные задачи<ref name=ME/> комбинаторикиШаблон:Переход:

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

Комбинаторика тесно связана со многими другими областями математики — алгеброй, геометрией, теорией вероятностей, теорией чисел и другимиШаблон:Переход. Она применяется в самых различных областях знаний, например, в генетике, информатике, статистике, статистической физике, лингвистике, музыке.

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

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

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

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

Примеры комбинаторных задач:

  1. Сколько имеется способов разместить <math>n</math> предметов по <math>m</math> ящикам, чтобы выполнялись заданные ограничения?
  2. Сколько существует функций <math>F</math> из <math>m</math>-элементного множества в <math>n</math>-элементное, удовлетворяющих заданным ограничениям?
  3. Сколько существует различных перестановок из 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,
или примерно <math>8{,}0658 \cdot 10^{67}.</math>
  2. При игре в кости бросаются две кости, и выпавшие очки складываются; сколько существует комбинаций, в которых сумма очков на верхних гранях равна двенадцати?
    Решение: Каждый возможный исход соответствует функции <math>F: \{1, 2\} \to \{1, 2, 3, 4, 5, 6\}</math> (аргумент функции — это номер кости, значение — очки на верхней грани). Очевидно, что лишь 6 + 6 даёт нам нужный результат 12. Таким образом, существует всего одна комбинация, при которой сумма очков на верхних гранях равна двенадцати.

История

Шаблон:Main

Древность и средние века

Основные комбинаторные понятия и вычислительные результаты появились в древнем мире. Классическая задача комбинаторики: «сколько есть способов извлечь <math>m</math> элементов из <math>N</math> возможных» упоминается ещё в сутрах древней Индии (начиная примерно с IV века до н. э.)<ref name="India">Amulya Kumar Bag. Binomial theorem in ancient India. Шаблон:Wayback Indian J. History Sci., 1:68-74, 1966.</ref>. Индийские математики, видимо, первыми открыли биномиальные коэффициенты и их связь с биномом Ньютона<ref name="India"/>. Во II веке до н. э. индийцы знали, что сумма всех биномиальных коэффициентов степени <math>n</math> равна <math>2^n</math>. Индийский математик Нарайяна Пандита впервые предложил алгоритм порождения всех перестановок.

Комбинаторные мотивы можно заметить в символике китайской «Книги Перемен» (V век до н. э.). По мнению её авторов, всё в мире комбинируется из различных сочетаний мужского и женского начал, а также восьми стихий: земля, горы, вода, ветер, гроза, огонь, облака и небоШаблон:Sfn. Историки отмечают также комбинаторные проблемы в руководствах по игре в Го и другие игры. Большой интерес математиков многих стран с древних времён неизменно вызывали магические квадраты.

Античные греки также рассматривали отдельные комбинаторные задачи, хотя систематическое изложение ими этих вопросов, если оно и существовало, до нас не дошло. Хрисипп (III век до н. э.) и Гиппарх (II век до н. э.) подсчитывали, сколько следствий можно получить из 10 аксиом; методика подсчёта нам неизвестна, но у Хрисиппа получилось более миллиона, а у Гиппарха — более 100000Шаблон:Sfn. Аристотель при изложении своей логики безошибочно перечислил все возможные типы трёхчленных силлогизмов. Аристоксен рассмотрел различные чередования длинных и коротких слогов в стихотворных размерах.<ref name=V9/> Какие-то комбинаторные правила пифагорейцы, вероятно, использовали при построении своей теории чисел и нумерологии (совершенные числа, фигурные числа, пифагоровы тройки и др.).

В Средние века комбинаторика также продолжала развиваться, в основном, за пределами европейской цивилизации. В XII веке индийский математик Бхаскара в своём основном труде «Лилавати» подробно исследовал задачи, связанные с перестановками и сочетаниями, включая перестановки с повторениями. Другой индийский математик, Шаблон:Iw (середина IX века), опубликовал формулы для числа перестановок и сочетаний, причём эти формулы, возможно, были знакомы индийским математикам ещё в VI веке н. э. Философ и астроном рабби Авраам ибн Эзра (около 1140 года) подсчитал число размещений с перестановками в огласовках имени Бога<ref>Краткий комментарий к Исход, 3:13.</ref>. Он же установил симметрию биномиальных коэффициентов. Точную формулу для них обнародовал позже талмудист и математик Леви бен Гершом (более известный как Герсонид) в 1321 году.

Несколько комбинаторных задач содержит «Книга абака» (Фибоначчи, XIII век). Например, он поставил задачу найти наименьшее число гирь, достаточное для взвешивания любого товара весом от 1 до 40 фунтов.

Новое время

Файл:PascalTriangleAnimated2.gif
Треугольник Паскаля

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

В эпоху Возрождения, наряду с прочими науками, комбинаторика начала стремительное развитие. Джероламо Кардано написал проницательное математическое исследование игры в кости, опубликованное посмертно. Теорией этой игры занимались также Никколо Тарталья и Галилео Галилей. История теории вероятностей началась с переписки заядлого игрока шевалье де Мерэ с Пьером Ферма и Блезом Паскалем, где были затронуты несколько тонких комбинаторных вопросов. Помимо азартных игр, комбинаторные методы использовались (и продолжают использоваться) в криптографии — как для разработки шифров, так и для их взлома.

Сам термин «комбинаторика» придумал Лейбниц, он считается основоположником современной комбинаторики. В 1666 году (ему было тогда 20 лет) опубликовал книгу «Рассуждения о комбинаторном искусстве». Правда, термин «комбинаторика» Лейбниц понимал чрезмерно широко, включая в него всю конечную математику и даже логикуШаблон:Sfn. Ученик Лейбница Якоб Бернулли, один из основателей теории вероятностей, изложил в своей книге «Искусство предположений» (1713) множество сведений по комбинаторике.

В этот же период формируется терминология новой науки. Термин «сочетание» (combination) впервые встречается у Паскаля (1653, опубликован в 1665 году). Термин «перестановка» (permutation) употребил в указанной книге Якоб Бернулли (хотя эпизодически он встречался и раньше). Бернулли использовал и термин «размещение» (arrangement).

После появления математического анализа обнаружилась тесная связь комбинаторных и ряда аналитических задач. Абрахам де Муавр и Джеймс Стирлинг нашли формулы для аппроксимации факториала<ref name="O'Connor">Шаблон:Cite web</ref>.

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

Кроме перестановок и сочетаний, Эйлер изучал разбиения, а также сочетания и размещения с условиями.

Современное состояние

Работы Паскаля, Ньютона, Якоба Бернулли и Эйлера стали фундаментальными в развитии этой области. В наше время работы Дж. Дж. Сильвестра (конец XIX века) и Шаблон:Iw (начало XX века) помогли заложить основы перечислительной и алгебраической комбинаторики. Теория графов также вызывала растущий интерес, особенно в связи с теоремой о четырёх красках и задачами экономики.

Во второй половине XX века комбинаторика пережила новый бурный рост, что было связано с быстрым раз­ви­ти­ем дис­крет­ной ма­те­ма­ти­ки, ин­фор­ма­ти­ки, ки­бер­не­ти­ки и пла­ни­ро­ва­ния экс­пе­ри­мен­та. Частично этот рост был стимулирован обнаруженными связями и приложениями в других областях математики — в алгебре, теории вероятностей, функциональном анализе, теории чисел Шаблон:Итд Эти связи стирают границы между комбинаторикой и другими областями математики, но в то же время приводят к определённой фрагментации комбинаторики.

В начале XX века началось развитие комбинаторной геометрии: были доказаны теоремы Радона, Хелли, Юнга, Бляшке, а также строго доказана изопериметрическая теорема. На стыке топологии, анализа и комбинаторики были доказаны теоремы Борсука — Улама и Шаблон:Iw. Во второй четверти XX века были поставлены проблема Борсука и проблема Нелсона — Эрдёша — Хадвигера. В 1940-х годах оформилась теория Рамсея. Отцом современной комбинаторики считается Пал Эрдёш, который ввёл в комбинаторику вероятностный анализ. Внимание к конечной математике и, в частности, к комбинаторике значительно повысилось со второй половины XX века, когда появились компьютеры. Сейчас это содержательная и быстроразвивающаяся область математики.

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

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

Ошибка скрипта: Модуля «Основная статья» не существует.

Файл:Catalan 4 leaves binary tree example.svg
Пять двоичных деревьев с 4 листьями, пример чисел Каталана

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

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

Числа Фибоначчи являются типичным примером задачи в перечислительной комбинаторике, а также известная Задача о письмах. Двенадцатеричный путь обеспечивает единую структуру для подсчета перестановок, сочетаний и разбиений.

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

Ошибка скрипта: Модуля «Основная статья» не существует. Аналитическая комбинаторика относится к перечислению комбинаторных структур с использованием инструментов из комплексного анализа и теории вероятностей. В отличие от перечислительной комбинаторики, которая использует явные комбинаторные формулы и производящие функции последовательности для описания результатов, аналитическая комбинаторика нацелена на получение асимптотических формул.

Файл:Partition3D.svg
Плоское разбиение

Теория разбиения

Ошибка скрипта: Модуля «Основная статья» не существует. Теория разбиения изучает различные перечислительные и асимптотические задачи, связанные с разбиением натуральных чисел, и тесно связана с q-рядами, специальными функциями и ортогональными многочленами. Первоначально она была частью теории чисел и анализа, а теперь рассматривается как часть комбинаторики или самостоятельная область. Она включает в себя биективный подход, различные инструменты анализа и аналитической теории чисел, имеет также связи со статистической механикой.

Файл:Petersen1 tiny.svg
Граф Петерсена

Теория графов

Ошибка скрипта: Модуля «Основная статья» не существует. Графы являются фундаментальными объектами в комбинаторике. Теория графов рассматривает перечисления (например, число <math>n</math> вершин с <math>k</math> рёбрами графа), существующие структуры (например, гамильтоновы циклы), алгебраические представления (например, имеет ли комбинаторное представление многочлен Татта <math>T_G(x,y)</math> для заданных графа <math>G</math> и двух чисел <math>x</math> и <math>y</math>?). Хотя между теорией графов и комбинаторикой существуют очень сильные связи, они иногда рассматриваются как отдельные предметы. В то же время комбинаторные методы применимы ко многим задачам теории графов, эти две дисциплины обычно используются для поиска решений различных типов задач.

Теория схем

Ошибка скрипта: Модуля «Основная статья» не существует. Теория схем — это исследование комбинаторных схем, которые представляют собой наборы подмножеств с определёнными свойствами пересечения. Блок-схемы — это комбинаторные схемы особого типа. Эта область является одной из старейших частей комбинаторики, например, предложенная в 1850 году задача Киркмана о школьницах. Решение задачи является частным случаем системы Штейнера, системы которой играют важную роль в классификации простых конечных групп. Эта область имеет дальнейшие связи с теорией кодирования и геометрической комбинаторикой.

Конечная геометрия

Ошибка скрипта: Модуля «Основная статья» не существует. Конечная геометрия изучает геометрические системы с конечным числом точек. Структуры аналогичны тем, которые встречаются в непрерывной геометрии (евклидово или проективное пространство), но определены комбинаторно. Эта область является богатым источником примеров для теории схем.

Файл:Hasse diagram of powerset of 3.svg
Диаграмма Хассе, булеан — <math>\{x, y, z\}</math>, упорядоченный по включению

Теория порядка

Ошибка скрипта: Модуля «Основная статья» не существует. Теория порядка — это изучение частично упорядоченных множеств, как конечных, так и бесконечных. Различные примеры частичных порядков встречаются в алгебре, геометрии, теории чисел и во всей комбинаторике, и теории графов. Известные классы и примеры частичных порядков включают решетки и булевы алгебры.

Теория матроидов

Ошибка скрипта: Модуля «Основная статья» не существует. Теория матроидов абстрагирует часть геометрии. Она изучает свойства множеств (обычно конечных множеств) векторов в векторном пространстве, которые не зависят от конкретных коэффициентов в линейно зависимом отношении. Не только структура, но и перечислительные свойства принадлежат теории матроидов. Теория матроидов была введена Хасслером Уитни и изучалась как часть теории порядка. В настоящее время это самостоятельная область исследований, имеющая ряд связей с другими разделами комбинаторики.

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

Ошибка скрипта: Модуля «Основная статья» не существует. Экстремальная комбинаторика изучает экстремальные вопросы о системах множеств. Типы вопросов, рассматриваемых в этом случае, относятся к самому большому возможному графу, который удовлетворяет определённым свойствам. Например, самый большой граф без треугольников на <math>2n</math> вершинах — это полный двудольный граф <math>K_{n,n}</math>. Часто бывает слишком трудно даже точно найти экстремальный ответШаблон:Уточнить <math>f(n)</math> и можно дать только асимптотическую оценку.

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

Шаблон:Main

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

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

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

в любом графе с 6 вершинами найдётся либо клика, либо независимое множество размера 3.
Файл:Self avoiding walk.svg
Самонепересекающаяся прогулка по решетке

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

Ошибка скрипта: Модуля «Основная статья» не существует. Этот раздел отвечает на вопросы вида: какова вероятность присутствия определённого свойства для случайного дискретного объекта, такого как случайный граф? Например, каково среднее число треугольников в случайном графе? Вероятностные методы также используются для определения существования комбинаторных объектов с определёнными заданными свойствами (для которых явные примеры может быть трудно найти), просто наблюдая, что вероятность случайного выбора объекта с этими свойствами больше 0. Этот подход (часто называемый вероятностным методом) доказал свою высокую эффективность в приложениях экстремальной комбинаторики и теории графов. Тесно связанной областью является изучение конечных цепей Маркова, особенно на комбинаторных объектах. Здесь снова используются вероятностные инструменты для оценки Шаблон:Iw.

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

Файл:Young diagram for 541 partition.svg
Диаграмма Юнга формы (5, 4, 1)

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

Ошибка скрипта: Модуля «Основная статья» не существует. Алгебраическая комбинаторика — это область математики, которая использует методы абстрактной алгебры, в частности теорию групп и теорию представлений, в различных комбинаторных контекстах и, наоборот, применяет комбинаторные методы к задачам алгебры. Алгебраическая комбинаторика постоянно расширяет свой охват, как в тематических направлениях, так и в методах и может рассматриваться как область математики, где взаимодействие комбинаторных и алгебраических методов особенно сильно и существенно.

Файл:Morse-Thue sequence.gif
Демонстрация создания последовательности Морса — Туэ.

Комбинаторика слов

Ошибка скрипта: Модуля «Основная статья» не существует. Комбинаторика слов имеет дело с формальными языками. Она возникла самостоятельно в нескольких областях математики, в том числе в теории чисел, теории групп и теории вероятности. Она имеет приложения в перечислительной комбинаторике, Шаблон:Iw, теоретической информатике, теории автоматов и лингвистике. Хотя многие приложения являются новыми, классическая иерархия Хомского классов формальных грамматик является, пожалуй, самым известным результатом в этой области.

Файл:Icosahedron.svg
Выпуклый правильный икосаэдр

Комбинаторная геометрия

Ошибка скрипта: Модуля «Основная статья» не существует. Геометрическая комбинаторика связана с выпуклой и дискретной геометрией, в частности с комбинаторикой многогранников. Например, она спрашивает, сколько граней каждого измерения может иметь выпуклый многогранник. Важную роль играют также метрические свойства многогранников, например, теорема Коши о жёсткости выпуклых многогранников. Рассматриваются также особые многогранники, такие как перестановочные многогранники, Шаблон:Iw и многогранники Биркгофа. Комбинаторная геометрия — это старомодное название дискретной геометрии.

Файл:Collier-de-perles-rouge-vert.svg
Пример ожерелья, разделённого на <math>k = 2</math> (то есть между двумя участниками дележа) и <math>t = 2</math> (то есть два типа бусин, имеется 8 красных и 6 зелёных). Показаны 2 разреза — один из участников получает большую секцию, а другой получает оставшиеся два куска.

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

Ошибка скрипта: Модуля «Основная статья» не существует. Топологическая комбинаторика применяет идеи и методы комбинаторики в топологии, при изучении раскрасок графа, справедливого дележа, разбиения, дерева принятия решений, частично упорядоченных множеств, задачи о восстановлении бус и Шаблон:Iw. Её не следует путать с комбинаторной топологией, которая является более старым названием алгебраической топологии.

Арифметическая комбинаторика

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

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

Ошибка скрипта: Модуля «Основная статья» не существует. Шаблон:Не переведено — применение идей и методов комбинаторики к бесконечным (в том числе, несчётным) множествам. Это часть теории множеств, область математической логики, но использует инструменты и идеи как теории множеств, так и экстремальной комбинаторики.

Шаблон:Iw использовал название непрерывной комбинаторики для описания Шаблон:Iw, поскольку существует много аналогий между подсчетом и мерой.

Связанные области

Файл:Kissing-3d.png
Контактное расположение сфер связано как теория кодирования с дискретной геометрией

Комбинаторная оптимизация

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

Теория кодирования

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

Дискретная и вычислительная геометрия

Дискретная геометрия (также называемая комбинаторной геометрией) также началась как часть комбинаторики, с ранними результатами выпуклых многогранников и контактных чисел. С появлением приложений дискретной геометрии в вычислительной геометрии, эти две области частично слились и стали отдельной областью изучения. Остается много связей с геометрической и топологической комбинаторикой, которые сами по себе можно рассматривать как порождения ранней дискретной геометрии.

Комбинаторика и динамические системы

Комбинаторные аспекты динамических систем — это ещё одна развивающаяся область. Здесь динамические системы могут быть определены комбинаторными объектами. См., например, динамическая система графов.

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

Между комбинаторикой и физикой, в частности статистической физикой, усиливается взаимосвязь. Примеры включают точное решение модели Изинга и связь между Шаблон:Iw с одной стороны, и хроматическими многочленами и многочленами Татте, с другой стороны.

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

Комбинаторика (в частности, теория Рамсея) содержит много известных открытых проблем, подчас с весьма несложной формулировкой. Например, неизвестно, при каком наименьшем <math>N</math> в любой группе из <math>N</math> человек найдутся 5 человек, либо попарно знакомых друг с другом, либо попарно незнакомых (хотя известно, что 49 человек достаточно)<ref>Шаблон:MathWorld</ref>.

Также есть и другие нерешённые задачи и недоказанные гипотезы:

  • Гипотеза Адамара (1893): для каждого натурального <math>n</math>, делящегося на 4, существует вещественная матрица Адамара порядка <math>n</math>. Пояснение: известно, что делимость на 4 является лишь необходимым условием существования матрицы Адамара. Существуют различные методы построения вещественных матриц Адамара порядка <math>n=4k</math> для некоторых бесконечных серий натуральных чисел, делящихся на 4, однако они не позволяют доказать гипотезу Адамара. Наименьшим порядком, кратным 4, для которого матрица Адамара неизвестна, является <math>n=668</math><ref>Шаблон:Статья</ref>.
  • Существование конечной проективной плоскости натурального порядка, не являющегося степенью простого числа.
  • Гипотеза Эрдёша — Реньи. Если <math>k</math> — фиксированное целое число <math>k \geqslant 3</math>, то <math>\lim\;\inf(per(A))^{\frac{1}{n}}>1</math> для <math>A</math> из <math>\Lambda_n^k</math>. Здесь <math>per(A)</math> — перманент матрицы <math>A, \Lambda_n^k</math> — множество всех <math>(0,1)</math> — матриц порядка <math>n</math> c <math>k</math> единицами в каждой строке и каждом столбце<ref>Шаблон:Книга</ref>.
  • Числа Рамсея <math>N(q_1,q_2,...,q_t;r)</math> для случая <math>t>2</math> почти не изученыШаблон:Sfn.
  • Задача нахождения минимума перманента дважды стохастической матрицы в общем случае не решенаШаблон:Sfn.
  • Не известны необходимые и достаточные условия, при которых существует общая трансверсаль для трёх семейств подмножеств<ref>Шаблон:Книга</ref>.
  • Задача о числе монотонных булевых функций от <math>n</math> аргументовШаблон:Sfn.

Комбинаторика в языкознании

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

Примечания

Шаблон:Примечания

Литература

Шаблон:Wiktionary

Ссылки

Шаблон:Rq Шаблон:Вс Шаблон:Разделы математики

Источник — https://camokathomelab.servebeer.com/mediawiki/index.php?title=Комбинаторика&oldid=7254