Комбинаторные формулы и правила

При рещении задач комбинаторики используют следующие правила.

Правило суммы. Если некоторый объект А может быть выбран из

множества объектов m способами, а другой объект В может быть выбран

n способами, то выбрать либо А, либо В можно m + n способами.

Правило произведения. Если объект А можно выбрать из множества

объектов m способами и после каждого такого выбора объект В можно

выбрать n способами, то пара объектов (А, В) в указанном порядке может

быть выбрана m· n способами.

Замечание. Набор (множество) элементов, для которых важен порядок следования, называется упорядоченным.

Правило (Принцип) Дирихле. Если вы хотите распределить n объектов по m (условным) ящикам, причем m строго меньше, m<n, то найдется по крайней мере один ящик, в котором будет находиться больше одно объекта

Замечание. Иногда можно встретить этот принцип под названием «принцип голубей» (рассаживание голубей по клеткам, в переводной литературе) или принцип кроликов (рассаживание кроликов по ящикам, в отечественной)

Определение. Множество (набор элементов) называется упорядоченным, если в нем важен порядок следования элементов. В противном случае множество называется неупорядоченным. Примером упорядоченных множеств могут служить номера телефонов, порядок лекций в расписании. Неупорядоченных –