Count all possible paths from top left to bottom right of a Matrix without crossing the diagonal | Function to calculate Binomial Coefficient C ( n , r ) ; C ( n , r ) = C ( n , n - r ) ; [ n * ( n - 1 ) * -- - * ( n - r + 1 ) ] / [ r * ( r - 1 ) * -- -- * 1 ] ; Function to calculate the total possible paths ; Update n to n - 1 ; Stores 2 nCn ; Stores Nth Catalan number ; Stores the required answer ; Driver Code
def binCoff ( n , r ) : NEW_LINE INDENT val = 1 NEW_LINE if ( r > ( n - r ) ) : NEW_LINE INDENT r = ( n - r ) NEW_LINE DEDENT for i in range ( r ) : NEW_LINE INDENT val *= ( n - i ) NEW_LINE val //= ( i + 1 ) NEW_LINE DEDENT return val NEW_LINE DEDENT def findWays ( n ) : NEW_LINE INDENT n = n - 1 NEW_LINE a = binCoff ( 2 * n , n ) NEW_LINE b = a // ( n + 1 ) NEW_LINE ans = b NEW_LINE return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 4 NEW_LINE print ( findWays ( n ) ) NEW_LINE DEDENT