Given a reference node at an infinitely spanning 2D grid, how can I express the number of back-tracking closed walks (closed walks that does not contain cycles) for that node in terms of L, which is the length of the walk?
Counting the number of back-tracking closed walks on a 2D grid.
2
$\begingroup$
combinatorics
graph-theory
-
1I would calculate it for $L=2,4,6$ and then look it up in the Online Encyclopedia of Integer Sequences. – 2012-07-05
1 Answers
1
I think this is the same as the number of walks of length $2n$ on the 4-regular tree beginning and ending at some fixed vertex, which is tabulated at the Online Encyclopedia of Integer Sequences. The generating function is given as ${3\over1+2\sqrt{1-12x}}$ and there's also an integral representation, ${2\over\pi}\int_0^{12}{x^n\sqrt{x(12-x)}\over16-x}\,dx$ and some other formulas.