Глава 2. Комбинаторика

Распространенными задачами комбинаторики являются задачи о числе размещений, перестановок, сочетаний. При подсчете числа различных комбинаций используются следующие правила.

Правило суммы. Если объект может быть выбран m способами, а объект В другими n способами, то выбор "либо , либо " может быть осуществлен способами.

Правило умножения. Если объект может быть выбран m способами и после каждого из таких выборов объект в свою очередь может быть выбран n способами, то выбор и в указанном порядке может быть осуществлен mn способами.

Набор элементов из множества называется выборкой объема r из n элементов. Выборка называется упорядоченной, если порядок следования элементов в ней задан. Упорядоченные выборки, различающиеся лишь порядком следования элементов, считаются различными.