Принцип сложения

5+0=5 показано набором точек.

В комбинаторике принцип сложения или правило суммы Это основной принцип подсчета . Проще говоря, это интуитивная идея, что если у нас есть несколько способов сделать что-то и B — способов сделать другое, и мы не можем делать и то, и другое одновременно, то есть $A+B$ способы выбора одного из действий. Говоря математическим языком, принцип сложения гласит, что для непересекающихся множеств A и B мы имеем $|A\cup B|=|A|+|B|$, при условии, что пересечение множеств без каких-либо элементов.

Правило суммы — это факт теории множеств . как видно из ранее упомянутого уравнения для объединения непересекающихся множеств A и B, равного |A| + |Б|.

Принцип сложения можно распространить на несколько наборов. Если $S_{1},S_{2},\ldots ,S_{n}$ являются попарно непересекающимися множествами, то имеем: $$|S_{1}|+|S_{2}|+\cdots +|S_{n}|=|S_{1}\cup S_{2}\cup \cdots \cup S_{n}|.$$Это утверждение можно доказать на основе принципа сложения индукцией по n .

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

3+2=5 показано фигурами.

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

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

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

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

Серия диаграмм Венна , иллюстрирующая принцип включения-исключения.

Принцип включения-исключения (также известный как принцип решета) . ) можно рассматривать как обобщение правила суммы, поскольку оно также перечисляет количество элементов в объединении некоторых множеств (но не требует, чтобы множества не пересекались). Он утверждает, что если A ₁ , ..., An _то конечные множества, $$\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{i=1}^{n}\left|A_{i}\right|-\sum _{i,j\,:\,1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|+\sum _{i,j,k\,:\,1\leq i<j<k\leq n}\left|A_{i}\cap A_{j}\cap A_{k}\right|-\ \cdots \ +(-1)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.$$

Принцип вычитания

Аналогично, для данного конечного множества S и другого множества A, если $A\subset S$, затем $|A^{c}|=|S|-|A|$. Чтобы доказать это, заметим, что $|A^{c}|+|A|=|S|$ по принципу сложения.

Приложения

Принцип сложения можно использовать для комбинаторного доказательства правила Паскаля . Чтобы рассчитать ${\binom {n+1}{k}}$, можно рассматривать как количество способов выбрать k человек из комнаты, в которой находятся n детей и 1 учитель. Тогда есть ${\binom {n}{k}}$ способы выбирать людей, не выбирая учителя, и ${\binom {n}{k-1}}$ способы выбора людей, включая учителя. Таким образом ${\binom {n+1}{k}}={\binom {n}{k}}+{\binom {n}{k-1}}$.

Принцип сложения также можно использовать для доказательства принципа умножения .

Ссылки

Библиография

• Биггс, Норман Л. (2002). Дискретная математика . Индия: Издательство Оксфордского университета . ISBN  978-0-19-871369-2 .

См. также

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