Combinatorics on ordered trees | Function returns value of Binomial Coefficient C ( n , k ) ; Calculate value of Binomial Coefficient in bottom up manner ; Base Cases ; Calculate value using previously stored values ; Function to calculate the number of trees with exactly k leaves . ; Function to calculate total number of Nodes of degree d in these trees . ; Function to calculate the number of trees in which the root has degree r . ; Driver code ; Number of trees having 3 edges and exactly 2 leaves ; Number of Nodes of degree 3 in a tree having 4 edges ; Number of trees having 3 edges where root has degree 2
def binomialCoeff ( n , k ) : NEW_LINE INDENT C = [ [ 0 for i in range ( k + 1 ) ] for j in range ( n + 1 ) ] NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT for j in range ( min ( i , k ) + 1 ) : NEW_LINE INDENT if ( j == 0 or j == i ) : NEW_LINE INDENT C [ i ] [ j ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT C [ i ] [ j ] = ( C [ i - 1 ] [ j - 1 ] + C [ i - 1 ] [ j ] ) NEW_LINE DEDENT DEDENT DEDENT return C [ n ] [ k ] NEW_LINE DEDENT def k_Leaves ( n , k ) : NEW_LINE INDENT ans = ( ( binomialCoeff ( n , k ) * binomialCoeff ( n , k - 1 ) ) // n ) NEW_LINE print ( " Number ▁ of ▁ trees ▁ " , " having ▁ 4 ▁ edges ▁ and ▁ exactly ▁ 2 ▁ " , " leaves ▁ : ▁ " , ans ) NEW_LINE DEDENT def numberOfNodes ( n , d ) : NEW_LINE INDENT ans = binomialCoeff ( 2 * n - 1 - d , n - 1 ) NEW_LINE print ( " Number ▁ of ▁ Nodes ▁ " , " of ▁ degree ▁ 1 ▁ in ▁ a ▁ tree ▁ having ▁ 4 ▁ " , " edges ▁ : ▁ " , ans ) NEW_LINE DEDENT def rootDegreeR ( n , r ) : NEW_LINE INDENT ans = r * binomialCoeff ( 2 * n - 1 - r , n - 1 ) NEW_LINE ans = ans // n NEW_LINE print ( " Number ▁ of ▁ trees ▁ " , " having ▁ 4 ▁ edges ▁ where ▁ root ▁ has ▁ " , " degree ▁ 2 ▁ : ▁ " , ans ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT k_Leaves ( 3 , 2 ) NEW_LINE numberOfNodes ( 3 , 1 ) NEW_LINE rootDegreeR ( 3 , 2 ) NEW_LINE DEDENT