# Matthew Russell
# Experimental Math
# Homework 13
# I give permission to post this

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

read `public_html/em12/C13.txt`;

# Using GuessH1(L,ORD,DEG,n,N) as a subroutine, write a procedure GuessH(L,n,N) that
# tries to guess a linear recurrence operator with polynomial coefficients, ope, phrased
# in terms of the discrete variable n and the corresponding shift operator, N
# (where Nf(n):=f(n+1)), of order+degree as small as possible, and within the same order+degree,
# with order as small as possible, annihilating the sequence L. If there is no such operator
# with (1+order)*(1+degree)+6 ≤ nops(L), return FAIL. If the conjectured operator, ope,
# has (1+order)*(1+degree)+6 < nops(L) then it should be checked that ope annihilated
# the whole list L (and if it does not, it should keep trying until (1+order)*(1+degree)+6=nops(L) )

GuessH:=proc(L,n,N) local len, ord, deg, G:

len:=nops(L):

for ord from 1 while (ord+1)+6<=len do
	for deg from 0 while (ord+1)*(deg+1)+6<=len do
		G:=GuessH1(L,ord,deg,n,N):
		if G<>`FAIL` and DoesAnnihilate(L,ord,deg,G) then
			return G:
		fi:
	od:
od:

return `FAIL`:

end:

DoesAnnihilate:=proc(L,ord,deg,G)

return evalb({seq(add(add(coeff(coeff(G,N,i),n,j)*L[k+i]*k^j,i=0..ord),j=0..deg),k=1..nops(L)-ord)}={0}):

end:

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

# By using LIF(P,u,N), write a procedure OTN(S,N) that inputs a set of
# non-negative integers, S, and outputs the list of non-neg. integers, let's
# call it L, 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. For example,
# OTN({0,2},7);
# should give
# [1,0,1,0,2,0,5]
# and OTN({0,1,2},7);
# should give the first seven terms of the Motzkin numbers sequence.

OTN:=proc(S,N)

return LIF(add(u^s,s in S),u,N):

end:

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

# Write a program AllOTN(S,N) that inputs a set S and outputs the
# set {[S1,OTN( {0} union S1,N)]} for all subsets S1 of S .

AllOTN:=proc(S,N) local S1:

return {seq([S1,OTN({0} union S1,N)],S1 in combinat[powerset](S))}

end:

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

# By looking at the output of
# AllOTN({1,2,3,4,5},20);
# find out which of the 32 subsets, S1, of {1,2,3,4,5},
# have the property that the number of ordered trees where the number
# of children of every vertex must belong to 0 union S1 is currently in the OEIS. 

# {}:		A000007
# {1}:		A000012
# {2}:		A126120
# {3}:		---
# {4}:		---
# {5}:		---
# {1,2}:	A001006
# {1,3}:	A071879
# {1,4}:	A127902
# {1,5}:	---
# {2,3}:	A001005
# {2,4}:	---
# {2,5}:	---
# {3,4}:	---
# {3,5}:	---
# {4,5}:	---
# {1,2,3}:	A036765
# {1,2,4}:	---
# {1,2,5}:	---
# {1,3,4}:	A198951
# {1,3,5}:	---
# {1,4,5}:	---
# {2,3,4}:	---
# {2,3,5}:	---
# {2,4,5}:	---
# {3,4,5}:	---
# {1,2,3,4}:	A036766
# {1,2,3,5}:	---
# {1,2,4,5}:	---
# {1,3,4,5}:	---
# {2,3,4,5}:	---
# {1,2,3,4,5}:	A036767

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