# what is the number of paths returning to 0 on the hexagonal lattice

I am looking for an estimation of the number of paths of length $$n$$ going from 0 to 0 on the hexagonal (or honeycomb) lattice.

I can find plenty on references on self avoiding paths, but I am looking into every paths. Is it considerably more difficult? Has anyone a reference?

• It should be easier: you are just looking for a diagonal entry on a power of a certain infinite adjacency matrix. May 5 '20 at 15:05
• For any finite graph $G$, if $A$ is its adjacency matrix, then $(A^n)_{ij}$ counts the number of walks from $i$ to $j$ of length $n$. So take the adjacency matrix for the lattice up to, say, $n/2$, and compute its powers. May 5 '20 at 15:05
• This is OEIS A002898 (oeis.org/A002898). May 5 '20 at 16:51

An exact formula is $$p(n) = \sum_{k=0}^m \binom{2k}{k} \binom{m}{k}^2$$ if $$n= 2m$$ is even, and $$0$$ otherwise. This is sequence A002893 on OEIS.
According to OEIS, the number of paths is asymptotic to $$p(n) \sim \frac{1}{2\pi n} 3^{n + 3/2}$$ when $$n$$ is even, which agrees with the estimate given by shurtados. In the above reference, Vidakovic proves that $$p(n) \geq C \cdot {3^n}/{n}$$ for some constant $$C$$.
If you want a rough answer, it is something of the order of $$\frac{3^n}{n}$$. This random paths are easier than self avoiding walks, you can think of these paths in this way: If you consider the even steps, these paths describe a random walk in a triangular lattice, which is a bit easier to describe. Each step $$X_i$$ is given by adding a sixth root of unity $$\rho^{j}$$, $$j= 1,2,\dots, 6$$. And we want to understand when $$S_n = X_1 + X_2 + \dots X_n$$ is equal to zero. After $$n$$ steps what you have $$S_n = A_n 1 + B_n\rho + C_n \rho^2 = (A_n - C_n)1 + (B_n + C_n)\rho$$ (here I'm using the fact that $$\rho^2 = \rho -1$$). You want to estimate the probability that $$A_n - C_n = 0$$ and $$B_n + C_n = 0$$.
I think the heuristic is that $$A_n, B_n, C_n$$ behave like standard random walks in the line (This is also true for $$A_n - C_n$$, and $$B_n + C_n$$) and so the probability of $$A_n - C_n = 0$$ or that $$B_n - C_n = 0$$ is of the order of $$\frac{1}{\sqrt{n}}$$, if these events were independent this gives you $$(\frac{1}{\sqrt{n}})^2 = \frac{1}{n}$$.