# Simple Generating Functions for Certain Young Tableaux with Periodic Walls

Feihu Liu1 and Guoce Xin2,∗ 1,2School of Mathematical Sciences, Capital Normal
University, Beijing 100048, PR China<EMAIL_ADDRESS>&
<EMAIL_ADDRESS>
(Date: January 26, 2024)

###### Abstract.

Recently, Banderier et. al. considered Young tableaux with walls, which are
similar to standard Young tableaux, except that local decreases are allowed at
some walls. We count the numbers $\overline{f}_{m}(n)$ of Young tableaux of
shape $2\times mn$ with walls, that allow local decreases at the $(jm+i)$-th
columns for all $j=0,\dots,n-1$ and $i=2,\dots,m$. We find that they have nice
generating functions (thanks to the OEIS) as follows.

$\overline{F}_{m}(x)=\sum_{n\geq
0}\overline{f}_{m}(n)x^{n}=\prod_{k=1}^{m}C(e^{k\frac{2\pi
i}{m}}x^{\frac{1}{m}})=\exp\left(\sum_{n\geq
1}\binom{2mn-1}{mn-1}\frac{x^{n}}{n}\right),$

where $C(x)=\frac{1-\sqrt{1-4x}}{2x}$ is the well-known Catalan generating
function. We prove generalizations of this result. Firstly, we use the
Yamanouchi word to transform Young tableaux with horizontal walls into lattice
paths. This results in a determinant formula. Then by lattice path counting
theory, we obtain the generating functions $F_{r}(x)$ for the number of
lattice paths from $(0,0)$ to $(\ell n-r,kn)$ that never go above the path
$(N^{k}E^{\ell})^{n-1}N^{k}E^{\ell-r}$, where $N,E$ stand for north and east
steps, respectively. We also obtain exponential formulas for $F_{1}(x)$ and
$F_{\ell}(x)$. The formula for $\overline{F}_{m}(x)$ is thus proved since it
is just $F_{1}(x)$ specializes at $k=\ell=m$.

$*$ This work is partially supported by NSFC(12071311).

_Mathematic subject classification_ : Primary 05A15; Secondary 05A10, 05E05.

_Keywords_ : Rectangular Young tableau; Lattice path; Puiseux’s theorem;
Symmetric function; Catalan number.

##  1\. Introduction

Throughout this paper, $\mathbb{C}$, $\mathbb{Z}$, $\mathbb{N}$ and
$\mathbb{P}$ denote the set of all complex numbers, all integers, non-negative
integers and positive integers, respectively.

Recently, Banderier et. al. [1, 2] considered a variation of standard Young
tableaux, called _Young tableaux with walls_. We give a rigorous definition
for our exploration. Let $\lambda$ be a partition of $n$, denoted
$\lambda\vdash n$. Its Young diagram is also denoted $\lambda$. See, e.g.,
[12, Section 1.7] for detailed definitions. In this paper, we focus on
$\lambda=(m,m)$, so the Young diagram of $\lambda$ is a $2\times m$ rectangle
with $|\lambda|=2m$ cells. Edges between two neighboring cells of $\lambda$
will be referred to as _walls_. A _Young building_ $\mathcal{B}$ of shape
$\lambda$ is a pair $\mathcal{B}=(\lambda,W)$ where $W$ is a subset of the
walls of $\lambda$. The walls in $W$ are depicted as bold red edges. A Young
tableau with walls over $\mathcal{B}$ is a filling of the cells of $\lambda$
by labels $1,2,\dots,n$, such that each label appears exactly once and the
labels are increasing along each row and column, (conditions for standard
Young tableaux) but two labels separated by a wall need not be increasing.
Denote by $YT(\lambda,W)$ the set of all such tableaux. It reduces to the set
of standard Young tableaux of shape $\lambda$ when $W$ is empty. See Figure 1
for an example of Young tableaux with walls of shape $\lambda=(6,6)$.

Figure 1. A Young tableaux of shape $\lambda=(6,6)$ with walls.

Let $\mathcal{B}=(\lambda,W)$ be a rectangular building. That is, $\lambda$ is
of rectangular shape. Define $\mathcal{B}^{n}$ to be the Young building formed
by connecting $n$ blocks of $\mathcal{B}$ horizontally. Then Young tableaux
over $\mathcal{B}^{n}$ are called _Young tableaux with periodic walls_. Note
that in this definition, $W$ is allowed to contain the rightmost edges of
$\lambda$. Figure 2 illustrates a Young building $\mathcal{B}_{2}$ on the left
and a Young tableau with walls in $YT(\mathcal{B}_{2}^{3})$ on the right.

Figure 2. A Young tableaux with periodic walls of a block $\mathcal{B}_{2}$ of
shape $(2,2)$.

In [2], Banderier and Wallner counted Young tableaux with periodic walls by
“the density method”. They considered a classification of $2\times 2$ periodic
shapes (a total of $2^{6}=64$ different models) and obtained counting formulas
for $60$ models. In particular, they obtained the counting formula

$\overline{f}_{2}(n):=|YT(\mathcal{B}_{2}^{n})|=2^{2n+1}\texttt{Cat}(n)-\texttt{Cat}(2n+1),$

where $\texttt{Cat}(n)$ is the well-known Catalan number with the Catalan
generating function

$C(x)=\sum_{n\geq 0}\texttt{Cat}(n)x^{n}=\frac{1-\sqrt{1-4x}}{2x}=\sum_{n\geq
0}\frac{1}{n+1}\binom{2n}{n}x^{n}.$ (1)

Note that $\overline{f}_{2}(n)$ is the sequence [A079489] in OEIS [11].

More generally, let $m$ be a positive integer and $\mathcal{B}_{m}$ be the
Young building shape $\lambda=(m,m)$ with horizontal walls in all columns
except the first column. See Figure 4 (on the left) for two examples of
elements in $YT(\mathcal{B}_{3}^{2})$. We are interested in the counting
formula of $\overline{f}_{m}(n)=|YT(\mathcal{B}_{m}^{n})|$.

Computer experiment suggests that $\overline{f}_{m}(n)$ for $m=3,4,5,6$ are
respectively the sequences [A213403], [A213404], [A213405] and [A213406] in
OEIS [11]. These sequences have nice generating functions, and can be
summarized as the following result.

######  Theorem 1.1.

Suppose $m$ is a positive integer. Let $\overline{f}_{m}(n)$ denote the number
of Young tableaux with periodic walls over $\mathcal{B}_{m}^{n}$, with
convention $\overline{f}_{m}(0)=1$. Then we have

$\overline{F}_{m}(x)=\sum_{n\geq
0}\overline{f}_{m}(n)x^{n}=\prod_{k=1}^{m}C(\xi^{k}x^{\frac{1}{m}})=\exp\left(\sum_{n\geq
1}\binom{2mn-1}{mn-1}\frac{x^{n}}{n}\right),$

where $\xi=e^{\frac{2\pi i}{m}}$ and $C(x)$ is the Catalan generating
function.

The motivation of this paper is to give a proof of this theorem.

To this end, we find several combinatorial interpretations of
$\overline{f}_{m}(n)$, including a lattice path interpretation. This allows us
to prove Theorem 1.1 using lattice path counting theory (e.g., [14, 4, 8]).
Indeed, our first result is the following.

######  Theorem 1.2.

Let $k,\ell\in\mathbb{P}$, $n\in\mathbb{N}$ and $1\leq r\leq\ell$. Let
$f_{r}(n)$ be the number of lattice paths from $(0,0)$ to $(\ell n-r,kn)$ that
never go above the path $(N^{k}E^{\ell})^{n-1}N^{k}E^{\ell-r}$, and let
$w_{1},...,w_{\ell}$ be the unique solutions of the equation
$(w-1)^{\ell}-xw^{k+\ell}=0$ that are fractional power series. Then the
generating function $F_{r}(x)=\sum_{n\geq 0}f_{r}(n)x^{n}$ (with the
convention $f_{r}(0)=1$) is given by

$F_{r}(x)=\sum_{i=0}^{r-1}(-1)^{i}\binom{\ell-r+i}{i}e_{\ell-r+1+i}(w_{1},w_{2},...,w_{\ell}),$

where $e_{m}(w_{1},...,w_{\ell})$ is the $m$-th elementary symmetric function
introduced in subsection 3.1.

Specifically, when $r=\ell$, this result was obtained by de Mier and Noy
([10]) in 2005.

For the two cases of $r=\ell$ and $r=1$, we obtain the following exponential
formulas.

######  Theorem 1.3.

Let $q(n)$ be the number of lattice paths from $(0,0)$ to $(\ell n,kn)$ that
never go above the path $(N^{k}E^{\ell})^{n}$. Let $Q(x)=\sum_{n\geq
0}q(n)x^{n}$. Then we have

$Q(x)=\exp\left(\sum_{n\geq 1}\binom{kn+\ell n}{\ell
n}\frac{x^{n}}{n}\right).$

######  Theorem 1.4.

Following the notation in Theorem 1.2. Let $f_{1}(n)$ be the number of lattice
paths from $(0,0)$ to $(\ell n-1,kn)$ that never go above the path
$(N^{k}E^{\ell})^{n-1}N^{k}E^{\ell-1}$. Let $F_{1}(x)=\sum_{n\geq
0}f_{1}(n)x^{n}$. Then we have

$F_{1}(x)=\exp\left(\sum_{n\geq 1}\binom{kn+\ell n-1}{\ell
n-1}\frac{x^{n}}{n}\right).$

The paper is organized as follows. In Section 2, we consider Young tableaux
with horizontal walls over a Young building $\mathcal{B}$, especially for
$\mathcal{B}$ of shape $(m,m)$, a two-rowed partition. By using the Yamanouchi
word [13, Propsition 7.10.3(d)], such Young tableaux are encoded by
$y$-sequences, lattice paths, and reverse partitions. This allows us to give a
determinant formula for $YT(\mathcal{B})$ using lattice path counting theory.
In particular, $\overline{f}_{m}(n)$ has a simple determinant formula in
Proposition 2.5. Section 3 is devoted to the proof of our main result, Theorem
1.2. In subsection 3.1 we introduce some basic knowledge about symmetric
functions and combinatorial sum identities that will be used in our proof. In
subsection 3.2, we first introduce the functional equation system in [10]
obtained from Matroid Theory, then solve the system and complete the proof of
Theorem 1.2. Section 4 focuses on the cases $r=1$ and $r=\ell$. We prove
Theorems 1.3 and 1.4 on their exponential formulas, and complete the proof of
Theorem 1.1. In Section 5, we discuss two other possible approaches to Theorem
1.2. This leads to two byproducts in Theorem 5.1 and Theorem 5.4.

##  2\. Rectangular Young Tableaux with Horizontal Walls

Let $\mathcal{B}=(\lambda,W)$ be a rectangular Young building with horizontal
walls. That is, $\lambda=(m,m,\dots,m)$, and $W$ contains only horizontal
walls. We use the Yamanouchi word [13, Propsition 7.10.3(d)] to transform
Young tableaux with walls over $\mathcal{B}$ into several combinatorial
objects, including lattice paths. Though most of the ideas work for general
$\lambda$, we focus on the two-row case, i.e., $\lambda=(m,m)$, for its
simplicity and its close relation with $f_{m}(n)$ in Theorem 1.2.

For a Young tableau $T$ with walls over $\mathcal{B}$ depicted in Figure 3,
its labels satisfy $x_{1}<x_{2}<\cdots$ and $y_{1}<y_{2}<\cdots$. Note that we
did not mark walls in Figure 3. Since $\mathcal{B}$ contains only horizontal
walls, we may encode $W$ as a subset $S$ of $[m]:=\\{1,\dots,m\\}$. Thus we
have the extra conditions $x_{i}<y_{i}$ for all $i\not\in S$.

$\begin{array}[]{|c|c|c|c|c|}\hline\cr y_{1}&y_{2}&y_{3}&\cdots&y_{m}\\\
\hline\cr x_{1}&x_{2}&x_{3}&\cdots&x_{m}\\\ \hline\cr\end{array}$

Figure 3.

Now we introduce several different encodings of $T\in YT((m,m),S)$.

  1. (1)

The _$y$ -sequence_ of $T$ is $y(T)=(y_{1},y_{2},\dots,y_{m})$. The _$x$
-sequence_ of $T$ is $x(T)=(x_{1},x_{2},\dots,x_{m})$. Then
$\\{x_{1},\dots,x_{m}\\}=[2m]\setminus\\{y_{1},\dots,y_{m}\\}$.

  2. (2)

