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