コンビネーション
Combination
$ n個の相異なる要素から$ k個の要素を選び出す方法の数
$ _nC_k = \frac{n!}{k! (n-k)!}
二項係数を使って$ \begin{pmatrix} n \\ k \end{pmatrix}と表現することもできる 実装
ちょっとむずい
漸化式を用いる
$ kに付いての漸化式: $ {}_n C_k = \frac{n - k + 1}{k} {}_n C_{k-1}
パスカルの三角形を利用: $ {}_n C_k = {}_{n-1} C_{k-1} + {}_{n-1} C_k パスカルの三角形のほうを用いて、再帰を使って以下のように計算可能 code:js
function combination(n, r) {
if (r === 0 || r === n) {
return 1;
}
return combination(n - 1, r - 1) + combination(n - 1, r);
}