The _Yamanouchi word_ of $T\in YT(\lambda,S)$ is defined by
$w(T)=w_{1}w_{2}\cdots w_{2m}$ with $w_{i}=\chi(i\ \text{in first row})$ where
$\chi(true)=1$ and $\chi(false)=0$.

  3. (3)

The lattice path of $T$ is defined by $p(T)=w(T)|_{0\to N,1\to E}$, which is
the $NE$-sequence of a lattice path, with $N=(0,1)$ and $E=(1,0)$ standing for
north step and east step, respectively.

  4. (4)

The _reverse partition_ of $T$ is defined to be the partition
$\mu(T)=(\mu_{1},\mu_{2},\dots,\mu_{m})$ lying above $p(T)$. More precisely,
$\mu_{i}\geq 0$ is the number of cells in the $(m-i+1)$-th row and to the left
of $p(T)$. In some contexts, it is also referred to as the co-area sequence.

For example, if $T$ is the figure in the bottom left corner of Figure 4 with
$S=\\{2,3,5,6\\}$, then the Yamanouchi word of $T$ is $011100011100$; the
$y$-sequence of $T$ is $y(T)=(2,3,4,8,9,10)$; the $x$-sequence of $T$ is
$x(T)=(1,5,6,7,11,12)$; the path of $T$ is $p(T)=NE^{3}N^{3}E^{3}N^{2}$; and
the reverse partition of $T$ is $\mu(T)=(0,3,3,3,6,6)$. It should be evident
that $\mu_{i}=x_{i}-i$.

Figure 4. An example of bijection for $\mathcal{B}_{3}^{2}$ in Proposition
2.5.

The following lemma is immediate.

######  Lemma 2.1.

For any $T,T^{\prime}$ in $YT((m,m),S)$ as above, the following are
equivalent.

  1. (1)

$\mu(T)\leq\mu(T^{\prime})$ componentwise, i.e., $\mu_{i}\leq\mu_{i}^{\prime}$
for all $i$ if $\mu(T)=(\mu_{1},\mu_{2},\dots,\mu_{m})$ and
$\mu(T^{\prime})=(\mu^{\prime}_{1},\mu^{\prime}_{2},\dots,\mu^{\prime}_{m})$.

  2. (2)

The path $p(T)$ lies above the path $p(T^{\prime})$;

  3. (3)

The $y$-sequence $y(T)$ is larger than the $y$-sequence $y(T^{\prime})$
componentwise. We also denote $y(T)\leq y(T^{\prime})$

We denote by $T\leq T^{\prime}$ if one of the above conditions holds (hence
all the conditions hold) true.

The proof of the lemma is straightforward and we omit it. Moreover, $\leq$ is
a partial order on $YT((m,m),[m])$ and hence on its restriction $YT((m,m),S)$
for all $S$. Indeed, it is the partial order induced by the containment
partial order on their reverse partitions.

Two extreme cases of $S$ are worth mentioning: i) When $S$ is empty, $T\in
YT((m,m),\emptyset)$ is a standard Young tableau, and its (classical)
Yamanouchi word $w(T)$ corresponds to a _Catalan path_ , i.e., a lattice path
that never goes below the diagonal. The Yamanouchi map $\varphi:T\mapsto p(T)$
establishes a bijection from standard Young tableaux of shape $(m,m)$ to
Catalan paths of size $m$. ii) When $S=[m]$, one can verify that the map
$\varphi$ establishes a bijection from $YT((m,m),[m])$ to the set of all
lattice paths from $(0,0)$ to $(m,m)$. These two cases invite us to find a
good interpretation of the image of $YT((m,m),S)$ under $\varphi$ for
arbitrary subset $S$.

To this end, we need the following lemma.

######  Lemma 2.2.

Suppose $S$ is a subset of $[m]$. Then any $T\in YT((m,m),S)$ satisfies
$y_{\min}\leq y(T)\leq y_{\max}(S)$, where $y_{\min}=(m+1,m+2,\dots,2m)$ and
$y_{\max}(S)=(Y_{1},\dots,Y_{m})$ is determined by the following rule: If
$i\not\in S$ then $Y_{i}=2i$; otherwise $i\in S$ and $Y_{i}=i_{0}+i$ where
$i_{0}$ is the largest $\ell<i$ satisfying $\ell\not\in S$ (if no such $\ell$
exists, then we set $i_{0}=0$).

###### Proof.

Assume $y(T)=(y_{1},\dots,y_{m})$. Since $y_{1}<y_{2}<\cdots<y_{m}\leq 2m$
always hold, $y_{\min}=(m+1,m+2,\dots,2m)\leq y(T)$ for any $S$.

To see that $y(T)\leq y_{\max}(S)$, we first check that $(Y_{1},\dots,Y_{m})$
is a $y$-sequence of certain $T^{\prime}\in YT((m,m),S)$. This is
straightforward. Next we claim that $y_{i}\geq Y_{i}$ for all $i$ so that the
proof is completed. We have to distinguish the two cases: i) If $i\not\in S$,
then $y_{1}<\cdots<y_{i}$ and $x_{1}<\cdots<x_{i}<y_{i}$. Thus $y_{i}\geq
2i=Y_{i}$; ii) If $i\in S$, then $y_{1}<\cdots<y_{i}$ and
$x_{1}<\cdots<x_{i_{0}}<y_{i_{0}}$. Thus $y_{i}\geq i+i_{0}=Y_{i}$ as desired.
∎

######  Proposition 2.3.

Suppose $S$ is a subset of $[m]$. Let $T^{0},T^{M}(S)$ be the tableau in
$YT((m,m),S)$ with $y$-sequence $y_{\min}$ and $y_{\max}(S)$ as in Lemma 2.2,
respectively. Then the following sets have the same cardinality.

  1. (1)

Tableaux $T$ in $YT((m,m),S)$ that satisfy $T^{0}\leq T\leq T^{M}(S)$;

  2. (2)

Lattice paths from $(0,0)$ to $(m,m)$ that stay above $p(T^{M}(S))$;

  3. (3)

Partitions contained in $\mu(T^{M}(S))$.

###### Proof.

The bijection between sets $(2)$ and $(3)$ is obvious, so it suffices to show
that $T\mapsto p(T)$ is the desired bijection from set $(1)$ to set $(2)$. For
a given tableaux $T$ in set $(1)$, the $y$-sequence of $T$ is
$y(T)=(y_{1},y_{2},...,y_{m})$. By Proposition 2.2, we have $y(T)\leq
y_{\max}(S)$, i.e., $y_{i}\geq Y_{i}$. By Lemma 2.1, the path $p(T)$ lies
above the path $p(T^{M}(S))$. So $p(T)$ is well defined between sets $(1)$ and
$(2)$. Moreover, $T\mapsto p(T)$ is an injection.

Given a path $P$ that stays above $p(T^{M}(S))$, we need to find a desired $T$
satisfying $p(T)=P$. Assuming that the $y$-sequence of $T^{M}(S)$ is
$(Y_{1},Y_{2},...,Y_{m})$, and the $x$-sequence of $T^{M}(S)$ is
$(X_{1},X_{2},...,X_{m})$. If $i\notin S$, then $X_{i}<Y_{i}$. Let’s construct
a $T$ such that $p(T)=P$. If the $r$-th step of $P$ is an $E$ step, then the
entry $r$ appears in the first row of $T$. We mark it as
$(y_{1},y_{2},...,y_{m})$ in ascending order. So we have $y_{i}\geq Y_{i}$ for
all $i$. If the $r$-th step of $P$ is a $N$ step, then the entry $r$ appears
in the second row of $T$. We mark it as $(x_{1},x_{2},...,x_{m})$ in ascending
order. So we have $x_{i}\leq X_{i}$ for all $i$. If $i\notin S$, then
$x_{i}\leq X_{i}<Y_{i}\leq y_{i}$. So $T$ in $YT((m,m),S)$ that satisfy
$T^{0}\leq T\leq T^{M}(S)$. Furthermore, $p(T)=P$ and $p(T)$ is a bijection.
This completes the proof. ∎

See Figure 4 for an example. The first step of $p(T)$ is always $N$ since the
$x_{1}$ in $\mathcal{B}_{m}^{n}$ has to be equal to $1$.

For the cardinality of $YT((m,m),S)$, there is a determinant formula by the
following result of Kreweras [9] in lattice path counting theory.

######  Lemma 2.4 ([9]).

Let $P_{1}=(a_{1},a_{2},...,a_{n})$ and $P_{2}=(b_{1},b_{2},...,b_{n})$ be two
fixed reverse partitions, where $a_{1}\leq a_{2}\leq\cdots\leq a_{n}$ and
$b_{1}\leq b_{2}\leq\cdots\leq b_{n}$. Suppose $P_{2}\leq P_{1}$, i.e.,
$b_{i}\leq a_{i}$ for $1\leq i\leq n$. The number of partitions lying between
$P_{2}$ and $P_{1}$ is

$\det\left(\binom{a_{i}-b_{j}+1}{j-i+1}\right)_{1\leq i,j\leq n}.$

For Lemma 2.4, the weighted counting of the partitions by area has been
studied. A $q$-analogous determinant formula was first obtained by Handa and
Mohanty [7], and later proved by Gessel and Loehr [5] using an elegant
involution argument.

Now we can give a determinant formula for $\overline{f}_{m}(n)$.

######  Proposition 2.5.

Follow the notation in Section 1. The cardinality
$\overline{f}_{m}(n)=\\#YT(\mathcal{B}_{m}^{n})$ is the number of lattice
paths from $(0,0)$ to $(mn,mn)$ that never go below the path
$N(E^{m}N^{m})^{n-1}E^{m}N^{m-1}$. Moreover, we have

$\overline{f}_{m}(n)=\det\left(\binom{a_{i}+1}{j-i+1}\right)_{1\leq i,j\leq
nm-1},$

where

$a_{i}=hm,\ \ (h-1)m+1\leq i\leq hm,\ 1\leq h\leq n-1$

and

$a_{i}=mn,\ \ (n-1)m+1\leq i\leq nm-1.$

###### Proof.

The first part follows by Proposition 2.3 with respect to $S=\\{jm+i\mid 2\leq
i\leq m,0\leq j\leq n-1\\}$, where one can verify that

$p(T^{0})=N^{mn}E^{mn},\ \ \mu(T^{0})=\underbrace{(0,0,...,0)}_{nm},$

and that

$p(T^{M}(S))=N(E^{m}N^{m})^{n-1}E^{m}N^{m-1},$
$\mu(T^{M}(S))=(0,\underbrace{m,...,m}_{m},\underbrace{2m,...,2m}_{m},...,\underbrace{(n-1)m,...,(n-1)m}_{m},\underbrace{mn,...,mn}_{m-1}).$

The second part then follows by the first part and Lemma 2.4, in which we
ignore the first element $0$. ∎

We are interested in finding a nice formula for the generating function of
$\overline{f}_{m}(n)$. Proposition 2.5 does not seem to help. Next we give a
recursive formula as follows.

######  Proposition 2.6.

Follow the notation as above. Suppose $m\geq 2$ and $n\geq 1$. Then we have

$\overline{f}_{m}(n)=\binom{2mn-1}{mn}-\sum_{i=1}^{n-1}\sum_{t=1}^{m}g_{t}(i)\binom{2m(n-i)+m-t-1}{m(n-i)-1}.$

where,

$g_{t}(i)=\binom{2mi-m+t-1}{mi}-\sum_{j=1}^{i-1}\sum_{r=1}^{m}g_{r}(j)\binom{2m(i-j)+t-r-1}{m(i-j)-1}$

and the initial value are

$g_{t}(1)=\binom{m+t-1}{m},\ \ 1\leq t\leq m.$

Note that $g_{m}(i)=\overline{f}_{m}(i)$.

###### Proof.

We use the lattice path interpretation. The theorem is an application of the
inclusion-exclusion principle. We only illustrate the idea by a simple
example, since the detailed proof is conceptually simple but tedious to
present.

Consider the counting of lattice paths for the case $m=3,n=2$ in Figure 4.
Firstly, we move $(0,0)$ and $(6,6)$ to $(-1,1)$ (point $M$) and $(5,7)$
(point $F$) respectively. Then we need to count lattice paths from $M$ to $F$
that never touch the lower red boundary $NE^{3}N^{3}E^{3}N^{2}$. For this, we
subtract from $\binom{6+6}{6}$ the number of bad lattice paths, i.e, those
touch the boundary. We classify the bad paths by their first touching of the
boundary, at the points $A$, $B$, $C$ and $D$ in Figure 4. This gives

