def catalan_binomial_coefficient(n):
    """
    The most fast version
    O(n): H(n) = C(2n, n) / (n + 1)
    wiki: https://en.wikipedia.org/wiki/Binomial_coefficient
                  n!
    C(n, k) = ----------
               k!(n-k)!
                                n + 1 - i
            = for i = 1 to k: -------------
                                    i
    """

    def binomialCofficient(n, k):
        # C(n, k ) = C(n, n - k)
        if k > n - k:
            k = n - k
        res = 1
        for i in range(k):
            res *= n - i
            res /= i + 1
        return res

    c = binomialCofficient(2 * n, n)
    return c // (n + 1)