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?
$\begingroup$
$\endgroup$
13
-
$\begingroup$ 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)$. $\endgroup$– Arsenii SagdeevCommented Jul 12, 2022 at 19:55
-
$\begingroup$ @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)$? $\endgroup$– A. GCommented Jul 12, 2022 at 20:22
-
2$\begingroup$ 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$ $\endgroup$– user44143Commented Jul 13, 2022 at 1:22
-
1$\begingroup$ @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. $\endgroup$– A. GCommented Jul 13, 2022 at 9:06
-
1$\begingroup$ 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. $\endgroup$– Peter TaylorCommented Jul 14, 2022 at 13:58
|
Show 8 more comments