합 규칙 (조합론)

정의
합 규칙은 조합론에서 사용되는 기본적인 원리 중 하나로, 서로 겹치지 않는(교집합이 빈) 두 사건이나 경우의 수를 합산하여 전체 경우의 수를 구하는 방법을 의미한다. 공식적으로는 다음과 같이 표현한다.

$$ |A \cup B| = |A| + |B|\quad (A \cap B = \varnothing) $$

여기서 $A$와 $B$는 각각 경우의 집합을 나타내며, $|X|$는 집합 $X$의 원소 개수를 의미한다. 이 원리는 두 집합뿐만 아니라 유한 개의 서로 겹치지 않는 집합에 대해 일반화될 수 있다.

$$ \Bigl|\bigcup_{i=1}^{n} A_i\Bigr| = \sum_{i=1}^{n} |A_i|\quad \bigl(A_i \cap A_j = \varnothing ; (i eq j)\bigr) $$

용도와 적용 예시

1. 단순 선택 문제

   • 예: 빨간 공 3개와 파란 공 2개가 들어 있는 주머니에서 하나의 공을 뽑는 경우의 수는 $3 + 2 = 5$가지이다.

2. 분할된 경우의 수 합산

   • 예: 길이가 4인 문자열을 만들 때, 첫 글자가 ‘A’인 경우와 ‘B’인 경우는 서로 겹치지 않으므로 전체 경우의 수는 두 경우의 수를 더한 값이 된다.

3. 문제 해결 전략

   • 복잡한 경우를 상호 배제되는 여러 하위 문제로 나누어 각각의 경우의 수를 구한 뒤, 이를 모두 더함으로써 전체 경우의 수를 구한다.

관련 원리

• 곱 규칙(곱의 법칙, 곱 원리)
  합 규칙과 대비되는 원리로, 독립적인 선택을 순차적으로 수행할 때 경우의 수를 곱하는 방법이다.
• 포함-배제 원리
  서로 겹치는 경우가 존재할 때, 단순히 합 규칙만 적용하면 중복 계산이 발생한다. 이때 포함-배제 원리를 사용해 중복을 조정한다.

어원 및 용어 설명

• 합(和): ‘더한다’는 의미의 한자어로, 경우의 수를 더한다는 의미에서 차용되었다.
• 규칙(規則): 일정한 방법이나 원칙을 의미한다.
• 영어권에서는 “Addition Principle”, “Sum Rule” 등으로 번역된다. 이러한 명칭은 경우의 집합을 “덧셈” 연산으로 결합한다는 점에서 유래한다.

사용 맥락

• 교과서·강의·수학 논문 등에서 기본적인 경우의 수 계산을 설명할 때 빈번히 등장한다.
• 알고리즘 설계·복잡도 분석·통계학 등 다양한 분야에서 경우의 수를 직접 구하거나 추정할 때 기본 전제가 된다.

참고

• 조합론 및 확률론 교과서 전반에 걸쳐 소개되는 표준 원리이며, 별도 특수한 정의가 요구되지 않는 한 일반적인 수학 교육 과정에서 다루어진다.