I'm trying to come up with the formula describing the number of paths on hexagonal lattice of length $$2n$$ that start at the origin $$O$$ and go back to $$O$$ but doing so for the first time at step $$2n$$ (i.e. first return to the origin).
Suppose I already have a formula for the number of such paths but without the condition of returning for the first time at step $$2n$$. Is there a way to go through this formula to the one I'm looking for? For example, through generating functions, etc?

• Assume that two sequences satisfy $f(n)=g(n)f(0)+g(n-1)f(1)+\dots+g(1)f(n-1)$ for all $n \ge 1$, with the initial condition $f(0)=g(0)=1$. Then it is not hard to see that their generated functions satisfy $F(x)-1=F(x)G(x)-F(x)$, i.e., $G(x) = 2-F^{-1}(x)$. Jul 12, 2022 at 19:55
• @ArseniiSagdeev, but is there actually a way to sum the series $F(x)$ in order to find $G(x)$ (the formula for $g(n)$ is quite complex)? And if so, would it help to find an analytical formula for $f(n)$?
– A. G
Jul 12, 2022 at 20:22
• If there are $f(n)$ paths of length $n$ from O to O, then I think the number of paths first coming back to O at $n$ is $f(n) - \sum_{i+j=n}f(i)f(j) + \sum_{i+j+k=n}f(i)f(j)f(k) - \dots$
– user44143
Jul 13, 2022 at 1:22
• @ArseniiSagdeev, I guess the links for the sequences of numbers you provided describe slightly different walks, i.e. the walks that move on a tile space, not along the edges... Probably, I should have written the question more clearly, but I'm looking for paths that go along the edges (between vertices) on a hexagonal lattice.
– A. G
Jul 13, 2022 at 9:06
• No, it's over a different graph. There are two interpretations of the term "hexagonal lattice": one is a lattice in the vector algebra sense and gives a graph where each vertex has degree six; the other gives the honeycomb graph where each vertex has degree 3. The desired walks in the latter aren't in OEIS, but this Sage code calculates them. Jul 14, 2022 at 13:58