$\overline{f}_{3}(2)=\binom{6+6}{6}-1\times\binom{5+6}{5}-1\times\binom{2+5}{2}-\binom{3+1}{3}\binom{2+4}{2}-\binom{3+2}{3}\binom{2+3}{2}=281.$

The subtracted terms are obtained in a similar way. Let us only explain the
last term corresponding to bad paths first touching $D$. The first term counts
the number of ways to go from $M$ to $D$ without touching the boundary. This
corresponds to going from $(0,0)$ to $C$ without going below the boundary, and
is hence counted by $g_{i}(t)$, but becomes simply $\binom{3+2}{3}$ in the
displayed picture; The second term counts the number of ways to go from $D$ to
$F$ arbitrarily, which is clearly $\binom{2+3}{2}$. ∎

In principle, Proposition 2.6 gives rise to a system of equations on the
generating functions $G_{t}(x)$ of $g_{t}(n)$ for $t=1,2,\dots,m$. Then one
can solve for $G_{t}(x)$ for all $t$ and hence $\overline{F}_{m}(x)$. Indeed,
this idea allows us to work out $\overline{F}_{m}(x)$ for $m=3,4$. Then in
OEIS, we find that $\overline{F}_{3}(x)$ and $\overline{F}_{4}(x)$ correspond
to [A213403] and [A213404] respectively. We further find that a similar system
has been solved in lattice path counting theory, which will be discussed in
the next section.

##  3\. Lattice Path Enumeration

Before obtaining the main results of this section, we need to introduce some
definitions and conclusions about symmetric functions.

###  3.1. Symmetric Functions

We need some basic results on symmetric functions. Most of them can be found
in [13].

Let $X=(x_{1},x_{2},...)$ be a set of indeterminates. A _homogeneous symmetric
function_ of degree $n$ ($n$ is a non-negative integer) over a commutative
ring $R$ (with identity) is a formal power series

$SF(X)=\sum_{\nu}c_{\nu}X^{\nu},$

where $\nu$ ranges over all weak compositions $\nu=(\nu_{1},\nu_{2},...)$ of
$n$, $c_{\nu}\in R$, $X^{\nu}=x_{1}^{\nu_{1}}x_{2}^{\nu_{2}}\cdots$, and
$c_{\nu}=c_{\mu}$ if $\mu$ is obtained from $\nu$ by permuting the entries.

Let $\Lambda^{n}$ be the set of all homogeneous symmetric functions of degree
$n$ over $R$. Then $\Lambda^{n}$ is a $R$-module. If $R$ is the rational
number field $\mathbb{Q}$, then $\Lambda^{n}$ is a vector space. Let
$\Lambda=\Lambda^{0}\oplus\Lambda^{1}\oplus\cdots$ be the vector space direct
sum.

Let $\mu=(\mu_{1},\mu_{2},...)_{\geq}$ be a partition of $n$, denoted
$\mu\vdash n$. The length of $\mu$, denoted $l(\mu)$, is the number of nonzero
entries of $\mu_{i}$. There are five important basis of $\Lambda^{n}$ indexed
by partitions, namely:

  1. (1)

The monomial symmetric functions: $m_{\mu}=m_{\mu}(X)=\sum_{\nu}X^{\nu}$,
where $\nu$ ranges over all rearrangements of the given partition $\mu$ and
$m_{\emptyset}=1$.

  2. (2)

The elementary symmetric functions: $e_{\mu}=e_{\mu_{1}}e_{\mu_{2}}\cdots$,
where $e_{n}=m_{1^{n}}$ and $e_{0}=1$.

  3. (3)

The complete symmetric functions: $h_{\mu}=h_{\mu_{1}}h_{\mu_{2}}\cdots$,
where $h_{n}=\sum_{\kappa\vdash n}m_{\kappa}$ and $h_{0}=1$.

  4. (4)

The power sum symmetric functions: $p_{\mu}=p_{\mu_{1}}p_{\mu_{2}}\cdots$,
where $p_{n}=m_{n}$ and $p_{0}=1$.

  5. (5)

The Schur functions: $s_{\mu}=\sum_{\nu\vdash|\mu|}K_{\mu\nu}m_{\nu}$, where
$K_{\mu\nu}$ is the Kostka number.

We only use symmetric functions on a finite number of variables, say
$x_{1},\dots,x_{n}$. One can treat $x_{i}=0$ for $i>n$. Let $\Lambda_{n}$ be
the set of all polynomials $f(X)$ in $\mathbb{Q}[x_{1},...,x_{n}]$ that are
invariant under any permutation of the variables. Then $f(X)$ is just a
symmetric function on $X=(x_{1},...,x_{n},0,0,...)$.

The following is the classical definition of Schur functions in the variables
$(x_{1},...,x_{n})$. See, e.g., [13, Theorem 7.15.1].

######  Lemma 3.1 ([13]).

Let $\mu=(\mu_{1},\mu_{2},...)$ be a partition of length $l(\mu)\leq n$. Let
$\delta=(n-1,n-2,...,0)$. Then we have

$s_{\mu}(x_{1},...,x_{n})=\frac{a_{\mu+\delta}}{a_{\delta}},$

where $a_{\mu+\delta}=\det(x_{i}^{\mu_{j}+n-j})_{i,j=1}^{n}$ and
$a_{\delta}=\det(x_{i}^{n-j})_{i,j=1}^{n}$.

We denote the Vandermonde determinant by

$\det V(x_{1},...,x_{n}):=(-1)^{\frac{n(n-1)}{2}}a_{\delta}=\prod_{1\leq
j<i\leq n}(x_{i}-x_{j}).$

We also use the _plethystic notation_ for symmetric functions to simplify the
proof. A good reference to plethystic notation is [6]. Let
$E(x_{1},x_{2},...)$ be a formal series of rational functions in the
parameters $x_{1},x_{2},...$. We define the plethystic substitution of $E$
into $p_{k}$, denoted $p_{k}[E]$, by $p_{k}[E]=E(x_{1}^{k},x_{2}^{k},...)$.
This is to distinguish $p_{k}[E]$ from the ordinary $k$-th power sum in a set
of variables $E$.

######  Lemma 3.2 ([6]).

Let $m\in\mathbb{N}$. We have

$\displaystyle
e_{m}[x_{1}+x_{2}+\cdots+x_{n}]=\sum_{i_{1}<i_{2}<\cdots<i_{m}}x_{i_{1}}x_{i_{2}}\cdots
x_{i_{m}},$ $\displaystyle e_{m}[E-F]=\sum_{i=0}^{m}e_{i}[E]e_{m-i}[-F],\ \ \
\ e_{m}[-X]=(-1)^{m}h_{m}[X].$

######  Lemma 3.3 (Section 7.6, [13]).

Suppose $n\geq 1$. The elementary symmetric functions and the complete
symmetric functions have the following relationship:

$\sum_{i=0}^{n}(-1)^{i}e_{i}h_{n-i}=0.$

Now let’s give a result involving the Vandermonde determinant.

######  Lemma 3.4.

Let $r\geq 1$ and $r\in\mathbb{N}$. Then

$\displaystyle\det\left(\begin{array}[]{ccccc}1&w_{1}&\cdots&w_{1}^{\ell-2}&w_{1}^{-r}\\\
1&w_{2}&\cdots&w_{2}^{\ell-2}&w_{2}^{-r}\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\
1&w_{\ell}&\cdots&w_{\ell}^{\ell-2}&w_{\ell}^{-r}\\\
\end{array}\right)=\frac{(-1)^{(\ell-1)^{2}}s_{\mu}(w_{1},...,w_{\ell})\det
V(w_{1},...,w_{\ell})}{e_{\ell}^{r}(w_{1},...,w_{\ell})},$

where $\mu=(r-1,r-1,...,r-1)$ with length $\ell(\mu)=\ell-1$.

###### Proof.

By direct computation, the left hand side becomes

$\displaystyle(w_{1}^{r}\cdots
w_{\ell}^{r})^{-1}\det\left(\begin{array}[]{ccccc}w_{1}^{r}&w_{1}^{r+1}&\cdots&w_{1}^{\ell+r-2}&1\\\
w_{2}^{r}&w_{2}^{r+1}&\cdots&w_{2}^{\ell+r-2}&1\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\
w_{\ell}^{r}&w_{\ell}^{r+1}&\cdots&w_{\ell}^{\ell+r-2}&1\\\
\end{array}\right)$ $\displaystyle=$
$\displaystyle(-1)^{\frac{(\ell-1)(\ell-2)}{2}}(w_{1}^{r}\cdots
w_{\ell}^{r})^{-1}a_{(\ell+r-2,\ell+r-3,...,r,0)}(w_{1},...,w_{\ell})$
$\displaystyle(\text{by Lemma \ref{SchurDeterm}})\quad=$
$\displaystyle(-1)^{\frac{(\ell-1)(\ell-2)}{2}}(w_{1}^{r}\cdots
w_{\ell}^{r})^{-1}s_{\mu}(w_{1},...,w_{\ell})\cdot
a_{(\ell-1,\ell-2,...,1,0)}(w_{1},...,w_{\ell})$ $\displaystyle=$
$\displaystyle\frac{(-1)^{(\ell-1)^{2}}s_{\mu}(w_{1},...,w_{\ell})\det
V(w_{1},...,w_{\ell})}{e_{\ell}^{r}(w_{1},...,w_{\ell})}.$

This completes the proof. ∎

######  Lemma 3.5.

Let $l\geq 1$ and $i\geq 0$. Let $\lambda=(i,i,...,i)$ with length
$\ell(\lambda)=\ell-1$. We have

$h_{i}(w_{1}^{-1},w_{2}^{-1},...,w_{\ell}^{-1})\cdot
e_{\ell}^{i}(w_{1},w_{2},...,w_{\ell})=s_{\lambda}(w_{1},w_{2},...,w_{\ell}).$

###### Proof.

Let $\delta=(\ell-1,\ell-2,...,0)$. By the classical definition of Schur
functions in Lemma 3.1 with respect to $\lambda=(i,i,...,i,0)$, we have

$\displaystyle
s_{\lambda}(w_{1},w_{2},...,w_{\ell})=\frac{a_{\lambda+\delta}(w_{1},w_{2},...,w_{\ell})}{a_{\delta}(w_{1},w_{2},...,w_{\ell})}$
$\displaystyle=$
$\displaystyle\det\left(\begin{array}[]{ccccc}w_{1}^{i+\ell-1}&w_{1}^{i+\ell-2}&\cdots&w_{1}^{i+1}&1\\\
w_{2}^{i+\ell-1}&w_{2}^{i+\ell-2}&\cdots&w_{2}^{i+1}&1\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\
w_{\ell}^{i+\ell-1}&w_{\ell}^{i+\ell-2}&\cdots&w_{\ell}^{i+1}&1\\\
\end{array}\right)\left(\det\left(\begin{array}[]{ccccc}w_{1}^{\ell-1}&w_{1}^{\ell-2}&\cdots&w_{1}&1\\\
w_{2}^{\ell-1}&w_{2}^{\ell-2}&\cdots&w_{2}&1\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\
w_{\ell}^{\ell-1}&w_{\ell}^{\ell-2}&\cdots&w_{\ell}&1\\\
\end{array}\right)\right)^{-1}$ $\displaystyle=$
$\displaystyle\frac{(w_{1}w_{2}\cdots w_{\ell})^{i+\ell-1}}{(w_{1}w_{2}\cdots
w_{\ell})^{\ell-1}}\det\left(\begin{array}[]{cccc}1&\cdots&w_{1}^{2-\ell}&w_{1}^{-i-\ell+1}\\\
1&\cdots&w_{2}^{2-\ell}&w_{2}^{-i-\ell+1}\\\ \vdots&\ddots&\vdots&\vdots\\\
1&\cdots&w_{\ell}^{2-\ell}&w_{\ell}^{-i-\ell+1}\\\
\end{array}\right)\left(\det\left(\begin{array}[]{cccc}1&\cdots&w_{1}^{2-\ell}&w_{1}^{1-\ell}\\\
1&\cdots&w_{2}^{2-\ell}&w_{2}^{1-\ell}\\\ \vdots&\ddots&\vdots&\vdots\\\
1&\cdots&w_{\ell}^{2-\ell}&w_{\ell}^{1-\ell}\\\
\end{array}\right)\right)^{-1}$ $\displaystyle=$
$\displaystyle(w_{1}w_{2}\cdots
w_{\ell})^{i}\det\left(\begin{array}[]{cccc}(w_{1}^{-1})^{i+\ell-1}&\cdots&w_{1}^{-\ell}&1\\\
(w_{2}^{-1})^{i+\ell-1}&\cdots&w_{2}^{-\ell}&1\\\
\vdots&\ddots&\vdots&\vdots\\\
(w_{\ell}^{-1})^{i+\ell-1}&\cdots&w_{\ell}^{-\ell}&1\\\
\end{array}\right)\left(\det\left(\begin{array}[]{cccc}(w_{1}^{-1})^{\ell-1}&\cdots&w_{1}^{-\ell}&1\\\
(w_{2}^{-1})^{\ell-1}&\cdots&w_{2}^{-\ell}&1\\\ \vdots&\ddots&\vdots&\vdots\\\
(w_{\ell}^{-1})^{\ell-1}&\cdots&w_{\ell}^{-\ell}&1\\\
\end{array}\right)\right)^{-1}$ $\displaystyle=$
$\displaystyle(w_{1}w_{2}\cdots w_{\ell})^{i}\cdot
s_{i}(w_{1}^{-1},w_{2}^{-1},...,w_{\ell}^{-1})$ $\displaystyle=$
$\displaystyle
e_{\ell}^{i}(w_{1},w_{2},...,w_{\ell})h_{i}(w_{1}^{-1},w_{2}^{-1},...,w_{\ell}^{-1}).$

