##Given the number of leaves "n" and number of labels "k" this program returns the number of rooted leaf multi labeled ##trees where the degree of the root is >=2, degree of non-root, non-leaf vertices is >=3 
#AUTHOR: Virginia Johnson (2011-10)  version 1
def G(n,k):
    #Gets input and will return the number of trees with leaves 0-n where  k is the size of the label set.
    T=[0]*(n+1)
    for i in range (n+1):
        #easy cases
        #no leaves
        if i==0:
            T[i]=0
        #1 leaf
        elif i==1:
            T[i]=k
        #for n>=2    
        else:            
            #find m= how many partitions there are of i 
            m=Partitions(i).cardinality()
            #set up a counter that will stop the loop when finished with all partitions (m-1)
            count=0
            #get the partitions 1 at a time and omit the first one
            g=iter(Partitions(i))
            g.next()
                
            while count != m-1:
                #fix this partition for the duration of the first calculation
                L=g.next()
                #print "L"     #will show partitions used if uncommented out
                #print L
                    
                #set up a string which holds counts
                S=[]
                    
                #count the number of times each integer in{1,...i-1} appears in partition
                for c in range (0,i):
                    S.append(list(L).count(c))
               
                #create string for product
                P=[0]*(i)
                P[0]=1
                
                for d in range (1,len(list(S))):
                    P[d]=binomial(T[d]+S[d]-1,S[d])
               
                T[i]+=prod(P)
                
                count=count+1
    #Uses T to calculate number of unrooted trees on n leaves using label set  size k. 
    U=[0]*(n+1)
    for i in range (n+1):
        #easy cases first
        #no leaves
        if i==0:
            U[i]=0
        #1 leaf
        elif i==1:
            U[i]=k
        #for n >=2
        else:
            U[i]=k*T[i-1]+T[i] 
            for j in range(1,i):
              U[i]+=T[j]*T[i-j]
       
    print "Rooted Non-binary Multi-leaf-labeled Trees"              
    print T
    print  "Unrooted Non-binary Multi-leaf-labeled Trees"              
    print U