1 Introduction
Counting lattice walks confined to a certain region in space is an important field of combinatorics. For recent developments on lattice walks, we refer to the surveys [Reference Humphreys9, Reference Krattenthaler and Bona11]. Let
$\mathscr {S}_d$
be the set of small steps
$\mathscr {S}_d=\{-1,0,1\}^{d}\setminus \{\mathbf {0}\}$
in the d-dimensional space. Let
$\mathscr {B}_d\not =\varnothing $
be a fixed subset of
$\mathscr {S}_d$
. Then, a
$\mathscr {B}_d$
-walk of length n in d-dimensional space starts at the origin
$\mathbf {0}$
and consists of n consecutive steps which are taken from the small step set
$\mathscr {B}_d$
.
There are many recent studies of
$\mathscr {B}_2$
-walks in the quarter plane. For
$\mathscr {B}_2=\{(1, 1), (-1, 0), (0,-1)\}$
, the
$\mathscr {B}_2$
-walks in the first quadrant are called Kreweras’ walks, first studied by Kreweras [Reference Kreweras12] in 1965. He obtained a complicated expression for the number of n-step walks ending at
$(i,j)$
. Gessel [Reference Gessel8] showed that the complete generating function (which counts all walks by the length and the coordinates of the endpoint) for Kreweras’ walks is algebraic.
Around 2001, Gessel conjectured a simple hypergeometric formula for the number of n-step
$\mathscr {B}_2$
-walks in the first quadrant ending at the origin
$\mathbf {0}$
(Gessel’s walks), where
$$ \begin{align*}\mathscr{B}_2=\{(1,0),(-1,0),(1,1),(-1,-1)\}.\end{align*} $$
Kauers et al. [Reference Kauers, Koutschan and Zeilberger10] first proved Gessel’s lattice walk conjecture through computer algebra calculations. A human proof of Gessel’s conjecture was presented by Bostan et al. [Reference Bostan, Kurkova and Raschel4]. Bostan and Kauers [Reference Bostan and Kauers3] proved that the complete generating function for Gessel’s walks is algebraic.
There are
$2^8$
models of
$\mathscr {B}_2$
-walks in the first quadrant. Bousquet-Mélou and Mishna [Reference Bousquet-Mélou, Mishna, Lladser, Maier, Mishna and Rechnitzer6] undertook a systematic classification of the
$256$
models of walks from the viewpoint of structural properties of the generating functions. They pointed out that there are
$79$
inherently different models, of which
$22$
models possess D-finite generating functions (the 23rd model (Gessel’s walks) was proved to be D-finite by Bostan and Kauers [Reference Bostan and Kauers3]). The complete generating functions for the remaining
$56$
models are not D-finite (see [Reference Bostan, Raschel and Salvy5, Reference Kurkova and Raschel13, Reference Melczer and Mishna14, Reference Mishna and Rechnitzer16]). It is remarkable that Dreyfus et al. [Reference Dreyfus, Hardouin, Roques and Singer7] developed a powerful new approach to the determination of the nature of the generating functions of walks in the quarter plane through the theory of elliptic curves and the Galois theory of difference equations.
Note that
$\mathscr {S}_2=\{-1,0,1\}^{2}\setminus \{\mathbf {0}\}$
. The
$\mathscr {S}_2$
-walks in the plane are sometimes called king walks. Similarly, the
$\mathscr {S}_{d}$
-walks in the d-dimensional space can be called d-dimensional king walks.
Recall that Gauss’ hypergeometric series are defined by
$$ \begin{align*} {}_{2}F_{1}\bigg( \begin{matrix} a~~b\\[0pt] c\end{matrix}; t\bigg)=\sum_{k=0}^{\infty}\frac{(a)_k (b)_k}{(c)_k}\frac{t^k}{k!}, \end{align*} $$
where
$(x)_k$
denotes the Pochhammer symbol
$(x)_k=x(x+1)\cdots (x+k-1)$
. In 2017, Bostan et al. [Reference Bostan, Chyzak, van Hoeij, Kauers and Pech2] proved that
$19$
D-finite generating functions for
$\mathscr {B}_2$
-walks in the first quadrant can be expressed in terms of Gauss’ hypergeometric series. For the remarkable example in [Reference Bostan, Chyzak, van Hoeij, Kauers and Pech2] of
$19$
models of king walks in the first quadrant, they established the generating function
$$ \begin{align} G(t)=\sum_{n=0}^{\infty}g_{n} t^n=\frac{1}{t}\int_{0}^{t}\frac{1}{(1+4x)^3}\cdot {}_{2}F_{1}\bigg( \begin{matrix} {3}/{2}~~{3}/{2}\\[0pt] 2\end{matrix}; \frac{16x(1+x)}{(1+4x)^2}\bigg)\,dx, \end{align} $$
where
$g_n$
denotes the number of king walks of length n in the first quadrant.
Interest in higher dimensional lattice walks has increased recently. For instance, Melczer and Wilson [Reference Melczer and Wilson15] investigated the asymptotics for higher dimensional lattice walks.
Let
$\mathbb {N}=\{0,1,2,3,\ldots \}$
and
$\mathbb {Z}$
be the set of integers. For
$n,a_1,\ldots ,a_r\in \mathbb {N}$
and
$b_1,\ldots ,b_s\in \mathbb {Z}$
, let
$\mathcal {W}_{n,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}$
denote the set of
$\mathscr {S}_{r+s}$
-walks (the so-called
$(r+s)$
-dimensional king walks) of length n ending at
$(a_1,\ldots ,a_r,b_1,\ldots ,b_s)$
, which never dip below
$x_i=0$
for
$i=1,\ldots ,r$
. For
$\{b_1,\ldots ,b_s\}=\varnothing $
, the
$(r+s)$
-dimensional king walks are confined to the nonnegative orthant. For
$\{b_1,\ldots ,b_s\}=\varnothing $
and
$r=2$
, the
$(r+s)$
-dimensional king walks reduce to the king walks in the first quadrant, one of the
$19$
models in [Reference Bostan, Chyzak, van Hoeij, Kauers and Pech2].
We also consider the small step set
$\overline {\mathscr {S}}_d=\{-1,1\}^{d}$
in d-dimensional space. Let
$\overline {\mathcal {W}}_{n,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}$
denote the set of
$\overline {\mathscr {S}}_{r+s}$
-walks of length n ending at the point
$(a_1,\ldots ,a_r,b_1,\ldots ,b_s)$
, which never dip below
$x_i=0$
for
$i=1,\ldots ,r$
. It is clear that
$\overline {\mathcal {W}}_{n,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}\subseteq \mathcal {W}_{n,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}$
.
We also investigate d-dimensional excursions, which are walks starting and ending at the origin
$\mathbf {0}$
in d-dimensional space. Let
$\mathcal {W}_n^{(r,s)}$
denote the excursion set:
$$ \begin{align*} \mathcal{W}_n^{(r,s)}=\mathcal{W}_{\scriptsize n,{\{\underbrace{0,\ldots,0}_{r}\},\{\underbrace{0,\ldots,0}_{s}\}}}. \end{align*} $$
We denote the cardinality of these walk sets by
$$ \begin{align*} W_n^{(r,s)} &=|\mathcal{W}_n^{(r,s)}|,\\ W_{n,{\{a_1,\ldots,a_r\},\{b_1,\ldots,b_s\}}} & =|\mathcal{W}_{n,{\{a_1,\ldots,a_r\},\{b_1,\cdots,b_s\}}}|,\\ \overline{W}_{n,{\{a_1,\ldots,a_r\},\{b_1,\ldots,b_s\}}} & =|\overline{\mathcal{W}}_{n,{\{a_1,\ldots,a_r\},\{b_1,\ldots,b_s\}}}|. \end{align*} $$
We focus on enumeration and divisibility for
$(r+s)$
-dimensional king walks confined to certain regions. Specifically, we establish an explicit formula for
$W_{n,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}$
through trinomial and Motzkin triangles, and derive a divisibility property of
$W_{p,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}$
for any odd prime p through group actions. As a first corollary, we obtain explicit formulae for the number of d-dimensional excursions and d-dimensional king walks of length n confined to the nonnegative orthant. As a second corollary, we show that the number of d-dimensional excursions of length p (an odd prime) confined to a certain region is always divisible by p.
The rest of the paper is organised as follows. To state the main results, we first introduce trinomial and Motzkin triangles in Section 2. The main results are stated in Section 3. We prove Theorem 3.1 in Section 4 by using the principle of inclusion and exclusion, and prove Theorem 3.4 in Section 5 through group actions.
2 Trinomial and Motzkin triangles
The Motzkin numbers
$\{M_n\}_{n\ge 0}=1, 1, 2, 4, 9, 21, 51, 127,\ldots, $
which first appeared in [Reference Motzkin17] in a circle chord setting, count the number of ways of connecting a subset of n points on a circle by nonintersecting chords. It is well known that
$$ \begin{align} M_n=\sum_{k=0}^n{n\choose 2k}C_k, \end{align} $$
where
$C_n$
is the Catalan number which counts the number of lattice walks on the upper right quadrant of a grid from
$(0,0)$
to
$(2n,0)$
if one is allowed to move by using only steps
$(1,1)$
and
$(1,-1)$
but forbidden from dipping below the axis
$y=0$
. For further combinatorial interpretations of Catalan numbers, we refer to [Reference Stanley19]. From (2.1), it is easy to see that the Motzkin number
$M_n$
also counts the number of lattice walks from
$(0,0)$
to
$(n,0)$
, which never dip below
$y=0$
, and are made up only of the steps
$(1, 0), (1, 1)$
and
$(1, -1)$
.
A sequence closely related to the Motzkin number
$M_n$
is the central trinomial coefficient
$T_n$
, which is the coefficient of
$x^n$
in the expansion of
$(1+x+x^2)^n$
. It is easy to see that
$T_n$
counts the number of lattice walks from
$(0,0)$
to
$(n,0)$
which are made up only of the steps
$(1, 0), (1, 1)$
and
$(1, -1)$
, so that
$$ \begin{align} T_n=\sum_{k=0}^n{n\choose 2k}{2k\choose k}. \end{align} $$
We remark that both Motzkin numbers and central trinomial coefficients have many different expressions (see, for instance, [Reference Sloane18, A001006 and A002426]). For example,
$$ \begin{align*} &M_n=\sum_{k=0}^n (-1)^{n+k}{n\choose k}C_{k+1},\\ &T_n=\sum_{k=0}^n (-1)^{n+k}{n\choose k}{2k\choose k}. \end{align*} $$
We consider the trinomial triangle
$T=[T(n,k)]_{n,k\ge 0}$
, where
$T(n,k)$
denotes the number of lattice walks from
$(0,0)$
to
$(n,k)$
, which are made up only of the steps
$(1, 0), (1, 1)$
and
$(1, -1)$
:
$$ \begin{align*} T=[T(n,k)]_{n,k\ge 0}=\begin{pmatrix} 1&&&&&&\\ 1&1&&&&&\\ 3&2&1&&&&\\ 7&6&3&1&&&\\ 19&16&10&4&1&&\\ 51&45&30&15&5&1&\\ \vdots&&&&&&\ddots \end{pmatrix}. \end{align*} $$
We also consider the Motzkin triangle
$M=[M(n,k)]_{n,k\ge 0}$
, where
$M(n,k)$
denotes the number of lattice walks from
$(0,0)$
to
$(n,k)$
, which never dip below
$y=0$
, and are made up only of the steps
$(1, 0), (1, 1)$
and
$(1, -1)$
:
$$ \begin{align*} M=[M(n,k)]_{n,k\ge 0}=\begin{pmatrix} 1&&&&&&\\ 1&1&&&&&\\ 2&2&1&&&&\\ 4&5&3&1&&&\\ 9&12&9&4&1&&\\ 21&30&25&14&5&1&\\ \vdots&&&&&&\ddots \end{pmatrix}. \end{align*} $$
Note that the
$0$
th columns of T and M are respectively the central trinomial coefficients and Motzkin numbers, namely,
$T(n,0)=T_n$
and
$M(n,0)=M_n$
for
$n\in \mathbb {N}$
.
By symmetry, we have
$T(n,k)=T(n,-k)$
. It is easy to find a closed form of the generating function for
$T(n,k)$
:
$$ \begin{align*} \sum_{k=-n}^n T(n,k)x^{n+k}=(1+x+x^2)^n, \end{align*} $$
so that
$$ \begin{align*} T(n,k)=\sum_{i=0}^n{n\choose i}{n-i\choose i+k}. \end{align*} $$
Let
$M'(n,k)=M(n,n-k)$
. Then,
$[M'(n,k)]_{n,k\ge 0}$
coincides with the Motzkin triangle defined by Amdeberhan et al. [Reference Amdeberhan, Apagodu and Zeilberger1], given by the generating function:
$$ \begin{align} \sum_{k=0}^nM'(n,k)x^k-\sum_{k=0}^nM'(n,k)x^{2n+2-k}=(1-x^2)(1+x+x^2)^n. \end{align} $$
From (2.3), we can easily derive an explicit formula for
$M(n,k)$
:
$$ \begin{align*} M(n,k)=\sum_{i=0}^n {n\choose i}\left({n-i\choose i+k}-{n-i\choose i+k+2}\right). \end{align*} $$
3 Main results
First, we establish an explicit formula for
$W_{n,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}$
through the trinomial triangle T and the Motzkin triangle M.
Theorem 3.1. For
$n,a_1,\ldots ,a_r\in \mathbb {N}$
and
$b_1,\ldots ,b_s\in \mathbb {Z}$
,
$$ \begin{align} W_{n,{\{a_1,\ldots,a_r\},\{b_1,\ldots,b_s\}}}=\sum_{k=0}^n (-1)^{n-k}{n\choose k}\prod_{i=1}^rM(k,a_i) \prod_{j=1}^s T(k,b_j). \end{align} $$
From (3.1), we derive an explicit formula for the number of
$(r+s)$
-dimensional excursions of length n with steps in
$\mathscr {S}_{r+s}$
, which never dip below
$x_i=0$
for
$i=1,\ldots ,r$
.
Corollary 3.2. For nonnegative integers
$n, r$
and s with
$r+s\ge 1$
,
$$ \begin{align} W_n^{(r,s)}=\sum_{k=0}^n(-1)^{n-k}{n\choose k}M_k^rT_k^s. \end{align} $$
From their combinatorial interpretations,
$W_{2n}^{(1,0)}$
and
$W_{2n}^{(0,1)}$
coincide with the Catalan number
$C_n$
and the central binomial coefficient
${2n\choose n}$
, respectively. It follows from (3.2) that
$$ \begin{align*} &C_n=\sum_{k=0}^{2n}(-1)^{k}{2n\choose k}M_k,\\ &{2n\choose n}=\sum_{k=0}^{2n}(-1)^{k}{2n\choose k}T_k, \end{align*} $$
which can be also deduced from (2.1) and (2.2) through binomial inversion.
Let
$E_{n}^{(r)}$
denote the number of r-dimensional excursions of length n with steps in
$\mathscr {S}_r$
, which are confined to the nonnegative orthant. From (3.2),
$$ \begin{align} E_{n}^{(r)}=\sum_{k=0}^n (-1)^{n-k}{n\choose k}M_k^r. \end{align} $$
By using (3.3), we list in Table 1 the first few terms of
$E_{n}^{(r)}$
for
$1\le r\le 4$
. We remark that
$E_{n}^{(2)}$
counts the number of excursions of length n with steps in
$\mathscr {S}_2$
in the first quadrant.
$E_{n}^{(r)}$
for
$1\le r\le 4$
.
Let
$Q_{n}^{(r)}$
denote the number of r-dimensional king walks of length n, which are confined to the nonnegative orthant. From (3.1), we also derive an explicit formula for
$Q_{n}^{(r)}$
.
Corollary 3.3. For any nonnegative integer n and positive integer r,
$$ \begin{align} Q_{n}^{(r)}=\sum_{0\le a_1,\ldots,a_r\le n} \sum_{k=0}^n (-1)^{n-k}{n\choose k}\prod_{i=1}^rM(k,a_i). \end{align} $$
By using (3.4), we list in Table 2 the first few terms of
$Q_{n}^{(r)}$
for
$1\le r\le 4$
. We remark that
$Q_{n}^{(2)}$
coincides with
$g_n$
in (1.1).
$Q_{n}^{(r)}$
for
$1\le r\le 4$
.
Let
$\{a_1,\ldots ,a_r\}'$
denote the multiset obtained by removing all the
$0$
s in
$\{a_1,\ldots ,a_r\}$
. For instance,
$\{1,0,2,1,0,3\}'=\{1,2,1,3\}$
.
Second, we prove a divisibility relation for
$W_{p,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}$
by using an algebro-combinatorial approach, where p is an odd prime.
Theorem 3.4. Let p be an odd prime. For
$a_1,\ldots ,a_r\in \mathbb {N}$
and
$b_1,\ldots ,b_s\in \mathbb {Z}$
,
$$ \begin{align} W_{p,{\{a_1,\ldots,a_r\},\{b_1,\ldots,b_s\}}}\equiv \overline{W}_{p,{\{a_1,\ldots,a_r\}',\{b_1,\ldots,b_s\}'}} \pmod{p}. \end{align} $$
Corollary 3.5. If the multiset
$\{a_1,\ldots ,a_r,b_1,\ldots ,b_s\}$
contains at least one nonzero even integer, then
$$ \begin{align} W_{p,{\{a_1,\ldots,a_r\},\{b_1,\ldots,b_s\}}}\equiv 0 \pmod{p}. \end{align} $$
Proof. Assume
$a_1$
is a nonzero even integer. Then,
$a_1\in \{a_1,\ldots ,a_r\}'$
. If there exists a lattice walk
$X\in \overline {\mathcal {W}}_{p,{\{a_1,\ldots ,a_r\}',\{b_1,\ldots ,b_s\}'}}$
, then the projection of X on the
$x_1$
-axis consists of p elements
$-1$
and
$1$
, and ends at a nonzero even integer, which is impossible. It follows that
$\overline {\mathcal {W}}_{p,\{a_1,\ldots ,a_r\}',\{b_1,\ldots ,b_s\}'}=\varnothing $
. By (3.5), we arrive at (3.6).
Corollary 3.6. For any odd prime p,
$$ \begin{align} W_p^{(r,s)}\equiv 0 \pmod{p}. \end{align} $$
4 Proof of Theorem 3.1
Let
$\mathcal {S}$
denote the set of lattice walks from the origin
$\mathbf {0}$
to
$(a_1,\ldots ,a_r,b_1,\ldots ,b_s)$
, which never dip below
$x_i=0$
for
$i=1,\ldots ,r$
and are made up of n steps taken from
$\{-1,0,1\}^{r+s}$
. For
$1\le k\le n$
, let
$$ \begin{align*} \mathcal{S}_i=\{X\in \mathcal{S}\mid\text{the } i\text{th step of } X \text{ is } \mathbf{0}\}. \end{align*} $$
Note that
$$ \begin{align*} W_{n,{\{a_1,\ldots,a_r\},\{b_1,\ldots,b_s\}}}=\bigg| \mathcal{S}-\bigcup_{k=1}^n\mathcal{S}_k\bigg|. \end{align*} $$
By the principle of inclusion and exclusion,
$$ \begin{align} W_{n,{\{a_1,\ldots,a_r\},\{b_1,\ldots,b_s\}}}=|\mathcal{S}|-\sum_{1\le i\le n}|\mathcal{S}_i| +\sum_{1\le i<j\le n}|\mathcal{S}_i\cap \mathcal{S}_j|-\cdots+(-1)^n\bigg|\bigcap_{i=1}^n\mathcal{S}_i\bigg|. \end{align} $$
It is clear that
$M(k,a)$
also counts the number of vectors
$(z_1,z_2,\ldots ,z_k)$
with
${z_i\in \{-1,0,1\}}$
,
$\sum _{j=1}^i z_j\ge 0$
for
$1\le i\le k$
and
$\sum _{j=1}^k z_j=a$
, and
$T(k,b)$
counts the number of vectors
$(z_1,z_2,\ldots ,z_k)$
with
$z_i\in \{-1,0,1\}$
and
$\sum _{j=1}^k z_j=b$
. It follows that the product
$$ \begin{align*} \prod_{i=1}^rM(k,a_i)\prod_{j=1}^s T(k,b_j) \end{align*} $$
counts the number of lattice walks from the origin
$\mathbf {0}$
to
$(a_1,\ldots ,a_r,b_1,\ldots ,b_s)$
, which never dip below
$x_i=0$
for
$i=1,\ldots ,r$
, and are made up of k steps taken from
$\{-1,0,1\}^{r+s}$
.
From the definition of
$\mathcal {S}_{k}$
, we deduce that the cardinality of the intersection of the sets
$\mathcal {S}_{k}$
,
$$ \begin{align*} \bigg|\bigcap_{m=1}^k \mathcal{S}_{i_m}\bigg| \end{align*} $$
counts the number of lattice walks from the origin
$\mathbf {0}$
to
$(a_1,\ldots ,a_r,b_1,\ldots ,b_s)$
, which never dip below
$x_i=0$
for
$i=1,\ldots ,r$
, and which are made of
$(n-k)$
steps taken from
$\{-1,0,1\}^{r+s}$
. It follows that
$$ \begin{align} \bigg|\bigcap_{m=1}^k \mathcal{S}_{i_m}\bigg|=\prod_{i=1}^rM(n-k,a_i)\prod_{j=1}^s T(n-k,b_j). \end{align} $$
Finally, combining (4.1) and (4.2), we arrive at
$$ \begin{align*} W_{n,{\{a_1,\ldots,a_r\},\{b_1,\ldots,b_s\}}} &=\sum_{k=0}^n (-1)^k {n\choose k}\prod_{i=1}^rM(n-k,a_i)\prod_{j=1}^s T(n-k,b_j)\\ &=\sum_{k=0}^n (-1)^{n-k} {n\choose k}\prod_{i=1}^rM(k,a_i)\prod_{j=1}^s T(k,b_j), \end{align*} $$
as desired.
5 Proof of Theorem 3.4
For any lattice walk
$X\in \mathcal {W}_{p,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}$
, let
$X_i=(x_{i1},x_{i2},\ldots ,x_{i(r+s)})^{T}$
be the ith step of X (
$i=1,\ldots ,p$
). Then, the lattice walk
$X=X_1 X_2 \cdots X_p\in \mathcal {W}_{p,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}$
can be expressed as the matrix
Let
$$ \begin{align*} &\mathcal{U}_{p,{\{a_1,\ldots,a_r\},\{b_1,\ldots,b_s\}}}\\[3pt] &\quad =\{X\in \mathcal{W}_{p,{\{a_1,\ldots,a_r\},\{b_1,\ldots,b_s\}}}\mid \text{at least one row of } X \text{ contains both } 0\text{s and nonzeros}\}, \end{align*} $$
and
$$ \begin{align*} &\mathcal{V}_{p,{\{a_1,\ldots,a_r\},\{b_1,\ldots,b_s\}}}\\[3pt] &\quad=\{X\in \mathcal{W}_{p,{\{a_1,\ldots,a_r\},\{b_1,\ldots,b_s\}}}\mid \text{each row of } X \text{ contains only } 0\text{s or only nonzeros}\}. \end{align*} $$
It is clear that
$$ \begin{align} \mathcal{U}_{p,{\{a_1,\ldots,a_r\},\{b_1,\ldots,b_s\}}}=\mathcal{W}_{p,{\{a_1,\ldots,a_r\},\{b_1,\ldots,b_s\}}} -\mathcal{V}_{p,{\{a_1,\ldots,a_r\},\{b_1,\ldots,b_s\}}}. \end{align} $$
We list all
$0$
s in the two multisets
$\{a_1,\ldots ,a_r\}$
and
$\{b_1,\ldots ,b_s\}$
:
$a_{i_1}=\cdots =a_{i_{r'}}=b_{j_1}=\cdots =b_{j_{s'}}=0$
. Note that the sum of p terms
$-1$
and
$1$
is always nonzero. For any
$X\in \mathcal {V}_{p,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}$
, the components of the walk X on the
$x_{i_k}$
-axis and the
$y_{j_l}$
-axis (corresponding to the
$i_k$
th and
$j_l$
th row of X) must be
$(\underbrace {0,0,\ldots ,0}_{p})$
for
$k=1,\ldots , r'$
and
$l=1,\ldots , s'$
, and the components of the walk X on the other axes all exclude
$0$
s. It follows that
$$ \begin{align} |\mathcal{V}_{p,{\{a_1,\ldots,a_r\},\{b_1,\ldots,b_s\}}}| =|\overline{\mathcal{W}}_{p,{\{a_1,\ldots,a_r\}',\{b_1,\ldots,b_s\}'}}|. \end{align} $$
By (5.1) and (5.2), we conclude that (3.5) is equivalent to
$$ \begin{align} |\mathcal{U}_{p,{\{a_1,\ldots,a_r\},\{b_1,\ldots,b_s\}}}|\equiv 0\pmod{p}. \end{align} $$
To prove (5.3), it suffices to show that
$\mathcal {U}_{p,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}$
can be partitioned into several pairwise disjoint subsets, all of which contain exactly p elements.
For any
$X\in \mathcal {U}_{p,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}$
, we define an operator
$\sigma $
on
$\mathcal {U}_{p,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}$
by
where
$(y_{1j},y_{2j},\ldots ,y_{pj})$
is obtained by shifting
$0$
s backward one position in the jth row
$(x_{1j},x_{2j},\ldots ,x_{pj})$
of X (if
$x_{pj}=0$
, then it is shifted to the first position), and keeping the order of
$-1$
and
$1$
in
$(x_{1j},x_{2j},\ldots ,x_{pj})$
for
$j=1,\ldots ,r+s$
. For instance, if
$$ \begin{align*}X=\begin{pmatrix} 1&0&-1&0&-1\\ 1&1&1&-1&0 \end{pmatrix}\in \mathcal{U}_{5,{\{2\},\{-1\}}}.\end{align*} $$
Then,
The corresponding lattice walks are shown in Figure 1.
The lattice walks X and
$\sigma (X)$
.
It is easy to check that
$\sigma (X)\in \mathcal {U}_{p,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}$
and
$\sigma ^p(X)=X$
for any
${X\in \mathcal {U}_{p,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}}$
. Let
$G=\langle \sigma \rangle $
denote the cyclic group generated by
$\sigma $
. Then,
$G=\{\sigma ,\sigma ^2,\ldots ,\sigma ^p\}$
and
$|G|=p$
. For any
$g\in G$
, g maps
$$ \begin{align*}\mathcal{U}_{p,{\{a_1,\ldots,a_r\},\{b_1,\ldots,b_s\}}}\to \mathcal{U}_{p,{\{a_1,\ldots,a_r\},\{b_1,\ldots,b_s\}}}.\end{align*} $$
For any
$X\in \mathcal {U}_{p,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}$
and
$g,h\in G$
, we have
$h(g(X))=(hg)(X)$
. That is, the group G acts on
$\mathcal {U}_{p,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}$
.
We shall prove that for any
$X\in \mathcal {U}_{p,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}$
and
$g,h\in G$
with
$g\not =h$
,
$$ \begin{align} g(X)\not=h(X). \end{align} $$
Note that (5.4) is equivalent to
$$ \begin{align*} \sigma^k(X)\not= \sigma^l(X) \end{align*} $$
for any
$X\in \mathcal {U}_{p,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}$
and
$1\le k<l\le p$
.
For any
$X\in \mathcal {U}_{p,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}$
, assume that the mth row of X contains both
$0$
s and nonzeros. We list all
$0$
s in the mth row of X:
$x_{j_1m}=x_{j_2m}=\cdots =x_{j_d m}=0$
, where
${1\le d\le p-1}$
. Assume that
$\sigma ^k(X)=\sigma ^l(X)$
for
$1\le k<l\le p$
. It follows that
$$ \begin{align} \begin{cases} j_1+l&\equiv i_1+k \pmod{p},\\ j_2+l&\equiv i_2+k\pmod{p},\\ &\vdots\\ j_d+l&\equiv i_d+k\pmod{p}, \end{cases} \end{align} $$
where
$i_1 i_2 \cdots i_d$
is a permutation of
$j_1 j_2\cdots j_d$
. We can rewrite (5.5) as
$$ \begin{align*} \begin{cases} j_1+q&\equiv i_1 \pmod{p},\\ j_2+q&\equiv i_2\pmod{p},\\ &\vdots\\ j_d+q&\equiv i_d\pmod{p}, \end{cases} \end{align*} $$
where
$q=l-k$
and
$1\le q\le p-1$
. Then, there exists an integer t with
$1\le t\le d\le p-1$
such that
$j_1+tq\equiv j_1\pmod {p}$
, and so
$p\mid tq$
. Since
$(q,p)=1$
and
$(t,p)=1$
, we have
$p\nmid tq$
. We are led to a contradiction. It follows that
$\sigma ^k(X)\not = \sigma ^l(X)$
for
$1\le k< l\le p$
and so (5.4) holds.
From (5.4), we deduce that if G acts on
$\mathcal {U}_{p,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}$
, then the orbit of each
$X\in \mathcal {U}_{p,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}$
has exactly p elements, that is,
$|\mathcal {O}_{X}|=p.$
For example, if
$$ \begin{align*}X=\begin{pmatrix} 1&0&-1&0&-1\\ 1&1&1&-1&0 \end{pmatrix}\in \mathcal{U}_{5,{\{2\},\{-1\}}},\end{align*} $$
then the orbit
$\mathcal {O}_{X}$
consists of the
$5$
distinct lattice walks shown in Figure 2.
The lattice walks
$X, \sigma (X), \ldots , \sigma ^4(X)$
.
If G acts on
$\mathcal {U}_{p,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}$
, then the distinct orbits form a set partition of the set
$\mathcal {U}_{p,{\{a_1,\ldots ,a_r\},\{b_1,\ldots ,b_s\}}}$
and it follows that
$$ \begin{align*} |\mathcal{U}_{p,{\{a_1,\ldots,a_r\},\{b_1,\ldots,b_s\}}}|\equiv 0\pmod{p}, \end{align*} $$
as desired.