The last “$=$” is due to the fact that $s_{i}=h_{i}$. ∎

We will use several variations of the well-known Vandermonde’s identity

$\sum_{i=0}^{n}\binom{a}{i}\binom{b}{n-i}=\binom{a+b}{n}.$

Vandermonde’s identity can be easily proved by equating coefficients of
$x^{n}$ on both sides of the equation $(1+x)^{a}\cdot(1+x)^{b}=(1+x)^{a+b}$.
This trick is sufficient for our purpose.

######  Lemma 3.6.

Let $j\leq\ell$ and $j+1\leq r$. We have

$\sum_{m=0}^{r-1-j}(-1)^{j+r+m+1}\binom{\ell-j}{r-1-m-j}=(-1)^{r-j-1}\binom{\ell-j-1}{r-j-1}.$

######  Lemma 3.7.

Let $j\leq\ell$, $i+j\leq r-1$ and $\ell\geq 0$. We have

$\sum_{m=i}^{r-1-j}(-1)^{r+m+i+j}\binom{\ell-j}{r-1-m-j}\binom{m+l}{i+\ell}=(-1)^{i-1}\binom{r-1}{i+j}.$

######  Lemma 3.8.

Let $j\leq\ell$, $j+1\leq r$ and $\ell\geq 0$. We have

$\sum_{m=0}^{r-1-j}(-1)^{j+r+m}\binom{\ell-j}{r-1-m-j}\binom{m+\ell}{\ell}=-\binom{r-1}{j}.$

###### Sketched proofs of Lemmas 3.6, 3.7 and 3.8.

Lemma 3.6 follows by equating the coefficients of $x^{r-j-1}$ on both sides of
the identity

$\displaystyle\sum_{k=0}^{\ell-j}\binom{\ell-j}{k}x^{k}\cdot\sum_{k\geq
0}(-x)^{k}=\frac{(1+x)^{\ell-j}}{(1+x)}=(1+x)^{\ell-j-1}=\sum_{k=0}^{\ell-j-1}\binom{\ell-j-1}{k}x^{k}.$

Lemma 3.7 follows by equating the coefficients of $x^{r-1-i-j}$ on both sides
of the identity

$\displaystyle\sum_{k\geq
0}\binom{i+\ell+k}{i+j}(-x)^{k}\cdot\sum_{k=0}^{\ell-j}\binom{\ell-j}{k}(-x)^{k}=\frac{(1+x)^{\ell-j}}{(1+x)^{i+\ell+1}}=\frac{1}{(1+x)^{i+j+1}}=\sum_{k\geq
0}\binom{i+j+k}{i+\ell}(-x)^{k}.$

Lemma 3.8 follows in a similar way, and we omit the proof. ∎

###  3.2. Lattice Paths

In this subsection, we focus on the counting of lattice paths from $(0,0)$ to
$(m,n)$ that never go above a given path $P$ by using steps $N=(0,1)$ and
$E=(1,0)$. For example, let’s flip the paths discussed in Section 2. Then
$\overline{f}_{m}(n)$ counts the number of lattice paths from $(0,0)$ to
$(mn-1,mn)$ that never go above the path $(N^{m}E^{m})^{n-1}N^{m}E^{m-1}$. We
use the convention $\overline{f}_{m}(0)=1$. When $m=1$, $\sum_{n\geq
0}\overline{f}_{1}(n)x^{n}=C(x)$ is the Catalan generating function.

Bonin, de Mier and Noy ([3]) made a connection between lattice paths and
matroids. They defined the _Tutte polynomial_ of a lattice path $P$ as
follows.

$t(P;z,y)=\sum_{\sigma:\text{not go above }P}z^{i(\sigma)}y^{e(\sigma)},$

where the sum ranges over all lattice paths $\sigma$ that never go above $P$,
$i(\sigma)$ is the number of common $N$ steps of $\sigma$ and $P$, and
$e(\sigma)$ is the number of common $E$ steps of $\sigma$ and $P$ before the
first $N$ step. In particular, $t(P;1,1)$ is the number of all paths that
never go above $P$.

We need the following result, which was first obtained from Matroid Theory.

######  Lemma 3.9 ([3]).

Let $PN$ be the path obtained from $P$ by appending a $N$ step, and $PE$ be
the path obtained similarly. Then we have

$\displaystyle t(PN;z,y)=z\cdot t(P;z,y);$ $\displaystyle
t(PE;z,y)=\frac{z}{z-1}\cdot t(P;z,y)+\left(y-\frac{z}{z-1}\right)\cdot
t(P;1,y).$

Readers are invited to find a combinatorial proof of the above lemma.

Let $q(n)$ be the number of lattice paths from $(0,0)$ to $(\ell n,kn)$ that
never go above the path $(N^{k}E^{\ell})^{n}$, where $k,\ell\in\mathbb{P}$ and
$n\in\mathbb{N}$. Using Lemma 3.9, de Mier and Noy obtained a nice expression
of the generating function $Q(x)=\sum_{n\geq 0}q(n)x^{n}$. See [10, Theorem 1]
or Corollary 3.11 below. For completeness, we briefly describe their proof
process as follows.

Let $P_{n}=(N^{k}E^{\ell})^{n}$ and $A_{n}=A_{n}(z,y)=t(P_{n};z,y)$, where
$A_{0}=1$. Define the operator $\Phi$ by

$\Phi A(z,y)=\frac{z}{z-1}A(z,y)+\left(y-\frac{z}{z-1}\right)A(1,y).$

Then Lemma 3.9 gives $A_{n+1}=\Phi^{\ell}(z^{k}A_{n})$. For each
$n\in\mathbb{N}$ and $1\leq i\leq\ell$, define the polynomials

$B_{i,n}=\Phi^{i}\left(z^{k}A_{n}(z,y)\right),\ \ C_{i,n}=B_{i,n}(1,y),$

where we set $C_{0,n}(y)=A_{n}(1,y)$. Thus we have $B_{\ell,n}=A_{n+1}$ and
$C_{0,n}(1)=A_{n}(1,1)$. Denote their generating functions by

$A=A(x)=\sum_{n\geq 0}A_{n}x^{n},\ \ \ C_{i}=C_{i}(x)=\sum_{n\geq
0}C_{i,n}x^{n},\ \ \ 0\leq i\leq\ell.$

Based on the above definitions, we have

$\displaystyle
B_{1,n}=\frac{z}{z-1}z^{k}A_{n}+\left(y-\frac{z}{z-1}\right)C_{0,n},$
$\displaystyle
B_{2,n}=\frac{z}{z-1}B_{1,n}+\left(y-\frac{z}{z-1}\right)C_{1,n},$
$\displaystyle...$ (2) $\displaystyle
B_{\ell,n}=\frac{z}{z-1}B_{\ell-1,n}+\left(y-\frac{z}{z-1}\right)C_{\ell-1,n},$
$\displaystyle A_{n+1}=B_{\ell,n}.$

In the above equations, we start from the last equation and repeatedly replace
$B_{i,n}$ from the previous equation. We have

$\sum_{n\geq
0}A_{n+1}x^{n}=\frac{A-1}{x}=\frac{z^{k+\ell}}{(z-1)^{\ell}}A+(yz-
y-z)\sum_{i=1}^{\ell}\frac{z^{i-1}}{(z-1)^{i}}C_{\ell-i}.$

Simplifying and setting $y=1$ give

$A\left((z-1)^{\ell}-xz^{k+\ell}\right)=(z-1)^{\ell}-x\sum_{i=1}^{\ell}z^{i+1}(z-1)^{\ell-i}C_{\ell-i}.$
(3)

This functional equation can be solved by the well-known kernel method.

The factor $\left((z-1)^{\ell}-xz^{k+\ell}\right)$ on the left hand side is
called the kennel. As a polynomial in $z$, it has $k+\ell$ roots. By Puiseus’s
theorem, [13, Chapter 6], these roots can be treated as elements in the field
of fractional Laurent series

$\mathbb{C}^{\text{fra}}((x))=\Big{\\{}\sum_{n\geq
N}a_{n,M}x^{n/M}:a_{n,M}\in\mathbb{C},N\in\mathbb{Z},\
M\in\mathbb{P}\Big{\\}}.$

Moreover, by [13, Proposition 6.1.8], exactly $\ell$ roots of the kernel are
fractional power series. Denote them by $w_{1}(x),w_{2}(x)$,$...,w_{\ell}(x)$.
Then $w_{i}(0)=1$ for $1\leq i\leq\ell$.

The substitution $z=w_{j}$ in Equation (3) is valid for $1\leq j\leq\ell$.
This gives a system of $\ell$ linear equations in $C_{j}$:

$\sum_{i=1}^{\ell}w_{j}^{i-1}(w_{j}-1)^{\ell-i}xC_{\ell-i}=(w_{j}-1)^{\ell},\
\ 1\leq j\leq\ell.$ (4)

Because $Q(x)=C_{0}=\sum_{n\geq 0}A_{n}(1,1)x^{n}$, de Mier and Noy only
obtained a nice expression for $C_{0}$ by using Lagrange’s interpolation
formula and an identity in [13, Exercise 7.4]. We find nice expressions of
$C_{r}$ for all $r$.

Our intermediate result is the following.

######  Theorem 3.10.

Let $\ell\in\mathbb{P}$ and $1\leq r\leq\ell$. Let
$\overline{w}_{i}=\frac{w_{i}-1}{w_{i}}$ for $1\leq i\leq\ell$. Then we have

$\displaystyle
xC_{\ell-r}=\sum_{m=0}^{r-1}e_{r-1-m}(\overline{w_{1}},\cdots,\overline{w_{\ell}})\left(\sum_{i=0}^{m}(-1)^{r+m+i}\binom{m+\ell}{i+\ell}\frac{s_{\mu}(w_{1},...,w_{\ell})}{e_{\ell}^{i}}+(-1)^{r+m+1}e_{\ell}\right),$
(5)

where $e_{\ell}=e_{\ell}(w_{1},...,w_{\ell})$ and $\mu=(i,i,...,i)$ with
length $\ell(\mu)=\ell-1$.

###### Proof.

By the system (4), we have

$\sum_{i=0}^{\ell-1}\left(\frac{w_{i}}{w_{j}-1}\right)^{i}xC_{\ell-i-1}=w_{j}-1,\
\ 1\leq j\leq\ell.$ (6)

The left side of equations (6) can be regarded as the result of evaluating the
polynomial $T(X)=\sum_{i=0}^{\ell-1}(xC_{\ell-i-1})X^{i}$ of degree $\ell-1$
at $X=X_{j}=\frac{w_{j}}{w_{j}-1}$ for $1\leq j\leq\ell$. That is,
$T(X_{j})=w_{j}-1$ for $1\leq j\leq\ell$. Then using Lagrange’s interpolation
formulas, we have

$T(X)=\sum_{j=1}^{\ell}\prod_{i\neq j}\frac{X-X_{i}}{X_{j}-X_{i}}T(X_{j}).$

This is the same as in [10] up to here.

Now consider the coefficient of $X^{r-1}$ in $T(X)$. We obtain

