#C9.txt: Oct. 6, 2016, the algebraic ("Schutzenberger") ansatz
Help:=proc(): print(` TseqL(S,N) , TseqV(S,N), BaS(H,D,h,d), baS(h,d), GP1(L,n,d) `): end:

#TseqL(S,N): the first N terms from n=1 to n=N for the number of
#ORDERED TREES with n leaves, where any vertex can have either zero children
#or a number of children in S
#f=x+add(f^s, s in S)
TseqL:=proc(S,N) local f,f1,f2, i,x:

 if member(1,S) then
   RETURN(FAIL):
 fi:

f:=x:
f1:=x+add(f^s,s in S):
f1:=add(coeff(f1,x,i)*x^i,i=0..N):

while f<>f1 do
 f:=f1:
 f1:=x+add(f1^s,s in S):
 f1:=add(coeff(f1,x,i)*x^i,i=0..N):
od:

[seq(coeff(f1,x,i),i=1..N)]:


end:





#TseqV(S,N): the first N terms from n=1 to n=N for the number of
#ORDERED TREES with n nodes, where any vertex can have either zero children
#or a number of children in S
#f=x+x*add(f^s, s in S)
TseqV:=proc(S,N) local f,f1,f2, i,x:

 

f:=x:
f1:=x*(1+add(f^s,s in S)):
f1:=add(coeff(f1,x,i)*x^i,i=0..N):

while f<>f1 do
 f:=f1:
 f1:=x*(1+add(f1^s,s in S)):
 f1:=add(coeff(f1,x,i)*x^i,i=0..N):
od:

[seq(coeff(f1,x,i),i=1..N)]:


end:



#BaS(H,D,h,d): the SET of ballots sequences in {H,D} with h H's and d D's such that
#(i.e. the number of H's is >= number of D's in every prefix)
BaS:=proc(H,D,h,d) local S,S1,s1:
option remember:
if (h=0 and d=0) then
 RETURN({[]}):
fi:

if d>h or d<0 or h<0 then
  RETURN({}):
fi:

S1:=BaS(H,D,h,d-1):
S:={seq([op(s1),D],s1 in S1)}:
S1:=BaS(H,D,h-1,d):
S:=S union {seq([op(s1),H],s1 in S1)}:
end:

#baS(h,d): the NUMBER of sequences in {H,D} with h H's and d D's
baS:=proc(h,d) option remember:
if (h=0 and d=0) then
 RETURN(1):
fi:

if d>h or d<0 or h<0 then
  RETURN(0):
fi:

baS(h,d-1)+baS(h-1,d):


end:

#GP1(L,n,d): inputs a list of pairs [input,output], and a variable n
#and outputs a polynomial of degree d such P(input)=output
GP1:=proc(L,n,d) local P,i,a,var,eq:
if nops(L)<d+2 then
 RETURN(FAIL):
fi:
P:=add(a[i]*n^i,i=0..d):
var:={seq(a[i],i=0..d)}:
eq:={seq(subs(n=L[i][1],P)=L[i][2],i=1..d+2)}:
var:=solve(eq,var):

if var=NULL then
  RETURN(FAIL):
fi:

P:=subs(var,P):

if {seq(subs(n=L[i][1],P)-L[i][2],i=d+3..nops(L))}<>{0} then

  RETURN(FAIL):
else
 RETURN(P):
fi:

end: