Правило умножения (правило «и») — одно из основных правил комбинаторики. Согласно ему, если элемент A можно выбрать n способами, и при любом выборе A элемент B можно выбрать m способами, то пару (A, B) можно выбрать n·m способами. Естественным образом обобщается на произвольную длину последовательности.
Содержание |
Выбрать книгу и диск из 10 книг и 12 дисков можно способами.
Если есть множество из n типов элементов, и нужно на каждом из m мест расположить элемент какого-либо типа (типы элементов могут совпадать на разных местах), то количество вариантов этого будет nm.
Пусть требуется найти количество слов, составленных не более, чем из 3 букв алфавита {a, b, c, d}. Количество n-буквенных слов равно количеству размещений из 4 букв на n мест с повторениями — оно равно . Количество всех слов (так как нужно учитывать любое из слов) будет складываться из количеств одно-, двух- и трёхбуквенных слов. Тогда ответ на первоначальный вопрос будет .
Правило умножения.