#Yusra Naqvi: HW #13
#OK to post

################################################################################
################################################################################

#1
#GuessH1(L,ord,deg,n,N): inputs a sequence L, non-negative integers ord and deg,
#and symbols n and N, and outputs a linear recurrence operator with polynomial 
#coefficients conjecturally annihilating the sequence L

GuessH1:=proc(L,ord,deg,n,N) local ope,a,i,j,var,eq,n1,var1:

if nops(L)<(1+ord)*(1+deg)+ord+6 then
 print(cat(`We need at least `,(1+ord)*(1+deg)+ord+6,` terms in L.`)):
 return(FAIL):
fi:

ope:=add(add(a[i,j]*n^i*N^j,i=0..deg),j=0..ord):
var:={seq(seq(a[i,j],i=0..deg),j=0..ord)}:

eq:={seq(
 add(subs(n=n1,coeff(ope,N,j))*L[n1+j],j=0..ord),
 n1=1..(1+ord)*(1+deg)+6)}:
 
var1:=solve(eq,var):
ope:=subs(var1,ope):

if ope=0 then
 return(FAIL):
fi:

ope:=subs({seq(v=1, v in var)},ope):
ope:=add(factor(coeff(ope,N,j))*N^j,j=0..deg(ope,N)):

end:

################################################################################

#GuessH(L,n,N): inputs a sequence L and symbols n and N, and outputs 
#a linear recurrence operator of minimum degree and order with polynomial 
#coefficients conjecturally annihilating the sequence L

GuessH:=proc(L,n,N) local m,ord,deg,ope,eq:

for m from 1 to nops(L)-7 do: 
 for ord from 1 to m do
  ope:=GuessH1(L,ord,m-ord,n,N):
  
  if ope<>FAIL then

   if ord*(m-ord)<=nops(L)-7-m then
    eq:={seq(add(subs(n=n1,coeff(ope,N,j))*L[n1+j],j=0..ord),
    n1=1..nops(L)-ord)}:
 
    if eq={0} then 
     return (ope):
    fi:
   
   else 
    return(FAIL):
   fi:

  fi: 

 od:
od:

FAIL:
  
end:

################################################################################
################################################################################

#2
#LIF(P,u,N): inputs an expression P(u) that possesses a Maclaurin expansion in u
#and outputs the first N terms of the series expansion of the unique f.p.s u(t)
#satisfying the functional equation u(t)=t*P(u(t)).
#For example:
#LIF(1+u^2,u,12);
#should return
#[1,0,1,0,2,0,5,0,14,0,42,0]

LIF:=proc(P,u,N) local n:

[seq(coeff(taylor(P^n,u=0,n),u,n-1)/n,n=1..N)]:

end:

################################################################################

#OTN(S,N): inputs a set of positive integers, S, and outputs the list L of
#length N of non-neg. integers such that L[n] is the number of ordered trees
#with n vertices where every vertex must have a number of children that is a 
#member of S or 0. 
#Note that this differs from the statement of problem in that we always take 0
#to be one of the possible numbers of children in order to get finite trees.

OTN:=proc(S,N) local S1,P,u,s:

S1:=S union {0}:

P:=0:
for s in S1 do
 P:=P+u^s:
od:

LIF(P,u,N):

end:

################################################################################
################################################################################

#3
#AllOTN(S,N): inputs a set S and outputs the set {[S1,OTN(S1,N)]} for all 
#subsets S1 of S. 

AllOTN:=proc(S,N) local PS,SS,S1:
with(combinat, powerset):

PS:=powerset(S):
SS:={}:

for S1 in PS do
 SS:=SS union {[S1,OTN(S1,N)]}:
od:

SS:

end:

################################################################################
################################################################################

#4
#{}:A7 
#{1}:A12
#{2}:A108
#{3}:A1764
#{4}:A2293
#{5}:A2294
#{1,2}:A1006
#{1,3}:A71879
#{1,4}:A127902
#{1,5}:Not in OEIS
#{2,3}:A1005
#{2,4}:A6605
#{2,5}:Not in OEIS
#{3,4}:Not in OEIS
#{3,5}:Not in OEIS
#{4,5}:Not in OEIS
#{1,2,3}:A36765
#{1,2,4}:Not in OEIS
#{1,2,5}:Not in OEIS
#{1,3,4}:A198951
#{1,3,5}:Not in OEIS
#{1,4,5}:Not in OEIS
#{2,3,4}:Not in OEIS
#{2,3,5}:Not in OEIS
#{2,4,5}:Not in OEIS
#{3,4,5}:Not in OEIS
#{1,2,3,4}:A36766 
#{1,2,3,5}:Not in OEIS
#{1,2,4,5}:Not in OEIS
#{1,3,4,5}:Not in OEIS
#{2,3,4,5}:Not in OEIS
#{1,2,3,4,5}:A36767

################################################################################