이항 계수(Binomial Coefficient)란?
이항 계수는 이항정리에서 등장하는 개념으로, 파스칼의 삼각형 형태로 배열할 수 있습니다. n개의 원소 중 r개를 선택하는 조합의 수를 의미하며, 다음 공식으로 표현됩니다.
nCr = n! / (r! × (n-r)!)
또는
nCr = n(n-1)(n-2)...(n-r+1) / r!
이항 계수 제곱의 합
이번 글에서 구하고자 하는 값은 각 이항 계수를 제곱한 뒤 모두 더한 값입니다.
(nC0)2 + (nC1)2 + (nC2)2 + ... + (nCn-1)2 + (nCn)2
입력 : n = 5
출력 : 252
동작 원리
이 프로그램은 먼저 n개 중 r개를 선택하는 각 이항 계수를 구합니다. 그다음 각 계수를 제곱하여 모두 더하면 최종 결과를 얻을 수 있습니다. 팩토리얼 함수를 활용해 주어진 n과 r에 대한 이항 계수를 계산하고, 반복문 안에서 제곱 값을 누적하는 방식으로 구현합니다.
참고로 수학적으로는 반데르몬드 항등식(Vandermonde's Identity)에 의해 이 합이 (2n)C(n), 즉 2n개 중 n개를 선택하는 조합의 수와 같다는 것이 알려져 있습니다. 실제로 n=5일 때 10C5 = 252이므로 위 결과와 일치합니다.
예제 코드
#include <iostream>
using namespace std;
int fact(int n){
int fact = 1, i;
for (i = 2; i <= n; i++){
fact *= i;
}
return fact;
}
int main(){
int n = 5;
int sum = 0;
int temp = 0;
for (int r = 0; r <= n; r++){
temp = fact(n) / (fact(r) * fact(n - r));
sum += (temp * temp);
}
cout << sum;
return 0;
}
실행 결과
252
마무리
이 코드는 팩토리얼 기반으로 직관적으로 동작하지만, n이 커지면 오버플로가 발생하기 쉽습니다. 큰 수를 다룰 때는 파스칼의 삼각형을 이용한 동적 계획법(DP)이나 반데르몬드 항등식을 활용하면 더 효율적으로 계산할 수 있습니다.