#Please do not post homework
#Tifany Tong, October 11th, 2020, HW #9

# Question 1: 
# RUID: 193002246
# (i):  
# 1/(1-a[1]*x-a[2]*y+a[5]*x*y-a[6]*x^3+a[7]*y^3) = 1/(1-x-9y+xy-2x^3+2y^3)
# DiagSeq2(1/(1-x-9y+xy-2x^3+2y^3), x, y, 51)[51] = 640503789547580772832910108536674228831753426918795459020186383215412877787907137

# (ii):
# {[a[1],a[3],a[9]], [a[2], a[4], a[5], [a[4],a[3],a[3]} = {[1,3,6],[9,0,0], [0,3,3]}
# DiagWalks3D({[0, 3, 3], [1, 3, 6], [9, 0, 0]}, 30) =
#[1, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 28, 0, 0, 
#  0, 0, 0, 0, 0, 0, 220, 0, 0, 0], so the answer is 0.




# Question 2:

WordsMod := proc(a, S, x) local i, ans, s:
factor(1/(1 - add(x^s, s in S)/(1 - x^a))):
end:

# WordsMod(5, {1, 2, 3, 4}, x) =
#                 / 4    3    2        \        
#                 \x  + x  + x  + x + 1/ (x - 1)
#                 ------------------------------
#                    5    4    3    2           
#                   x  + x  + x  + x  + x - 1   

# coeff(taylor(%, x = 0, 101), x, 100) =
#                 118272656870560296827634782280

#Question 3 
ResComps := proc(S, x) local i, ans, s:
factor(1/(1 - add(x^s, s in S))):
end:

#ResComps({2, 3}, x) =
#                                1     
#                         - -----------
#                            3    2    
#                           x  + x  - 1

#coeff(taylor(%, x = 0, 301), x, 300) =
#             1783989181648501315351477258985332242

# Question 4

# gfun[listtorec](DiagWalks2D({[0, 1], [1, 0]}, 40), h(n)) =
# [{(-n - 2) h(n + 2) + (6 + 4 n) h(n + 1), h(0) = 1, h(1) = 2}, ogf]
# (DiagWalks2D({[0, 1], [1, 0]}, 40) appears as A984 in the OEIS. 

# gfun[listtorec](DiagWalks2D({[0, 1], [1, 0], [1, 1]}, 40), h(n)) =
# [{(-n - 3) h(n + 3) + (15 + 6 n) h(n + 2) + (-n - 2) h(n + 1), 
#  h(0) = 1, h(1) = 3, h(2) = 13}, ogf]
# (DiagWalks2D({[0, 1], [1, 0], [1, 1]}, 40) appears as A1850 in the OEIS. 

# gfun[listtorec](DiagWalks2D({[0, 1], [0, 2], [1, 0], [2, 0]}, 40), h(n));
#   [{(352*n^3 + 2768*n^2 + 7088*n + 5920)*h(n + 1) + (-484*n^3 - 4048*n^2 - 11184*n - 10204)*h(n + 2) + (-352*n^3 - 3120*n^2 - 9114*n - 8766)*h(n + 3) + (55*n^3 + 515*n^2 + 1570*n + 1560)*h(n + 4), h(0) = 1, h(1) = 2, h(2) = 14, h(3) = 84}, ogf]

# (DiagWalks2D({[0, 1], [0, 2], [1, 0], [2, 0]}, 40) appears as A036692 in the OEIS. 

# gfun[listtorec](DiagWalks2D({[0, 1], [0, 2], [1, 0], [1, 1], [2, 0], [2, 2]}, 40), h(n)) = FAIL

# (DiagWalks2D({[0, 1], [0, 2], [1, 0], [1, 1], [2, 0], [2, 2]}, 40) appears as A192365 in the OEIS. 


# Question 5
# gfun[listtorec](DiagWalks3D({[0, 0, 1], [0, 1, 0]}, 50), h(n)) = [{(-27*n^2 - 81*n - 60)*h(n + 1) + (n^2 + 4*n + 4)*h(n + 2), h(0) = 1, h(1) = 6}, ogf]
# This corresponds to A6480 in the OEIS. 


# gfun[listtorec](DiagWalks3D({[0, 0, 1], [0, 1, 0], [1,0,0], [0, 1, 1], [1, 0, 1], [1, 1, 0]}, 50), h(n)) = 
#   [{(-27*n^3 - 216*n^2 - 537*n - 420)*h(n + 1) + (-108*n^3 - 972*n^2 - 2856*n - 2760)*h(n + 2) + (-107*n^3 - 1070*n^2 - 3555*n - 3924)*h(n + 3) + (2*n^3 + 22*n^2 + 80*n + 96)*h(n + 4), h(0) = 1, h(1) = 12, h(2) = 366, h(3) = 13800}, ogf]
# This corresponds to A268550 in the OEIS

# gfun[listtorec](DiagWalks3D({[0, 0, 1], [0, 1, 0], [1,0,0], [0, 1, 1], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, 50), h(n)) =
# [{(3*n^3 + 23*n^2 + 56*n + 44)*h(n + 1) + (-9*n^3 - 78*n^2 - 221*n - 206)*h(n + 2) + (171*n^3 + 1653*n^2 + 5281*n + 5570)*h(n + 3) + (-3*n^3 - 32*n^2 - 112*n - 128)*h(n + 4), h(0) = 1, h(1) = 13, h(2) = 409, h(3) = 16081}, ogf]
# This corresponds to A126086 in the OEIS. 

#Question 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, x, y, z:
if not (type(S, set) and type(N, integer) and 0 <= N) 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: