#OK to post homework
#Kent Mei, 10/11/20, Assignment 9

#---------------------------------
#Part 1

#Part i)

#The rational function is 1/(1-1*x-8*y+1*x*y-1*x^3+4*y^3).
#DiagSeq2(1/(1-1*x-8*y+1*x*y-1*x^3+4*y^3),x,y,50)[51] = 16000961263620911475625551503754832839109175200771835149196347298503108429137 
#which is the coefficient of x^50y^50 in the bi-Taylor expansion.

#Part ii)

#Fundamental atomic steps are {[1,6,9], [8,1,1], [1,6,6]}
#DiagWalks3D({[1,6,9], [8,1,1], [1,6,6]},30)[31] = 0.
#There are no ways to get from (0,0,0) to (30,30,30) using the above fundamental steps.


#---------------------------------
#Part 2

#Seems exactly like the CompsGFCon procedure from lecture 8.

WordsMod:=proc(a,S,x) local s:

factor(1/(1-add(x^s, s in S)/(1-x^a))):

end:

#GFseq(WordsMod(5,{1,2,3,4},x),x,100)[101]
#There are 118272656870560296827634782280 ways to walk from 0 to 100 where all positive steps are allowed except multiples of 5.


#---------------------------------
#Part 3

ResComps:=proc(S,x) 

factor(1/(1-(x/(1-x))+add(x^s, s in S)))

end:

#GFseq(ResComps({2,3},x),x,300)[301] 
#There are 179789662603291780480882832586094549526183607154633616127794901 number of walks from 0 to 300 where every step-size is permitted except 2 and 3.


#---------------------------------
#Part 4

#Part i)

#The sequence is in the OEIS as A984.
#[{(-n-2)*f(n+2)+(6+4*n)*f(n+1), f(0) = 1, f(1) = 2}, ogf]

#Part ii)

#The sequence is in the OEIS as A1850.
#[{(-n-3)*f(n+3)+(15+6*n)*f(n+2)+(-n-2)*f(n+1), f(0) = 1, f(1) = 3, f(2) = 13}, ogf]

#Part iii)

#The sequence is in the OEIS as A36692.
#[{(352*n^3+2768*n^2+7088*n+5920)*f(n+1)+(-484*n^3-4048*n^2-11184*n-10204)*f(n+2)+(-352*n^3-3120*n^2-9114*n-8766)*f(n+3)+(55*n^3+515*n^2+1570*n+1560)*f(n+4), f(0) = 1, f(1) = 2, f(2) = 14, f(3) = 84}, ogf]

#Part iv)

#The sequence is in the OEIS as A192365.
#It doesn't seem to work for N = 40. There doesn't seem to be a good guess for a recursive sequence.


#---------------------------------
#Part 5
#(I think all the sets have typos where [0,0,1] is in the set instead of [1,0,0])

#Part i)

#I think there was a typo. For the set given, the sequence is [1,0,0,0,...]. But I think the actual set should be {[1,0,0],[0,1,0],[0,0,1]}.

#The sequence is in the OEIS as A6480.
#[{(-27*n^2-81*n-60)*f(n+1)+(n^2+4*n+4)*f(n+2), f(0) = 1, f(1) = 6}, ogf]

#Part ii)

#The sequence is in the OEIS as A268550.
#[{(-27*n^3-216*n^2-537*n-420)*f(n+1)+(-108*n^3-972*n^2-2856*n-2760)*f(n+2)+(-107*n^3-1070*n^2-3555*n-3924)*f(n+3)+(2*n^3+22*n^2+80*n+96)*f(n+4), f(0) = 1, f(1) = 12, f(2) = 366, f(3) = 13800}, ogf]

#Part iii)

#The sequence is in the OEIS as A126086.
#[{(3*n^3+23*n^2+56*n+44)*f(n+1)+(-9*n^3-78*n^2-221*n-206)*f(n+2)+(171*n^3+1653*n^2+5281*n+5570)*f(n+3)+(-3*n^3-32*n^2-112*n-128)*f(n+4), f(0) = 1, f(1) = 13, f(2) = 409, f(3) = 16081}, ogf]


#---------------------------------
#Part 6

DiagSeq4:=proc(f,x1,x2,x3,x4,N) local i:

if subs({x1=0,x2=0,x3=0,x4=0},denom(f))=0 then
 print(`The denominator of`, f, `should have a non-zero constant term `):
 RETURN(FAIL):
fi:

[seq(coeff(taylor(coeff(taylor(coeff(taylor(coeff(taylor(f,x1=0,N+1),x1,i),x2=0,N+1),x2,i),x3=0,N+1),x3,i),x4=0,N+1),x4,i),i=0..N)]:

end:


