Help:=proc(): print(`RT(S), RT1(S,r), SetP(S,k),Snk1(k,N),SnkD(k,N)`):

end:



#SetP(S,k): The collection of set partitions
#into k-(disjoint) sets of S
SetP:=proc(S,k) local fav,S1,SP1,SP,i,sp1:
option remember:

if k<0 then
   ERROR(`Bad input`):
fi:

if S={} then
 RETURN({}):
fi:


  if k=1 then
    RETURN({{S}}):
  fi:

fav:=S[1]:


S1:=S minus {fav}:

SP1:=SetP(S1,k-1):

SP:={ seq(sp1 union {{fav}}, sp1 in SP1) }:

SP1:=SetP(S1,k):

for sp1 in SP1 do
 for i from 1 to k do
  SP:=SP union { {op(1..i-1,sp1), sp1[i] union {fav}, op(i+1..k,sp1)} }:
 od:
od:

SP:

end:




#Snk(n,k): The Stirling numbers  of the second kind

Snk:=proc(n,k) local fav,S1,SP1,SP,i,sp1:
option remember:


if k<0 then
   ERROR(`Bad input`):
fi:

if n=0 then
 RETURN(0):
fi:


  if k=1 then
    RETURN(1):
  fi:



Snk(n-1,k-1)+k*Snk(n-1,k):



end:



SnkD:=proc(k,N) local n:

[seq(Snk(n,k),n=1..N)];
end:


#Snk1(k,N): a generatingfunctionology approach to
#seq(Snk(n,k),n=1..N):
Snk1:=proc(k,N) local x,f:
f:=(exp(x)-1)^k/k!:
f:=taylor(f,x=0,N+1):

[seq(coeff(f,x,i)*i!,i=1..N)]:

end:


RT:=proc(S) local r:
{seq( op(RT1(S,r)), r in S)}:
end:

#Combine(L,r): Given a list of sets of rooted trees
#finds all the combinations with one from each
Combine:=proc(L,r) local L1,t,C1,C2,c1,c2:

if nops(L)=1 then
 RETURN({seq([r, t[2] union {[t[1],r]} ], t in L[1]) }):
fi:

L1:=[op(1..nops(L)-1,L)]:

C1:=Combine(L1,r):
C2:=Combine([L[nops(L)]],r):


{seq(seq([r,c1[2] union c2[2]], c1 in C1),c2 in C2)}:

end:


#RT1(S,r):The set of labelled rooted trees on the set of labels S
#a rooted tree is denoted by [Root,SetOfEdges]
RT1:=proc(S,r) local Par,Rtrees,i,ListS,L,p,P:
option remember:

if nops(S)=1 then
 if  not member(r,S) then
   RETURN({}):
 else
   RETURN({ [r,{}] }):
  fi:
fi:
 


Rtrees:={}:


 for i from 1 to nops(S)-1 do
  Par:=SetP(S minus {r}, i):
   
   for P in Par do
     L:=[]:
      for p in P do
       L:=[op(L),RT(p)]:
      od:
     Rtrees:= Rtrees union Combine(L,r):
    od:


 od:

Rtrees:
end: