#OK to post homework
#Sam Minkin, 10/11, Assignment 9

Problem 1:

(i). What is the coefficient of x^50y^50 in the bi-Taylor expansion of the rational function: 1/(1 - x - 7*y + 1*x*y - 3*x^3 + 6*y^3)?

Running DiagSeq2(f, x, y, 50), the 50th element is:
21862648522381747226993387094644161605561305426292740991832109948387676744271

(ii). In how many ways can you walk from [0,0,0] to [30,30,30] if the fundamental ("atomic") steps are {[1,9,8], [7,1,1], [1,9,9]}?

Running DiagWalks3D({[1, 9, 8], [1, 9, 9], [7, 1, 1]}, 30), we get:
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
So there are 0 ways to walk to [30,30,30] using the atomic steps that I used.

2. 

In this case, we have finite sequences of numbers whose elements modulus a are in S.

Suppose we have a subset S = {1,2}. Then, we want to find finite sequences who modulus the value a gives an element in S.

As an example, consider a=3, we can have a finite sequence of the form:
1, 4, 7, ..., 3n + 1 =>
x^1 + x^4 + x^7 + .. + x^(3n+1) = x * (1 + x^3 + (x^3)^2 + ... + (x^3)^n) = x * (1 - (x^3)^n) / (1 - x^3)
Since, n can vary, we have that to infinity it is given by x * 1/(1-x^3).
In general, it is x^c/(1-x^a)

So our procedure is:

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

- What is the number of ways of walking from 0 to 100 where all positive steps are allowed except multiples of 5?

In this case, we want to exclude multiples of 5, meaning that if x % 5 = 0, then it should be excluded. So, if we choose a = 5, and S = {1,2,3,4} then we will have all numbers such that x % 5 != 0, as we desired.

The generating function corresponding to WordsMod(5,{1,2,3,4},x) is:
f:=(x - 1)*(x^4 + x^3 + x^2 + x + 1)/(x^5 + x^4 + x^3 + x^2 + x - 1)

Next, we can get the number of ways of walking from 0 to 100 by looking at the coefficients of the expansion of our generating function as a power series:

Running, GFseq(f, x, 100)[101], we get:
118272656870560296827634782280

Problem 3:

S: set whose elements should be excluded from the walk sequence
For example, if S = {1,2,3}, then our generating function would be:
f = 1/1 - (x^4 + x^5 + x^6 ... ) = 1/(1 - (x/1-x - x^1 - x^2 - x^3))

