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 program to test above functions 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
< ? php function binomialCoeff ( $ n , $ k ) { $ C = array ( array ( ) ) ; $ i ; $ j ; for ( $ i = 0 ; $ i <= $ n ; $ i ++ ) { for ( $ j = 0 ; $ j <= min ( $ i , $ k ) ; $ j ++ ) { if ( $ j == 0 or $ j == $ i ) $ C [ $ i ] [ $ j ] = 1 ; else $ C [ $ i ] [ $ j ] = $ C [ $ i - 1 ] [ $ j - 1 ] + $ C [ $ i - 1 ] [ $ j ] ; } } return $ C [ $ n ] [ $ k ] ; } function k_Leaves ( $ n , $ k ) { $ ans = ( binomialCoeff ( $ n , $ k ) * binomialCoeff ( $ n , $ k - 1 ) ) / $ n ; echo " Number ▁ of ▁ trees ▁ having ▁ 4 ▁ edges ▁ and ▁ " , " exactly ▁ 2 ▁ leaves ▁ : ▁ " , $ ans , " STRNEWLINE " ; return 0 ; } function numberOfNodes ( $ n , $ d ) { $ ans = binomialCoeff ( 2 * $ n - 1 - $ d , $ n - 1 ) ; echo " Number ▁ of ▁ nodes ▁ of ▁ degree ▁ 1 ▁ in " , " ▁ a ▁ tree ▁ having ▁ 4 ▁ edges ▁ : ▁ " , $ ans , " STRNEWLINE " ; return 0 ; } function rootDegreeR ( $ n , $ r ) { $ ans = $ r * binomialCoeff ( 2 * $ n - 1 - $ r , $ n - 1 ) ; $ ans = $ ans / $ n ; echo " Number ▁ of ▁ trees ▁ having ▁ 4 ▁ edges " , " ▁ where ▁ root ▁ has ▁ degree ▁ 2 ▁ : ▁ " , $ ans ; return 0 ; } k_Leaves ( 3 , 2 ) ; numberOfNodes ( 3 , 1 ) ; rootDegreeR ( 3 , 2 ) ; ? >