Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
I would calculate it for $L=2,4,6$ and then look it up in the Online Encyclopedia of Integer Sequences. – Gerry Myerson Jul 5 '12 at 1:22
up vote 1 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.