In general our generating function should be:
f = 1/(1 - (x/1-x - sum(x^s, s in S)).
The procedure which outputs this function is:

ResComps:=proc(S,x) local s:
factor(1/(1 - (x/(1-x) - add(x^s, s in S)))):
end:

Then, the generating function corresponding to ResComps({2,3},x) is:
f:=(x - 1)/((x^2 - x + 1)*(x^2 + x - 1))

The number of walks excluding those of size 2 and 3 from 0 to 300 is given by GFseq(f,x,300)[301]:
179789662603291780480882832586094549526183607154633616127794901

Problem 4:

(i). DiagWalks2D({[0,1],[1,0]},40);
Output: [1, 2, 6, 20, 70, 252, 924, 3432, 12870, 48620, 184756, 705432, 2704156, 10400600, 40116600, 155117520, 601080390, 2333606220, 9075135300, 35345263800, 137846528820, 538257874440, 2104098963720, 8233430727600, 32247603683100, 126410606437752, 495918532948104, 1946939425648112, 7648690600760440, 30067266499541040, 118264581564861424, 465428353255261088, 1832624140942590534, 7219428434016265740, 28453041475240576740, 112186277816662845432, 442512540276836779204, 1746130564335626209832, 6892620648693261354600, 27217014869199032015600, 107507208733336176461620]

OEIS: A000984

gfun[listtorec](L, f(n)):
[{(-n - 2) f(n + 2) + (6 + 4 n) f(n + 1), f(0) = 1, f(1) = 2}, ogf]


(ii). DiagWalks2D({[0,1],[1,0],[1,1]},40);

Output: [1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, 1462563, 8097453, 45046719, 251595969, 1409933619, 7923848253, 44642381823, 252055236609, 1425834724419, 8079317057869, 45849429914943, 260543813797441, 1482376214227923, 8443414161166173, 48141245001931263, 274738209148561921, 1569245074591690083, 8970232353223635949, 51313576749006450879, 293733710358893793729, 1682471873186160624243, 9642641465118083682429, 55294491352291112747007, 317241780630136241094657, 1820991621200098527441027, 10457362855894862001750669, 60078868458555230983696959, 345299757825442889707393857, 1985346154034162284608274707, 11419126147845924397833900957, 65701922725618214591910684159, 378150244155138145169182750209]

OEIS: A001850

gfun[listtorec](L, f(n)):
[{(-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]


(iii). DiagWalks2D({[0,1],[1,0],[0,2],[2,0]},40);
  
Output: [1, 2, 14, 84, 556, 3736, 25612, 177688, 1244398, 8777612, 62271384, 443847648, 3175924636, 22799963576, 164142004184, 1184574592592, 8567000931404, 62073936511496, 450518481039956, 3274628801768744, 23833760489660324, 173679413875623368, 1267013689048017584, 9252299435205985664, 67626504432024377756, 494710324956646794296, 3621791112234327295592, 26534383313499716907504, 194529413506239838951024, 1427026630616364232856416, 10474450985957996054150576, 76924819005707350396260192, 565226994478396276874021358, 4155153128570549776415060268, 30559526512591226909700271992, 224848729555165636463415722784, 1655038891063501813947452278468, 12186822164518997043970184661512, 89769447797439589097829820560392, 661476500151656115107632518838128, 4875741284021393250978952096137064]

OEIS: A036692

gfun[listtorec](L, f(n)):
[{(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]
  
(iv). DiagWalks2D({[0,1],[1,0],[0,2],[2,0],[1,1],[2,2]},40);

Output: [1, 3, 22, 165, 1327, 10950, 92045, 783579, 6733966, 58294401, 507579829, 4440544722, 39000863629, 343677908223, 3037104558574, 26904952725061, 238854984979423, 2124492829796598, 18927927904130617, 168888613467092895, 1508973226894216106, 13498652154574126523, 120886709687492946083, 1083687170568092836350, 9723660300694365146989, 87322023363899721467343, 784797155029928933462614, 7058384549327774062817985, 63525027490219905080597647, 572078727948766828614679830, 5154896021503193637126695629, 46475144470335949808346622587, 419221380265186873217492981134, 3783331574173309950816296187025, 34158702327707968075053323650645, 308541107632605100591602320772210, 2788040608584603973862476702488265, 25202873888846971990310549726981859, 227906767043212151853904258820045110, 2061638450059846741700344736532466833, 18655567955631232569396589476504942877]

OEIS: A192365

gfun[listtorec](L, f(n));
FAIL
(No linear recurrence found).

Problem 5:

(i). DiagWalks3D({[1,0,0],[0,1,0],[0,0,1]}, 50);

OEIS: A006480

gfun[listtorec](L, f(n)):
[{(-27*n^2 - 81*n - 60)*f(n + 1) + (n^2 + 4*n + 4)*f(n + 2), f(0) = 1, f(1) = 6}, ogf]


(ii). DiagWalks3D({[0,0,1],[0,1,0],[0,0,1],[1,1,0],[1,0,1],[0,1,1]}, 50);

OEIS: A268542

gfun[listtorec](L, f(n)):
[{(-567*n^3 - 4104*n^2 - 9549*n - 7140)*f(n + 1) + (-1281*n^3 - 10553*n^2 - 28546*n - 25400)*f(n + 2) + (-672*n^3 - 6208*n^2 - 18752*n - 18400)*f(n + 3) + (42*n^3 + 430*n^2 + 1424*n + 1504)*f(n + 4), f(0) = 1, f(1) = 4, f(2) = 42, f(3) = 520}, ogf]


(iii). DiagWalks3D({[0,0,1],[0,1,0],[0,0,1],[1,1,0],[1,0,1],[0,1,1],[1,1,1]}, 50);

OEIS: A112019

gfun[listtorec](L, f(n)):
[{(-59*n^3 - 448*n^2 - 1084*n - 848)*f(n + 1) + (-295*n^3 - 2535*n^2 - 7185*n - 6740)*f(n + 2) + (-2301*n^3 - 22074*n^2 - 69941*n - 73044)*f(n + 3) + (118*n^3 + 1250*n^2 + 4336*n + 4896)*f(n + 4), f(0) = 1, f(1) = 5, f(2) = 55, f(3) = 749}, ogf]


Problem 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: