最初に

C++で書かれた、nCrの組み合わせコードです。

表記

組み合わせ

重複組み合わせ

情報

組み合わせ Wikipedia、重複組み合わせ Wikipedia

C++コード

/**
* 組み合わせ：n個のものから重複無くr個とった組み合わせの数
* @param [in] n 要素数
* @param [in] r n個からr個とる数
* @return 組み合わせ数を返す
*/
template<typename IntType>
IntType nCr(IntType n, IntType r)
{
    if ( r > n ) return 0;
    if ( r * 2 > n ) r = n - r;
    if ( r == 0 ) return 1;

    IntType result = n;
    for ( IntType i = 2; i <= r; ++i ) {
        result *= (n - i + 1);
        result /= i;
    }
    return result;
}

/**
* 重複組合せ
* n個のものから重複を許して r個とった組み合わせの数
* @param [in] n 要素数
* @param [in] r n個のものから重複を許して r個とる数
* @return 組み合わせ数を返す
*/
template<typename IntType>
IntType nHr(IntType n, IntType r)
{
    return nCr(n+r-1,r);
}

オンライン実行