Binomial Coefficient(이항계수)

Basic Concept

---

The binomial coefficient is given by
$$ \begin{pmatrix}n\\k\end{pmatrix}=_nC_k=\frac{n!}{k!\left(n-k\right)!} \text{    for } 0 \le k\le n.$$

 

For values of n and k that are not small, we cannot compute the binomial coefficient directly from this definition because n! is very large even for moderate values of n. We can eliminate the need to compute n! or k! by using this recursive property.

$$ \begin{pmatrix}n\\k\end{pmatrix}=_nC_k = \begin{cases} _{n-1}C_{k-1}+_{n-1}C_k  & \text{    } 0 \lt k \lt n \\1 & \text{    } k = 0 \text{ or } k = n.\end{cases} $$

 

👉 계산량이 많은 n!이나 k!의 계산 없이도 상기 재귀식을 사용하여 이항계수를 구할 수 있다.

 

(참고) Pseudo Code

• Binomial Coefficient (Divide-and-Conquer)

int bincoeff(int n, int k)
// Problem: Compute the binomial coefficient.
// Inputs: nonnegative integers n and k, where k <= n.
// Outputs: the binomial coefficient nCk
{
    if (k == 0 || n == k)
        return 1;
    else
        return bincoeff(n-1, k-1) + bincoeff(n-1, k);
}

 

👉 분할정복법을 사용하여 이항계수를 푸는 것은 간단하지만 효율적이지는 않다. bincoeff(n-1, k-1)과 bincoeff(n-1, k)는 모두 bincoeff(n-2, k-1)의 결과가 필요하고, 이 값은 해당 알고리즘에서 중복 계산되므로 시간복잡도 관점에서 비효율적이다. 

분할정복법은 나눠진 문제들 간에 서로 연관성이 없는 문제를 해결하는데 적합함을 상기하자.

 

 

Binomial Coefficient Using Dynamic Programming

---

Algorithm Design

1. Establish a recursive property. B[i][j] will contain $_iC_j$
2. solve an instance of the problem in a bottom-up fashion by computing the rows in B in sequence starting with the first row.

$$ B[i][j] = \begin{cases} B[i-1][j-1] + B[i-1][j]  & \text{    } 0 \lt j \lt i \\1 & \text{    } j = 0 \text{ or } j = i.\end{cases} $$

 

Example The array B used to compute the binomial coefficient.

 

 

Compute row 0:

B[0][0] = 1

 

Compute row 1:

B[1][0] = 1
B[1][1] = 1

 

Compute row 2:

B[2][0] = 1
B[2][1] = B[1][0] + B[1][1] = 1 + 1 = 2
B[2][2] = 1

 

Compute row 3:

B[3][0] = 1
B[3][1] = B[2][0] + B[2][1] = 1 + 2 = 3
B[3][2] = B[2][1] + B[2][2] = 2 + 1 = 3
B[3][3] = 1

 

Compute row 4:

B[4][0] = 1
B[4][1] = B[3][0] + B[3][1] = 1 + 3 = 4
B[4][2] = B[3][1] + B[3][2] = 3 + 3 = 6

 

👉 동적계획법으로 $_n​C_k$를 계산하기 위해 B[0][0]부터 시작해서 위에서 아래로 재귀관계식을 적용해 배열을 채워나간다. 종국에 가서는 최종해가 B[n][k]에 저장된다.

 

Pseudo Code

• Binomial Coefficient (Dynamic Programming)

int bincoeff2(int n, int k)
{
  index i, j;
  int B[0..n][0..k];

  for (i = 0; i <= n; ++i)
    for (j = 0; j <= minimum(i,k); ++j)
      if (j == 0 || j == i)
        B[i][j] = 1;
      else
        B[i][j] = B[i-1][j-1] + B[i-1][j];

  return B[n][k];
}

 

Source Code

• binomial2.h

// File: binomial2.h
#ifndef BINCOEFF_H
#define BINCOEFF_H

namespace algorithms
{
  int binomial_coefficient(int** b, int n, int k);
  // Problem: Compute the binomial coefficient.
  // Input: nonnegative integers n and k, where k <= n.
  // Output: the binomial coefficient (n, k).

} // namespace algorithms

#endif

 

• binomial2.cpp

// File: binomial2.cpp
#include <algorithm> // Provides min
#include "binomial2.h"

namespace algorithms
{
  int binomial_coefficient(int** B, int n, int k)
  {
    // Improvement to the algorithm would be
    // to take advantage of the fact that (n,k) = (n, n-k)
    //  if ((n/2) < k)
    //    k = n - k;

    for (int i = 0; i <= n; ++i)
    {
      for (int j = 0; j <= std::min(i, k); ++j)
      {
        if (j == 0 || j == i)
          B[i][j] = 1;
        else
          B[i][j] = B[i - 1][j - 1] + B[i - 1][j];
      }
    }

    return B[n][k];
  }
} // namespace algorithms

 

• bincoefftest.cpp

// File: bincoefftest.cpp
#include <iostream>
#include <iomanip>
#include <cstdlib> // Provides EXIT_SUCCESS;
#include "binomial2.h"
using namespace std;
using namespace algorithms;

int** get_matrix_space(int m, int n);
void release_matrix_space(int** b, int m);

int main( )
{
  int** binomial;
  int n, k;

  cout << "Compute the binomial coefficient (n, k): ";
  cin >> n >> k;
  binomial = get_matrix_space(n, k);
  cout << "The answer for (" << n << ", " << k << ") is "
       << binomial_coefficient(binomial, n, k) << endl;

  for (int i = 0; i <= n; ++i)
  {
    for (int j = 0; j <= k; ++j)
    {
      if (binomial[i][j] != 0)
        cout << setw(4) << binomial[i][j] << " ";
    }
    cout << endl;
  }

  release_matrix_space(binomial, n);
  return EXIT_SUCCESS;
}

int** get_matrix_space(int m, int n)
{
  // Allocate the matrix
  // Please make sure that we need to allocate [m+1][n+1]
  int **data = new int *[m + 1];
  for (int i = 0; i < m + 1; ++i)
    data[i] = new int[n + 1];

  // Initialize the matrix
  for (int i = 0; i < m + 1; ++i)
    for (int j = 0; j < n + 1; ++j)
      data[i][j] = 0;
  return data;
}

void release_matrix_space(int** b, int m)
{
  for (int i = 0; i < m + 1; ++i)
    delete[] b[i];
  delete[] b;
}

 

 

Time Complexity Analysis

---

Basic operation

the number of passes through the for-j loop

 

Input size

n, k

 

Every-Case Time Complexity

 

$\displaystyle T(n) = \frac{k(k+1)}{2} + (n - k +1)(k + 1) = \frac{(2n-k+2)(k+1)}{2} \in \Theta(nk) $

 

The following table shows the number of passes for each value of i

 

i	0	1	2	3	...	k-1	k	k+1	...	n
Num of Passes for-j loop	1	2	3	4	...	k	k+1	k+1	...	k+1

 

The total number of passes is therefore given by

 

$\displaystyle 1 + 2 + 3 + 4 + ... + k + \underbrace{(k+1) + (k+1) + ... + (k+1)}_{\text{n-k+1 times}} $