#OK to post
#Soham Palande, Assignment 15, 11/01/2020




#PART 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..n),seq([i,0],i=-n..-1),seq([0,i],i=1..k),seq([0,i],i=-k..-1)}:

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:


#EXAMPLE

RoG(3,10)
[{2, 3, 4, 11, 21}, {1, 3, 4, 5, 12, 22}, {1, 2, 4, 5, 6, 13, 23}, {1, 2, 3, 5, 6, 7, 14, 24}, {2, 3, 4, 6, 7, 8, 15, 25}, {3, 4, 5, 7, 8, 9, 16, 26}, {4, 5, 6, 8, 9, 10, 17, 27}, {5, 6, 7, 9, 10, 18, 28}, {6, 7, 8, 10, 19, 29}, {7, 8, 9, 20, 30}, {1, 12, 13, 14, 21}, {2, 11, 13, 14, 15, 22}, {3, 11, 12, 14, 15, 16, 23}, {4, 11, 12, 13, 15, 16, 17, 24}, {5, 12, 13, 14, 16, 17, 18, 25}, {6, 13, 14, 15, 17, 18, 19, 26}, {7, 14, 15, 16, 18, 19, 20, 27}, {8, 15, 16, 17, 19, 20, 28}, {9, 16, 17, 18, 20, 29}, {10, 17, 18, 19, 30}, {1, 11, 22, 23, 24}, {2, 12, 21, 23, 24, 25}, {3, 13, 21, 22, 24, 25, 26}, {4, 14, 21, 22, 23, 25, 26, 27}, {5, 15, 22, 23, 24, 26, 27, 28}, {6, 16, 23, 24, 25, 27, 28, 29}, {7, 17, 24, 25, 26, 28, 29, 30}, {8, 18, 25, 26, 27, 29, 30}, {9, 19, 26, 27, 28, 30}, {10, 20, 27, 28, 29}], [[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [1, 9], [1, 10], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [2, 9], [2, 10], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [3, 7], [3, 8], [3, 9], [3, 10]]


The first few terms of the number of closed Hamiltonian paths (Hamiltonian Cycles) starting at 1 in a 3 * n graph

seq(SAWnu(RoG(3,n)[1]),n=1..6)
0, 6, 96, 3132, 84192, 1821912


#This sequence is NOT in the OEIS. 



#PART 2

#The total number of walks from [0,0] to [40,40] using the given atomic steps

NuW([40,40],{[1,0],[0,1],[1,1],[2,2]})
   2382564832244243056285491057263


#The total number of walks from [0,0] to [40,40] using the given atomic steps that stay in x>=y (that is, they stay under x=y)

NuGW([40,40],{[1,0],[0,1],[1,1],[2,2]})
	89322096703094945357683861273



#the first 20 terms of of the sequence enumerating walks from [0,0,0] to [n,n,n] with atomic steps #{[1,0,0],[0,1,0],[0,0,1],[1,1,1]}

SeqW({[1,0,0],[0,1,0],[0,0,1],[1,1,1]},20)

[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 x ≥ y ≥ z

SeqGW({[1,0,0],[0,1,0],[0,0,1],[1,1,1]},20)
[2, 10, 88, 1043, 14778, 236001, 4107925, 76314975, 1491934038, 30389576308, 640286048416, 13877540824735, 308102204007536, 6983346070924707, 161156356282624227, 3778249609096250059, 89826197363219012470, 2162338803354415120414, 52637415804379149938876, 1294313658632145337351381]