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

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

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

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

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

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

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

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

1. Сколькими способами можно разместить n предметов по m ящикам, чтобы выполнялись заданные ограничения?
2. Сколько существует функций <math>F</math> из m-элементного множества в n-элементное, удовлетворяющих заданным ограничениям?
3. Сколько существует различных перестановок из 52 игральных карт?

   Ответ: 52! (52 факториал), то есть, 80658175170943878571660636856403766975289505440883277824000000000000 или примерно 8,0658 × 10⁶⁷.

4. При игре в кости бросаются две кости, и выпавшие очки складываются; сколько существует комбинаций, в которых сумма очков на верхних гранях равна двенадцати?

   Решение: Каждый возможный исход соответствует функции <math>F: \{1, 2\} \to \{1, 2, 3, 4, 5, 6\}</math> (аргумент функции — это номер кости, значение — очки на верхней грани). Очевидно, что лишь 6+6 даёт нам нужный результат 12. Таким образом, существует лишь одна функция, ставящая в соответствие 1 число 6, и 2 число 6. Или, другими словами, существует всего одна комбинация, при которой сумма очков на верхних гранях равна двенадцати.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

• Комбинаторная оптимизация
• Теория вероятностей

Литература

• Андерсон, Джеймс.  Дискретная математика и комбинаторика = Discrete Mathematics with Combinatorics. — М.: «Вильямс», 2006. — С. 960. — ISBN 0-13-086998-8.
• Виленкин Н. Я.  [ilib.mccme.ru/djvu/combinatorika.htm Популярная комбинаторика]. — М.: Наука, 1975.
• Ерош И. Л.  Дискретная математика. Комбинаторика — СПб.: СПбГУАП, 2001. — 37 c.
• Липский В.  Комбинаторика для программиста. — М.: Мир, 1988. — 213 с.
• Раизер Г. Дж.  Комбинаторная математика. — пер. с англ. — М., 1966.
• Райгородский А. М.  [www.mccme.ru/dubna/2006/notes/raygorodsky.pdf Линейно-алгебраические и вероятностные методы в комбинаторике]. — Летняя школа «Современная математика». — Дубна, 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.

Ссылки

• [www.mathelp.spb.ru/book2/tv3.htm Теория вероятностей. 3. Элементы комбинаторики]
• Белешко Д. [rain.ifmo.ru/cat/view.php/theory/combinations/combinations1-2004 Комбинаторика]. 2004.

Отрывок, характеризующий Комбинаторика

