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