Все формулы РФ

Математика / Графы, логика

Правило произведения в комбинаторике

Формула описывает прием «умножение последовательных шагов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Опубликовано: Обновлено:

Дискретная математикаКомбинаторикаЕсть историческая справкаСтраницы с задачами и решениями

Формула

$$N=m_1m_2\cdots m_k$$

Обозначения

$N$
искомое число вариантов или объектов подсчета, штука
$n$
размер исходного конечного множества или число позиций, штука
$k$
число выбранных элементов, шагов или учитываемых случаев, штука

Условия применения

  • Все объекты должны соответствовать модели «умножение последовательных шагов», без скрытого изменения правил между этапами подсчета.
  • Множества и варианты считаются конечными; порядок, повторения и несовместность случаев определяют до подстановки чисел.
  • Если случаи пересекаются, пересечения нужно явно учесть, иначе одни и те же объекты будут посчитаны несколько раз.

Ограничения

  • Формула «умножение последовательных шагов» не исправляет неверную модель: при другом отношении к порядку или повторениям получится другой ответ.
  • Для бесконечных множеств и зависимых вероятностных моделей прямой конечный подсчет требует отдельного обоснования.
  • При больших параметрах лучше сохранять факториалы и биномиальные коэффициенты до сокращения, чтобы не вносить арифметические ошибки.

Подробное объяснение

Формула «умножение последовательных шагов» переводит словесное условие в точный счет конечных объектов. Ее смысл состоит в выборе модели: считаются случаи, последовательные шаги, группы без порядка, пересечения множеств, рекуррентные члены или пары вершин.

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

При росте параметров ответ может увеличиваться очень быстро: факториалы, биномиальные коэффициенты и рекуррентные последовательности дают заметный скачок даже при небольшом n. Поэтому полезно сначала оценить масштаб и проверить крайние случаи, например k=0, k=n или пустое пересечение.

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

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

Как пользоваться формулой

  1. Определите объекты, которые считает прием «умножение последовательных шагов».
  2. Уточните, важен ли порядок и разрешены ли повторения.
  3. Разбейте условие на случаи, шаги или пересечения.
  4. Подставьте параметры и выполните сокращение выражения.
  5. Проверьте результат малым примером или крайним случаем.

Историческая справка

Элементарная комбинаторика развивалась из счета игр, календарных задач, торговли, переписки и алгебраических разложений. В XVII-XVIII веках Паскаль, Ферма, Якоб Бернулли, Эйлер и другие авторы связали конечный подсчет с вероятностью, биномиальными коэффициентами и алгеброй, хотя многие правила существовали в практическом виде раньше.

Формула «умножение последовательных шагов» в нынешней записи является результатом учебной стандартизации XIX-XX веков. Комбинаторные идеи стали использоваться в алгебре, теории графов, статистике и информатике; закрепились обозначения факториала, мощности множества, биномиального коэффициента и рекуррентной последовательности. Поэтому обычно говорят о традиции, а не о единственном авторе.

Историческая линия формулы

У формулы «умножение последовательных шагов» нет единственного автора в современном учебном смысле. Ее правильнее относить к длительной комбинаторной традиции, где практические задачи счета, алгебраические обозначения и теория конечных множеств постепенно пришли к компактной записи.

Пример

Задача: применить прием «умножение последовательных шагов» к конечному набору вариантов. Дано: имеется 8 различных объектов, нужно выполнить выбор по правилу, соответствующему формуле, и найти число вариантов. Подстановка: сначала определяем, важен ли порядок и есть ли пересечения; затем записываем параметры n=8 и k=3 либо соответствующие мощности множеств. Выполняем вычисление по формуле и получаем числовой ответ. Ответ: количество вариантов равно найденному значению в штуках. Проверка: на маленькой модели с n=3 можно перечислить все варианты вручную и увидеть, что каждый объект подсчета появляется ровно один раз.

Частая ошибка

Для правила произведения опасно считать все шаги одинаковыми, если после выбора меняются ограничения. Например, при выборе без повторений число вариантов убывает, а при выборе с запретом соседства зависит от предыдущего символа. Нельзя заменять произведение суммой только потому, что в условии перечислены этапы. Хорошая проверка - описать один полный объект как цепочку решений и убедиться, что каждый множитель относится к своему шагу.

Практика

Задачи с решением

Посчитать малую модель

Условие. Применить ту же формулу к параметрам 4 и 2.

Решение. Определяем порядок и повторения, затем подставляем малые параметры в формулу.

Ответ. Получается ответ, проверяемый прямым перечислением.

Проверить крайний случай

Условие. Подставить минимальный допустимый параметр.

Решение. Сравниваем результат с очевидным смыслом пустого выбора, одного случая или одной вершины.

Ответ. Формула согласуется с прямым смыслом.

Дополнительные источники

  • Graham R. L., Knuth D. E., Patashnik O. Concrete Mathematics
  • Rosen K. H. Discrete Mathematics and Its Applications
  • van Lint J. H., Wilson R. M. A Course in Combinatorics

Связанные формулы

Математика

Правило суммы в комбинаторике

$N=m_1+m_2+\cdots+m_k$

Формула описывает прием «сложение несовместных случаев» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Число перестановок без повторений

$P_n=n!$

Формула описывает прием «перестановки разных объектов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Число размещений без повторений

$A_n^k=\frac{n!}{(n-k)!}$

Формула описывает прием «упорядоченный выбор» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Число сочетаний без повторений

$C_n^k=\binom nk=\frac{n!}{k!(n-k)!}$

Формула описывает прием «неупорядоченный выбор» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Бином Ньютона для конечной степени

$(a+b)^n=\sum_{k=0}^n\binom nk a^{n-k}b^k$

Формула описывает прием «биномиальное разложение» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.