Binomial coefficient

이항 계수(Binomial coefficient)는 n 개 에서 k 개를 고르는 (순서 없는)조합의 가짓수입니다. 이는 nCk 로 보통 표현하며 

이항 다항식 $${\displaystyle x+y} 의 거듭제곱 $${\displaystyle (x+y)^{n}}에 대해서, 전개한 각 항 $${\displaystyle x^{k}y^{n-k}}의 계수이기도 합니다.

 

 

그리고 위와 같이 점화식으로 표현할 수 있습니다.

따라서 이항 계수는 아래와 같은 방법으로 구할 수 있습니다. 

const int MAX = 1000;
 
//memset(cache, -1, sizeof(cache))
int cache[MAX][MAX];
 
int getBinomialCoefficient(int n, int k)
{
    ///모든 원소를 다 고르는 경우 또는 고를 원소가 없는 경우
    if (n == k || k == 0)
        return 1;
 
    if (cache[n][k] != -1)
        return cache[n][k];
 
    return cache[n][k] = getBinomialCoefficient(n - 1, k - 1) + getBinomialCoefficient(n - 1, k);
}

또는 factorial 을 직접 계산해서 구할 수도 있겠네요.

int factorial(int number)
{
    if (number <= 1)
        return 1;
    else
        return number * factorial(number - 1);    
}
 
int getBinomialCoefficient(int n, int k)
{
    return factorial(n) / factorial(n - k) / factorial(k);
}
 

출처: https://en.wikipedia.org/wiki/Binomial_coefficient