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

Раздел 4

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

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

Комбинаторика возникла в XVI веке. Первые задачи комбинаторики касались азартных игр – сколькими способами можно получить данное число очков, бросая две или три кости, или сколькими способами можно вытянуть двух королей из карточной колоды и т.д. Подобные вопросы и явились движущей силой развития комбинаторики и теории вероятностей. Яркий свет в комбинаторике оставили Паскаль, Я. Бернулли, Лейбниц, Эйлер и другие математики. В ХХ веке, в связи с созданием ЭВМ и повышением интереса к дискретной математике комбинаторика переживает бурный рост. Комбинаторные задачи возникают в анализе и алгебре, геометрии и топологии, в различных разделах математики и в приложениях.

Из сказанного становится понятным, что комбинаторика имеет дело лишь с натуральными числами. Поэтому, может показаться, что она более «элементарна», чем другие разделы математики. Такое впечатление обманчиво.

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