Self-avoiding walks and Fibonacci numbers
Arthur T. Benjamin · The Fibonacci Quarterly · 2006
By combinatorial arguments, we prove that the number of self-avoiding walks on the strip {0, 1} × ℤ is 8Fn – 4 when n is odd and is 8Fn – n when n is even. Also, when backwards moves are prohibited, we derive simple expressions for the number of length n self-avoiding walks on {0, 1} × ℤ, ℤ × ℤ, the triangular lattice, and the cubic lattice.