Calculator of combinations without repetition I am interested to find an absolute value (not an approximation) of "combination without repetition" for given \$n\$ and \$k\$, or \$\binom{n}{k}\$. 

The brute force solution would look like this 

private static ulong Factorial(int x)
{
    ulong res = 1;
    while (x &gt; 1)
    {
        res *= (ulong)x--;
    }
    return res;
}

public static int Combination0(int k, int n)
{
    k = Math.Min(k, n - k);
    if (n &lt; 2 || k &lt; 1) return 1;
    if (k == 1) return n;
    return (int)(Factorial(n) / (Factorial(k) * Factorial(n - k)));
}


We can slightly optimize this solution, by finding \$\prod_{n\geq i&gt;k}{i}\$ 
instead of \$\frac{n!}{(n-k)!}\$.

private static ulong Factorial(int x, int until = 0)
{
    ulong res = 1;
    while (x &gt; until)
    {
        res *= (ulong)x--;
    }
    return res;
}

public static int Combination1(int k, int n)
{
    k = Math.Min(k, n - k);
    if (n &lt; 2 || k &lt; 1) return 1;
    if (k == 1) return n;
    return (int)(Factorial(n, n - k) / Factorial(k));
}


But these two solutions have one significant problem - we are limited by ulong.MaxValue, which is more than \$20!\$, but less than \$21!\$.

Another way to find the number of combinations, which doesn't have the previously described problem, is the Pascal's triangle.

public static int Combination2(int k, int n)
{
    k = Math.Min(k, n - k);
    if (n &lt; 2 || k &lt; 1) return 1;
    if (k == 1) return n;
    int[] triangle = new int[k + 1];
    triangle[0] = 1;

    // expanding
    int i = 0;
    for (; i &lt; k; i++)
    {
        for (int j = i + 1; j &gt; 0; j--)
        {
            triangle[j] += triangle[j - 1];
        }
    }

    // progressing
    for (; i &lt; n - k; i++)
    {
        for (int j = k; j &gt; 0; j--)
        {
            triangle[j] += triangle[j - 1];
        }
    }

    // collapsing
    for (; i &lt; n; i++)
    {
        int until = k - (n - i);
        for (int j = k; j &gt; until; j--)
        {
            triangle[j] += triangle[j - 1];
        }
    }
    return triangle[k];
}




But the problem is that Combination2 is significantly slow. 

I would appreciate any comments and suggestions for an improvement.



Update

@quasar and @henrik-hansen suggested the way to prevent overflow by calculating \$\prod_{0 \leq i &lt; k}{\frac{n-i}{i+1}}\$.
One trick is to keep the partial products in small, \${n}\choose{k}\$ so they don't overflow. 

I iteratively multiply \$n/(n-k)\$ by \$(n-1)/(n-k-1)\$, cache the result in an accumulator, multiply that by \$(n-2)/(n-k-2)\$ and so forth.

#include &lt;iostream&gt;

template &lt;class T&gt;
T choose(T n, T k)
{
    T accum = 1;
    T m = n;
    for (T i = 1; i &lt;= m - k; i++)
    {
        accum = accum * n / (n - k);
        n--;
    }
    return accum;
}

int main()
{
    std::cout &lt;&lt; std::fixed;
    long double n = 50, k = 25;
    std::cout &lt;&lt; "\nLDBL_MAX" &lt;&lt; LDBL_MAX;
    long double result = choose(n, k);
    std::cout &lt;&lt; "\nC(" &lt;&lt; n &lt;&lt; "," &lt;&lt; k &lt;&lt; ") = " &lt;&lt; result;
    std::cin.clear();
    std::cin.get();
    return 0;
}