$\displaystyle xC_{\ell-r}$ $\displaystyle=\sum_{j=1}^{\ell}\prod_{i\neq
j}\frac{1}{X_{j}-X_{i}}\left((-1)^{\ell-r}\sum_{1\leq
k_{1}<k_{2}<\cdots<k_{r-1}\leq\ell\atop k_{1},...,k_{r-1}\neq
j}\frac{X_{1}X_{2}\cdots X_{\ell}}{X_{k_{1}}\cdots
X_{k_{r-1}}X_{j}}\right)T(X_{j})$
$\displaystyle=(-1)^{\ell-r}\frac{w_{1}w_{2}\cdots
w_{\ell}}{(w_{1}-1)\cdots(w_{\ell}-1)}\sum_{j=1}^{\ell}\prod_{i\neq
j}\frac{(w_{j}-1)(w_{i}-1)}{w_{i}-w_{j}}\cdot$ $\displaystyle\ \
\cdot\left(\sum_{1\leq k_{1}<k_{2}<\cdots<k_{r-1}\leq\ell\atop
k_{1},...,k_{r-1}\neq
j}\frac{(w_{k_{1}}-1)\cdots(w_{k_{r-1}}-1)(w_{j}-1)}{w_{k_{1}}w_{k_{2}}\cdots
w_{k_{r-1}}w_{j}}\right)(w_{j}-1)$ $\displaystyle=(-1)^{\ell-r}w_{1}\cdots
w_{\ell}\sum_{j=1}^{\ell}\prod_{i\neq
j}\frac{-1}{w_{j}-w_{i}}\cdot\left(\sum_{1\leq
k_{1}<\cdots<k_{r-1}\leq\ell\atop k_{1},...,k_{r-1}\neq
j}\frac{(w_{k_{1}}-1)\cdots(w_{k_{r-1}}-1)}{w_{k_{1}}w_{k_{2}}\cdots
w_{k_{r-1}}w_{j}}\right)(w_{j}-1)^{\ell}$ $\displaystyle=(-1)^{r+1}w_{1}\cdots
w_{\ell}\sum_{j=1}^{\ell}\prod_{i\neq
j}\frac{1}{w_{j}-w_{i}}\cdot\left(\sum_{1\leq
k_{1}<\cdots<k_{r-1}\leq\ell\atop k_{1},...,k_{r-1}\neq
j}\frac{(w_{k_{1}}-1)\cdots(w_{k_{r-1}}-1)}{w_{k_{1}}w_{k_{2}}\cdots
w_{k_{r-1}}}\right)\frac{(w_{j}-1)^{\ell}}{w_{j}}.$

Denote by

$g(w_{j})=\left(\sum_{1\leq k_{1}<\cdots<k_{r-1}\leq\ell\atop
k_{1},...,k_{r-1}\neq
j}\frac{(w_{k_{1}}-1)\cdots(w_{k_{r-1}}-1)}{w_{k_{1}}w_{k_{2}}\cdots
w_{k_{r-1}}}\right)\frac{(w_{j}-1)^{\ell}}{w_{j}}.$

Then by definition of the Vandermonde determinant, we have

$\displaystyle xC_{\ell-r}$ $\displaystyle=(-1)^{r+1}w_{1}\cdots
w_{\ell}\sum_{j=1}^{\ell}\prod_{i\neq j}\frac{1}{w_{j}-w_{i}}\cdot g(w_{j})$
$\displaystyle=(-1)^{r+1}w_{1}\cdots
w_{\ell}\sum_{j=1}^{\ell}\frac{(-1)^{\ell-j}g(w_{j})\det
V(w_{1},...,w_{\ell}\setminus w_{j})}{\det V(w_{1},...,w_{\ell})},$

where $\det V(w_{1},...,w_{\ell}\setminus w_{j})$ represents the Vandermonde
determinant of the variables
$w_{1},...,w_{j-1},w_{j+1},...,w_{\ell}$. Furthermore, we have

$\displaystyle G=\sum_{j=1}^{\ell}(-1)^{\ell+j}g(w_{j})\det
V(w_{1},...,w_{\ell}\setminus
w_{j})=\det\left(\begin{array}[]{ccccc}1&w_{1}&\cdots&w_{1}^{\ell-2}&g(w_{1})\\\
1&w_{2}&\cdots&w_{2}^{\ell-2}&g(w_{1})\\\
1&w_{3}&\cdots&w_{3}^{\ell-2}&g(w_{3})\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\
1&w_{\ell}&\cdots&w_{\ell}^{\ell-2}&g(w_{\ell})\\\ \end{array}\right).$

Observe that $G$ becomes i) $0$ if $g(w)$ is $1,w,\dots,w^{\ell-2}$; ii) $\det
V(w_{1},...,w_{\ell})$ if $g(w)=w^{\ell-1}$; iii)
$\frac{(-1)^{(\ell-1)^{2}}s_{\mu}\det
V(w_{1},...,w_{\ell})}{e_{\ell}^{i+1}(w_{1},...,w_{\ell})}$ (by Lemma 3.4) if
$g(w)=w^{-i-1}$ for $i\geq 0$. Thus we shall write $g(w_{j})$ as a polynomial
in $w_{j}$ with coefficients symmetric in $w_{1},\dots,w_{\ell}$.

To this end, we use plethestic notation by treating
$\overline{w}_{i}=\frac{w_{i}-1}{w_{i}}$ for $1\leq i\leq\ell$ as variables.
Then $w_{i}=\frac{\overline{w}_{i}-1}{\overline{w}_{i}}$ is not a variable.
Let
$\overline{w}=\overline{w_{1}}+\overline{w_{2}}+\cdots+\overline{w_{\ell}}$.
By Lemma 3.2, we have

$\displaystyle g(w_{j})$
$\displaystyle=e_{r-1}[\overline{w}-\overline{w}_{j}]\cdot\frac{(w_{j}-1)^{\ell}}{w_{j}}=\sum_{m=0}^{r-1}e_{r-1-m}[\overline{w}]\cdot
e_{m}[-\overline{w_{j}}]\cdot\frac{(w_{j}-1)^{\ell}}{w_{j}}$
$\displaystyle=\sum_{m=0}^{r-1}e_{r-1-m}[\overline{w}]\cdot(-1)^{m}\cdot\frac{(w_{j}-1)^{m+\ell}}{w_{j}^{m+1}}=\sum_{m=0}^{r-1}(-1)^{m}e_{r-1-m}[\overline{w}]\sum_{i=0}^{m+\ell}(-1)^{i}\binom{m+\ell}{i}w_{j}^{\ell-i-1}.$

Therefore, we obtain

$\displaystyle G$
$\displaystyle=\sum_{m=0}^{r-1}(-1)^{m}e_{r-1-m}[\overline{w}]\left(\sum_{i=0}^{m}(-1)^{\ell+i+(\ell-1)^{2}}\binom{m+\ell}{i+\ell}\frac{s_{\mu}\det
V(w_{1},...,w_{\ell})}{e_{\ell}^{i+1}}+\det V(w_{1},...,w_{\ell})\right).$

Now we have

$\displaystyle xC_{\ell-r}$ $\displaystyle=(-1)^{r+1}w_{1}\cdots
w_{\ell}\left(\sum_{m=0}^{r-1}(-1)^{m}e_{r-1-m}[\overline{w}]\left(\sum_{i=0}^{m}(-1)^{i+1}\binom{m+\ell}{i+\ell}\frac{s_{\mu}}{e_{\ell}^{i+1}}+1\right)\right)$
$\displaystyle=\sum_{m=0}^{r-1}e_{r-1-m}[\overline{w}]\left(\sum_{i=0}^{m}(-1)^{r+m+i}\binom{m+\ell}{i+\ell}\frac{s_{\mu}}{e_{\ell}^{i}}+(-1)^{r+m+1}e_{\ell}\right).$

This completes the proof. ∎

Now we present our proof of Theorem 1.2.

###### Proof of Theorem 1.2.

For $1\leq r\leq\ell$, let $f_{r}(n)$ be the number of lattice paths from
$(0,0)$ to $(\ell n-r,kn)$ that never go above the path
$(N^{k}E^{\ell})^{n-1}N^{k}E^{\ell-r}$. We consider the generating function
$F_{r}(x)=\sum_{n\geq 0}f_{r}(n)x^{n}$ with the convention $f_{r}(0)=1$. Then
it is easy to see that $F_{r}(x)=xC_{\ell-r}+1$ for $1\leq r\leq\ell$.

To simplify Equation (5), we need to write $e_{r-1-m}[\overline{w}]$ in terms
of $e_{i}=e_{i}(w_{1},\dots,w_{\ell})$. Consider the generating function of
$e_{i}[\overline{w}]$ as follows.

$\displaystyle\prod_{i=1}^{\ell}(1+t\overline{w}_{i})$
$\displaystyle=\prod_{i=1}^{\ell}\left(1+t(1-w_{i}^{-1})\right)=\prod_{i=1}^{\ell}(1+t-t\cdot
w_{i}^{-1})$
$\displaystyle=(1+t)^{\ell}\prod_{i=1}^{\ell}\left(1-\frac{t}{1+t}w_{i}^{-1}\right)$
$\displaystyle=(1+t)^{\ell}\sum_{j\geq
0}e_{j}(w_{1}^{-1},w_{2}^{-1},...w_{\ell}^{-1})(-1)^{j}\left(\frac{t}{1+t}\right)^{j}$
$\displaystyle=\sum_{j\geq
0}e_{j}(w_{1}^{-1},w_{2}^{-1},...,w_{\ell}^{-1})(-1)^{j}t^{j}(1+t)^{\ell-j}.$

Taking the coefficient of $t^{r-m-1}$ on both sides of the above equation, we
obtain

$\displaystyle e_{r-1-m}[\overline{w}]$
$\displaystyle=[t^{r-m-1-j}]\sum_{j=0}^{r-m-1}(-1)^{j}e_{j}(w_{1}^{-1},w_{2}^{-1},...,w_{\ell}^{-1})(1+t)^{\ell-j}$
(7)
$\displaystyle=\sum_{j=0}^{r-m-1}(-1)^{j}\binom{\ell-j}{r-m-1-j}e_{j}(w_{1}^{-1},w_{2}^{-1},...,w_{\ell}^{-1})$
$\displaystyle=e_{\ell}^{-1}\sum_{j=0}^{r-m-1}(-1)^{j}\binom{\ell-j}{r-m-1-j}e_{\ell-j}(w_{1},w_{2},...,w_{\ell}).$

By Equation (5), we first obtain

$\displaystyle\sum_{m=0}^{r-1}e_{r-1-m}[\overline{w}](-1)^{r+m+1}e_{\ell}=$
$\displaystyle\sum_{m=0}^{r-1}\sum_{j=0}^{r-1-m}(-1)^{r+m+1+j}\binom{\ell-j}{r-1-m-j}e_{\ell-j}(w_{1},w_{2},...,w_{\ell})$
$\displaystyle=$
$\displaystyle\sum_{j=0}^{r-1}\sum_{m=0}^{r-1-j}(-1)^{j+r+m+1}\binom{\ell-j}{r-1-m-j}e_{\ell-j}(w_{1},w_{2},...,w_{\ell})$
$\displaystyle(\text{By Lemma }\ref{CTbinomTT1}.)\ \ \ =$
$\displaystyle\sum_{j=0}^{r-1}(-1)^{r-j-1}\binom{\ell-j-1}{r-j-1}e_{\ell-j}(w_{1},w_{2},...,w_{\ell})$
$\displaystyle=$
$\displaystyle\sum_{i=0}^{r-1}(-1)^{i}\binom{\ell-r+i}{i}e_{\ell-r+1+i}(w_{1},w_{2},...,w_{\ell}).$
(8)

By $F_{r}(x)=xC_{\ell-r}+1$ and observing Equation (5), we assert that

$\displaystyle
1+\sum_{m=0}^{r-1}e_{r-1-m}[\overline{w}]\left(\sum_{i=0}^{m}(-1)^{r+m+i}\binom{m+\ell}{i+\ell}\frac{s_{\mu}}{e_{\ell}^{i}}\right)=0.$
(9)

i.e.,

$\displaystyle
1+\sum_{m=0}^{r-1}\left(\sum_{j=0}^{r-m-1}(-1)^{j}\binom{\ell-j}{r-m-1-j}e_{j}(w_{1}^{-1},...,w_{\ell}^{-1})\right)\left(\sum_{i=0}^{m}(-1)^{r+m+i}\binom{m+\ell}{i+\ell}\frac{s_{\mu}}{e_{\ell}^{i}}\right)=0.$

We first consider the case $i=0$ on the left side of the above equation. We
have

