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