Count distinct regular bracket sequences which are not N periodic | Function that finds the value of Binomial Coefficient C ( n , k ) ; Since C ( n , k ) = C ( n , n - k ) ; Calculate the value of [ n * ( n - 1 ) * -- - * ( n - k + 1 ) ] / [ k * ( k - 1 ) * -- - * 1 ] ; Return the C ( n , k ) ; Binomial coefficient based function to find nth catalan number in O ( n ) time ; Calculate value of 2 nCn ; Return C ( 2 n , n ) / ( 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 ; Difference between counting ways of 2 * N and N is the result ; Given value of N ; Function call
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 = res * ( n - i ) NEW_LINE res = res // ( i + 1 ) NEW_LINE DEDENT return res NEW_LINE DEDENT def catalan ( n ) : NEW_LINE INDENT c = binomialCoeff ( 2 * n , n ) NEW_LINE return c // ( n + 1 ) NEW_LINE DEDENT def findWays ( n ) : NEW_LINE INDENT if ( ( n & 1 ) == 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT return catalan ( n // 2 ) NEW_LINE DEDENT def countNonNPeriodic ( N ) : NEW_LINE INDENT print ( findWays ( 2 * N ) - findWays ( N ) ) NEW_LINE DEDENT N = 4 NEW_LINE countNonNPeriodic ( N ) NEW_LINE