# 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
#####################################################################################