조합 (수학) 편집하기

조합(Combination)은 주어진 집합에서 순서를 고려하지 않고 특정 개수의 원소를 선택하는 방법을 의미한다. 조합은 수학에서 조합론(Combinatorics)의 핵심 개념 중 하나로, 이항 계수(Binomial Coefficient)와 밀접한 관련이 있다.
==개요==
조합은 '''순서를 고려하지 않는 선택'''을 의미하며, 반대로 순서를 고려하는 경우는 '''순열(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
==조합 예제==
예를 들어, 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}
==조합의 성질==
*C(n, 0) = 1 (n개의 원소 중 아무것도 선택하지 않는 경우)
*C(n, n) = 1 (n개의 원소를 모두 선택하는 경우)
*C(n, 1) = n (n개의 원소 중 하나를 선택하는 경우)
*C(n, r) = C(n, n - r) (대칭성)
==파스칼의 삼각형과 조합==
파스칼의 삼각형(Pascal’s Triangle)은 조합의 값과 밀접한 관계가 있으며, 다음과 같은 성질을 만족한다.
*C(n, r) = C(n-1, r-1) + C(n-1, r)
이를 이용하면 조합을 재귀적으로 계산할 수 있다.
{| class="wikitable"
|+파스칼의 삼각형에서 조합 값
|-
!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
|}
==조합과 이항 정리==
이항 정리(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)은 이항 정리에서 각 항의 계수로 등장한다.
==조합의 응용==
조합은 다양한 분야에서 활용된다.
*'''확률과 통계''' - 조합을 이용한 확률 계산 (예: 복권, 카드 게임 확률)
*'''암호학''' - 키 생성 및 비밀번호 조합 계산
*'''그래프 이론''' - 그래프 내 서브셋 찾기
*'''동적 프로그래밍''' - 조합을 활용한 최적화 문제 해결
==같이 보기==
*[[순열]] 
*[[이항 정리]]
*[[파스칼의 삼각형]]
*[[조합론]]
[[분류:수학]]