二項係数(Binomial)

説明

二項係数 ${}_n \mathrm{C} _k$ を $\frac {k(k-1)\dots (n-k+1)} {k(k-1)\dots 1}$ を利用して求める。

この求め方は $k$ が小さい時に有効。テーブルを得たい場合はパスカルの三角形による 二項係数テーブル、$n$ が小さい場合は 組合せ を用いると良い。

計算量

• $O(k)$

実装例

• binomial($n$, $k$):= ${}_n \mathrm{C} _k$ を返す。

template< typename T >
T binomial(int64_t N, int64_t K) {
  if(K < 0 || N < K) return 0;
  T ret = 1;
  for(T i = 1; i <= K; ++i) {
    ret *= N--;
    ret /= i;
  }
  return ret;
}