Основные правила комбинаторики.

Термин «комбинаторика» был введен Лейбницем («Рассуждения о комбинаторном искусстве», 1666 год). Основные задачи комбинаторики:

a) Перечислительной задача. найти число комбинаторных конфигураций с заданными свойствами.

b) Существует ли комбинаторная конфигурация с (очень сложными) заданными свойствами?

c) Алгоритмическая задача. Найти метод генерации комбинаторных конфигураций с заданными свойствами.

d) Оптимизационная задача. Найти комбинаторную конфигурацию с экстремальным значением некоторого параметра.

В теории множеств доказываются следующие правила о числе элементов множеств:

(I) Правило суммы. .

(II) Правило произведения. .

Формулировка правила суммы на языке комбинаторики:

(I) Если объект можно выбрать способами и объект можно выбрать способами, причем, ни один из выборов не совпадает ни с каким выбором , то выбор «или » можно осуществить способами.

Формулировка правила произведения на языке комбинаторики:

(II) Если объект X можно выбрать m способами и объект Y можно выбрать способами, то упорядоченную пару (X,Y) можно выбрать mn способами.

Операции объединения, пересечения и декартового произведения двух множеств могут быть обобщены на множеств , , …, .

Объединение множеств , , …, содержит те, и только те, элементы, которые принадлежат хотя бы одному из множеств A₁,…,A_n:

.

Пересечение множеств , , …, содержит те, и только те, элементы, которые принадлежат одновременно каждому из множеств A₁,…,A_n:

.

Декартово произведение n множеств , , содержит последовательности из n элементов, i-й элемент которой принадлежит множеству :

.

Правило суммы может быть обобщено: если множества попарно не пересекаются, то

.

Правило произведения может быть обобщено:

.