Enumeration of Walks in the Square Lattice According to Their Areas

We study the area distribution of closed walks of length \( n \), starting and ending at the origin. The concept of algebraic area of a walk in the square lattice is slightly modified and the usefulness of this concept is demonstrated through a simple argument. The idea of using a generating function of the form \( (x + x^{-1} + y + y^{-1})^n \) to study these walks is then discussed from a special viewpoint. Based on this, a polynomial time algorithm for calculating the exact distribution of such walks for a given length is concluded. The presented algorithm takes advantage of the Chinese remainder theorem to overcome the problem of arithmetic with large integers. Finally, the results of the implementation are given for \( n = 32, 64, 128 \).