C#で組み合わせを求める

いわゆる_nC_k

　「色違いの5個のボールが袋に入っている。その袋から3つ取り出す場合の組み合わせの数を求めよ」
という中学数学に出てきそうな問題を解くためのやつ。
表記としては₅C₃と書く。

計算

　₅C₃では次のようになる。

₅C₃ = (5×4×3)/(3×2×1) = 10

　_nC_k = _nC_n-k なので、計算量が少ない方を選べばいい。

できたもの

/// <summary>
/// 組み合わせの数を求める
/// </summary>
/// <param name="n">要素数</param>
/// <param name="k">選ぶ数</param>
/// <returns>nCk</returns>
public BigInteger Count(long n, long k)
{
    if (k > n - k) k = n - k;

    var numerator = new BigInteger(1);
    var denominator = new BigInteger(1);
    var tmp = 1L;

    for (int count = 1; count <= k; count++)
    {
        numerator *= n;
        n--;

        denominator *= tmp;
        tmp++;
    }

    return numerator / denominator;
}

なんでおっさんはすぐBigIneger使うん？

　答えがすぐに爆発するからやで。

Count(600, 25) = 110400461164029879580081326850533034570953024

　こんなふうに、ちょっと大きい数字を与えただけでintの範囲を軽く超えてくる。
もうBigInteger使うしかないでしょ。

組み合わせとは

ja.wikipedia.org

Combinationの語源

www.etymonline.com

組合せ数学 (岩波科学ライブラリー)

組合せ論の精選102問 (数学オリンピックへの道)

ヴァン・リント&ウィルソン 組合せ論 上