$\displaystyle
1+\sum_{m=0}^{r-1}\left(\sum_{j=0}^{r-m-1}(-1)^{j}\binom{\ell-j}{r-m-1-j}e_{j}(w_{1}^{-1},...,w_{\ell}^{-1})\right)\left((-1)^{r+m}\binom{m+\ell}{\ell}\right)$
$\displaystyle=$ $\displaystyle
1+\sum_{j=0}^{r-1}\sum_{m=0}^{r-1-j}(-1)^{r+m+j}\binom{\ell-j}{r-1-m-j}\binom{m+\ell}{\ell}e_{j}(w_{1}^{-1},...,w_{\ell}^{-1})$
$\displaystyle=$ $\displaystyle
1+\sum_{j=0}^{r-1}-\binom{r-1}{j}e_{j}(w_{1}^{-1},...,w_{\ell}^{-1})\ \ \
(\text{By Lemma }\ref{CTbinomTT2}.)$ $\displaystyle=$
$\displaystyle-\sum_{j=1}^{r-1}\binom{r-1}{j}e_{j}(w_{1}^{-1},...,w_{\ell}^{-1}).$

Now we consider the case $i>0$. By Equation (9), we have

$\displaystyle\sum_{m=1}^{r-1}\sum_{j=0}^{r-m-1}\sum_{i=1}^{m}(-1)^{r+m+i+j}\binom{\ell-j}{r-m-1-j}\binom{m+\ell}{i+\ell}e_{j}(w_{1}^{-1},...,w_{\ell}^{-1})\frac{s_{\mu}}{e_{\ell}^{i}}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{r-1}\sum_{j=0}^{r-1-i}\sum_{m=i}^{r-1-j}(-1)^{r+m+i+j}\binom{\ell-j}{r-m-1-j}\binom{m+\ell}{i+\ell}e_{j}(w_{1}^{-1},...,w_{\ell}^{-1})\frac{s_{\mu}}{e_{\ell}^{i}}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{r-1}\sum_{j=0}^{r-1-i}(-1)^{i-1}\binom{r-1}{j+i}e_{j}(w_{1}^{-1},...,w_{\ell}^{-1})\frac{s_{\mu}}{e_{\ell}^{i}}.\
\ \ (\text{By Lemma }\ref{CTbinomTT3}.)$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{r-1}\sum_{j=0}^{r-1-i}(-1)^{i-1}\binom{r-1}{j+i}e_{j}(w_{1}^{-1},...,w_{\ell}^{-1})h_{i}(w_{1}^{-1},...,w_{\ell}^{-1})\
\ \ (\text{By Lemma }\ref{HESlambda}.)$ $\displaystyle=$
$\displaystyle\binom{r-1}{1}e_{1}(w_{1}^{-1},...,w_{\ell}^{-1})+\cdots+\binom{r-1}{r-1}e_{r-1}(w_{1}^{-1},...,w_{\ell}^{-1})\
\ \ (\text{By Lemma }\ref{EtoHorHtoE}.)$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{r-1}\binom{r-1}{j}e_{j}(w_{1}^{-1},...,w_{\ell}^{-1}).$

Therefore, Equation (9) is correct. Furthermore, combining Equations (5),
(3.2), and (9), we have

$F_{r}(x)=xC_{\ell-r}+1=\sum_{i=0}^{r-1}(-1)^{i}\binom{\ell-r+i}{i}e_{\ell-r+1+i}(w_{1},w_{2},...,w_{\ell}).$

This completes the proof. ∎

The following results were first obtained by de Mier and Noy.

######  Corollary 3.11 ([10]).

Following the notation in Theorem 1.2. Let $q(n)$ be the number of lattice
paths from $(0,0)$ to $(\ell n,kn)$ that never go above the path
$(N^{k}E^{\ell})^{n}$. Then the generating function $Q(x)=\sum_{n\geq
0}q(n)x^{n}$ is given by

$Q(x)=\frac{-1}{x}(1-w_{1})\cdots(1-w_{\ell}).$

###### Proof.

By the lattice path interpretation of $C_{0}$, we have $Q(x)=C_{0}$. By
Theorem 1.2, we have

$\displaystyle Q(x)$
$\displaystyle=\frac{1}{x}(F_{\ell}(x)-1)=\frac{1}{x}\left(\sum_{i=0}^{\ell-1}(-1)^{i}e_{i+1}-1\right)$
$\displaystyle=\frac{1}{x}\left(\sum_{i=0}^{\ell}(-1)^{i-1}e_{i}\right)=\frac{-1}{x}(1-w_{1})(1-w_{2})\cdots(1-w_{\ell}).$

This completes the proof. ∎

######  Corollary 3.12.

Following the notation in Theorem 1.2. If $r=1$, then we have

$F_{1}(x)=w_{1}w_{2}\cdots w_{\ell}.$

If $r=2$, then we have

$F_{2}(x)=\left(1-\ell+\sum_{j=1}^{\ell}\frac{1}{w_{j}}\right)\cdot\prod_{j=1}^{\ell}w_{j}.$

In particular, if $r=1$ and $k=\ell$, then

$F_{1}(x)=\prod_{j=1}^{\ell}C(\xi^{j}x^{\frac{1}{\ell}}).$

If $r=2$ and $k=\ell$, then

$F_{2}(x)=\left(1-\ell+\sum_{j=1}^{\ell}\frac{1}{C(\xi^{j}x^{\frac{1}{\ell}})}\right)\cdot\prod_{j=1}^{\ell}C(\xi^{j}x^{\frac{1}{\ell}}),$

where $C(x)$ is the Catalan function and $\xi$ is a primitive $\ell$-th root
of unity $\xi=e^{\frac{2\pi i}{\ell}}$.

##  4\. Exponential Formulas for $Q(x)$ and $F_{1}(x)$

In this section, we mainly give two exponential formulas in Theorems 4.1 and
4.3, using ideas from the doctoral thesis of the second author, especially
[15, Chapter 1, 1-5]. The thesis also includes some basic knowledge of
Puiseux’s theorem.

Throughout this section, we always use the following factorization

$\displaystyle(w-1)^{\ell}-xw^{k+\ell}=-x(w-w_{1})\cdots(w-w_{\ell})(w-w_{\ell+1})\cdots(w-w_{k+\ell}).$
(10)

By Puiseux’s theorem, we may assume $w_{i}$ are all fractional Laurent series
in $\mathbb{C}^{\text{fra}}((x))$ and $w_{1},...,w_{\ell}$ is the unique
fractional power series. Moreover, $w_{i}|_{x=0}=1$ for $1\leq i\leq\ell$.

Now we state our first result.

######  Theorem 4.1.

Follow the notation in Corollary 3.11. Let $q(n)$ be the number of lattice
paths from $(0,0)$ to $(\ell n,kn)$ that never go above the path
$(N^{k}E^{\ell})^{n}$. Then we have

$Q(x)=\sum_{n\geq 0}q(n)x^{n}=\exp\left(\sum_{n\geq 1}\binom{kn+\ell n}{\ell
n}\frac{x^{n}}{n}\right).$

###### Proof.

Put $w=u+1$ in (10). We obtain the factorization

$\displaystyle
u^{\ell}-x(u+1)^{k+\ell}=-x(u-u_{1})(u-u_{2})\cdots(u-u_{k+\ell}),$ (11)

where $u_{i}=w_{i}-1,\ 1\leq i\leq k+\ell$ are fractional Laurent series, and
$u_{1},...,u_{\ell}$ are the only fractional power series. Moreover,
$u_{i}|_{x=0}=0$ for $1\leq i\leq\ell$.

Rewrite (11) as

$\displaystyle
1-\frac{x(u+1)^{k+\ell}}{u^{\ell}}=A(x)\Big{(}1-\frac{u_{1}}{u}\Big{)}\cdots\Big{(}1-\frac{u_{\ell}}{u}\Big{)}\Big{(}1-\frac{u}{u_{\ell+1}}\Big{)}\cdots\Big{(}1-\frac{u}{u_{k+\ell}}\Big{)}.$
(12)

Then by comparing the lowest power terms of $u$ on both sides of the above
equation, we obtain

$-\frac{x}{u^{\ell}}=A(x)\cdot(-\frac{u_{1}}{u})\cdots(-\frac{u_{\ell}}{u}).$

Therefore by Corollary 3.11, we have

$(A(x))^{-1}=\frac{(-1)^{\ell+1}}{x}u_{1}\cdots
u_{\ell}=\frac{(-1)^{\ell+1}}{x}(w_{1}-1)\cdots(w_{\ell}-1)=Q(x).$

Now we extract $(A(x))^{-1}$ through taking logarithms and working in
$\mathbb{C}((u))^{\text{fra}}((x))$, i.e., the field of fractional Laurent
series in $x$ with coefficients Laurent series in $u$. We have

$\displaystyle\ln\left(1-\frac{x(u+1)^{k+\ell}}{u^{\ell}}\right)^{-1}$
$\displaystyle=\ln(A(x))^{-1}+\sum_{i=1}^{\ell}\ln\left(1-\frac{u_{i}}{u}\right)^{-1}+\sum_{j=\ell+1}^{\ell+k}\ln\left(1-\frac{u}{u_{i}}\right)^{-1}$
$\displaystyle=\ln(A(x))^{-1}+\sum_{i=1}^{\ell}\sum_{n\geq
1}\frac{u_{i}^{n}}{nu^{n}}+\sum_{j=\ell+1}^{\ell+k}\sum_{n\geq
1}\frac{u^{n}}{nu_{j}^{n}}$ $\displaystyle=\ln(A(x))^{-1}+\sum_{n\geq
1}\frac{1}{nu^{n}}\sum_{i=1}^{\ell}u_{i}^{n}+\sum_{n\geq
1}\frac{u^{n}}{n}\sum_{j=\ell+1}^{\ell+k}\frac{1}{u_{j}^{n}}.$ (13)

On the right hand side of Equation (13), the second term only contains
negative power terms of $u$, and the third term only contains positive power
terms of $u$. Thus the first term $\ln(A(x))^{-1}$ is exactly the constant
term, denoted $\mathop{\mathrm{CT}}_{u}$, and we have

$\displaystyle\ln(A(x))^{-1}$
$\displaystyle=\mathop{\mathrm{CT}}_{u}\ln\left(1-\frac{x(u+1)^{k+\ell}}{u^{\ell}}\right)^{-1}=\mathop{\mathrm{CT}}_{u}\sum_{n\geq
1}\frac{1}{n}\left(\frac{(1+u)^{k+\ell}\cdot x}{u^{\ell}}\right)^{n}$
$\displaystyle=\mathop{\mathrm{CT}}_{u}\sum_{n\geq 1}\frac{(1+u)^{kn+\ell
n}}{nu^{\ell n}}\cdot x^{n}=\sum_{n\geq 1}\binom{kn+\ell n}{\ell
n}\frac{x^{n}}{n}.$

Therefore,

$Q(x)=(A(x))^{-1}=\exp\left(\sum_{n\geq 1}\binom{kn+\ell n}{\ell
n}\frac{x^{n}}{n}\right).$

This completes the proof. ∎

By observing the second term on the right hand side of Equation (13), we found
that

$\sum_{m\geq 1}\frac{1}{mu^{m}}\sum_{i=1}^{\ell}u_{i}^{m}=\sum_{m\geq
1}\frac{p_{m}(u_{1},...,u_{\ell})}{m}u^{-m},$

where $p_{m}$ is the power sum symmetric function. Thus we can also extract an
interesting formula for $p_{m}(u_{1},...,u_{\ell})$ as follows.
$m^{-1}p_{m}(u_{1},...,u_{\ell})$ is the coefficient of $u^{-m}$ in Equation
(13). Therefore we have

$\displaystyle
m^{-1}p_{m}(u_{1},...,u_{\ell})=[u^{-m}]\ln\left(1-\frac{x(u+1)^{k+\ell}}{u^{\ell}}\right)^{-1}=[u^{-m}]\sum_{n\geq
1}\frac{(1+u)^{kn+\ell n}x^{n}}{nu^{\ell n}}=\sum_{n\geq 1}\binom{kn+\ell
n}{\ell n-m}\frac{x^{n}}{n},$

where $\binom{kn+\ell n}{\ell n-m}=0$ for $\ell n<m$. We summarize the above
results as the following proposition.

######  Proposition 4.2.

Let $m\geq 1$. Let $w_{1},...,w_{\ell}$ be the unique solutions of the
equation $(w-1)^{\ell}-xw^{k+\ell}=0$ that are fractional power series. We
have

$p_{m}(w_{1}-1,...,w_{\ell}-1)=m\cdot\sum_{n\geq 1}\binom{kn+\ell n}{\ell
n-m}\frac{x^{n}}{n},$

where $\binom{kn+\ell n}{\ell n-m}=0$ for $\ell n<m$.

