조합론(combinatorics)에서, 합의 규칙 또는 덧셈 원칙은 기본 세는 원칙(counting principle)입니다. 간단히 말해서, 만약 우리가 어떤 일을 하는 방법의 A의 숫자와 또 다른 일을 하는 방법의 B의 숫자가 있고 동시에 둘 다 할 수 없으면, 행동 중 하나를 선택하는 A + B 방법이 있다는 직관적인 아이디어입니다.
보다 공식적으로, 합의 규칙은 집합 이론(set theory)에 관한 사실입니다. 그것은 쌍별 서로소 집합(disjoint sets)의 유한 모음의 크기의 합이 이들 집합의 합집합의 크기라고 말합니다. 즉,\(\displaystyle S_{1}, S_{2},..., S_{n}\)가 쌍별 서로소 집합이면, 우리는 다음을 가집니다:
\(\quad\displaystyle |S_{1}|+|S_{2}|+\cdots+|S_{n}| = |S_{1} \cup S_{2} \cup \cdots \cup S_{n}|. \)
Simple example
오늘 한 사람이 마을 북쪽 부분 또는 남쪽 부분에 있는 한 가게에서 쇼핑하기로 결정했습니다. 만약 그들이 마을 북쪽 부분을 방문하면, 그들은 쇼핑몰, 가구점, 보석점 (3 방법)에서 쇼핑할 것입니다. 만약 그들이 도시의 남쪽 부분을 방문하면, 옷가게 또는 신발가게 (2 방법)에서 쇼핑할 것입니다.
따라서 그 사람이 오늘 쇼핑을 마칠 수 있는 3+2=5 가능한 상점이 있습니다.
Inclusion–exclusion principle
포함–제외 원리(inclusion–exclusion principle)는, 역시 체 원리라고 알려져 있으며, 일부 집합의 합집합에서 원소의 숫자를 너무 열거한다는 점에서 합의 규칙의 일반화로 생각될 수 있습니다 (그러나 집합을 서로소인 것으로 요구하지 않습니다). 그것은 \(A_1, ..., A_n\)가 유한 집합이면, 다음임을 말합니다:
\(\quad\displaystyle
\begin{align}
\biggl|\bigcup_{i=1}^n A_i\biggr| & {} =\sum_{i=1}^n\left|A_i\right|
-\sum_{i,j\,:\,1 \le i < j \le n}\left|A_i\cap A_j\right| \\
& {}\qquad +\sum_{i,j,k\,:\,1 \le i < j < k \le 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{align}\)
References
- Leung, K. T.; Cheung, P. H. (1988-04-01). Fundamental Concepts of Mathematics. Hong Kong University Press. ISBN 978-962-209-181-8.
- Penner, R. C. (1999). Discrete Mathematics: Proof Techniques and Mathematical Structures. World Scientific. ISBN 978-981-02-4088-2.
- Biggs, Norman L. (2002). Discrete Mathematics. India: Oxford University Press. pp. 91, 112. ISBN 978-0-19-871369-2.
- "enumerative combinatorics". planetmath.org. 22 March 2013. Archived from the original on 23 July 2014. Retrieved 14 August 2021.
See also
