이항 계수란?
조합의 수학적 표현으로, n개의 원소 중에서 r개의 원소를 선택하는 경우의 수를 의미한다.
2를 상징하는 '이항'이라는 말이 붙은 이뉴는 하나의 아이템에 대해서는 '뽑거나', '안뽑거나' 두 가지의 선택만이 있기 때문이다.
예를들어 5개의 카드에서 3개의 카드를 중복 없이 순서에 상관없이 뽑는 경우의 수를 계산할 때 조합을 사용할 수 있다.
수학에서 이항계수는 이항(두개의 항) 정리에서 계수로 나타나는 양의 정수를 뜻하는데, 보통 n ≥ k ≥ 0의 정수 쌍으로 나타낸다.
계수: 일반적으로 어떤 변수에 곱해진 인자
ax^2 + b: 계수는 a, 변수는 x, 차수는 2, 상수는 b를 의미한다.
이항계수는 위와 같이 나타낼 수 있는데 이는 우리가 아는 아래와 같은 조합 공식을 볼 수 있다.
여기서 (n/r)은 이항 거듭 제곱 (1+x)^n의 다항식 전개에서 x^k 항의 계수로 이 계수는 곱셈 공식으로 계산할 수 있다.
아래는 예시 문제이다.
이항 계수 공식의 성질
기본 정의
이항 계수는 n개의 원소에서 r개를 선택하는 방법의 수를 나타낸다.
- n! = n*(n-1) .... 1 은 팩토리얼
- r! * (n-r)!은 중복을 제거하는 역할을 한다.
재귀적 성질
위 식을 좀 더 같단하게 쓴다면 아래와 같이 쓸 수 있다.
만약 n과 r의 이항계수를 구한다면 이렇게 아래와 같이 나타낼 수 있다.
위 점화식을 흔히 파스칼의 법칙이라 부른다.
알고리즘을 공부하는 사람이면 이 공식은 무조건 외우고 있도록 하자.
앞이 똑같으면 1올려주고 뒤에는 큰거 선택
경계 조건
nC0과 nCn의 값은 무조건 1이다. 따라서 1C1과 2C2도 같은 값이다. 필요에 따라 값들을 바꿔가며 문제를 풀 수 있을 것이다.
간단하게 표현하자면 이렇게 된다.
# 경계조건 과 재귀적 성질을 코드화
public class Main {
public static void main(String[] args) {
System.out.println(Combination(4,3));
}
private static int Combination(int n, int r){
// nCr
//경계 조건
if(n==r || r == 0){
return 1;
}
//재귀적 성질
return Combination(n-1, r-1) + Combination(n-1, r);
}
}