DiagWalks4D:=proc(S,N) local s,x1,x2,x3,x4:
if not (type(S, set) and type(N,integer) and N>=0) then
 print(`Bad input`):
 RETURN(FAIL):
fi:

DiagSeq4(1/(1-add(x1^s[1]*x2^s[2]*x3^s[3]*x4^s[4], s in S)),x1,x2,x3,x4,N ) :

end:

#---------------------------------
#Part 7

DiagSeqk:=proc(k,x,f,N) local i, j, expr, Ans:

if subs({seq(x[i] = 0, i= 1..k)},denom(f))=0 then
 print(`The denominator of`, f, `should have a non-zero constant term `):
 RETURN(FAIL):
fi:

Ans := []:

for i from 0 to N do
 for j from 1 to k do 
  if j = 1 then
  	expr := coeff(taylor(f,x[1]=0,N+1),x[1],i):

  else
  	expr := coeff(taylor(expr,x[j]=0,N+1),x[j],i):
  fi:
 od:
 Ans := [op(Ans), expr]:
od:

Ans:

end:



DiagWalkskD:=proc(k,S,N) local s, i:
if not (type(S, set) and type(N,integer) and N>=0 and type(k,integer) and k>=0) then
 print(`Bad input`):
 RETURN(FAIL):
fi:

DiagSeqk(k,x,1/(1-add(product(x[i]^s[i],i = 1..k), s in S)), N):

end:

#DiagWalkskD(5,{[0,0,0,0,1],[0,0,0,1,0],[0,0,1,0,0],[0,1,0,0,0],[1,0,0,0,0]},30) = 
#[1, 120, 113400, 168168000, 305540235000, 623360743125120, 1370874167589326400, 3177459078523411968000, 7656714453153197981835000, 19010638202652030712978200000, 48334775757901219912115629238400, 125285878026462826569986857692288000, 329981831728425465309559251123033960000, 880904182555008823696060440775388083200000, 2378829279642818668557063558238537401024000000, 6488042236961891255293961040027911906585223168000, 17849652006367453441718319866826741334636604727435000, 49483489990691693514084754590623288847484101183928200000, 138111769240983764138112371984550958225339753129069359000000, 387816525421519997289404915382104310119595585522072549480000000, 1094915415525119820987225688309818220883072063883928031640993360000, 3106458136225250035939783180023922881957330505387169213085457747200000, 8852882145761863169024674569386279453404139518181309940509640340944000000, 25331892668172071335880887078820346794321175621094961817855799600366080000000, 72755444168359390781419086354177426080495033866603529785192512490019730225000000, 209675392008150744000792141397774335773205539928916448379146355606377497864093125120, 606175001373847188137092096519711291361683024323497370397731028649290432388133673574400, 1757578114236476972213710302850757683565360442178523640238228161664471827121737281937408000, 5109823239599689705035460336005873315860909697805055045277926779110563034354221172077084160000, 14893263607816643017066328440633338030833583983586243000335745992116811166824202362289425203200000, 43510396035467823424176446506017461718722415850356251193016875748191038270605101838303678118004326400]

#It is in the OEIS as sequence A8978.


#DiagWalkskD(5,{[0,0,0,0,1],[0,0,0,1,0],[0,0,1,0,0],[0,1,0,0,0],[1,0,0,0,0],[1,1,1,1,1]},30)
#[1, 121, 114121, 169417921, 308238414121, 629799991355641, 1387152264043496161, 3220175519103433952161, 7771784978946238318454761, 19326687177288750280293146161, 49215884415076728067274047737961, 127771596843320597524806463425540481, 337062262660060823184775010238222648481, 901234166879496857175124242700615007966881, 2437596832482572040871174118497997542520724481, 6658899956062028781628193808327568261182848184481, 18348867861757695691806466888058805891243925190241001, 50948444532733813437405325550146559204731159526335080001, 142427124406632073029017531714651626499980154768375338027201, 400571463991854235526828056620464756837624498187955181355339001, 1132729402549301509677356709860392397264050489978212445682778961801, 3218868310555279819326992709267643811038435737429918837514988149831321, 9187866026204518478209054754409852039688856178003637864603125021311200321, 26332374415250899329797363809607667197130936416830530512697500502773880004321, 75749612499237921274787363988469606613321865791455829196211915356019080295348321, 218652793142807873344927725745139374015034689563172286390112554756722834906801968841, 633137929644008205946174883927024705976118568437317454261868226412397931755176096415761, 1838686872073198548168554351721405007974978579006972696929427385657796269301672196203918761, 5354167117735517687032641333532311498885973199734416455961892212230120575133684939097387538561, 15630356958383957846461352438095058842805645249863370363131910845638675743349470678004195804701761, 45736727992276014537478832205052890593105000294400354315898503894862128236831617568042132585313883681]

#It is in the OEIS as sequence A82489.