Элементы комбинаторики

Комбинаторика – ветвь математики, изучающая комбинации и перестановки предметов, – возникла в XVII в. Долгое время казалось, что комбинаторика лежит вне основного русла развития математики и ее приложений. Положение изменилось после появления вычислительных машин и связанного с этим расцвета конечной математики. Сейчас комбинаторные методы применяются в теории случайных процессов, статистике, математическом программировании, вычислительной математике, биологии, планировании экспериментов, расшифровке кодов ДНК и т.д.

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

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

Первое упоминание о вопросах, близких к комбинаторным, встречается в китайских рукописях XII–XIII вв. до н.э. В Древнем Китае увлеклись составлением магических квадратов, в которых заданные числа располагали так, что сумма по всем горизонталям, вертикалям и диагоналям была одной и той же.

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

Работы Паскаля и Ферма в XVII в. ознаменовали рождение двух ветвей математической науки – комбинаторики и теории вероятностей – они сформировали и доказали первые теоремы данных наук.

Первым рассматривал комбинаторику как самостоятельную ветвь науки немецкий математик Г. Лейбниц, опубликовавший в 1666 г. работу «Об искусстве комбинаторики», в которой впервые появился термин «комбинаторный». Замечательные достижения в области комбинаторики принадлежат Л. Эйлеру. Комбинаторными задачами интересовались и математики, занимавшиеся составлением и разгадыванием шифров, изучением древних письменностей.

По мере развития комбинаторики выяснилось, что, несмотря на внешнее различие изучаемых ею вопросов, многие из них имеют одно и то же математическое содержание и сводятся к задачам о конечных множествах и подмножествах. С ее помощью можно подсчитать число решений различных комбинаторных задач. В основе этой теории лежат «правило суммы» и «правило произведения», о которых мы будем говорить позже. Часто приходится считать число последовательностей длины m, составленных из элементов некоторого множества А, состоящего из n элементов. Целый ряд задач возникает при разбиении множества на части: найти число разбиений, если число частей равно k; найти, сколькими способами можно число n записать в виде суммы k слагаемых и пр. В решении комбинаторных задач часто используются графические методы, графы. Иногда при решении комбинаторных проблем нужно лишь доказать, что данная проблема имеет решение, или убедиться в его отсутствии.