Глава 5. Основы комбинаторики

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

Мы разделяем задачи пересчета, перечисления и оптимизации. Если нас интересует, сколько элементов, принадлежащих конечному множеству, обладает неким свойством (набором свойств),

то это задача пересчета.

Если необходимо выделить все элементы множества, обладающие заданным свойством, то это – задача перечисления.

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

При решении указанных задач используются следующие поня-

тия [4.1].

Подмножество из m элементов на множестве Х, состоящем из n элементов, называется (n, m) выборкой, где m – объем этой выборки.

Если (n, m) выборка рассматривается с учетом порядка элементов в них, то она называется (n, m)-размещением и обозначается

Anm от слова arrengment. Если m = n, то такое (n, n)-размещение называется собственно Pn перестановкой.

Если порядок элементов в выборке (n, m) не имеет значения, то она называется (n, m)-сочетанием и обозначается Cnm (от слова

combination).

И перестановки, и сочетания могут быть с повторениями и без повторений.

Рассмотрим множество X={a, b, c}.Тогда все упорядоченные и неупорядоченные выборки объемом 2 выглядят следующим образом:

1) размещения с повторениями {aa, ab, ac, ba, bb, bc, ca, cb, cc},

Anm = 9 ;