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

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

Правило суммы. Если элементaможет быть выбранmспособами, а элементb другими kспособами, то выбор одного из этих элементов –aилиbможет быть сделанm+kспособами.

Пример. На конюшне четыре лошади и два пони. Сколько возможностей выбрать себе скакуна? Здесь используем правило суммы: выбираем один элемент из двух множеств (лошадь или пони)способами.

Правило произведения. Если элементaможет быть выбранmспособами, а после этого элементbвыбираетсяkспособами, то выбор пары элементовв заданном порядке может быть произведенспособами.

Пример. Пару лыж можно выбрать шестью способами, пару ботинок – тремя. Сколькими способами можно выбрать лыжи с ботинками? Здесь выбираем пару элементов (лыжи, ботинки) – всего способов.

Правило включения-исключения. Если свойствомSобладаетmэлементов, а свойствомPобладаетkэлементов, то свойствомSилиPобладаетэлементов, гдеl– количество элементов, обладающих одновременно и свойствомS, и свойствомP.

Пример. На полке стоят банки с компотом из яблок и груш. В десяти банках есть яблоки, в шести – груши, в трех – и яблоки, и груши. Сколько всего банок на полке? Здесь, т.е. всего на полкебанок.