Find the number of valid parentheses expressions of given length | 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 ) ; Function to find possible ways to put balanced parenthesis in an expression of length n ; If n is odd , not possible to create any valid parentheses ; Otherwise return n / 2 'th  Catalan Number ; Driver Code
def binomialCoeff ( 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 *= ( n - i ) ; NEW_LINE res /= ( i + 1 ) ; NEW_LINE DEDENT return int ( res ) ; NEW_LINE DEDENT def catalan ( n ) : NEW_LINE INDENT c = binomialCoeff ( 2 * n , n ) ; NEW_LINE return int ( c / ( n + 1 ) ) ; NEW_LINE DEDENT def findWays ( n ) : NEW_LINE INDENT if ( n & 1 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT return catalan ( int ( n / 2 ) ) ; NEW_LINE DEDENT n = 6 ; NEW_LINE print ( " Total ▁ possible ▁ expressions ▁ of ▁ length " , n , " is " , findWays ( 6 ) ) ; NEW_LINE