Правило умножения (комбинаторика) | это... Что такое Правило умножения (комбинаторика)? (original) (raw)

Правило умножения, иначе называемое правилом «и» — одно из основных правил комбинаторики. Согласно ему, если элемент A можно выбрать n способами и, при любом выборе A (то есть независимо), элемент B можно выбрать m способами, то пару (A, B) можно выбрать n*m способами. Естественным образом обобщается на произвольную длину последовательности.

Ключевые выражения в формулировке, приводящие к правилу умножения: «и то, и другое», «одновременно», «независимо», «каждый из».

Содержание

• 1 Примеры
  • 1.1 Простой
  • 1.2 Количество размещений с повторениями
  • 1.3 Составной

Примеры

Простой

Выбрать книгу и диск из 10 книг и 12 дисков можно способами. Правило сложения

Количество размещений с повторениями

Если есть множество из n типов элементов и нужно на каждое из m мест расположить элемент какого-либо типа (типы элементов могут совпадать на разных местах), то количество вариантов этого будет n m, так как выборы независимы.

Составной

Пусть требуется найти количество слов, составленных не более, чем из 3 букв алфавита {a, b,c, d}. Количество n-буквенных слов равно количеству размещений из 4 букв на n мест с повторениями — оно равно 4_n_. Количество всех слов (так как нужно учитывать любое из слов) будет складываться из количеств одно-, двух- и трёхбуквенных слов. Тогда ответ на первоначальный вопрос будет 41 + 42 + 43 = 84.