Combinations.cs

using System;

namespace CombinatoricsLib
{
    public class Combinations
    {
        private static ulong Factorial(int x, int until = 0)
        {
            ulong res = 1;
            while (x != until)
            {
                res *= (ulong)x--;
            }
            return res;
        }

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

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


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

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

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

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

        public static int Combination3(int k, int n)
        {
            k = Math.Min(k, n - k);
            if (n < 2 || k < 1) return 1;
            if (k == 1) return n;
            int count = n;
            int x = 1;
            while (x < k)
            {
                count *= n - x++;
                count /= x;
            }
            return count;
        }

        public static int CombinationHansen(int k, int n)
        {
            k = Math.Min(k, n - k);
            if (n < 2 || k < 1) return 1;
            if (k == 1) return n;
            int count = n;
            for (int x = 1; x <= k - 1; x++)
            {
                count = count * (n - x) / x;
            }
            return (count / k);
        }
    }
}

CombinationsBenchmark.cs

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Attributes.Columns;
using BenchmarkDotNet.Attributes.Exporters;
using BenchmarkDotNet.Attributes.Jobs;
using BenchmarkDotNet.Reports;
using BenchmarkDotNet.Running;
using CombinatoricsLib;

namespace Benchmarks
{
    [ClrJob]
    [RPlotExporter, RankColumn]
    public class CombinationsBenchmark
    {
        [Params(8, 11, 16, 19, 20)] public int N;

        [Benchmark]
        public void Combination0()
        {
            for (int i = 0; i <= N; i++)
            {
                Combinations.Combination0(i, N);
            }
        }

        [Benchmark]
        public void Combination1()
        {
            for (int i = 0; i <= N; i++)
            {
                Combinations.Combination1(i, N);
            }
        }

        [Benchmark]
        public void Combination2()
        {
            for (int i = 0; i <= N; i++)
            {
                Combinations.Combination2(i, N);
            }
        }

        [Benchmark]
        public void Combination3()
        {
            for (int i = 0; i <= N; i++)
            {
                Combinations.Combination3(i, N);
            }
        }

        [Benchmark]
        public void CombinationHansen()
        {
            for (int i = 0; i <= N; i++)
            {
                Combinations.CombinationHansen(i, N);
            }
        }

        public static Summary Run()
        {
            return BenchmarkRunner.Run<CombinationsBenchmark>();
        }
    }
}

CombinationsBenchmark.md

BenchmarkDotNet=v0.10.14, OS=Windows 10.0.16299.371 (1709/FallCreatorsUpdate/Redstone3)
Intel Core i7-7820HQ CPU 2.90GHz (Kaby Lake), 1 CPU, 8 logical and 4 physical cores
Frequency=2835938 Hz, Resolution=352.6170 ns, Timer=TSC
  [Host] : .NET Framework 4.7.1 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.2633.0
  Clr    : .NET Framework 4.7.1 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.2633.0

Job=Clr  Runtime=Clr  

Method	N	Mean	Error	StdDev	Median	Rank
Combination0	8	98.27 ns	1.5877 ns	1.3258 ns	98.36 ns	6
Combination1	8	74.25 ns	0.9599 ns	0.8979 ns	74.20 ns	4
Combination2	8	118.75 ns	0.6953 ns	0.6504 ns	118.68 ns	7
Combination3	8	38.15 ns	0.2153 ns	0.1909 ns	38.13 ns	1
CombinationHansen	8	50.54 ns	0.6765 ns	0.6328 ns	50.56 ns	2
Combination0	11	177.24 ns	2.1238 ns	1.9866 ns	177.43 ns	9
Combination1	11	121.65 ns	1.5122 ns	1.4145 ns	122.21 ns	8
Combination2	11	270.98 ns	5.3618 ns	10.0707 ns	266.82 ns	13
Combination3	11	72.61 ns	0.8160 ns	0.7633 ns	72.83 ns	3
CombinationHansen	11	95.04 ns	0.6758 ns	0.5643 ns	94.99 ns	5
Combination0	16	357.80 ns	3.3599 ns	3.1429 ns	357.29 ns	18
Combination1	16	211.48 ns	1.1436 ns	1.0697 ns	211.45 ns	11
Combination2	16	707.82 ns	9.0663 ns	8.4806 ns	710.00 ns	22
Combination3	16	180.39 ns	1.8440 ns	1.7249 ns	180.69 ns	10
CombinationHansen	16	222.64 ns	1.5143 ns	1.2645 ns	222.95 ns	12
Combination0	19	495.49 ns	3.0490 ns	2.5461 ns	495.04 ns	20
Combination1	19	277.37 ns	5.7925 ns	13.3093 ns	273.31 ns	14
Combination2	19	1,181.08 ns	7.1716 ns	6.3574 ns	1,180.61 ns	23
Combination3	19	275.50 ns	1.2740 ns	1.1917 ns	275.46 ns	14
CombinationHansen	19	329.21 ns	4.2598 ns	3.9847 ns	328.31 ns	17
Combination0	20	539.65 ns	2.1774 ns	2.0367 ns	539.69 ns	21
Combination1	20	288.70 ns	3.8677 ns	3.6178 ns	288.69 ns	15
Combination2	20	1,381.07 ns	10.9915 ns	9.1784 ns	1,378.39 ns	24
Combination3	20	314.97 ns	1.5115 ns	1.4139 ns	315.18 ns	16
CombinationHansen	20	373.35 ns	4.7866 ns	4.4774 ns	375.16 ns	19