組み合わせ

最終更新日27 Mar 2015 09:48

階乗

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);
}