조합과 순열
이항 계수
이항 계수란 조합의 개수를 나타내는 수학적 개념이다.
즉, n개의 원소 중에서 r개의 원소를 선택하는 경우의 수를 의미한다. 이를 수식으로 표현하면
n / r = n! / r!(n-r)!으로 표현할 수 있으며, nCr 연산이라고도 부른다.
- nCr 자바 코드
public static long ncr(int n, int r) {
if (r > n) return 0;
if (r == 0 || r == n) return 1;
r = Math.min(r, n - r);
long result = 1;
for (int i = 0; i < r; i++) {
result *= (n - i);
result /= (i + 1);
}
return result;
}- 이항 계수의 합 : 2^n
- 자기 자신을 포함하는 조합의 합 : 2^(n-1)
예를 들어서, {1, 2, 3, 4}라는 원소가 있을 때, 이 중에서 1을 포함하는 모든 조합은 {2, 3, 4} 부분 집합의 개수에 1을 더한 것과 같다. 즉, 2^3 = 8개의 부분 집합이 있고 이 모든 부분집합에 1이 들어가면 1이 포함된 부분집합이 되는 것이다.
공집합, 2, 3, 4, 23, 24, 34, 234 // 여기에 1을 추가하면 1이 포함된 부분집합이 된다.