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?
 A: 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}$. 
Observe also that this answer is the same as in the square lattice, and it seems this estimate should hold for more general tilings. See also Random walk on a Penrose tiling.
A: This is answered by Ian Agol here, with the reference "All Roads Lead to Rome-Even in the Honeycomb World", Brani Vidakovic, Amer. Statist. 48 (1994) no. 3, 234-236.
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$.
