#OK to post
#Sam Minkin, 11/01, Assignment 15

QUESTION #1:

#RoG(k,n): The Rook graph on a k by n board
RoG:=proc(k,n) local V,E,i,j,T1,v,Neighs,Moves,m,pt:

#The set the list of  vertices in the k by n board (using matrix indexing)
V:=[seq(seq(seq([i,j],j=1..n),i=1..k))]:

#T1 is a labelling of the vertices in V

for i from 1 to nops(V) do
T1[V[i]]:=i:
od:

#E is a list such that its i-th entry is the set of neighbors of V[i] using the above-indexing

E:=[]:

for i from 1 to nops(V) do
 pt:=V[i]:

Moves:={seq([i,0],i=1..(k-1)), seq([0,i],i=1..(n-1)),seq([0, -i], i = 1..(n-1)), seq([-i, 0],i = 1..(k-1))}:
#There are up to 8 neighbors of any vertex 
Neighs:={seq(pt+m,m in Moves)}:

#But many of them fall off the board, 
Neighs:=Neighs intersect convert(V,set):

#We append to the "list of neighbors" the set of neighbors of the current vertex BUT in terms of their "ids" (given by T1)
#getting a description of the graph in "cannical form"
E:=[op(E),{seq(T1[v],v in Neighs)}]:
od:

#We return the graph in "canonical form" where the vertices (members of V), are labelled by positive inetegers from 1 to nops(V)
#together with the "dictionary"
E,V:
end:

We have that seq(SAWnu(RoG(3, i)[1]), i = 1 .. 6) returns:
2, 6, 96, 3132, 252240, 36307440

This sequence is not in the OEIS.


QUESTION #2:

(i) ComboProj2.txt

We can find the number of walks from [0,0] to [40,40] using the NuW function:
NuW([40,40],{[1,0],[0,1],[1,1],[2,2]}) returns:
2382564832244243056285491057263

To find the number of walks that never go above x=y, we can subtract the number of good walks from the number of walks:
evalf(NuW([40,40],{[1,0],[0,1],[1,1],[2,2]}) - NuGW([40,40],{[1,0],[0,1],[1,1],[2,2]})) returns:
2.293242735541148110927807195990*10^30

(ii) ComboProj3.txt

We can find the first 20 terms of the sequence enumerating walks from [0,0,0] to [n,n,n] by running InfoA({[1,0,0],[0,1,0],[0,0,1],[1,1,1]},n,N,20,5,2):
[7, 115, 2371, 54091, 1307377, 32803219, 844910395, 22188235867, 591446519797, 15953338537885, 434479441772845, 11927609772412075, 329653844941016785, 9163407745486783435, 255982736410338609931, 7181987671728091545787, 202271071826031620236525, 5715984422606794841997001, 162016571360163769411597081, 4604748196249289767697705221]

The corresponding sequence for those walks that stay in in x ≥ y ≥ z can be found using:
InfoGA({[1,0,0],[0,1,0],[0,0,1],[1,1,1]},n,N,20,5,2):
[2, 10, 88, 1043, 14778, 236001, 4107925, 76314975, 1491934038, 30389576308, 640286048416, 13877540824735, 308102204007536, 6983346070924707, 161156356282624227, 3778249609096250059, 89826197363219012470, 2162338803354415120414, 52637415804379149938876, 1294313658632145337351381]