Глава 3. Структуры на множестве. Комбинаторика

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

Комбинаторика – это раздел математики, в котором для конечных множеств рассматриваются различные соединения элементов: перестановки, размещения, сочетания. В задачах, связанных с выборкой элементов множества, необходимо подсчитать количество различных комбинаций этих элементов. С теоретико-множественной точки зрения решение комбинаторных задач связано с выбором из некоторого множества подмножеств, обладающих определенными свойствами, и упорядочением множеств. Комбинаторика возникла в ХVI веке. В ней рассматривались задачи, связанные в основном с азартными играми. В процессе изучения таких задач были выработаны некоторые общие подходы к их решению, получены формулы для подсчёта числа различных комбинаций.

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

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