Правило суммы - Rule of sum

В комбинаторика, то правило суммы или принцип сложения является основным принцип подсчета. Проще говоря, идея заключается в том, что если у нас есть А способы что-то делать и B способов сделать что-то еще, и мы не можем делать и то, и другое одновременно, тогда есть А + B способы выбрать одно из действий.

Более формально правило суммы - это факт о теория множеств. Он утверждает, что сумма размеров конечного набора попарно непересекающиеся множества размер объединения этих множеств. То есть, если ${\displaystyle S_{1},S_{2},...,S_{n}}$ являются попарно непересекающимися множествами, то имеем:

${\displaystyle |S_{1}|+|S_{2}|+\cdots +|S_{n}|=|S_{1}\cup S_{2}\cup \cdots \cup S_{n}|}$

Простой пример

Сегодня женщина решила делать покупки в одном магазине, либо в северной, либо в южной части города. Если она посетит северную часть города, она сделает покупки в торговом центре, мебельном магазине или ювелирном магазине (3 способа). Если она посетит южную часть города, она сделает покупки либо в магазине одежды, либо в магазине обуви (2 способа).

Таким образом, существует 3 + 2 = 5 возможных магазинов, в которых женщина могла бы сделать покупки сегодня.

Принцип включения-исключения

Основная статья: Принцип включения-исключения

Принцип включения-исключения можно рассматривать как обобщение правила суммы, поскольку он также перечисляет количество элементов в объединении некоторых множеств (но не требует, чтобы множества были непересекающимися). В нем говорится, что если А₁, ..., А_п конечные множества, то

${\displaystyle {\begin{aligned}{\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}&{}=\sum _{i=1}^{n}\left|A_{i}\right|-\sum _{i,j\,:\,1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|\\&{}\qquad +\sum _{i,j,k\,:\,1\leq i<j<k\leq n}\left|A_{i}\cap A_{j}\cap A_{k}\right|-\ \cdots \ +\left(-1\right)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.\end{aligned}}}$

Смотрите также

• Комбинаторный принцип
• Правило продукта
• Принцип включения-исключения