# Matthew Russell # Experimental Math # Homework 19 # I give permission to post this read `public_html/em12/C19.txt`: read `public_html/em12/hw18.txt`: read `public_html/em12/C6.txt`: ##################################################################################### # By using Wn(A,FP,B,n), with A={0,1}, and appropriate FP, # that you have to program yourself, write a procedure NdnC(d,n), that finds, in a clever way, Nd(n). # [Hint, the largest "difference" an AP of size d in {1, ...n} can have is (n-d)/(d-1)] NdnC:=proc(d,n) local A,FP: A:={0,1}: FP:=SFP(d,n): return Wn(A,FP,B,n): end: ##################################################################################### # Modify Wn(A,FP,B,n) to procedure # WnX(A,FP,B,n,x) # (using an analog/extension of WnG(A,FP,B,n) that you may call WnGX(A,FP,B,n,x)) # that outputs not just the number of words of length n avoiding the set of # patterns in FP but the weight enumerator where the weight of a word # a1 a2 a3 ... an # is # x[a1]x[a2] ... x[an] # For example # WnX({1,2},{[1,B,1]},B,3,x); # should return # expand((x[1]+x[2])^3-x[1]*(x[1]+x[2])*x[1]); # [Hint: It is a minor pogramming modification in the line: # co:=co+WGn(A,FP,B,n-1,BFP1): ] WnX:=proc(A,FP,B,n,x) return WGnX(A,FP,B,n,{},x): end: WGnX:=proc(A,FP,B,n,BFP,x) local counter,a,BFP1: option remember: if member([],BFP union FP) then return 0: fi: if n=0 then return 1: fi: counter:=0: for a in A do BFP1:=AdjustBFP(a,B,FP,BFP): counter:=expand(counter+x[a]*WGnX(A,FP,B,n-1,BFP1,x)): od: return counter: end: ##################################################################################### # Using your # WnX(A,FP,B,n,x) # with A={0,1}, write a procedure # adnC(d,n) # that computes ad(n) cleverly. # [Hint: similar to NdnC(d,n), but now you need the degree of x[1] in the weight-enumerator.] adnC:=proc(d,n) local A,FP: A:={0,1}: FP:=SFP(d,n): return degree(WnX(A,FP,B,n,x),x[1]): end: ##################################################################################### # [Human Problem]: Using generatingfunctionology and linear algebra, # prove that for any finite set of finite patterns, the "infinite sequence" # [seq(Wn(A,FP,B,n), n=1..infinity)]: # is C-finite. # Let A be an alphabet and let FP be a finite set of finite patterns containing elements # of A, along with (possibly) a blank B. Let N be the length of the longest forbidden pattern. # (In progress) ##################################################################################### # Believing your proof (or believing me), interface # Wn(A,FP,B,n) # With GuessRec(L) of C6.txt, to write a procedure # WnR(A,FP,B,N) # that uses the first N terms of Wn(A,FP,B,n) to try and guess a C-finite description of that sequence (or return FAIL). WnR:=proc(A,FP,B,N) local L: L:=[seq(Wn(A,FP,B,n),n=1..N)]: return GuessRec(L): end: # What are: # WnR({1,2},{[1,1]},B,60); # = [[-1, -1], [2, 3]] # WnR({0,1},{[1,1,1],[0,0,0]},B,60); # = [[-1, -1], [2, 4]] # WnR({0,1},{[1,1,1,1],[0,0,0,0]},B,60); # = [[-1, -1, -1], [2, 4, 8]] # WnR({a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}, {[d,o,r,o,n],[d,B,o,B,r,B,o,B,n]},B,100); # (Note: fixed to include `v` in the alphabet) # = [[-26, 0, 0, 0, 2, -26, 676, -17576, 456976, -1, 26, 0, 0, 0, -3, 26, -1352, 0, 0, 0, 0, 0, 0, 0, 1], # [26, 676, 17576, 456976, 11881375, 308915724, 8031808148, 208826994272, 5429500937120, # 141167000602370, 3670341397830146, 95428860279966824, 2481149949625113728, 64509887831250168736, # 1677256801278467538269, 43608669492556433587452, 1133825215948714586103456, 29479450652365844680379856, # 766465587941714581179849616, 19928101931970411885560383365, 518130563013877042540242072648, # 13471392370709989493023397440900, 350256142679548497482735104595720, 9106658176736827011456605811559488, # 236773072738946929326737191050813688]]