«Le chef de la garienison de Glogau avec dix mille hommes, demande au Roi de Prusse, ce qu'il doit faire s'il est somme de se rendre?… Tout cela est positif.
«Bref, esperant en imposer seulement par notre attitude militaire, il se trouve que nous voila en guerre pour tout de bon, et ce qui plus est, en guerre sur nos frontieres avec et pour le Roi de Prusse . Tout est au grand complet, il ne nous manque qu'une petite chose, c'est le general en chef. Comme il s'est trouve que les succes d'Austerlitz aurant pu etre plus decisifs si le general en chef eut ete moins jeune, on fait la revue des octogenaires et entre Prosorofsky et Kamensky, on donne la preference au derienier. Le general nous arrive en kibik a la maniere Souvoroff, et est accueilli avec des acclamations de joie et de triomphe.
«Le 4 arrive le premier courrier de Petersbourg. On apporte les malles dans le cabinet du Marieechal, qui aime a faire tout par lui meme. On m'appelle pour aider a faire le triage des lettres et prendre celles qui nous sont destinees. Le Marieechal nous regarde faire et attend les paquets qui lui sont adresses. Nous cherchons – il n'y en a point. Le Marieechal devient impatient, se met lui meme a la besogne et trouve des lettres de l'Empereur pour le comte T., pour le prince V. et autres. Alors le voila qui se met dans une de ses coleres bleues. Il jette feu et flamme contre tout le monde, s'empare des lettres, les decachete et lit celles de l'Empereur adressees a d'autres. А, так со мною поступают! Мне доверия нет! А, за мной следить велено, хорошо же; подите вон! Et il ecrit le fameux ordre du jour au general Benigsen
«Я ранен, верхом ездить не могу, следственно и командовать армией. Вы кор д'арме ваш привели разбитый в Пултуск: тут оно открыто, и без дров, и без фуража, потому пособить надо, и я так как вчера сами отнеслись к графу Буксгевдену, думать должно о ретираде к нашей границе, что и выполнить сегодня.
«От всех моих поездок, ecrit il a l'Empereur, получил ссадину от седла, которая сверх прежних перевозок моих совсем мне мешает ездить верхом и командовать такой обширной армией, а потому я командованье оной сложил на старшего по мне генерала, графа Буксгевдена, отослав к нему всё дежурство и всё принадлежащее к оному, советовав им, если хлеба не будет, ретироваться ближе во внутренность Пруссии, потому что оставалось хлеба только на один день, а у иных полков ничего, как о том дивизионные командиры Остерман и Седморецкий объявили, а у мужиков всё съедено; я и сам, пока вылечусь, остаюсь в гошпитале в Остроленке. О числе которого ведомость всеподданнейше подношу, донеся, что если армия простоит в нынешнем биваке еще пятнадцать дней, то весной ни одного здорового не останется.
«Увольте старика в деревню, который и так обесславлен остается, что не смог выполнить великого и славного жребия, к которому был избран. Всемилостивейшего дозволения вашего о том ожидать буду здесь при гошпитале, дабы не играть роль писарскую , а не командирскую при войске. Отлучение меня от армии ни малейшего разглашения не произведет, что ослепший отъехал от армии. Таковых, как я – в России тысячи».
«Le Marieechal se fache contre l'Empereur et nous punit tous; n'est ce pas que с'est logique!
«Voila le premier acte. Aux suivants l'interet et le ridicule montent comme de raison. Apres le depart du Marieechal il se trouve que nous sommes en vue de l'ennemi, et qu'il faut livrer bataille. Boukshevden est general en chef par droit d'anciennete, mais le general Benigsen n'est pas de cet avis; d'autant plus qu'il est lui, avec son corps en vue de l'ennemi, et qu'il veut profiter de l'occasion d'une bataille „aus eigener Hand“ comme disent les Allemands. Il la donne. C'est la bataille de Poultousk qui est sensee etre une grande victoire, mais qui a mon avis ne l'est pas du tout. Nous autres pekins avons, comme vous savez, une tres vilaine habitude de decider du gain ou de la perte d'une bataille. Celui qui s'est retire apres la bataille, l'a perdu, voila ce que nous disons, et a ce titre nous avons perdu la bataille de Poultousk. Bref, nous nous retirons apres la bataille, mais nous envoyons un courrier a Petersbourg, qui porte les nouvelles d'une victoire, et le general ne cede pas le commandement en chef a Boukshevden, esperant recevoir de Petersbourg en reconnaissance de sa victoire le titre de general en chef. Pendant cet interregne, nous commencons un plan de man?uvres excessivement interessant et original. Notre but ne consiste pas, comme il devrait l'etre, a eviter ou a attaquer l'ennemi; mais uniquement a eviter le general Boukshevden, qui par droit d'ancnnete serait notre chef. Nous poursuivons ce but avec tant d'energie, que meme en passant une riviere qui n'est рas gueable, nous brulons les ponts pour nous separer de notre ennemi, qui pour le moment, n'est pas Bonaparte, mais Boukshevden. Le general Boukshevden a manque etre attaque et pris par des forces ennemies superieures a cause d'une de nos belles man?uvres qui nous sauvait de lui. Boukshevden nous poursuit – nous filons. A peine passe t il de notre cote de la riviere, que nous repassons de l'autre. A la fin notre ennemi Boukshevden nous attrappe et s'attaque a nous. Les deux generaux se fachent. Il y a meme une provocation en duel de la part de Boukshevden et une attaque d'epilepsie de la part de Benigsen. Mais au moment critique le courrier, qui porte la nouvelle de notre victoire de Poultousk, nous apporte de Petersbourg notre nomination de general en chef, et le premier ennemi Boukshevden est enfonce: nous pouvons penser au second, a Bonaparte. Mais ne voila t il pas qu'a ce moment se leve devant nous un troisieme ennemi, c'est le православное qui demande a grands cris du pain, de la viande, des souchary, du foin, – que sais je! Les magasins sont vides, les сhemins impraticables. Le православное se met a la Marieaude, et d'une maniere dont la derieniere campagne ne peut vous donner la moindre idee. La moitie des regiments forme des troupes libres, qui parcourent la contree en mettant tout a feu et a sang. Les habitants sont ruines de fond en comble, les hopitaux regorgent de malades, et la disette est partout. Deux fois le quartier general a ete attaque par des troupes de Marieaudeurs et le general en chef a ete oblige lui meme de demander un bataillon pour les chasser. Dans une de ces attaques on m'a еmporte ma malle vide et ma robe de chambre. L'Empereur veut donner le droit a tous les chefs de divisions de fusiller les Marieaudeurs, mais je crains fort que cela n'oblige une moitie de l'armee de fusiller l'autre.
[Со времени наших блестящих успехов в Аустерлице, вы знаете, мой милый князь, что я не покидаю более главных квартир. Решительно я вошел во вкус войны, и тем очень доволен; то, что я видел эти три месяца – невероятно.
«Я начинаю аb ovo. Враг рода человеческого , вам известный, аттакует пруссаков. Пруссаки – наши верные союзники, которые нас обманули только три раза в три года. Мы заступаемся за них. Но оказывается, что враг рода человеческого не обращает никакого внимания на наши прелестные речи, и с своей неучтивой и дикой манерой бросается на пруссаков, не давая им времени кончить их начатый парад, вдребезги разбивает их и поселяется в потсдамском дворце.
«Я очень желаю, пишет прусской король Бонапарту, чтобы ваше величество были приняты в моем дворце самым приятнейшим для вас образом, и я с особенной заботливостью сделал для того все нужные распоряжения на сколько позволили обстоятельства. Весьма желаю, чтоб я достигнул цели». Прусские генералы щеголяют учтивостью перед французами и сдаются по первому требованию. Начальник гарнизона Глогау, с десятью тысячами, спрашивает у прусского короля, что ему делать, если ему придется сдаваться. Всё это положительно верно. Словом, мы думали внушить им страх только положением наших военных сил, но кончается тем, что мы вовлечены в войну, на нашей же границе и, главное, за прусского короля и заодно с ним. Всего у нас в избытке, недостает только маленькой штучки, а именно – главнокомандующего. Так как оказалось, что успехи Аустерлица могли бы быть положительнее, если б главнокомандующий был бы не так молод, то делается обзор осьмидесятилетних генералов, и между Прозоровским и Каменским выбирают последнего. Генерал приезжает к нам в кибитке по Суворовски, и его принимают с радостными и торжественными восклицаниями.
4 го приезжает первый курьер из Петербурга. Приносят чемоданы в кабинет фельдмаршала, который любит всё делать сам. Меня зовут, чтобы помочь разобрать письма и взять те, которые назначены нам. Фельдмаршал, предоставляя нам это занятие, ждет конвертов, адресованных ему. Мы ищем – но их не оказывается. Фельдмаршал начинает волноваться, сам принимается за работу и находит письма от государя к графу Т., князю В. и другим. Он приходит в сильнейший гнев, выходит из себя, берет письма, распечатывает их и читает письма Императора, адресованные другим… Затем пишет знаменитый суточный приказ генералу Бенигсену.
Фельдмаршал сердится на государя, и наказывает всех нас: неправда ли это логично!
Вот первое действие. При следующих интерес и забавность возрастают, само собой разумеется. После отъезда фельдмаршала оказывается, что мы в виду неприятеля, и необходимо дать сражение. Буксгевден, главнокомандующий по старшинству, но генерал Бенигсен совсем не того же мнения, тем более, что он с своим корпусом находится в виду неприятеля, и хочет воспользоваться случаем дать сражение самостоятельно. Он его и дает.
Это пултуская битва, которая считается великой победой, но которая совсем не такова, по моему мнению. Мы штатские имеем, как вы знаете, очень дурную привычку решать вопрос о выигрыше или проигрыше сражения. Тот, кто отступил после сражения, тот проиграл его, вот что мы говорим, и судя по этому мы проиграли пултуское сражение. Одним словом, мы отступаем после битвы, но посылаем курьера в Петербург с известием о победе, и генерал Бенигсен не уступает начальствования над армией генералу Буксгевдену, надеясь получить из Петербурга в благодарность за свою победу звание главнокомандующего. Во время этого междуцарствия, мы начинаем очень оригинальный и интересный ряд маневров. План наш не состоит более, как бы он должен был состоять, в том, чтобы избегать или атаковать неприятеля, но только в том, чтобы избегать генерала Буксгевдена, который по праву старшинства должен бы был быть нашим начальником. Мы преследуем эту цель с такой энергией, что даже переходя реку, на которой нет бродов, мы сжигаем мост, с целью отдалить от себя нашего врага, который в настоящее время не Бонапарт, но Буксгевден. Генерал Буксгевден чуть чуть не был атакован и взят превосходными неприятельскими силами, вследствие одного из таких маневров, спасавших нас от него. Буксгевден нас преследует – мы бежим. Только что он перейдет на нашу сторону реки, мы переходим на другую. Наконец враг наш Буксгевден ловит нас и атакует. Оба генерала сердятся и дело доходит до вызова на дуэль со стороны Буксгевдена и припадка падучей болезни со стороны Бенигсена. Но в самую критическую минуту курьер, который возил в Петербург известие о пултуской победе, возвращается и привозит нам назначение главнокомандующего, и первый враг – Буксгевден побежден. Мы теперь можем думать о втором враге – Бонапарте. Но оказывается, что в эту самую минуту возникает перед нами третий враг – православное , которое громкими возгласами требует хлеба, говядины, сухарей, сена, овса, – и мало ли чего еще! Магазины пусты, дороги непроходимы. Православное начинает грабить, и грабёж доходит до такой степени, о которой последняя кампания не могла вам дать ни малейшего понятия. Половина полков образуют вольные команды, которые обходят страну и все предают мечу и пламени. Жители разорены совершенно, больницы завалены больными, и везде голод. Два раза мародеры нападали даже на главную квартиру, и главнокомандующий принужден был взять баталион солдат, чтобы прогнать их. В одно из этих нападений у меня унесли мой пустой чемодан и халат. Государь хочет дать право всем начальникам дивизии расстреливать мародеров, но я очень боюсь, чтобы это не заставило одну половину войска расстрелять другую.]