######  Theorem 4.3.

Follow the notation in Theorem 1.2. Let $f_{1}(n)$ be the number of lattice
paths from $(0,0)$ to $(\ell n-1,kn)$ that never go above the path
$(N^{k}E^{\ell})^{n-1}N^{k}E^{\ell-1}$. Then we have

$F_{1}(x)=\sum_{n\geq 0}f_{1}(n)x^{n}=\exp\left(\sum_{n\geq 1}\binom{kn+\ell
n-1}{\ell n-1}\frac{x^{n}}{n}\right).$

###### Proof.

Rewrite Equation (10) as

$(w-1)^{\ell}-xw^{k+\ell}=B(x)\cdot\prod_{i=1}^{\ell}(w-w_{i})\prod_{j=\ell+1}^{\ell+k}\left(1-\frac{w}{w_{j}}\right),$

where

$B(x)=(-1)^{k+1}x\cdot w_{\ell+1}\cdots w_{\ell+k}.$

Thus we obtain

$1-\frac{xw^{k+\ell}}{(w-1)^{\ell}}=B(x)\cdot\prod_{i=1}^{\ell}\frac{w-w_{i}}{w-1}\prod_{j=\ell+1}^{\ell+k}\left(1-\frac{w}{w_{j}}\right).$

Now making the substitution $w\to w^{-1}$ and simplifying gives

$\displaystyle
1-\frac{xw^{-k}}{(1-w)^{\ell}}=B(x)\cdot\prod_{i=1}^{\ell}\frac{1-ww_{i}}{1-w}\prod_{j=\ell+1}^{\ell+k}\left(1-\frac{1}{ww_{j}}\right).$
(14)

By Equation (14), we have

$w^{k}(1-w)^{\ell}-x=B(x)\cdot\prod_{i=1}^{\ell}(1-w_{i}w)\prod_{j=\ell+1}^{\ell+k}\left(w-\frac{1}{w_{j}}\right).$

Then by comparing the coefficients of $w^{k+\ell}$ on both sides of the above
equation, we obtain

$(-1)^{\ell}w^{k+\ell}=B(x)\cdot(-1)^{\ell}w^{\ell+k}\prod_{i=1}^{\ell}w_{i}.$

Therefore we have

$(B(x))^{-1}=w_{1}w_{2}\cdots w_{\ell}=F_{1}(x),$

where the second equality follows by Corollary 3.12.

Again, by taking logarithms in (14), we obtain

$\displaystyle\ln\left(1-\frac{xw^{-k}}{(1-w)^{\ell}}\right)^{-1}$
$\displaystyle=\ln(B(x))^{-1}+\sum_{i=1}^{\ell}\ln\left(\frac{1-ww_{i}}{1-w}\right)^{-1}+\sum_{j=\ell+1}^{\ell+k}\ln\left(1-\frac{1}{ww_{j}}\right)^{-1}$
$\displaystyle=\ln(B(x))^{-1}+\sum_{i=1}^{\ell}\ln\left(1-\frac{w(w_{i}-1)}{1-w}\right)^{-1}+\sum_{j=\ell+1}^{\ell+k}\ln\left(1-\frac{1}{ww_{j}}\right)^{-1}$
$\displaystyle=\ln(B(x))^{-1}+\sum_{i=1}^{\ell}\sum_{n\geq
1}\frac{1}{n}\left(\frac{(w_{i}-1)w}{1-w}\right)^{n}+\sum_{j=\ell+1}^{\ell+k}\sum_{n\geq
1}\frac{1}{n(ww_{j})^{n}}.$ (15)

On the right hand side of Equation (15), the second term only contains
positive power terms of $w$, and the third term only contains negative power
terms of $w$. Thus the first term is just the constant term

$\displaystyle\ln(B(x))^{-1}=\mathop{\mathrm{CT}}\limits_{w}\ln\left(1-\frac{xw^{-k}}{(1-w)^{\ell}}\right)^{-1}=\sum_{n\geq
1}\frac{x^{n}}{n}\mathop{\mathrm{CT}}\limits_{w}\frac{1}{w^{kn}(1-w)^{\ell
n}}=\sum_{n\geq 1}\binom{kn+\ell n-1}{kn}\frac{x^{n}}{n}.$

Thus we have

$F_{1}(x)=(B(x))^{-1}=\exp\left(\sum_{n\geq 1}\binom{kn+\ell n-1}{\ell
n-1}\frac{x^{n}}{n}\right).$

This completes the proof. ∎

###### Proof of Theorem 1.1.

The theorem is followed by Proposition 2.3, Theorem 1.2 and Theorem 1.4. ∎

Similar to Proposition 4.2, we can obtain the following result.

######  Proposition 4.4.

Let $m\geq 1$. Let $w_{1},...,w_{\ell}$ be the unique solutions of the
equation $(w-1)^{\ell}-xw^{k+\ell}=0$ that are fractional power series. Let
$w_{\ell+1},...,w_{\ell+k}$ be the other $k$ solutions in the field of
fractional Laurent series $\mathbb{C}^{\text{fra}}((x))$. We have

$p_{m}(w_{\ell+1}^{-1},...,w_{\ell+k}^{-1})=m\cdot\sum_{n\geq 1}\binom{\ell
n+kn-m-1}{kn-m}\frac{x^{n}}{n},$

where $\binom{kn+\ell n-m-1}{kn-m}=0$ for $kn<m$ or $kn+\ell n<m+1$.

##  5\. Two Byproducts

Our proof of Theorem 1.2 seems lengthy, so we tried to solve the system (4)
for $C_{t}$, $0\leq t\leq\ell$ in other ways. This leads to two byproducts,
namely, Corollary 5.3 and Theorem 5.4. Simple proofs of the byproducts may
give rise simple proofs of Theorem 1.2.

###  5.1. Recursive Operation

In [10], de Mier and Noy obtained the full Tutte polynomials as follows:

$\sum_{n\geq
0}A_{n}(z,y)x^{n}=\frac{-(z-w_{1})\cdots(z-w_{\ell})}{(xz^{k+\ell}-(z-1)^{\ell})(y+w_{1}-yw_{1})\cdots(y+w_{\ell}-yw_{\ell})}.$

We only need the specialization at $y=1$. Let

$\displaystyle\mathrm{\overline{A}}(z):=\sum_{n\geq
0}A_{n}(z,1)x^{n}=\frac{-(z-w_{1})\cdots(z-w_{\ell})}{xz^{k+\ell}-(z-1)^{\ell}}.$
(16)

######  Theorem 5.1.

Following the notation in Theorem 1.2. Let $1\leq r\leq\ell-1$. Then we have

$F_{r}(x)=1+\sum_{i=1}^{\ell-r}S(\ell-r,i)x\mathrm{\overline{B}}_{1}^{(i-1)}(1),$

where

$\mathrm{\overline{B}}_{1}(z)=(k+1)z^{k}\mathrm{\overline{A}}(z)+z^{k+1}\mathrm{\overline{A}}^{\prime}(z),\
\ \
\mathrm{\overline{A}}(z)=\frac{-(z-w_{1})\cdots(z-w_{\ell})}{xz^{k+\ell}-(z-1)^{\ell}},$

the $S(\ell-r,i)$ are Stirling numbers of the second kind and
$\mathrm{\overline{B}}^{(i-1)}_{1}(z)$ is a $(i-1)$-th degree differential
operation for $\mathrm{\overline{B}}_{1}(z)$.

###### Proof.

Follow the notation in Subsection 3.2. Let

$\mathrm{\overline{B}}_{i}(z)=\sum_{n\geq 0}B_{1,n}x^{n},\ \ \ 1\leq
i\leq\ell.$

We simultaneously calculate the generating functions for both sides of
Equation (2) at $y=1$. This gives the following equations.

$\displaystyle\mathrm{\overline{B}}_{1}(z)=\frac{z^{k+1}\mathrm{\overline{A}}(z)-C_{0}}{z-1},\
\
\mathrm{\overline{B}}_{2}(z)=\frac{z\mathrm{\overline{B}}_{1}(z)-C_{1}}{z-1},\
\ \cdots,\ \
\mathrm{\overline{B}}_{\ell}(z)=\frac{z\mathrm{\overline{B}}_{\ell-1}(z)-C_{\ell-1}}{z-1}.$

By L’Hospital’s rule, we have

$\mathrm{\overline{B}}_{1}(z)=(k+1)z^{k}\mathrm{\overline{A}}(z)+z^{k+1}\mathrm{\overline{A}}^{\prime}(z),\
\ \
\mathrm{\overline{B}}_{i}(z)=\mathrm{\overline{B}}_{i-1}(z)+z\mathrm{\overline{B}}^{\prime}_{i-1}(z),\
\ 2\leq i\leq\ell.$

By the recursion for the Stirling numbers of the second kind $S(t,i)$ (see
[11, A008277] or [12, Chapter 1]):

$S(t,i)=i\cdot S(t-1,i)+S(t-1,i-1),\ \ S(1,1)=1,\ \ S(t,i)=0,(i>t),$

we have

$\mathrm{\overline{B}}_{t}(z)=\sum_{i=1}^{t}S(t,i)z^{i-1}\mathrm{\overline{B}}^{(i-1)}_{1}(z),\
\ 1\leq t\leq\ell,$

where $\mathrm{\overline{B}}^{(i-1)}_{1}(z)$ is a $(i-1)$-th derivative of
$\mathrm{\overline{B}}_{1}(z)$ with respect to $z$. Furthermore, by
$C_{t}=\sum_{n\geq 0}C_{t,n}x^{n}=\mathrm{\overline{B}}_{t}(1)$, $1\leq
t\leq\ell-1$, we have

$C_{t}=\sum_{i=1}^{t}S(t,i)\mathrm{\overline{B}}_{1}^{(i-1)}(1),\ \ 1\leq
t\leq\ell-1.$

Note that $C_{0}=\mathrm{\overline{A}}(1)$.

The proof is then completed by $F_{r}(x)=xC_{\ell-r}+1$ for $1\leq r\leq\ell$.
∎

######  Corollary 5.2.

Follow the notation in Theorem 5.1. We have

$F_{\ell-1}(x)=1+\left(\ell-1-\sum_{i=1}^{\ell}\frac{1}{1-w_{i}}\right)\prod_{i=1}^{\ell}(1-w_{i}).$

###### Proof.

By Theorem 5.1, we have

$\mathrm{\overline{A}}(1)=\frac{-1}{x}\prod_{j=1}^{\ell}(1-w_{j}),\ \ \ \ \
\mathrm{\overline{A}}^{\prime}(1)=-\frac{1}{x}\prod_{j=1}^{\ell}(1-w_{j})\left(\sum_{i=1}^{\ell}\frac{1}{1-w_{i}}-\ell-k\right).$

Moreover,

$\mathrm{\overline{B}}_{1}(1)=(k+1)\mathrm{\overline{A}}(1)+\mathrm{\overline{A}}^{\prime}(1)=\frac{1}{x}\left(\ell-1-\sum_{i=1}^{\ell}\frac{1}{1-w_{i}}\right)\prod_{j=1}^{\ell}(1-w_{j}).$

Furthermore, by Theorem 5.1, we have
$F_{\ell-1}=1+x\mathrm{\overline{B}}_{1}(1)$. This completes the proof. ∎

Theorem 1.2 implies that

$\displaystyle F_{\ell-1}(x)$
$\displaystyle=\sum_{i=0}^{\ell-2}(-1)^{i}\binom{1+i}{i}e_{i+2}(w_{1},...,w_{\ell})$
$\displaystyle=e_{2}(w_{1},...,w_{\ell})-2e_{3}(w_{1},...,w_{\ell})+\cdots+(-1)^{\ell-2}(\ell-1)e_{\ell}(w_{1},...,w_{\ell}).$

This result can also be explained by Corollary 5.2 as follows.

$\displaystyle F_{\ell-1}(x)$
$\displaystyle=1+(1-w_{1})\cdots(1-w_{\ell})\left(\ell-1-\sum_{i=1}^{\ell}\frac{1}{1-w_{i}}\right)$
$\displaystyle=1+(\ell-1)(e_{0}-e_{1}+e_{2}+\cdots+(-1)^{\ell}e_{\ell})-\left(\frac{\prod_{j=1}^{\ell}(1-w_{j})}{1-w_{1}}+\cdots+\frac{\prod_{j=1}^{\ell}(1-w_{j})}{1-w_{\ell}}\right)$
$\displaystyle=1+(\ell-1)(e_{0}-e_{1}+\cdots+(-1)^{\ell}e_{\ell})-(\ell
e_{0}-(l-1)e_{1}+\cdots+(-1)^{\ell-1}e_{\ell-1}+0\cdot e_{\ell})$
$\displaystyle=e_{2}-2e_{3}+\cdots+(-1)^{\ell-2}(\ell-1)e_{\ell},$

