ОСНОВНЫЕ ПРАВИЛА КОМБИНАТОРИКИ

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

1.Правило птичьих гнезд

Если имеются n + 1 птицы, которых необходимо разместить в n гнездах, то при любом способе размещения хотя бы в одном гнезде окажется не менее двух птиц.

Для обоснования справедливости приведенного правила воспользуемся методом рассуждений от противного. Предположим, что данное правило неверно. Пусть после распределения птиц в каждом гнезде оказалось не более чем по одной птице. Перенумеруем гнёзда, в которые попало по птице натуральными числами 1, . . . , k. Поскольку в гнёзда попало всего k птиц и k £ n, то в гнёздах оказались размещены не все птицы. Из получаемого противоречия следует, что предположение о противном неверно, а, значит, верно правило птичьих гнёзд.

2. Правило умножения.

Пусть необходимо строить все возможные n-элементные последовательности a₁, ... , a_n, для которых выполнены условия:

a) первый элемент таких последовательностей может быть выбран m₁ способами;

b) если i < n, то для каждого способа выбора значений первых i элементов последовательности значение i+1-го элемента таких последовательностей может быть выбрано m_i+1 способами.

Тогда число различных последовательностей a₁, . . . , a_n равно:

m₁m₂ . . . m _n.

Обосновать справедливость правила умножения можно, например, математической индукцией по значению n.