Combinatorics on ordered trees | java code to find the number of ordered trees with given number of edges and leaves ; 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
import java . io . * ; class GFG { static int binomialCoeff ( int n , int k ) { int [ ] [ ] C = new int [ n + 1 ] [ k + 1 ] ; int i , j ; for ( i = 0 ; i <= n ; i ++ ) { for ( j = 0 ; j <= Math . min ( i , k ) ; j ++ ) { if ( j == 0 j == i ) C [ i ] [ j ] = 1 ; else C [ i ] [ j ] = C [ i - 1 ] [ j - 1 ] + C [ i - 1 ] [ j ] ; } } return C [ n ] [ k ] ; } static int k_Leaves ( int n , int k ) { int ans = ( binomialCoeff ( n , k ) * binomialCoeff ( n , k - 1 ) ) / n ; System . out . println ( " Number ▁ of ▁ trees ▁ " + " having ▁ 4 ▁ edges ▁ and ▁ exactly ▁ 2 ▁ " + " leaves ▁ : ▁ " + ans ) ; return 0 ; } static int numberOfNodes ( int n , int d ) { int ans = binomialCoeff ( 2 * n - 1 - d , n - 1 ) ; System . out . println ( " Number ▁ of ▁ nodes ▁ " + " of ▁ degree ▁ 1 ▁ in ▁ a ▁ tree ▁ having ▁ 4 ▁ " + " edges ▁ : ▁ " + ans ) ; return 0 ; } static int rootDegreeR ( int n , int r ) { int ans = r * binomialCoeff ( 2 * n - 1 - r , n - 1 ) ; ans = ans / n ; System . out . println ( " Number ▁ of ▁ trees ▁ " + " having ▁ 4 ▁ edges ▁ where ▁ root ▁ has " + " ▁ degree ▁ 2 ▁ : ▁ " + ans ) ; return 0 ; } public static void main ( String [ ] args ) { k_Leaves ( 3 , 2 ) ; numberOfNodes ( 3 , 1 ) ; rootDegreeR ( 3 , 2 ) ; } }