Enumeration of Random Walk Positions in $L_1$-norm ball in ${\mathbb{Z}}^d$

In this paper, we mainly concerned about deriving the general formula to count the possible positions of $n$ step random walk in ${\mathbb{Z}}^d$ with unit length in each step, which we denoted as $\mathrm{\mid }{P}_n^d\mathrm{\mid }$. For our results, we firstly propose a recurrence relation of the counting formula: $\mathrm{\mid }{P}_n^{d+1}\mathrm{\mid }=\mathrm{\mid }{P}_n^d\mathrm{\mid }+2{\sum }_{k=0}^{n-1}\mathrm{\mid }{P}_k^d\mathrm{\mid }$. Next, we propose two methods in deriving the explicit formula of $\mathrm{\mid }{P}_n^d\mathrm{\mid }$ using generating functions and Faulhaber’s formula. Finally, we reached our main theorem in the matrix representation of our formula.