where $e_{i}=e_{i}(w_{1},...,w_{\ell})$ for $0\leq i\leq\ell$.

######  Corollary 5.3.

Follow the notation in Theorem 5.1. Then we have

$\displaystyle\sum_{i=1}^{\ell-r}S(\ell-r,i)x\Big{(}(k+1)z^{k}\mathrm{\overline{A}}_{j}(z)+z^{k+1}\mathrm{\overline{A}}_{j}^{(1)}(z)\Big{)}^{(i-1)}\Big{|}_{z=1}$
$\displaystyle=$ $\displaystyle\left\\{\begin{array}[]{ll}-1&\ \text{if}\ \
j=0;\\\ 0&\ \text{if}\ \ 1\leq j\leq\ell-r;\\\
(-1)^{j+r-1-\ell}\binom{j-1}{j+r-1-\ell}&\ \text{if}\ \ \ell-r+1\leq
j\leq\ell,\end{array}\right.$

where
$\mathrm{\overline{A}}_{j}(z)=\frac{(-1)^{j+1}z^{\ell-j}}{xz^{k+\ell}-(z-1)^{\ell}}$
and the $S(\ell-r,i)$ are Stirling numbers of the second kind.

###### Proof.

By Equation (16), we have

$\mathrm{\overline{A}}(z)=\sum_{j=0}^{\ell}\mathrm{\overline{A}}_{j}(z)e_{j}(w_{1},...,w_{\ell}).$

Therefore

$\mathrm{\overline{B}}_{1}(z)=(k+1)z^{k}\mathrm{\overline{A}}(z)+z^{k+1}\mathrm{\overline{A}}^{\prime}(z)=\sum_{j=0}^{\ell}((k+1)z^{k}\mathrm{\overline{A}}_{j}(z)+z^{k+1}\mathrm{\overline{A}}_{j}^{\prime}(z))e_{j}(w_{1},...,w_{\ell}).$

By Theorem 5.1, we have

$F_{r}(x)=1+\sum_{j=0}^{\ell}\left(\sum_{i=1}^{\ell-r}S(\ell-r,i)x\Big{(}(k+1)z^{k}\mathrm{\overline{A}}_{j}(z)+z^{k+1}\mathrm{\overline{A}}_{j}^{(1)}(z)\Big{)}^{(i-1)}\Big{|}_{z=1}\right)e_{j}(w_{1},...,w_{\ell}).$

The corollary is followed by Theorem 1.2. ∎

###  5.2. A Symmetric Function Formula

It is natural to solve the system (4) for $C_{\ell-r}$ using Kramer’s rule.
Rewrite (4) as

$\displaystyle\sum_{i=1}^{\ell}\left(\frac{w_{j}}{w_{j}-1}\right)^{i-1}xC_{\ell-i}=(w_{j}-1),\
\ 1\leq j\leq\ell.$

Let $\widehat{w}_{i}=\frac{w_{i}}{w_{i}-1}$, i.e.,
$w_{i}=\frac{\widehat{w}_{i}}{\widehat{w}_{i}-1}$ for $1\leq i\leq\ell$. By
Kramer’s rule, we have $xC_{\ell-r}=\frac{D_{r}}{D}$, where

$\displaystyle
D=\det\left(\begin{array}[]{cccc}1&\widehat{w}_{1}&\cdots&\widehat{w}_{1}^{\ell-1}\\\
1&\widehat{w}_{2}&\cdots&\widehat{w}_{2}^{\ell-1}\\\
\vdots&\vdots&\ddots&\vdots\\\
1&\widehat{w}_{\ell}&\cdots&\widehat{w}_{\ell}^{\ell-1}\end{array}\right)=\det
V(\widehat{w}_{1},\widehat{w}_{2},...,\widehat{w}_{\ell}).$

and

$\displaystyle
D_{r}=\det\left(\begin{array}[]{cccccccc}1&\widehat{w}_{1}&\cdots&\widehat{w}_{1}^{r-2}&w_{1}-1&\widehat{w}_{1}^{r}&\cdots&\widehat{w}_{1}^{\ell-1}\\\
1&\widehat{w}_{2}&\cdots&\widehat{w}_{2}^{r-2}&w_{2}-1&\widehat{w}_{2}^{r}&\cdots&\widehat{w}_{2}^{\ell-1}\\\
\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&\vdots\\\
1&\widehat{w}_{\ell}&\cdots&\widehat{w}_{\ell}^{r-2}&w_{\ell}-1&\widehat{w}_{\ell}^{r}&\cdots&\widehat{w}_{\ell}^{\ell-1}\end{array}\right).$

Now rewrite

$w_{i}-1=-\frac{\widehat{w}_{i}}{1-\widehat{w}_{i}}-1=-\sum_{m\geq
0}(\widehat{w}_{i})^{m},\ \ \ 1\leq i\leq\ell,$

and put in the above equation for $D_{r}$ and expand by linearity. When $0\leq
m\leq\ell$, the corresponding term is $0$, except that the term corresponding
to $m=r-1$ is $-\det
V(\widehat{w}_{1},\widehat{w}_{2},...,\widehat{w}_{\ell})$. The remaining
terms correspond to $m\geq\ell$. By Lemma 3.1 and some simple calculations, we
have

$D_{r}=-\det V(\widehat{w}_{1},...,\widehat{w}_{\ell})+(-1)^{\ell-r+1}\det
V(\widehat{w}_{1},...,\widehat{w}_{\ell})\sum_{m\geq
l}s_{(m-\ell+1,1^{\ell-r})}(\widehat{w}_{1},...,\widehat{w}_{\ell}),$

where $(m-\ell+1,1^{\ell-r})=(m-\ell+1,1,1,...,1)$ with length $\ell-r+1$.
Therefore, we have

$F_{r}(x)=1+xC_{\ell-r}=1+\frac{D_{r}}{D}=(-1)^{\ell-r+1}\sum_{m\geq
1}s_{(m,1^{\ell-r})}(\widehat{w}_{1},...,\widehat{w}_{\ell}).$ (17)

By Theorem 1.2, we complete the proof of Theorem 5.4 as follows.

######  Theorem 5.4.

Let $\ell,r\in\mathbb{P}$ and $\ell\geq r$. Let
$\widehat{w}_{i}=\frac{w_{i}}{w_{i}-1}$, $1\leq i\leq\ell$. We have

$\sum_{m\geq
1}s_{(m,1^{\ell-r})}(\widehat{w}_{1},...,\widehat{w}_{\ell})=\sum_{i=0}^{r-1}(-1)^{\ell-r+i+1}\binom{\ell-r+i}{i}e_{\ell-r+i+1}(w_{1},...,w_{\ell}).$

######  Example 5.5.

Suppose $\ell=r$. Theorem 1.2 implies that

$F_{\ell}(x)=\sum_{i=0}^{\ell-1}(-1)^{i}e_{i+1}(w_{1},...,w_{\ell}).$ (18)

This formula can be explained by Equation (17) as follows.

$F_{\ell}(x)=-\sum_{m\geq 1}s_{m}(\widehat{w}_{1},...,\widehat{w}_{\ell}).$

Because $s_{m}(x_{1},x_{2},...)=h_{m}(x_{1},x_{2},...)$ and $\sum_{m\geq
0}h_{m}(x_{1},x_{2},...)t^{m}=\frac{1}{\prod_{i}(1-x_{i}t)}$ (see, e.g., [13,
Theorem 7.6.1]), we have

$\displaystyle F_{\ell}(x)$ $\displaystyle=-\sum_{m\geq
1}h_{m}(\widehat{w}_{1},...,\widehat{w}_{\ell})=1-\sum_{m\geq
0}h_{m}(\widehat{w}_{1},...,\widehat{w}_{\ell})$
$\displaystyle=1-\frac{1}{(1-\widehat{w}_{1})(1-\widehat{w}_{2})\cdots(1-\widehat{w}_{\ell})}=1-(1-w_{1})(1-w_{2})\cdots(1-w_{\ell})$
$\displaystyle=e_{1}(w_{1},...,w_{\ell})-e_{2}(w_{1},...,w_{\ell})+\cdots+(-1)^{\ell-1}e_{\ell}(w_{1},...,w_{\ell}).$

##  6\. Concluding Remark

Let $S_{m}$ ($2\leq m\leq 6$) be the sequences [A079489], [A213403],
[A213404], [A213405] and [A213406] in OEIS [11]. We have proved in Theorem 1.1
that $S_{m}$ is in fact our $\overline{f}_{m}(n)$. Now we can enrich the
content of these sequences. We summarize as follows:

  1. (1)

The sequences $S_{m}$ are the number of rectangular Young tableaux
$\mathcal{B}_{m}^{n}$ with periodic walls of a block $\mathcal{B}_{m}$.

  2. (2)

The sequences $S_{m}$ are the number of lattice paths from $(0,0)$ to
$(mn,mn)$ that never go below the path $N(E^{m}N^{m})^{n-1}E^{m}N^{m-1}$. (See
Proposition 2.5.)

  3. (3)

A recursive formula for sequences $S_{m}$ is shown in Proposition 2.6.

  4. (4)

A determinant formula for sequences $S_{m}$ is given in Proposition 2.5.

  5. (5)

The generating functions of sequences $S_{m}$ are given in Corollary 1.1.
These are also the explanation of these sequences in OEIS.

  6. (6)

The generating functions of sequences $S_{m}$ are given by the exponential
formulas in Theorem 4.3 with $k=l=m$.

In this paper, we only enumerated Young tableaux with periodic walls over
$\mathcal{B}_{m}$. The idea works for all Young building blocks with
horizontal walls. Our next project is to study these generating functions.

Acknowledgements: We are grateful to Menghao Qu for many useful suggestions.
This work is partially supported by the National Natural Science Foundation of
China [12071311].

## References

  * [1] C. Banderier, P. Marchal, and M. Wallner, _Rectangular Young tableaux with local decreases and the density method for uniform random generation_ , GASCom 2018, CEUR Workshop Proceedings. Vol.2113 (2018), 60–68.
  * [2] C. Banderier, and M. Wallner, _Young tableaux with periodic walls: counting with the density method_ , Proceedings of the 33rd Conference on FPSAC. 85B (2021), Article#47.
  * [3] J. Bonin, A. de Mier, and M. Noy, _Lattice path matroids: enumerative aspects and Tutte polynomials_ , J. Combin. Theory Ser. A. 104 (2003), 63–94.
  * [4] R. J. Chapman, T. Chow, A. Khetan, D. P. Moulton, and R. J. Waters, _Simple formulas for lattice paths avoiding certain periodic staircase boundaries_ , J. Combin. Theory Ser. A. 116 (1)(2009), 205–214.
  * [5] Ira M. Gessel, and M. Loehr, _Note on enumeration of partitions contained in a given shape_ , Linear Algebra Appl. 432 (2010), 583–585.
  * [6] J. Haglund, _The $q$,$t$-Catalan Number and the Space of Diagonal Harmonics: with an appendix on the combinatorics of Macdonald polynomials_, AMS University Lecture Series, 2008.
  * [7] B. R. Handa, and S. G. Mohanty, _On $q$-binomial coefficients and some statistical applications_, SIAM J. Math. Anal. 11 (1980), 1027–1035.
  * [8] J. Irving, and A. Rattan, _The number of lattice paths below a cyclically shifting boundary_ , J. Combin. Theory Ser. A. 116 (2009), 499–514.
  * [9] G. Kreweras, _Sur une classe de problémes de denombrement liés au treillis des partitions des entiers_ , Cahiers du BURO. 6 (1965), 5–105.
  * [10] A. de Mier, and M. Noy, _A solution to the tennis ball problem_ , Theoret. Comput. Sci. 346 (2005), 254–264.
  * [11] N. J. A. Sloane, _The on-line encyclopedia of integer sequences_ , published electronically at http://oeis.org.
  * [12] R. P. Stanley, _Enumerative Combinatorics (volume 1)_ , Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, 2012.
  * [13] R. P. Stanley, _Enumerative Combinatorics (volume 2)_ , Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, 1999.
  * [14] U. Tamm, _Lattice paths not touching a given boundary_ , J. Statist. Plann. Inference. 105 (2002), 433–448.
  * [15] G. Xin, _The ring of Malcev-Neumann series and the residue theorem_ , Ph.D. thesis, Brandeis University (2004).