조합 (수학)

조합(Combination)은 주어진 집합에서 순서를 고려하지 않고 특정 개수의 원소를 선택하는 방법을 의미한다. 조합은 수학에서 조합론(Combinatorics)의 핵심 개념 중 하나로, 이항 계수(Binomial Coefficient)와 밀접한 관련이 있다.

1 개요

조합은 순서를 고려하지 않는 선택을 의미하며, 반대로 순서를 고려하는 경우는 순열(Permutation)이라고 한다. 조합의 개수를 구하는 공식은 다음과 같다.

• 조합 공식
  • n개 중 r개를 선택하는 경우의 수:
  • C(n, r) = nCr = n! / (r!(n - r)!)

여기서,

• n! = n × (n-1) × ... × 1 (계승, Factorial)
• r! = r × (r-1) × ... × 1
• (n - r)! = (n - r) × (n - r - 1) × ... × 1

2 조합 예제

예를 들어, 5개의 원소 {A, B, C, D, E} 중 3개를 선택하는 조합을 구하면:

C(5, 3) = 5! / (3!(5-3)!) = (5 × 4 × 3!) / (3! × 2 × 1) = 10

가능한 조합은:

• {A, B, C}
• {A, B, D}
• {A, B, E}
• {A, C, D}
• {A, C, E}
• {A, D, E}
• {B, C, D}
• {B, C, E}
• {B, D, E}
• {C, D, E}

3 조합의 성질

• C(n, 0) = 1 (n개의 원소 중 아무것도 선택하지 않는 경우)
• C(n, n) = 1 (n개의 원소를 모두 선택하는 경우)
• C(n, 1) = n (n개의 원소 중 하나를 선택하는 경우)
• C(n, r) = C(n, n - r) (대칭성)

4 파스칼의 삼각형과 조합

파스칼의 삼각형(Pascal’s Triangle)은 조합의 값과 밀접한 관계가 있으며, 다음과 같은 성질을 만족한다.

• C(n, r) = C(n-1, r-1) + C(n-1, r)

이를 이용하면 조합을 재귀적으로 계산할 수 있다.

파스칼의 삼각형에서 조합 값

n	r=0	r=1	r=2	r=3	r=4	r=5
0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1

5 조합과 이항 정리

이항 정리(Binomial Theorem)에 따르면, 조합은 다항식 전개와 관련이 있다.

• (a + b)ⁿ = Σ C(n, r) a^(n-r) b^r

예를 들어, (a + b)³을 전개하면:

• (a + b)³ = C(3, 0)a³b⁰ + C(3, 1)a²b¹ + C(3, 2)a¹b² + C(3, 3)a⁰b³
• = 1a³ + 3a²b + 3ab² + 1b³

이항 계수 C(n, r)은 이항 정리에서 각 항의 계수로 등장한다.

6 조합의 응용

조합은 다양한 분야에서 활용된다.

• 확률과 통계 - 조합을 이용한 확률 계산 (예: 복권, 카드 게임 확률)
• 암호학 - 키 생성 및 비밀번호 조합 계산
• 그래프 이론 - 그래프 내 서브셋 찾기
• 동적 프로그래밍 - 조합을 활용한 최적화 문제 해결

7 같이 보기

• 순열
• 이항 정리
• 파스칼의 삼각형
• 조합론