組み合わせ

combination.png

texコード

{}_n\mathrm{C}_x

異なるn個のものから、異なるm個を選ぶ場合の組み合わせの総数は?

(1)
\begin{align} nCr=\frac{n!}{r!(n-r)!}\\ \end{align}

常に$n>r$である。

(2)
\begin{align} nCr=\frac{n(n-1)(n-2)....(r+1)r!}{r!(n-r)!}\\ \end{align}

これを約分するとこうなる

(3)
\begin{align} nCr=\frac{n(n-1)(n-2)....(r+1)}{(n-r)!}\\ \end{align}
(4)
\begin{align} nCr=\frac{\prod_{i=(r+1)}^n i}{(n-r)!} \end{align}

この定義通りにコードを書くとこうなるが

int combination(int _n,int _r){
    unsigned long long numerator=1;//分子
    unsigned long long denominator=1;//分母
    for(int i=_n;i>=_r+1;i--){
        numerator*=i;
    }
    for(int i=_n-_r;i>0;i--){
        denominator*=i;
    }
    if(numerator<denominator){cout<<"失敗"<<endl;return -1;}
 
    return (int)(numerator/denominator);
}

大きな数の時、失敗してしまうのだ。
$32C6$で既にアウトだ。
なので、コンピュータに計算させるなら、漸化式にした方がいいみたい。(5)
\begin{align} {}_n\mathrm{C}_{r}=\frac{n-r+1}{r}{}_n\mathrm{C}_{r-1} \end{align}

欠点

これは数学的解法。
何か例外が発生した場合柔軟に対処できないのが問題。
これをコンピュータにやらせるぐらいだったら、
動的計画法メモ化再帰を使った方がいいらしいぞ。

サポートサイト Wikidot.com