Combinatorics Meets Potential Theory

Philippe D'Arco, Valentina Lacivita, Sami Mustapha


Using potential theoretic techniques, we show how it is possible to determine the dominant asymptotics for the number of walks of length $n$, restricted to the positive quadrant and taking unit steps in a balanced set $\Gamma$.

The approach is illustrated through an example of inhomogeneous space walk. This walk takes its steps in $\{ \leftarrow, \uparrow, \rightarrow, \downarrow \}$ or $\{ \swarrow, \leftarrow, \nwarrow, \uparrow,\nearrow, \rightarrow, \searrow, \downarrow \}$, depending on the parity of the coordinates of its positions. The exponential growth of our model is $(4\phi)^n$, where $\phi= \frac{1+\sqrt 5}{2}$denotes the Golden ratio, while the subexponential growth is like $1/n$.

As an application of our approach we prove the non-D-finiteness in two dimensions of the length generating functions corresponding to nonsingular small step sets with an infinite group and zero-drift.


Lattice path enumeration; analytic combinatorics in several variables; discrete potential theory; discrete harmonic functions

Full Text: PDF