Program for nth Catalan Number | Returns value of Binomial Coefficient C ( n , k ) ; since C ( n , k ) = C ( n , n - k ) ; Calculate value of [ n * ( n - 1 ) * -- - * ( n - k + 1 ) ] / [ k * ( k - 1 ) * -- -- * 1 ] ; A Binomial coefficient based function to find nth catalan number in O ( n ) time ; Calculate value of 2 nCn ; return 2 nCn / ( n + 1 ) ; Driver Code
def binomialCoefficient ( n , k ) : NEW_LINE INDENT res = 1 NEW_LINE if ( k > n - k ) : NEW_LINE INDENT k = n - k NEW_LINE DEDENT for i in range ( k ) : NEW_LINE INDENT res = res * ( n - i ) NEW_LINE res = res / ( i + 1 ) NEW_LINE DEDENT return res NEW_LINE DEDENT def catalan ( n ) : NEW_LINE INDENT c = binomialCoefficient ( 2 * n , n ) NEW_LINE return c / ( n + 1 ) NEW_LINE DEDENT for i in range ( 10 ) : NEW_LINE INDENT print ( catalan ( i ) , end = " ▁ " ) NEW_LINE DEDENT