ON THE EHRHART POLYNOMIAL OF SCHUBERT MATROIDS

NEIL J.Y. FAN AND YAO LI

ABSTRACT. In this paper, we give a formula for the number of lattice points in
the dilations of Schubert matroid polytopes. As applications, we obtain the
Ehrhart polynomials of uniform and minimal matroids as simple special cases,
and give a recursive formula for the Ehrhart polynomials of $(a,b)$-Catalan
matroids. Ferroni showed that uniform and minimal matroids are Ehrhart
positive. We show that all sparse paving Schubert matroids are Ehrhart
positive and their Ehrhart polynomials are coefficient-wisely bounded by those
of minimal and uniform matroids. This confirms a conjecture of Ferroni for the
case of sparse paving Schubert matroids. Furthermore, we express the Ehrhart
polynomials of three families of Schubert matroids as positive combinations of
the Ehrhart polynomials of uniform matroids, yielding Ehrhart positivity of
these Schubert matroids.

##  1 Introduction

Let $S$ be a subset of $[n]:=\\{1,2,\ldots,n\\}$. The Schubert matroid ${\rm
SM}_{n}(S)$ is the matroid with ground set $[n]$ and bases

$\\{T\subseteq[n]\colon T\leq S\\},$

where $T\leq S$ means that: $|T|=|S|$ and the $i$-th smallest element of $T$
does not exceed that of $S$ for $1\leq i\leq|T|$. Schubert matroids are also
called freedom matroids, generalized Catalan matroids, PI-matroids, and
shifted matroids in the literature, see, for example, Ardila [1], Ardila, Fink
and Rincón [2], and Bonin and de Mier [5]. In particular, uniform matroids,
minimal matroids and $(a,b)$-Catalan matroids are special kinds of Schubert
matroids. It is also worth mentioning that Schubert matroids are specific
families of lattice path matroids [4, 5, 17], or more generally transversal
matroids [1] and positroids [22].

Suppose that $M=([n],\mathcal{B})$ is a matroid with ground set $[n]$ and base
set $\mathcal{B}$. The matroid polytope $\mathcal{P}(M)$ associated to $M$ is
the convex hull

$\displaystyle\mathcal{P}(M)=\mathrm{conv}\\{e_{B}\colon B\in\mathcal{B}\\},$
(1.1)

where $e_{B}=e_{b_{1}}+\cdots+e_{b_{k}}$ for
$B=\\{b_{1},\ldots,b_{k}\\}\subseteq[n]$ and $\\{e_{i}\colon 1\leq i\leq n\\}$
is the standard basis of $\mathbb{R}^{n}$. Given a polytope $\mathcal{P}$ and
a positive integer $t$, the $t$-dilation $t\mathcal{P}$ of $\mathcal{P}$ is
defined as $t\mathcal{P}=\\{t\alpha|\alpha\in\mathcal{P}\\}$. Let
$i(\mathcal{P},t)=|t\mathcal{P}\cap\mathbb{Z}^{n}|$ denote the number of
lattice points in $t\mathcal{P}$. It is well known that for integral
polytopes, $i(\mathcal{P},t)$ is a polynomial in $t$, called the Ehrhart
polynomial of $\mathcal{P}$. For simplicity, write $i(M,t)$ for
$i(\mathcal{P}(M),t)$.

It was conjectured by De Loera, Haws and Köppe [19] that all matroids are
Ehrhart positive, i.e., the Ehrhart polynomial of any matroid polytope has
positive coefficients. Moreover, since matroid polytopes are specific families
of generalized permutohedra, Castillo and Liu [6] conjectured that generalized
permutohedra are also Ehrhart positive. Recently, Ferroni [11, 12] showed that
hypersimplices and minimal matroids are Ehrhart positive. In [13], Ferroni
showed that all sparse paving matroids of rank 2 are Ehrhart positive, but
provided counterexamples to both aforementioned conjectures of all ranks
greater than or equal to 3. Ferroni, Jochemko and Schröter [14] further showed
that all matroids of rank 2 are Ehrhart positive and are coefficient-wisely
bounded by minimal and uniform matroids.

In this paper, we consider the Ehrhart polynomials of Schubert matroid
polytopes. Schubert matroid polytopes $\mathcal{P}({\rm SM}_{n}(S))$ are the
Minkowski summands of the Newton polytopes of key polynomials and Schubert
polynomials, or more generally, Schubitopes, see Fink, Mészáros and St. Dizier
[15]. We provide a formula for the number of lattice points in the
$t$-dilation $t\mathcal{P}({\rm SM}_{n}(S))$ of $\mathcal{P}({\rm
SM}_{n}(S))$, which can also be interpreted as weighted enumeration of certain
lattice paths. To this end, we first show that $t\mathcal{P}({\rm SM}_{n}(S))$
is in fact the Newton polytope of the key polynomial $\kappa_{t\alpha}(x)$,
where $\alpha$ is the indicator vector of $S$. It follows from Fink, Mészáros
and St. Dizier [15] that each lattice point in the Newton polytope of
$\kappa_{t\alpha}(x)$ is an exponent vector of $\kappa_{t\alpha}(x)$. Then we
use Kohnert algorithm to generate all the different monomials of
$\kappa_{t\alpha}(x)$ and thus obtain a formula for the number of lattice
points in $t\mathcal{P}({\rm SM}_{n}(S))$.

As applications, we obtain the Ehrhart polynomials of hypersimplices [16] and
minimal matroids [12] as simple special cases, and give a recursive formula
for the Ehrhart polynomials of $(a,b)$-Catalan matroids. We also show that all
sparse paving Schubert matroids are Ehrhart positive by proving that they are
coefficient-wisely bounded by the minimal and uniform matroids. Ferroni [12]
conjectured that all matroids are coefficient-wisely bounded by the minimal
and uniform matroids, which was disproved by Ferroni [13] later on. We confirm
this conjecture for the case of sparse paving Schubert matroids. Moreover, we
express the Ehrhart polynomials of three families of Schubert matroids as
positive combinations of the Ehrhart polynomials of hypersimplices, which
imply Ehrhart positivity of these Schubert matroids.

To describe our results, we need some notations. Assume that $S\subseteq[n]$
is a finite set of positive integers. Since we only consider Schubert matroids
${\rm SM}_{n}(S)$, it suffices to let $n$ be the maximal element of $S$. The
indicator vector $\mathbb{I}(S)$ of $S$ is the 0-1 vector
$\mathbb{I}(S)=(i_{1},\ldots,i_{n})$, where $i_{j}=1$ if $j\in S$, and 0
otherwise. Clearly, $i_{n}=1$. For simplicity, write
$\mathbb{I}(S)=(0^{r_{1}},1^{r_{2}},\ldots,0^{r_{2m-1}},1^{r_{2m}})$, where
$0^{r_{1}}$ represents $r_{1}$ copies of 0’s, $1^{r_{2}}$ represents $r_{2}$
copies of 1’s, etc. Thus $S$ can be written as an integer sequence
$r(S)=(r_{1},r_{2},\ldots,r_{2m})$ of length $2m$, where $r_{1}\geq 0$ and
$r_{i}>0$ for $i\geq 2$. It is easy to see that given such an integer sequence
$r$, there is a unique set $S$ whose indicator vector $\mathbb{I}(S)$ can be
written in this way. We will use $S$, $r$ or $r(S)$ interchangeably with no
further clarification. For example, let $S=\\{2,6,7,10\\}\subseteq[10]$, then
$\mathbb{I}(S)=(0,1,0^{3},1^{2},0^{2},1)$ and $r(S)=(1,1,3,2,2,1)$.

Given $r=(r_{1},r_{2},\ldots,r_{2m})$, define two integer sequences
$u=(u_{1},\ldots,u_{m})$ and $v=(v_{1},\ldots,v_{m})$ as follows. For $1\leq
i\leq m$, let

$\displaystyle u_{i}$
$\displaystyle=\min\left\\{r_{2i-1},\sum_{j=i+1}^{m}r_{2j}\right\\}\ \
\text{and}\ \ v_{i}=\min\left\\{r_{2i},\sum_{j=1}^{i-1}r_{2j-1}\right\\},$
(1.2)

where empty sums are interpreted as 0. Assume that $a,b,t\geq 0$ and
$c\in\mathbb{Z}$ are all integers, define

$\displaystyle F(a,b,c,t)=\sum_{j=0}^{a+b}(-1)^{j}{a+b\choose
j}{(t+1)(b-j)+a+c-1\choose a+b-1}.$ (1.3)

By convention, ${0\choose 0}=1$ and ${n\choose k}=0$ if $k<0$ or $n<k$. Notice
that if $j>\frac{bt+c}{t+1}$ in (1.3), then $(t+1)(b-j)+a+c-1<a+b-1$, and thus
${(t+1)(b-j)+a+c-1\choose a+b-1}=0$.

######  Theorem 1.1.

Let $S\subseteq[n]$ with $r(S)=(r_{1},\ldots,r_{2m})$. We have

$\displaystyle i({\rm
SM}_{n}(S),t)=\sum_{(c_{1},\ldots,c_{m})}\prod_{j=1}^{m}F(r_{2j-1},r_{2j},c_{j},t),$
(1.4)

where $c_{1}+\cdots+c_{m}=0$, and for $1\leq j\leq m$,

$\displaystyle-tv_{j}\leq c_{j}\leq tu_{j}\ \ \text{and}\ \
c_{1}+\cdots+c_{j}\geq 0.$

######  Remark 1.

Knauer, Martínez-Sandoval and Ramírez Alfonsín [17, Theorem 3.4] gave a
description of the integral points in lattice path matroid polytopes in terms
of certain generalized lattice paths. The formula in (1.4) can also be
interpreted as weighted enumeration of certain lattice paths. Given $S,r,u,v$
as above, let

$\displaystyle\mathcal{T}_{r,t}=\\{(c_{1},\ldots,c_{m})\,|\,-tv_{j}\leq
c_{j}\leq tu_{j},\ \text{for}\ 1\leq j\leq m\\}.$ (1.5)

For $\mathbf{c}=(c_{1},\ldots,c_{m})\in\mathcal{T}_{r,t}$, view $\mathbf{c}$
as a lattice path from $(0,0)$ to $(m,0)$ such that no steps go below the
$x$-axis, where $c_{j}$ presents an up step $(0,0)\rightarrow(1,c_{j})$ if
$c_{j}>0$, a horizontal step $(0,0)\rightarrow(1,0)$ if $c_{j}=0$, or a down
step $(0,0)\rightarrow(1,-|c_{j}|)$ if $c_{j}<0$. Assign a weight to each path
$\mathbf{c}$ as

${\rm{wt}}(\mathbf{c})=\prod_{j=1}^{m}F(r_{2j-1},r_{2j},c_{j},t).$

Then

$i({\rm
SM}_{n}(S),t)=\sum_{\mathbf{c}\in\mathcal{T}_{r,t}}{\rm{wt}}(\mathbf{c}).$

For example, let $S=\\{3,6,8\\}\subseteq[8]$. Then
$\mathbb{I}(S)=(0^{2},1,0^{2},1,0,1)$, $r=(2,1,2,1,1,1)$ and
$(u_{1},u_{2},u_{3})=(2,1,0),$ $(v_{1},v_{2},v_{3})=(0,1,1)$. If $t=1$, then
$0\leq c_{1}\leq 2,\ -1\leq c_{2}\leq 1,\ -1\leq c_{3}\leq 0$, and the paths
in $\mathcal{T}_{r,1}$ are illustrated in Figure 1.1, their corresponding
paths $(c_{1},c_{2},c_{3})$ are $(0,0,0),(0,1,-1),$
$(1,-1,0),(1,0,-1),(2,-1,-1),$ respectively.

$\cdot$$\cdot$$\cdot$$\cdot$

$\cdot$$\cdot$$\cdot$$\cdot$

$\cdot$$\cdot$$\cdot$$\cdot$

$\cdot$$\cdot$$\cdot$$\cdot$

$\cdot$$\cdot$$\cdot$$\cdot$

Figure 1.1: Paths in $\mathcal{T}_{r,1}$ for $r=(2,1,2,1,1,1)$.

Now we consider some applications of Theorem 1.1.

###  1.1 Uniform matroids

Let $r=(n-k,k)$, where $n>k\geq 1$, we obtain the uniform matroid $U_{k,n}$.
That is, the uniform matroid $U_{k,n}$ is equivalent to $\text{SM}_{n}(S)$
with

$S=\\{n-k+1,\ldots,n\\}.$

In this case, $m=1,\ c_{1}=0$, thus $i(U_{k,n},t)=F(n-k,k,0,t)$, which was
first obtained by Katzman [16] and then shown to have positive coefficients by
Ferroni [11].

######  Corollary 1.2 (Katzman [16]).

We have

$i(U_{k,n},t)=F(n-k,k,0,t)=\sum_{i=0}^{k-1}(-1)^{i}{n\choose
i}{(k-i)t-i+n-1\choose n-1}.$

Since $F(a,b,0,t)$ has positive coefficients for any $a,b\geq 1$, it is
natural to ask whether $F(a,b,c,t)$ defined in (1.3) has positive coefficients
or not. The following conjecture was verified for $a,b,c\leq 10$.

######  Conjecture 1.3.

$F(a,b,c,t)$ has positive coefficients for any $a,b\geq 1$ if and only if
$c=0,\pm 1$.

Since $F(1,1,c,t)=t+1-|c|$, we see that if $|c|>1$, then $F(1,1,c,t)$ has
negative coefficients. Thus to prove Conjecture 1.3, it is enough to show that
if $c=\pm 1$, then $F(a,b,c,t)$ is a positive polynomial in $t$ for any
$a,b\geq 1$.

Moreover, we express the Ehrhart polynomials of three families of Schubert
matroids as positive combinations of $F(a,b,0,t)$. For convenience, let
$i(r(S),t)$ denote $i({\rm SM}_{n}(S),t)$.

######  Corollary 1.4.

Let $a,b$ be positive integers. Then

$\displaystyle i((a,b,a,b),t)$
$\displaystyle=\frac{1}{2}F(2a,2b,0,t)+\frac{1}{2}F(a,b,0,t)^{2},$ (1.6)
$\displaystyle i((a,a,b,b),t)$
$\displaystyle=\frac{1}{2}F(a+b,a+b,0,t)+\frac{1}{2}F(a,a,0,t)F(b,b,0,t),$
(1.7) $\displaystyle i((1,1,a,a+1),t)$
$\displaystyle=\frac{1}{2}(t+2)F(a+1,a+1,0,t).$ (1.8)

Therefore, when $r(S)=(a,a,b,b),(a,b,a,b)$ or $(1,1,a,a+1)$, the Schubert
matroids ${\rm SM}_{n}(S)$ are Ehrhart positive.

We remark that by Knauer, Martínez-Sandoval and Ramírez Alfonsín [17], a
Schubert matroid ${\rm SM}_{n}(S)$ corresponds to the lattice path matroid
$M(U,L)$, where

${\rm st}(U)=\mathbb{I}(S)\ \text{and}\ {\rm st}(L)=(0^{n-|S|},1^{|S|}),$

see also Bonin, de Mier and Noy [4]. There is a specific family of lattice
path matroids called snakes, denoted as $S(a_{1},\ldots,a_{n})$. Knauer,
Martínez-Sandoval and Ramírez Alfonsín [17, Theorem 3.8] gave an explicit
formula for the Ehrhart polynomial of $P_{S(n-k,k)}$. Ferroni [12, Proposition
2.4] showed that the snake matroid $S(n-k,k)$ is isomorphic to the minimal
matroid $T_{k,n}$. Thus Corollary 1.4 actually shows that the lattice path
matroids $M[U,L]$ are Ehrhart positive when ${\rm
st}(U)=(0^{a},1^{b},0^{a},1^{b})$, $(0^{a},1^{a},0^{b},1^{b})$ or
$(0,1,0^{a},1^{a+1})$ for any $a,b\geq 1$ and $L$ is the trivial lower bound.

###  1.2 Minimal matroids

Let $r=(1,k-1,n-k-1,1)$, where $n>k\geq 2$, we are lead to the minimal matroid
$T_{k,n}$. That is, $T_{k,n}$ is the Schubert matroid $\text{SM}_{n}(S)$ with

$S=\\{2,3,\ldots,k,n\\}.$

Minimal matroids were first studied independently by Dinolt [9] and Murty
[21]. Ferroni [12] showed that $T_{k,n}$ is the graphic matroid of a
$(k+1)$-cycle with one edge replaced by $n-k$ parallel copies. By Theorem 1.1,
$u=(1,0),v=(0,1)$ and $(c_{1},c_{2})=(j,-j)$ for $0\leq j\leq t$, then

$i(T_{k,n},t)=\sum_{j=0}^{t}F(1,k-1,j,t)F(n-k-1,1,-j,t).$

Since both $F(1,k-1,j,t)$ and $F(n-k-1,1,-j,t)$ are binomial coefficients, by
a routine calculation, we can obtain the following closed formula of
$i(T_{k,n},t)$.

######  Corollary 1.5 (Ferroni [12]).

We have

$\displaystyle i(T_{k,n},t)=\frac{1}{{n-1\choose k-1}}{t+n-k\choose
n-k}\sum_{j=0}^{k-1}{n-k+j-1\choose j}{t+j\choose j}.$ (1.9)

It is obvious that $i(T_{k,n},t)$ has positive coefficients.

###  1.3 $(a,b)$-Catalan matroids

Let $r=(\overbrace{a,b,a,b,\ldots,a,b}^{2n})$, where $a,b,n\geq 1$, we obtain
the $(a,b)$-Catalan matroid $\mathbf{C}_{n}^{a,b}$ introduced by Bonin, de
Mier and Noy [4, Definition 3.7]. In particular, when $a=b=1$, we obtain the
Schubert matroid $\mathbf{C}_{n}^{1,1}$, which is equivalent to
$\text{SM}_{2n}(S)$ with

$S=\\{2,4,\ldots,2n\\}.$

In [1], Ardila studied the Catalan matroid $\mathbf{C}_{n}$, which is the
Schubert matroid $\text{SM}_{2n-1}(S)$ with $S=\\{1,3,\ldots,2n-1\\}$ and an
additional loop $2n$. It is easy to see that $\mathbf{C}_{n}^{1,1}$ is
isomorphic to $\mathbf{C}_{n+1}$.

A composition $\sigma=(\sigma_{1},\ldots,\sigma_{s})$ of $n$ is an ordered
nonnegative integer sequence such that $\sigma_{1}+\cdots+\sigma_{s}=n$. Let
$\ell(\sigma)=s$ denote the number of parts of $\sigma$. Given two
compositions $\sigma$ and $\sigma^{\prime}$, we say that $\sigma$ and
$\sigma^{\prime}$ are equivalent, denoted as $\sigma\sim\sigma^{\prime}$, if
$\sigma^{\prime}$ can be obtained from $\sigma$ by cyclic shifting, i.e.,
$\sigma^{\prime}=(\sigma_{j},\ldots,\sigma_{s},\sigma_{1},\ldots,\sigma_{j-1})$
for some $2\leq j\leq s$. Let $d(\sigma)$ denote the cardinality of the
equivalence class of $\sigma$. Denote $\Gamma_{n}$ by a transversal of the
equivalence classes consisting of compositions of $n$ with at least two parts
and minimal parts larger than 1. That is, if $\sigma\in\Gamma_{n}$, then
$\min\\{\sigma_{1},\ldots,\sigma_{s}\\}>1$, $\ell(\sigma)>1$, and if
$\sigma,\sigma^{\prime}\in\Gamma_{n}$, then $\sigma^{\prime}$ and $\sigma$ are
not equivalent.

######  Theorem 1.6.

For $a,b\geq 1$ and $n\geq 2$, we have

$\displaystyle i(\mathbf{C}_{n}^{a,b},t)$
$\displaystyle=\frac{1}{n}F(na,nb,0,t)-\frac{1}{n}F(a,b,0,t)^{n}+F(a,b,0,t)\cdot
i(\mathbf{C}_{n-1}^{a,b},t)$
$\displaystyle\quad+\sum_{\sigma\in\Gamma_{n}}(-1)^{\ell(\sigma)}\frac{d(\sigma)}{\ell(\sigma)}\cdot
i(\overline{\mathbf{C}}_{\sigma}^{a,b},t),$ (1.10)

where $\displaystyle
i(\overline{\mathbf{C}}_{\sigma}^{a,b},t)=\prod_{j=1}^{\ell(\sigma)}i(\overline{\mathbf{C}}_{\sigma_{j}}^{a,b},t)$
and

$\displaystyle
i(\overline{\mathbf{C}}_{\sigma_{j}}^{a,b},t)=i(\mathbf{C}_{\sigma_{j}}^{a,b},t)-F(a,b,0,t)\cdot
i(\mathbf{C}_{\sigma_{j}-1}^{a,b},t),$ (1.11)

and $i(\mathbf{C}_{1}^{a,b},t)=F(a,b,0,t)$.

For example, since $\Gamma_{2}=\Gamma_{3}=\emptyset$ and
$\Gamma_{4}=\\{(2,2)\\}$, we have

$\displaystyle i(\mathbf{C}_{2}^{a,b},t)$
$\displaystyle=\frac{1}{2}F(2a,2b,0,t)+\frac{1}{2}F(a,b,0,t)^{2}$
$\displaystyle i(\mathbf{C}_{3}^{a,b},t)$
$\displaystyle=\frac{1}{3}F(3a,3b,0,t)-\frac{1}{3}F(a,b,0,t)^{3}+F(a,b,0,t)\cdot
i(\mathbf{C}_{2}^{a,b},t)$ $\displaystyle i(\mathbf{C}_{4}^{a,b},t)$
$\displaystyle=\frac{1}{4}F(4a,4b,0,t)-\frac{1}{4}F(a,b,0,t)^{4}+F(a,b,0,t)\cdot
i(\mathbf{C}_{3}^{a,b},t)+\frac{1}{2}i(\overline{\mathbf{C}}_{2},t).$

For $n=9$, let
$\Gamma_{9}=\\{(7,2),(6,3),(5,4),(5,2,2),(4,3,2),(4,2,3),(3,3,3),(3,2,2,2)\\}.$
Thus

$\displaystyle i(\mathbf{C}_{9}^{a,b},t)$
$\displaystyle=\frac{1}{9}F(9a,9b,0,t)-\frac{1}{9}F(a,b,0,t)^{9}+F(a,b,0,t)\cdot
i(\mathbf{C}_{8}^{a,b},t)$
$\displaystyle\quad+i(\overline{\mathbf{C}}_{(7,2)}^{a,b},t)+i(\overline{\mathbf{C}}_{(6,3)}^{a,b},t)+i(\overline{\mathbf{C}}_{(5,4)}^{a,b},t)-i(\overline{\mathbf{C}}_{(5,2,2)}^{a,b},t)$
$\displaystyle\quad-i(\overline{\mathbf{C}}_{(4,3,2)}^{a,b},t)-i(\overline{\mathbf{C}}_{(4,2,3)}^{a,b},t)-\frac{1}{3}i(\overline{\mathbf{C}}_{(3,3,3)}^{a,b},t)+i(\overline{\mathbf{C}}_{(3,2,2,2)}^{a,b},t),$

where
$i(\overline{\mathbf{C}}_{(4,3,2)}^{a,b},t)=i(\overline{\mathbf{C}}_{(4,2,3)}^{a,b},t).$

Computational experiments suggest the following two conjectures.

######  Conjecture 1.7.

For integers $a,b,n\geq 1$, $F(na,nb,0,t)-F(a,b,0,t)^{n}$ has positive
coefficients.

######  Conjecture 1.8.

For integers $a,b,n\geq 1$, $i(\overline{\mathbf{C}}_{n}^{a,b},t)$ has
positive coefficients.

Notice that the positivity of $i(\overline{\mathbf{C}}_{n}^{a,b},t)$ implies
the positivity of $i(\mathbf{C}_{n}^{a,b},t)$.

###  1.4 Sparse paving Schubert matroids

Let $r=(k-1,1,1,n-k-1)$, where $n>k\geq 2$, we obtain a special Schubert
matroid, denoted as ${\rm Sp}_{k,n}$. In fact, as will be shown in Proposition
6.1, ${\rm Sp}_{k,n}$ is a sparse paving matroid, and a Schubert matroid
$\text{SM}_{n}(S)$ is sparse paving if and only if $r(S)=(k-1,1,1,n-k-1)$,
namely,

$S=\\{k,k+2,\ldots,n\\}.$

######  Theorem 1.9.

Sparse paving Schubert matroids are Ehrhart positive and are coefficient-
wisely bounded by minimal and uniform matroids. That is, we have the
coefficient-wise inequality

$\displaystyle i(T_{k,n},t)\leq i({\rm Sp}_{k,n},t)\leq i(U_{k,n},t).$ (1.12)

The organization of this paper is as follows. In Section 2, we recall basic
definitions and notations of matroids and key polynomials. In Section 3, we
give a proof of Theorem 1.1. In Section 4, we explore some further properties
of $F(a,b,c,t)$ and prove Corollary 1.4 and 1.5. Section 5 is devoted to prove
Theorem 1.6. Finally, we show that sparse paving Schubert matroids are Ehrhart
positive in Section 6.

##  2 Preliminaries

A matroid is a pair $M=(E,\mathcal{I})$ consisting of a finite set $E$, called
the ground set, and a collection $\mathcal{I}$ of subsets of $E$, called
independent sets, such that:

  1. (1)

$\emptyset\in\mathcal{I}$;

  2. (2)

If $J\in\mathcal{I}$ and $I\subseteq J$, then $I\in\mathcal{I}$;

  3. (3)

If $I,J\in\mathcal{I}$ and $|I|<|J|$, then there exists $j\in J\setminus I$
such that $I\cup\\{j\\}\in\mathcal{I}$.

By (2), a matroid $M$ is determined by the collection $\mathcal{B}$ of maximal
independent sets, called the bases of $M$. By (3), all the bases have the same
cardinality, called the rank of $M$, denoted as ${\rm rk}(M)$. So we can write
$M=(E,\mathcal{B})$. The dual of $M$ is the matroid
$M^{*}=(E,\mathcal{B}^{*})$, where $\mathcal{B}^{*}=\\{E\setminus
B:B\in\mathcal{B}\\}$. It is easy to check that the dual of a Schubert matroid
${\rm SM}_{n}(S)$ is isomorphic to ${\rm SM}_{n}(S^{\prime})$, where
$r(S^{\prime})$ is the reverse of $r(S)$.

A subset $I$ of $E$ is called dependent if it is not an independent set. If
$C\subseteq E$ is dependent but every proper subset of $C$ is independent, we
say that $C$ is a circuit. A subset $F$ of $E$ is called a flat if ${\rm
rk}_{M}(F\cup\\{a\\})>{\rm rk}_{M}(F)$ for every $a\notin F$. A hyperplane $H$
is a flat such that ${\rm rk}_{M}(H)={\rm rk}(M)-1$.

We say that $M$ is paving if every circuit of $M$ has cardinality at least
${\rm rk}(M)$. A matroid $M$ is sparse paving if both $M$ and its dual are
paving. A matroid is sparse paving if and only if every subset of cardinality
${\rm rk}(M)$ is either a basis or a circuit-hyperplane, see, for example,
Bonin [3] or Ferroni [13, Lemma 2.7].

The rank function ${\rm rk}_{M}:2^{E}\rightarrow\mathbb{Z}$ of $M$ is defined
by

${\rm rk}_{M}(T)=\max\\{|T\cap B|\colon B\in\mathcal{B}\\},\ \ \ \text{for
$T\subseteq E$}.$

Let ${\rm rk}_{S}$ denote the rank function of a Schubert matroid ${\rm
SM}_{n}(S)$. Fan and Guo [10, Theorem 3.3] provided an efficient algorithm to
compute ${\rm rk}_{S}(T)$ for any $T\subseteq[n]$. It is well known that the
matroid polytope $\mathcal{P}(M)$ defined in (1.1) associated to a matroid
$M=([n],\mathcal{B})$ is a generalized permutohedron perametrized by the rank
function of $M$, see, for example, Fink, Mészáros and St. Dizier [15]. To be
specific,

$\mathcal{P}(M)=\left\\{x\in\mathbb{R}^{n}\colon\sum_{i\in[n]}x_{i}={\rm
rk}_{M}([n])\ \ \text{and}\ \ \sum_{i\in T}x_{i}\leq{\rm rk}_{M}(T)\ \
\text{for $T\subsetneq[n]$}\right\\}.$ (2.1)

The key polynomials $\kappa_{\alpha}(x)$ associated to compositions
$\alpha\in\mathbb{Z}_{\geq 0}^{n}$ can be defined recursively as below. If
$\alpha=(\alpha_{1},\alpha_{2},\ldots,\alpha_{n})$ is a partition (i.e.,
weakly decreasing), then set
$\kappa_{\alpha}(x)=x_{1}^{\alpha_{1}}x_{2}^{\alpha_{2}}\cdots
x_{n}^{\alpha_{n}}.$ Otherwise, choose an index $i$ such that
$\alpha_{i}<\alpha_{i+1}$, and let $\alpha^{\prime}$ be obtained from $\alpha$
by interchanging $\alpha_{i}$ and $\alpha_{i+1}$. Set

$\kappa_{\alpha}(x)=\partial_{i}(x_{i}\kappa_{\alpha^{\prime}}(x)).$

Here $\partial_{i}$ is the divided difference operator sending a polynomial
$f(x)\in\mathbb{R}[x_{1},\ldots,x_{n}]$ to

$\partial_{i}(f(x))=\frac{f(x)-s_{i}f(x)}{x_{i}-x_{i+1}},$

where $s_{i}f(x)$ is obtained from $f(x)$ by interchanging $x_{i}$ and
$x_{i+1}$. Key polynomials are also called Demazure characters, they are
characters of the Demazure modules for the general linear groups, see Demazure
[7, 8].

Kohnert [18] found that the key polynomial $\kappa_{\alpha}(x)$ can be
generated by applying the Kohnert algorithm to the skyline diagram of
$\alpha$, see also Reiner and Shimozono [23]. Recall that the skyline diagram
$D(\alpha)$ of a composition $\alpha=(\alpha_{1},\ldots,\alpha_{n})$ is a
diagram consisting of the first $\alpha_{i}$ boxes in row $i$. For example,
Figure 2.2 is the skyline diagram of $\alpha=(1,3,0,2)$.

Figure 2.2:  The skyline diagram $D(\alpha)$ for $\alpha=(1,3,0,2)$.

The Kohnert algorithm is defined based on Kohnert moves on diagrams. A diagram
$D$ is a finite collection of boxes in $\mathbb{Z}_{>0}^{2}$. A box in row $i$
and column $j$ of the grid is denoted $(i,j)$. Here, the rows (respectively,
columns) are labeled increasingly from top to bottom (respectively, from left
to right). A Kohnert move on $D$ selects the rightmost box in a row of $D$ and
moves it within its column up to the first available position. To be specific,
a box $(i,j)$ of $D$ can be moved up to a position $(i^{\prime},j)$ by a
Kohnert move whenever: (i) the box $(i,j)$ is the rightmost box in the $i$-th
row of $D$, (ii) the box $(i^{\prime},j)$ does not belong to $D$, and (iii)
for any $i^{\prime}<r<i$, the box $(r,j)$ belongs to $D$.

A Kohnert diagram for $D(\alpha)$ is the diagram obtained from $D(\alpha)$ by
applying a sequence of Kohnert moves. For a diagram $D$, let
$x^{D}=\prod_{(i,j)\in D}x_{i}$. Kohnert [18] showed that

$\kappa_{\alpha}(x)=\sum_{D}x^{D},$

where the sum takes over all the Kohnert diagrams for $D(\alpha)$. For
example, Figure 2.3 displays all the Kohnert diagrams for $\alpha=(0,2,1)$.
Thus
$\kappa_{(0,2,1)}(x)=x_{2}^{2}x_{3}+x_{1}x_{2}x_{3}+x_{1}x_{2}^{2}+x_{1}^{2}x_{3}+x_{1}^{2}x_{2}$.

Figure 2.3: Kohnert diagrams for $\alpha=(0,2,1)$.

##  3 Proof of Theorem 1.1

In order to give a proof of Theorem 1.1, we first show that $t\mathcal{P}({\rm
SM}_{n}(S))$ is in fact the Newton polytope of a key polynomial.

Recall that for a polynomial

$f=\sum_{\alpha\in\mathbb{Z}_{\geq
0}^{n}}c_{\alpha}x^{\alpha}\in\mathbb{R}[x_{1},\ldots,x_{n}],$

the Newton polytope of $f$ is the convex hull of the exponent vectors of $f$:

$\mathrm{Newton}(f)=\mathrm{conv}(\\{\alpha\colon c_{\alpha}\neq 0\\}).$

It is obvious that each exponent vector of $f$ is a lattice point in
$\mathrm{Newton}(f)$. Monical, Tokcan and Yong [20] introduced the notion of
saturated Newton polytope (SNP) of a polynomial $f$, i.e., $f$ has saturated
Newton polytope (SNP) if every lattice point in $\mathrm{Newton}(f)$ is also
an exponent vector of $f$. It was conjectured by Monical, Tokcan and Yong [20]
and proved by Fink, Mészáros and St. Dizier [15] that key polynomials
$\kappa_{\alpha}(x)$ have SNP.

Moreover, Fink, Mészáros, St. Dizier [15] also showed that the Newton
polytopes of key polynomials $\kappa_{\alpha}(x)$ are the Minkowski sum of
Schubert matroid polytopes associated to the columns of $D(\alpha)$. More
precisely, let $D(\alpha)=(D_{1},\ldots,D_{n})$, where $D_{j}$ is the $j$-th
column of $D(\alpha)$. View $D_{j}$ as a subset of $[n]$:

$D_{j}=\\{1\leq i\leq n\colon(i,j)\in D_{j}\\}.$

Then the column $D_{j}$ defines a Schubert matroid ${\rm SM}_{n}(D_{j})$. Let
${\rm rk}_{j}$ denote the rank function of ${\rm SM}_{n}(D_{j})$. Then

$\displaystyle\mathrm{Newton}(\kappa_{\alpha})$
$\displaystyle=\mathcal{P}({\rm SM}_{n}(D_{1}))+\cdots+\mathcal{P}({\rm
SM}_{n}(D_{n}))$
$\displaystyle=\left\\{x\in\mathbb{R}^{n}\colon\sum_{i\in[n]}x_{i}=|D(\alpha)|\
\ \text{and}\ \ \sum_{i\in T}x_{i}\leq{\rm rk}_{\alpha}(T)\ \ \text{for
$T\subsetneq[n]$}\right\\},$ (3.1)

where $|D(\alpha)|$ denotes the number of boxes in $D(\alpha)$ and

${\rm rk}_{\alpha}(T)={\rm rk}_{1}(T)+\cdots+{\rm rk}_{n}(T).$

######  Lemma 3.1.

Let $S$ be a subset of $[n]$ and $\alpha=\mathbb{I}(S)$ be the indicator
vector of $S$. Given any positive integer $t$, we have

$t\mathcal{P}({\rm SM}_{n}(S))=\mathrm{Newton}(\kappa_{t\alpha}).$

Proof. It is easy to see that ${\rm rk}_{S}([n])=|S|$ is the number of
elements in $S$. By (2.1), we find that

$t\mathcal{P}({\rm
SM}_{n}(S))=\left\\{x\in\mathbb{R}^{n}\colon\sum_{i\in[n]}x_{i}=t\cdot|S|\ \
\text{and}\ \ \sum_{i\in T}x_{i}\leq t\cdot{\rm rk}_{S}(T)\ \ \text{for
$T\subsetneq[n]$}\right\\}.$

On the other hand, since now $\alpha=\mathbb{I}(S)$ is a 0-1 vector,
$D(t\alpha)$ has exactly $t$ columns, every column determines the same
Schubert matroid, which is exactly ${\rm SM}_{n}(S)$. Moreover,
$|D(t\alpha)|=t\cdot|S|$ and ${\rm rk}_{t\alpha}(T)=t\cdot{\rm rk}_{S}(T)$.
Thus by (3), we conclude that

$\mathrm{Newton}(\kappa_{t\alpha})=t\mathcal{P}({\rm SM}_{n}(S)).$

This completes the proof.

Now we are in a position to give a proof of Theorem 1.1.

Proof of Theorem 1.1. By Lemma 3.1, the number of lattice points in
$t\mathcal{P}({\rm SM}_{n}(S))$ is the same as that in
$\mathrm{Newton}(\kappa_{t\alpha})$. Since key polynomials have saturated
Newton polytopes, $i(\mathcal{P}({\rm SM}_{n}(S)),t)$ is equal to the number
of different monomials in $\kappa_{t\alpha}(x)$.

Now we enumerate all the different monomials in $\kappa_{t\alpha}(x)$ by
Kohnert algorithm. Let $D(t\alpha)$ be the skyline diagram of $t\alpha$. Let
$D$ be a Kohnert diagram obtained from $D(t\alpha)$ by applying a sequence of
Kohnert moves. Let $n=r_{1}+r_{2}+\cdots+r_{2m}$ denote the number of parts of
$\alpha$, or equivalently, the number of rows of $D$, and denote
$\beta=(\beta_{1},\ldots,\beta_{n})$, where $\beta_{i}$ is the number of boxes
in the $i$-th row of $D$. Clearly, we have $0\leq\beta_{i}\leq t$. For $1\leq
j\leq m$, let

$d_{j}=r_{1}+r_{2}+\cdots+r_{2j}$

and

$c_{j}=\sum_{i=d_{j-1}+1}^{d_{j}}\beta_{i}-r_{2j}t,$

where $d_{0}=0$. Since the
$\beta_{1}+\cdots+\beta_{n}=(r_{2}+r_{4}+\cdots+r_{2m})t$, we have

$c_{1}+c_{2}+\cdots+c_{m}=(\beta_{1}+\cdots+\beta_{n})-(r_{2}+r_{4}+\cdots+r_{2m})t=0.$

It is also easy to see that the number of boxes in the top $d_{j}$ rows of $D$
is larger than or equal to that of $D(t\alpha)$, and the number of boxes in
the bottom $d_{m}-d_{j}$ rows of $D$ is smaller than that of $D(t\alpha)$.
That is,

$\beta_{1}+\cdots+\beta_{d_{j}}\geq(\alpha_{1}+\cdots+\alpha_{d_{j}})t=(r_{2}+r_{4}+\cdots+r_{2j})t.$

and

$\beta_{d_{j}+1}+\cdots+\beta_{d_{m}}\leq(\alpha_{d_{j}+1}+\cdots+\alpha_{d_{m}})t=(r_{2j+2}+\cdots+r_{2m})t.$

Thus we have

$c_{1}+c_{2}+\cdots+c_{j}=(\beta_{1}+\cdots+\beta_{d_{j}})-(r_{2}+r_{4}+\cdots+r_{2j})t\geq
0.$

Moreover, we have

$\displaystyle c_{j}$
$\displaystyle=\sum_{i=d_{j-1}+1}^{d_{j}}\beta_{i}-r_{2j}t\leq\sum_{i=d_{j-1}+1}^{d_{m}}\beta_{i}-r_{2j}t$
$\displaystyle\leq\sum_{i=d_{j-1}+1}^{d_{m}}t\alpha_{i}-r_{2j}t=(r_{2j+2}+\cdots+r_{2m})t.$

And

$\displaystyle c_{j}$
$\displaystyle=\sum_{i=d_{j-1}+1}^{d_{j}}\beta_{i}-r_{2j}t\leq\sum_{i=d_{j-1}+1}^{d_{j}}t-r_{2j}t=(r_{2j-1}+r_{2j})t-r_{2j}t=r_{2j-1}t.$

Thus we have

$\displaystyle c_{j}\leq\min\\{r_{2j-1},r_{2j+2}+\cdots+r_{2m}\\}t=tu_{j}.$
(3.2)

Similarly, we have

$\displaystyle c_{j}$
$\displaystyle=\sum_{i=1}^{d_{j}}\beta_{i}-\sum_{i=1}^{d_{j-1}}\beta_{i}-r_{2j}t\geq\sum_{i=1}^{d_{j}}t\alpha_{i}-\sum_{i=1}^{d_{j-1}}\beta_{i}-r_{2j}t$
$\displaystyle\geq\sum_{i=1}^{d_{j}}t\alpha_{i}-\sum_{i=1}^{d_{j-1}}t-r_{2j}t=\left(\sum_{i=1}^{j}r_{2i}\right)t-\sum_{i=1}^{d_{j-1}}t-r_{2j}t$
$\displaystyle=-(r_{1}+r_{3}+\cdots+r_{2j-3})t.$

And

$c_{j}=\sum_{i=d_{j-1}+1}^{d_{j}}\beta_{i}-r_{2j}t\geq-r_{2j}t.$

Then we find

$\displaystyle
c_{j}\geq-\min\\{r_{2j},r_{1}+r_{3}+\cdots+r_{2j-3}\\}t=-tv_{j}.$ (3.3)

Therefore, $\beta=(\beta_{1},\ldots,\beta_{n})$ satisfies the following system
of equations

$\displaystyle\left\\{\begin{array}[]{c}\ \
\sum\limits_{i=1}^{d_{1}}\beta_{i}=r_{2}t+c_{1},\\\\[10.0pt]
\sum\limits_{i=d_{1}+1}^{d_{2}}\beta_{i}=r_{4}t+c_{2},\\\\[10.0pt] \vdots\\\
\sum\limits_{i=d_{m-1}+1}^{d_{m}}\beta_{i}=r_{2m}t+c_{m},\end{array}\right.$
(3.8)

where $c_{1}+c_{2}+\cdots+c_{m}=0$, and for $1\leq j\leq m$,

$\displaystyle-tv_{j}\leq c_{j}\leq tu_{j}\ \ \text{and}\ \
c_{1}+c_{2}+\cdots+c_{j}\geq 0.$

Now we enumerate the number of nonnegative integer solutions of the equation

$\displaystyle\sum_{i=d_{j-1}+1}^{d_{j}}\beta_{i}=r_{2j}t+c_{j},\quad(0\leq\beta_{i}\leq
t).$ (3.9)

Since $0\leq\beta_{i}\leq t$, it is easy to see that the number of solutions
of equation (3.9) is the coefficient of $x^{r_{2j}t+c_{j}}$ in

$\displaystyle(1+x+\cdots+x^{t})^{d_{j}-d_{j-1}}$
$\displaystyle=(1+x+\cdots+x^{t})^{r_{2j-1}+r_{2j}}$
$\displaystyle=(1-x^{t+1})^{r_{2j-1}+r_{2j}}\cdot(1-x)^{-(r_{2j-1}+r_{2j})}$
$\displaystyle=\left(\sum_{i^{\prime}=0}^{r_{2j-1}+r_{2j}}(-1)^{i^{\prime}}{r_{2j-1}+r_{2j}\choose
i^{\prime}}x^{(t+1)i^{\prime}}\right)\left(\sum_{j^{\prime}=0}^{\infty}{r_{2j-1}+r_{2j}+j^{\prime}-1\choose
j^{\prime}}x^{j^{\prime}}\right)$
$\displaystyle=\sum_{j^{\prime}=0}^{\infty}\sum_{i^{\prime}=0}^{r_{2j-1}+r_{2j}}(-1)^{i^{\prime}}{r_{2j-1}+r_{2j}\choose
i^{\prime}}{r_{2j-1}+r_{2j}+j^{\prime}-1\choose
j^{\prime}}x^{j^{\prime}+(t+1)i^{\prime}}.$ (3.10)

Let $j^{\prime}=r_{2j}t+c_{j}-(t+1)i^{\prime}$ in (3.10), we see that the
coefficient of $x^{r_{2j}t+c_{j}}$ is

$\displaystyle
F(r_{2j-1},r_{2j},c_{j},t):=\sum_{i^{\prime}=0}^{r_{2j-1}+r_{2j}}(-1)^{i^{\prime}}{r_{2j-1}+r_{2j}\choose
i^{\prime}}{(t+1)(r_{2j}-i^{\prime})+r_{2j-1}+c_{j}-1\choose
r_{2j-1}+r_{2j}-1}.$ (3.11)

Consequently, the number of different monomials in $\kappa_{t\alpha}(x)$ is

$\sum_{(c_{1},\ldots,c_{m})}\prod_{j=1}^{m}F(r_{2j-1},r_{2j},c_{j},t).$

Conversely, suppose that $(\beta_{1},\ldots,\beta_{n})$ is an integer sequence
such that $0\leq\beta_{i}\leq t$ and $(\beta_{1},\ldots,\beta_{n})$ satisfies
the system of equations (3.8), we shall show that there is a diagram $D$ whose
$i$-th row has $\beta_{i}$ boxes and $D$ can be obtained from $D(t\alpha)$ by
applying Kohnert moves.

First of all, by adding all the equations in (3.8) together and combing the
condition $c_{1}+\cdots+c_{m}=0$, we have

$\beta_{1}+\beta_{2}+\cdots+\beta_{n}=(r_{2}+r_{4}+\cdots+r_{2m})t.$

That is, $\beta_{1}+\beta_{2}+\cdots+\beta_{n}$ is equal to the total number
of boxes in $D(t\alpha)$. We construct $D$ as follows. Fill the sequence of
integers $1^{\beta_{1}},2^{\beta_{2}},\ldots,n^{\beta_{n}}$ into the boxes of
$D(t\alpha)$ along the rows from top to bottom and from right to left. Then
move the box $(i,j)$ filled with $k$ to $(k,j)$. Denote the resulting diagram
by $D$. For example, Figure 3.4 displays the construction of $D$ for
$t\alpha=(0,0,3,0,3,3)$ and $\beta=(2,2,1,3,0,1)$.

$\longrightarrow$

$2$$1$$1$$4$$3$$2$$6$$4$$4$$\longrightarrow$

Figure 3.4: An illustration of the construction of $D$.

We aim to show that $D$ is indeed a Kohnert diagram. Since $0\leq\beta_{i}\leq
t$, by the construction of $D$, it is easy to see that there do not exist two
boxes in the same column of $D(t\alpha)$ that are filled with the same
integer. By the definition of Kohnert moves, to show that $D$ is indeed a
Kohnert diagram, it suffices to show that there does not exist a box of
$D(t\alpha)$ which is filled with an integer larger than its row index.

Suppose to the contrary that there is a box $(i,j)$ filled with $s$ and $s>i$.
Without loss of generality, we can assume that $(i,j)$ is such a box with $i$
largest. Since $i<s\leq n=r_{1}+\cdots+r_{2m}$, there exist integers $k,l$
such that $k\leq l$ and

$\displaystyle r_{1}+r_{2}+\cdots+r_{2k-1}$ $\displaystyle<i\leq
r_{1}+r_{2}+\cdots+r_{2k}=d_{k}$ (3.12) $\displaystyle
r_{1}+r_{2}+\cdots+r_{2l-1}$ $\displaystyle<s\leq
r_{1}+r_{2}+\cdots+r_{2l}=d_{l}.$ (3.13)

There are three cases.

Case 1. $l=k$, that is,

$r_{1}+r_{2}+\cdots+r_{2l-1}<i<s\leq r_{1}+r_{2}+\cdots+r_{2l}=d_{l}.$

By (3.8), we have

$\beta_{1}+\cdots+\beta_{d_{l}}=(r_{2}+r_{4}+\cdots+r_{2l})t+c_{1}+\cdots+c_{l}.$

Since $c_{1}+\cdots+c_{l}\geq 0$, we find that

$\beta_{1}+\cdots+\beta_{d_{l}}\geq(r_{2}+r_{4}+\cdots+r_{2l})t.$

That is to say, the integers $1,2,\ldots,d_{l}$ must occupy at least the top
$d_{l}=r_{1}+r_{2}+\cdots+r_{2l}$ rows (including empty rows) of $D(t\alpha)$.
On the other hand, since the box $(i,j)$ is filled with $s$ and $s>i$, we see
that the rows $i+1,\ldots,s,s+1,\ldots,d_{l}$ of $D(t\alpha)$ are occupied by
some of the integers among $s,s+1,\ldots,d_{l}$. In particular, the integers
$s,s+1,\ldots,d_{l}$ must occupy at least $d_{l}-s+1$ rows of $D(t\alpha)$.
Therefore,

$\beta_{s}+\beta_{s+1}+\cdots+\beta_{d_{l}}>(d_{l}-s+1)t.$

Thus there must exist some $\beta_{j}>t$, which contradicts with the
assumption $0\leq\beta_{j}\leq t$.

Case 2. $l\geq k+1$ and $i=d_{k}$. In this case, we have

$s>r_{1}+r_{2}+\cdots+r_{2l-1}\geq r_{1}+r_{2}+\cdots+r_{2k+1}=i+r_{2k+1}.$

Similar to Case 1, we see that the integers $s,s+1,\ldots,d_{l}$ must occupy
all the boxes of $D(t\alpha)$ in the rows $s,s+1,\ldots,d_{l}$. Thus

$\beta_{s}+\beta_{s+1}+\cdots+\beta_{d_{l}}>(d_{l}-s+1)t,$

which is a contradiction.

Case 3. $l\geq k+1$ and $i<d_{k}$. In this case, we have $i+1\leq d_{k}$ and

$s>r_{1}+r_{2}+\cdots+r_{2l-1}\geq r_{1}+r_{2}+\cdots+r_{2k+1}\geq
i+r_{2k+1}\geq i+1.$

By the choice of $(i,j)$, $i$ is the largest index such that $s>i$ and $(i,j)$
is filled with $s$, we see that $s$ can not appear in the $(i+1)$-st row of
$D(t\alpha)$. Thus we have

$\displaystyle\beta_{1}+\beta_{2}+\cdots+\beta_{s}\leq(\alpha_{1}+\alpha_{2}+\cdots+\alpha_{i})t\leq(r_{2}+r_{4}+\cdots+r_{2k})t.$
(3.14)

Moreover, since $s>r_{1}+r_{2}+\cdots+r_{2l-1}=d_{l-1}+r_{2l-1}\geq d_{l-1}$
and $\beta_{s}>0$, we derive that

$\displaystyle\beta_{1}+\cdots+\beta_{s}>\beta_{1}+\cdots+\beta_{d_{l-1}}=(r_{2}+r_{4}+\cdots+r_{2l-2})t+c_{1}+\cdots+c_{l-1},$
(3.15)

Combing (3.14) and (3.15), we get

$(r_{2}+r_{4}+\cdots+r_{2l-2})t+c_{1}+\cdots+c_{l-1}<(r_{2}+r_{4}+\cdots+r_{2k})t.$

Since $c_{1}+\cdots+c_{l-1}\geq 0$, we must have $2l-2<2k$, that is, $l<k+1$.
This is a contradiction.

##  4 Properties of $F(a,b,c,t)$

In this section, we explore some further properties of $F(a,b,c,t)$ as defined
in (1.3), and prove Corollaries 1.5 and 1.4.

By (3.9) and (3.11) in the proof of Theorem 1.1, $F(a,b,c,t)$ is the number of
integer solutions of the equation

$\displaystyle\left\\{\begin{array}[]{ll}x_{1}+x_{2}+\cdots+x_{a+b}=bt+c,\\\
0\leq x_{i}\leq t,\ \text{for $1\leq i\leq a+b$}.\end{array}\right.$ (4.3)

The following are some useful initial values of $F(a,b,c,t)$:

$\displaystyle F(a,1,0,t)$ $\displaystyle=\binom{a+t}{a},\quad
F(a,b,c,1)={a+b\choose b+c},$ $\displaystyle F(a,0,c,t)$
$\displaystyle=\binom{a+c-1}{c},\ \text{for $0\leq c<t$},$ $\displaystyle
F(a,1,c,t)$
$\displaystyle=\left\\{\begin{array}[]{ll}\displaystyle\sum_{i=1}^{a+1}{c+i-1\choose
c}{t+a-i\choose t-1}-(a+1){a+c-1\choose a},&\hbox{if $c\geq 0$;}\\\\[15.0pt]
\displaystyle{t+a+c\choose a},&\hbox{if $c<0$.}\end{array}\right.$ (4.6)

Ferroni [11, Theorem 4.3] showed that $i(U_{k,n},t)$, or equivalently
$F(n-k,k,0,t)$, has positive coefficients by giving a combinatorial
interpretation of the coefficient of $t^{m}$ for any $m\geq 0$. More
precisely,

$\displaystyle[t^{m}]i(U_{k,n},t)=\frac{1}{(n-1)!}\sum_{j=0}^{k-1}W(j,n,m+1)A(m,k-j-1),$
(4.7)

where $W(j,n,m+1)$ are the weighted Lah numbers and $A(m,k-j-1)$ are the
Eulerian numbers. In particular, $W(0,n,k)={n\brack k}$ is the unsigned
Stirling number of the first kind. It is well known that

$t(t+1)\cdots(t+n-1)=\sum_{k=0}^{n}{n\brack k}t^{k},$

and

$\displaystyle{n\brack k}=(n-1){n-1\brack k}+{n-1\brack k-1}.$ (4.8)

We proceed to develop some further properties of the polynomial $F(a,b,c,t)$.

######  Lemma 4.1.

We have

$\displaystyle F(a,b,c,t)$ $\displaystyle=F(b,a,-c,t)$ (4.9) $\displaystyle
F(a,b,c,t)$ $\displaystyle=F(a+1,b-1,c+t,t)$ (4.10) $\displaystyle
F(a+1,b,0,t)$ $\displaystyle=\sum_{i=0}^{t}F(a,b,-i,t).$ (4.11)

Proof. Let $y_{i}=t-x_{i}$ in the equation (4.3). Then
$y_{1}+y_{2}+\cdots+y_{a+b}=(a+b)t-(bt+c)=at-c$, where $0\leq y_{i}\leq t$. It
is easy to see that the number of integer solutions of this equation is
$F(b,a,-c,t)$. Thus (4.9) holds.

Since both $F(a,b,c,t)$ and $F(a+1,b-1,t+c,t)$ are the number of solutions of
$x_{1}+\cdots+x_{a+b}=bt+c=(b-1)t+t+c$, where $0\leq x_{i}\leq t$, we obtain
(4.10).

Similarly, since $F(a+1,b,0,t)$ is the number of solutions of the equation
$x_{1}+\cdots+x_{a+b}=bt-x_{a+b+1}$, where $0\leq x_{i}\leq t$ for
$i=1,\ldots,a+b+1$, we see that (4.11) follows.

In the following of this section, we consider $i(r(S),t)$ when $r(S)$ has only
four elements. Let $a,b,c,d$ be nonnegative integers, and $r(S)=(a,b,c,d)$.
Then $u=(\min\\{a,d\\},0),v=(0,\min\\{a,d\\})$ and by (4.9),

$\displaystyle
i((a,b,c,d),t)=i((d,c,b,a),t)=\sum_{j=0}^{t\cdot\min\\{a,d\\}}F(a,b,j,t)F(c,d,-j,t).$
(4.12)

######  Theorem 4.2.

For any nonnegative integers $a,b,c,d$, we have

$\displaystyle
i((a,b,c,d),t)+i((b,a,d,c),t)=F(a+c,b+d,0,t)+F(a,b,0,t)F(c,d,0,t).$ (4.13)

Proof. Since $F(a+c,b+d,0,t)$ is the number of solutions of
$x_{1}+\cdots+x_{a+b+c+d}=(b+d)t$, where $0\leq x_{i}\leq t$, which is equal
to the sum of number of solutions of

$\displaystyle\left\\{\begin{array}[]{ll}x_{1}+\cdots+x_{a+b}=bt+j,\\\
x_{a+b+1}+\cdots+x_{a+b+c+d}=dt-j,\\\ 0\leq x_{i}\leq t,\ \text{for $1\leq
i\leq a+b+c+d$},\end{array}\right.$ (4.17)

for all possible integers $j$. It is clear that if $j<-bt$, then the first
equation of (4.17) has no solutions. If $j<-ct$, then the second equation has
no solution. Thus $j\geq-t\cdot\min\\{b,c\\}$. Similarly, one can check that
$j\leq t\cdot\min\\{a,d\\}$. Therefore,

$\displaystyle F(a+c,b+d,0,t)$
$\displaystyle=\sum_{j=-t\cdot\min\\{b,c\\}}^{t\cdot\min\\{a,d\\}}F(a,b,j,t)F(c,d,-j,t)$
$\displaystyle=\sum_{j=0}^{t\cdot\min\\{a,d\\}}F(a,b,j,t)F(c,d,-j,t)+\sum_{j=-t\cdot\min\\{b,c\\}}^{0}F(a,b,j,t)F(c,d,-j,t)$
$\displaystyle\qquad-F(a,b,0,t)F(c,d,0,t)$
$\displaystyle=\sum_{j=0}^{t\cdot\min\\{a,d\\}}F(a,b,j,t)F(c,d,-j,t)+\sum_{j=0}^{t\cdot\min\\{b,c\\}}F(b,a,j,t)F(d,c,-j,t)$
$\displaystyle\qquad-F(a,b,0,t)F(c,d,0,t)$
$\displaystyle=i((a,b,c,d),t)+i((b,a,d,c),t)-F(a,b,0,t)F(c,d,0,t),$

where the last step holds by (4.12).

######  Corollary 4.3.

We have

$\displaystyle i((1,1,a,b),t)+i((1,1,b-1,a+1),t)=(t+2)F(a+1,b,0,t).$ (4.18)

Proof. Since $F(1,1,i,t)=t+1-i$ for $0\leq i\leq t$, by (4.12), we find

$\displaystyle i((1,1,a,b),t)+i((1,1,b-1,a+1),t)$
$\displaystyle=\sum_{i=0}^{t}((t-i+1)F(a,b,-i,t)+(t-i+1)F(b-1,a+1,-i,t))$
$\displaystyle=\sum_{i=0}^{t}((t-i+1)F(a,b,-i,t)+(t-i+1)F(a,b,i-t,t))$
$\displaystyle=\sum_{i=0}^{t}((t-i+1)F(a,b,-i,t)+(i+1)F(a,b,-i,t))$
$\displaystyle=\sum_{i=0}^{t}(t+2)F(a,b,-i,t)$
$\displaystyle=(t+2)F(a+1,b,0,t),$

where the second step holds by (4.9) and (4.10), and the last step follows
from (4.11).

Proof of Corollary 1.4. By (4.12), we find $i((a,b,a,b),t)=i((b,a,b,a),t)$.
The equations (1.6) and (1.7) follow directly from (4.13). And (1.8) is a
special case of (4.18).

In the rest of this section, we give a proof of Corollary 1.5.

Recall that the minimal matroid $T_{k,n}$ is the Schubert matroid ${\rm
SM}_{n}(S)$ with

$S=\\{2,3,\ldots,k,n\\},$

where $n>k\geq 2$.

Proof of Corollary 1.5. Since $r=(1,k-1,n-k-1,1)$, by (4.12), we have

$\displaystyle i(T_{k,n},t)=\sum_{j=0}^{t}F(1,k-1,j,t)F(n-k-1,1,-j,t).$ (4.19)

By (4.9) and (4.10), we have

$\displaystyle F(1,k-1,j,t)=F(k-1,1,-j,t)=F(k,0,t-j,t)=\binom{k+t-j-1}{t-j}$

and

$\displaystyle F(n-k-1,1,-j,t)=F(n-k,0,t-j,t)={t-j+n-k-1\choose n-k-1}.$

Then

$\displaystyle i(T_{k,n},t)$ $\displaystyle=\sum_{j=0}^{t}{t-j+n-k-1\choose
n-k-1}\binom{k+t-j-1}{t-j}$ $\displaystyle=\sum_{j=0}^{t}{j+n-k-1\choose
n-k-1}\binom{k+j-1}{j}.$ (4.20)

Thus we need to show that

$\displaystyle\sum_{j=0}^{t}{j+n-k-1\choose
n-k-1}\binom{k+j-1}{j}=\frac{1}{{n-1\choose k-1}}{t+n-k\choose
n-k}\sum_{j=0}^{k-1}{n-k+j-1\choose j}{t+j\choose j}.$ (4.21)

Let $s=n-k$ in (4.21), then we aim to show that

$\displaystyle\binom{s+k-1}{s}\sum_{j=0}^{t}\binom{j+s-1}{s-1}\binom{j+k-1}{k-1}=\binom{t+s}{s}\sum_{j=0}^{k-1}\binom{j+s-1}{s-1}\binom{t+j}{j}.$
(4.22)

It is easy to see that the left hand side of (4.22) is the coefficient of
$y^{s-1}x^{k-1}$ in

$\displaystyle\binom{s+k-1}{s}\sum_{j=0}^{t}(1+y)^{s+j-1}(1+x)^{k+j-1}$
$\displaystyle=\binom{k-1+s}{s}(1+y)^{s-1}(1+x)^{k-1}\cdot\frac{1-((1+y)(1+x))^{t+1}}{-x-y-
xy}.$ (4.23)

Similarly, the right hand side of (4.22) is the coefficient of $y^{s-1}x^{t}$
in

$\displaystyle\binom{t+s}{s}\sum_{j=0}^{k-1}(1+y)^{s+j-1}(1+x)^{t+j}$
$\displaystyle=\binom{t+s}{s}(1+y)^{s-1}(1+x)^{t}\cdot\frac{1-((1+y)(1+x))^{k}}{-x-y-
xy}.$ (4.24)

One can check that the coefficient of $y^{s-1}x^{k-1}$ in (4) is equal to the
coefficient of $y^{s-1}x^{t}$ in (4). Thus (4.22) follows. This completes the
proof.

To conclude this section, we remark that, in fact, we can compute
$i((1,1,a,b),t)$ recursively for any $a,b\geq 1$ by (4.13) and (4.18). For
instance, let $a=3,b=7$, we aim to compute $i((1,1,3,7),t)$. By (4.18), we
find

$i((1,1,3,7),t)+i((1,1,6,4),t)=(t+2)F(4,7,0,t).$

By (4.13), we have

$\displaystyle i((1,1,4,6),t)+i((1,1,6,4),t)$
$\displaystyle=F(7,5,0,t)+F(1,1,0,t)F(4,6,0,t)$
$\displaystyle=F(7,5,0,t)+(t+1)F(4,6,0,t).$

Again, by (4.18),

$i((1,1,4,6),t)+i((1,1,5,5),t)=(t+2)F(5,6,0,t),$

where by (1.7), $i((1,1,5,5),t)=\frac{1}{2}(F(6,6,0,t)+(t+1)F(5,5,0,t))$.
Thus, we obtain

$\displaystyle i((1,1,3,7),t)$
$\displaystyle=(t+2)(F(4,7,0,t)+F(5,6,0,t))-F(7,5,0,t)-(t+1)F(4,6,0,t)$
$\displaystyle\qquad-\frac{1}{2}(F(6,6,0,t)+(t+1)F(5,5,0,t)).$ (4.25)

If $r(S)=(a,1,b,1)$, then ${\rm SM}_{n}(S)$ is a Schubert matroid of rank 2.
Ferroni, Jochemko and Schröter [14, Theorem 1.1] showed that all matroids of
rank 2 are Ehrhart positive. By (4.12), we have

$\displaystyle i((a,1,b,1),t)$
$\displaystyle=i((1,b,1,a),t)=\sum_{j=0}^{t}F(1,b,j,t)F(1,a,-j,t)$
$\displaystyle=\sum_{j=0}^{t}F(a,1,j,t){b+t-j\choose b},$ (4.26)

where $F(a,1,j,t)$ has an explicitly expression by (4.6). However, it is not
obvious that (4.26) is a positive polynomial in $t$. Similarly, if
$r(S)=(a,1,b,1,c,1)$, then ${\rm SM}_{n}(S)$ is a Schubert matroid of rank 3.
We can obtain a formula for $i((a,1,b,1,c,1),t)$, i.e.,

$\displaystyle i((a,1,b,1,c,1),t)=\sum_{i=0}^{t}{t+c-i\choose
c}\sum_{j=-i}^{t+i}F(a,1,j,t)F(b,1,i-j,t),$ (4.27)

where $F(a,1,j,t)$ and $F(b,1,i-j,t)$ have explicit expressions by (4.6).

Although Ferroni [13] showed that not all matroids of ranks larger than or
equal to 3 are Ehrhart positive, it is still possible that Schubert matroids
of any rank are Ehrhart positive.

######  Problem 4.4.

Show that $i((1,1,a,b),t),i((a,1,b,1),t),i((a,b,b,a),t),i((a,1,b,1,c,1),t)$
have positive coefficients for any $a,b,c\geq 1$.

######  Problem 4.5.

Show that $i((a,b,c,d),t)$ has positive coefficients for any $a,b,c,d\geq 1$.

##  5 $(a,b)$-Catalan matroids

In this section, we give a proof of Theorem 1.6.

Recall that the $(a,b)$-Catalan matroid $\mathbf{C}_{n}^{a,b}$ is the Schubert
matroid ${\rm SM}_{(a+b)n}(S)$, where

$r(S)=(\overbrace{a,b,a,b,\ldots,a,b}^{2n}).$

Given a composition $\sigma$ of $n$, $\ell(\sigma)$ denotes the number of
parts of $\sigma$, $d(\sigma)$ denotes the cardinality of the equivalent class
containing $\sigma$. And $\Gamma_{n}$ is the set of pairwise non-equivalent
compositions of $n$ with at least two parts and minimal parts larger than 1.

It is readily to see that (1.6) is equivalent to

$\displaystyle F(na,nb,0,t)$ $\displaystyle=n\cdot
i(\mathbf{\overline{C}}_{n}^{a,b},t)+F^{n}(a,b,0,t)+\sum_{\sigma\in\Gamma_{n}}(-1)^{\ell(\sigma)-1}\frac{nd(\sigma)}{\ell(\sigma)}\cdot
i(\overline{\mathbf{C}}_{\sigma}^{a,b},t),$ (5.1)

where $\displaystyle
i(\overline{\mathbf{C}}_{\sigma}^{a,b},t)=\prod_{j=1}^{\ell(\sigma)}i(\overline{\mathbf{C}}_{\sigma_{j}}^{a,b},t)$
and

$i(\overline{\mathbf{C}}_{\sigma_{j}}^{a,b},t)=i(\mathbf{C}_{\sigma_{j}}^{a,b},t)-F(a,b,0,t)\cdot
i(\mathbf{C}_{\sigma_{j}-1}^{a,b},t).$

We shall prove (5.1) by interpreting both sides in terms of weighted
enumerations of certain lattice paths.

Let us begin with interpreting $i(\mathbf{C}_{n}^{a,b},t)$ and $F(na,nb,0,t)$
separately. By Theorem 1.1, since $r=(a,b,\ldots,a,b)$, for $1\leq j\leq n$,
we have

$\displaystyle u_{j}=\min\\{a,(n-j)b\\},\ v_{j}=\min\\{b,(j-1)a\\}.$ (5.2)

Thus

$\displaystyle i(\mathbf{C}_{n}^{a,b},t)$
$\displaystyle=\sum_{(c_{1},\ldots,c_{n})}\prod_{j=1}^{n}F(a,b,c_{j},t),$

where $c_{1}+\cdots+c_{n}=0$, $c_{1}+\cdots+c_{j}\geq 0$ and $-tv_{j}\leq
c_{j}\leq tu_{j}$, for $1\leq j\leq n$.

On the other hand, since $F(na,nb,0,t)$ is the number of solutions of

$\displaystyle\left\\{\begin{array}[]{ll}x_{1}+x_{2}+\cdots+x_{(a+b)n}=bnt,\\\
0\leq x_{i}\leq t,\ \text{for $1\leq i\leq(a+b)n$}.\end{array}\right.$

which is equivalent to the system of equations

$\displaystyle\left\\{\begin{array}[]{c}x_{1,1}+\cdots+x_{1,a+b}=bt+c^{\prime}_{1},\\\
x_{2,1}+\cdots+x_{2,a+b}=bt+c^{\prime}_{2},\\\ \vdots\\\
x_{n,1}+\cdots+x_{n,a+b}=bt+c^{\prime}_{n},\end{array}\right.$ (5.7)

for all possible integers $c^{\prime}_{1},\ldots,c^{\prime}_{n}$, where $0\leq
x_{i,j}\leq t$ for $1\leq i\leq n$ and $1\leq j\leq a+b$, and
$c^{\prime}_{1}+\cdots+c^{\prime}_{n}=0$. It is easy to see that we can
require $-bt\leq c^{\prime}_{j}\leq at$ for $1\leq j\leq n$. Thus

$\displaystyle
F(na,nb,0,t)=\sum_{(c^{\prime}_{1},\ldots,c^{\prime}_{n})}\prod_{j=1}^{n}F(a,b,c^{\prime}_{j},t),$

where $c^{\prime}_{1}+\cdots+c^{\prime}_{n}=0$, and $-bt\leq
c^{\prime}_{j}\leq at$ for $1\leq j\leq n$.

Let

$\displaystyle\mathcal{C}_{n}^{a,b}=\left\\{(c_{1},\ldots,c_{n})\,|\,\sum_{i=1}^{n}c_{i}=0,\
\sum_{i=1}^{j}c_{i}\geq 0\ \text{and}\ -tv_{j}\leq c_{j}\leq tu_{j},\ \forall\
1\leq j\leq n\right\\}$ (5.8)

and

$\displaystyle\mathcal{F}_{n}^{a,b}=\left\\{(c_{1},\ldots,c_{n})\,|\,\sum_{i=1}^{n}c_{i}=0,\
-bt\leq c_{j}\leq at,\ \forall\ 1\leq j\leq n\right\\}.$ (5.9)

Clearly, $\mathcal{C}_{n}^{a,b}\subseteq\mathcal{F}_{n}^{a,b}$. We can view
each sequence $\mathbf{c}=(c_{1},\ldots,c_{n})\in\mathcal{F}_{n}^{a,b}$ as a
lattice path from $(0,0)$ to $(n,0)$ such that $c_{j}$ represents: an up step
$(0,0)\rightarrow(1,c_{j})$ if $c_{j}>0$, a down step
$(0,0)\rightarrow(1,-|c_{j}|)$ if $c_{j}<0$, or a horizontal step
$(0,0)\rightarrow(1,0)$ if $c_{j}=0$. Assign a weight to $\mathbf{c}$ as

${\rm wt}(\mathbf{c})=\prod_{j=1}^{n}F(a,b,c_{j},t).$

In particular, $F(a,b,0,t)^{n}$ is the weight of the path $(0,0,\ldots,0)$.
Then

$i(\mathbf{C}_{n}^{a,b},t)=\sum_{\mathbf{c}\in\mathcal{C}_{n}^{a,b}}{\rm
wt}(\mathbf{c})\ \ \text{and}\ \
F(na,nb,0,t)=\sum_{\mathbf{c}\in\mathcal{F}_{n}^{a,b}}{\rm wt}(\mathbf{c})$

can be viewed as weighted enumerations of lattice paths in
$\mathcal{C}_{n}^{a,b}$ and $\mathcal{F}_{n}^{a,b}$, respectively. Let

$\displaystyle\mathcal{\overline{C}}_{n}^{a,b}=\\{(c_{1},\ldots,c_{n})\in\mathcal{C}_{n}^{a,b}\,|\,c_{n}\neq
0\\}.$ (5.10)

Then we find

$\displaystyle
i(\mathbf{\overline{C}}_{n}^{a,b},t)=\sum_{\mathbf{c}\in\mathcal{\overline{C}}_{n}^{a,b}}{\rm
wt}(\mathbf{c}).$ (5.11)

Moreover, given a composition $\sigma=(\sigma_{1},\ldots,\sigma_{s})$ of $n$,
denote

$\displaystyle\mathcal{\overline{C}}_{\sigma}^{a,b}=\\{(\mathbf{c}_{1},\ldots,\mathbf{c}_{s})\,|\,\mathbf{c}_{j}\in\mathcal{\overline{C}}_{\sigma_{j}}^{a,b},\
\text{for}\ 1\leq j\leq s\\},$ (5.12)

then

$i(\mathcal{\overline{C}}_{\sigma}^{a,b},t)=\prod_{j=1}^{\ell(\sigma)}i(\overline{\mathbf{C}}_{\sigma_{j}}^{a,b},t)=\sum_{\mathbf{c}\in\mathcal{\overline{C}}_{\sigma}^{a,b}}{\rm
wt}(\mathbf{c}).$

Therefore, (5.1) is equivalent to

$\displaystyle\sum_{\mathbf{c}\in\mathcal{F}_{n}^{a,b}}{\rm
wt}(\mathbf{c})=n\cdot\sum_{\mathbf{c}\in\mathcal{\overline{C}}_{n}^{a,b}}{\rm
wt}(\mathbf{c})+{\rm
wt}((0,\ldots,0))+\sum_{\sigma\in\Gamma_{n}}(-1)^{\ell(\sigma)-1}\frac{nd(\sigma)}{\ell(\sigma)}\sum_{\mathbf{c}\in\mathcal{\overline{C}}_{\sigma}^{a,b}}{\rm
wt}(\mathbf{c}).$ (5.13)

To prove (5.13), we shall enumerate the number of appearances of each
$\mathbf{c}\in\mathcal{F}_{n}^{a,b}$ in the right hand side of (5.13) by
inclusion-exclusion. To this end, define two operators $R$ and $L$ on each
$\mathbf{c}=(c_{1},\ldots,c_{n})\in\mathcal{F}_{n}^{a,b}$ as follows

$\displaystyle R(\mathbf{c})$ $\displaystyle=(c_{2},\ldots,c_{n},c_{1}),$
$\displaystyle L(\mathbf{c})$ $\displaystyle=(c_{n},c_{1},\ldots,c_{n-1}),$

and let $R^{m}(\mathbf{c})=(c_{m+1},\ldots,c_{n},c_{1},\ldots,c_{m})$ denote
the effect of applying $R$ to $\mathbf{c}$ $m$ times, where $m\geq 1$. Similar
$L^{m}(\mathbf{c})$ denote applying $L$ to $\mathbf{c}$ $m$ times. It is clear
that $R^{n}(\mathbf{c})=L^{n}(c)=\mathbf{c}$. Denote
$\mathcal{L}^{m}_{\mathbf{c}}$ by the list of paths obtained from $\mathbf{c}$
by applying $L$ to $\mathbf{c}$ $m-1$ times, i.e.,

$\mathcal{L}^{m}_{\mathbf{c}}=(\mathbf{c},L(\mathbf{c}),L^{2}(\mathbf{c}),\ldots,L^{m-1}(\mathbf{c})).$

It is quite possible that $\mathcal{L}^{m}_{\mathbf{c}}$ contains repeated
paths. Similarly, let

$\mathcal{R}^{m}_{\mathbf{c}}=(\mathbf{c},R(\mathbf{c}),R^{2}(\mathbf{c}),\ldots,R^{m-1}(\mathbf{c})).$

Obviously, each path in $\mathcal{L}^{m}_{\mathbf{c}}$ or
$\mathcal{R}^{m}_{\mathbf{c}}$ has the same weight.

Denote $n\cdot\mathcal{\overline{C}}_{n}^{a,b}$ by the list of paths that each
$\mathbf{c}$ of $\mathcal{\overline{C}}_{n}^{a,b}$ are replaced by the $n$
paths in $\mathcal{R}^{n}_{\mathbf{c}}$. Similarly, denote
$\frac{nd(\sigma)}{\ell(\sigma)}\cdot\mathcal{\overline{C}}_{\sigma}^{a,b}$ by
the list of paths that each $\mathbf{c}$ of
$\mathcal{\overline{C}}_{\sigma}^{a,b}$ are replaced by the
$\frac{nd(\sigma)}{\ell(\sigma)}$ paths in
$\mathcal{R}^{\frac{nd(\sigma)}{\ell(\sigma)}}_{\mathbf{c}}$ for any
$\sigma\in\Gamma_{n}$. If there is a minus sign in front of some
$\frac{nd(\sigma)}{\ell(\sigma)}\cdot\mathcal{\overline{C}}_{\sigma}^{a,b}$,
then we delete the number of appearances of each
$\mathbf{c}\in\frac{nd(\sigma)}{\ell(\sigma)}\cdot\mathcal{\overline{C}}_{\sigma}^{a,b}$
in the enumeration. Assume that $\Gamma_{n}$ has $\gamma_{n}$ different
compositions, i.e.,
$\Gamma_{n}=\\{\sigma^{1},\sigma^{2},\ldots,\sigma^{\gamma_{n}}\\}$. Let

$\displaystyle\left(n\cdot\mathcal{\overline{C}}_{n}^{a,b},(-1)^{\ell(\sigma^{1})-1}\frac{nd(\sigma^{1})}{\ell(\sigma^{1})}\cdot\mathcal{\overline{C}}_{\sigma^{1}}^{a,b},\ldots,(-1)^{\ell(\sigma^{\gamma_{n}})-1}\frac{nd(\sigma^{\gamma_{n}})}{\ell(\sigma^{\gamma_{n}})}\cdot\mathcal{\overline{C}}_{\sigma^{\gamma_{n}}}^{a,b}\right).$
(5.14)

To prove (5.13), we aim to show that, after cancellations, each
$\mathbf{c}\in\mathcal{F}_{n}^{a,b},\mathbf{c}\neq(0,\ldots,0)$ appears
exactly once in (5.14).

######  Example 5.1.

Let $n=6,a=2,b=3,t=1$ and
$\mathbf{c}=(1,-1,2,-2,1,-1)\in\mathcal{F}_{6}^{2,3}$. Then
$\Gamma_{6}=\\{(4,2),(3,3),(2,2,2)\\}$. We aim to enumerate the number of
appearances of $\mathbf{c}$ in

$\displaystyle\left(6\overline{\mathcal{C}}_{6}^{2,3},-6\overline{\mathcal{C}}_{(4,2)}^{2,3},-3\overline{\mathcal{C}}_{(3,3)}^{2,3},2\overline{\mathcal{C}}_{(2,2,2)}^{2,3}\right).$
(5.15)

One can check that $\mathbf{c}$ appears in $6\overline{\mathcal{C}}_{6}^{2,3}$
3 times. That is, for the 3 paths
$\mathbf{c}_{1}=\mathbf{c},\mathbf{c}_{2}=(2,-2,1,-1,1,-1),\mathbf{c}_{3}=(1,-1,1,-1,2,-2)$
in $\overline{\mathcal{C}}_{6}^{2,3}$, $\mathbf{c}$ appears in each of
$\mathcal{R}^{6}_{\mathbf{c}_{1}},\mathcal{R}^{6}_{\mathbf{c}_{2}},\mathcal{R}^{6}_{\mathbf{c}_{3}}$
exactly once. Similarly, $\mathbf{c}$ appears in
$6\overline{\mathcal{C}}_{(4,2)}^{2,3}$ 3 times with minus sign. That is, for
the 3 paths
$\mathbf{c}_{1}^{\prime}=\mathbf{c},\mathbf{c}_{2}^{\prime}=\mathbf{c}_{2},\mathbf{c}_{3}^{\prime}=\mathbf{c}_{3}$
in $\overline{\mathcal{C}}_{(4,2)}^{2,3}$, $\mathbf{c}$ appears in each of
$\mathcal{R}^{6}_{\mathbf{c}_{1}^{\prime}},\mathcal{R}^{6}_{\mathbf{c}_{2}^{\prime}},\mathcal{R}^{6}_{\mathbf{c}_{3}^{\prime}}$
exactly once. Moreover, $\mathbf{c}$ appears in
$3\overline{\mathcal{C}}_{(3,3)}^{2,3}$ 0 times, and appears in
$2\overline{\mathcal{C}}_{(2,2,2)}^{2,3}$ exactly once. That is,
$\mathbf{c}\in\overline{\mathcal{C}}_{(2,2,2)}^{2,3}$ and $\mathbf{c}$ only
appears in $\mathcal{R}^{2}_{\mathbf{c}}=(\mathbf{c},(-1,2,-2,1,-1,1))$ once.
Therefore, the total number of appearances of $\mathbf{c}$ in (5.15) is 1.

Given a path $\mathbf{c}\in\mathcal{F}_{n}^{a,b}$, if $\mathbf{c}$ does not go
below the $x$-axis, then we write $\mathbf{c}\geq 0$ for simplicity, and say
$\mathbf{c}$ is nonnegative. Otherwise, write $\mathbf{c}<0$ and say
$\mathbf{c}$ is negative. Obviously, if $\mathbf{c}\geq 0$, then
$c_{1}+\cdots+c_{j}\geq 0$ for any $1\leq j\leq n$.

It is clear that
$\mathcal{\overline{C}}_{n}^{a,b}\subseteq\mathcal{F}_{n}^{a,b}$ and
$\mathcal{\overline{C}}_{\sigma}^{a,b}\subseteq\mathcal{F}_{n}^{a,b}$ for any
$\sigma\in\Gamma_{n}$. By the definitions of $\mathcal{C}_{n}^{a,b}$ and
$\mathcal{F}_{n}^{a,b}$ in (5.8) and (5.9), it seems possible that there
exists $\mathbf{c}\in\mathcal{F}_{n}^{a,b}$ and $\mathbf{c}\geq 0$, but
$\mathbf{c}\notin\mathcal{C}_{n}^{a,b}$. However, we show that this situation
can not happen.

For $\mathbf{c}=(c_{1},\ldots,c_{n})\in\mathcal{F}_{n}^{a,b}$, let

$\mathcal{E}_{\mathbf{c}}=\\{(c_{j},\ldots,c_{n},c_{1},\ldots,c_{j-1})\,|\,1\leq
j\leq n\\}$

denote the set of paths that can be obtained from $\mathbf{c}$ by cyclic
shifting.

######  Lemma 5.2.

Each $\mathcal{E}_{\mathbf{c}}$ contains a nonnegative path.

Proof. Given $\mathbf{c}=(c_{1},\ldots,c_{n})$, define
$d_{j}=c_{1}+\cdots+c_{j}$ for $1\leq j\leq n$. If $d_{1},\ldots,d_{n}\geq 0$,
then it is clear that $\mathbf{c}$ is nonnegative. If $d_{j}<0$ for some $j$,
then let $k$ be the smallest index such that
$d_{k}=\min\\{d_{1},\ldots,d_{n}\\}$. Let
$\mathbf{c}^{\prime}=(c_{k+1},\ldots,c_{n},c_{1},\ldots,c_{k})\in\mathcal{E}_{\mathbf{c}}$.
It is easy to see that $\mathbf{c}^{\prime}$ is nonnegative.

######  Lemma 5.3.

We have

$\displaystyle\mathcal{F}_{n}^{a,b}=\bigcup_{\mathbf{c}\in\mathcal{C}_{n}^{a,b}}\mathcal{E}_{\mathbf{c}}.$
(5.16)

Proof. By Lemma 5.2,

$\mathcal{F}_{n}^{a,b}=\bigcup_{\mathbf{c}\in\mathcal{F}_{n}^{a,b},\,\mathbf{c}\geq
0}\mathcal{E}_{\mathbf{c}}.$

Clearly,
$\mathcal{C}_{n}^{a,b}\subseteq\\{\mathbf{c}\in\mathcal{F}_{n}^{a,b}\,|\,\mathbf{c}\geq
0\\}$. We aim to show that

$\\{\mathbf{c}\in\mathcal{F}_{n}^{a,b}\,|\,\mathbf{c}\geq
0\\}\subseteq\mathcal{C}_{n}^{a,b}.$

Given $\mathbf{c}=(c_{1},\ldots,c_{n})\in\mathcal{F}_{n}^{a,b}$ such that
$\mathbf{c}\geq 0$, we need to show that $-tv_{j}\leq c_{j}\leq tu_{j}$ for
any $1\leq j\leq n$. Since $\mathbf{c}\geq 0$, we have
$c_{1}+\cdots+c_{j-1}\geq 0$. Adding the first $j$ equations in (5.7)
together, we obtain

$\displaystyle
jbt+c_{1}+\cdots+c_{j-1}+c_{j}=\sum_{i=1}^{j}\sum_{i^{\prime}=1}^{a+b}x_{i,i^{\prime}}\leq
bnt,$ (5.17)

thus $c_{j}\leq(n-j)bt$. Combing the fact $c_{j}\leq at$, we arrive at

$c_{j}\leq\min\\{(n-j)bt,at\\}=tu_{j}.$

On the other hand, by (5.17), we obtain

$(j-1)bt+c_{1}+\cdots+c_{j-1}=\sum_{i=1}^{j-1}\sum_{i^{\prime}=1}^{a+b}x_{i,i^{\prime}}\leq(j-1)(a+b)t,$

thus

$(n-j+1)bt+c_{j}+\cdots+c_{n}=\sum_{i=j}^{n}\sum_{i^{\prime}=1}^{a+b}x_{i,i^{\prime}}\geq
bnt-(j-1)(a+b)t,$

so we see that

$\displaystyle c_{j}\geq-(j-1)at-(c_{j+1}+\cdots+c_{n})\geq-(j-1)at,$ (5.18)

where $c_{j+1}+\cdots+c_{n}\leq 0$ since $c_{1}+\cdots+c_{n}=0$ and
$c_{1}+\cdots+c_{j}\geq 0$. Combining the fact $c_{j}\geq-bt$ and (5.18), we
obtain

$c_{j}\geq\min\\{-bt,-(j-1)at\\}=-tv_{j},$

as desired.

By Lemma 5.2 and Lemma 5.3, we can divide the discussions into three cases,
that is, $\mathbf{c}\geq 0,c_{n}\neq 0$, or $\mathbf{c}\geq 0,c_{n}=0$, or
$\mathbf{c}<0$.

######  Proposition 5.4.

Let $\mathbf{c}=(c_{1},\ldots,c_{n})\geq 0$ such that $c_{n}\neq 0$. Then
$\mathbf{c}$ appears exactly once in (5.14).

To give a proof of Proposition 5.4, we need to enumerate how many copies of
$\mathbf{c}$ appearing in each
$\frac{nd(\sigma)}{\ell(\sigma)}\mathcal{\overline{C}}_{\sigma}^{a,b}$. To
this end, we first give a combinatorial interpretation of the coefficient
$\frac{nd(\sigma)}{\ell(\sigma)}$.

For a composition $\sigma=(\sigma_{1},\ldots,\sigma_{s})$ of $n$, denote
$p(\sigma)$ by the least period of $\sigma$, that is, $p(\sigma)$ is the
smallest integer such that $\sigma_{i}=\sigma_{i+p(\sigma)}$ for all $i$. If
$\sigma$ has no period, then we define $p(\sigma)=\ell(\sigma)$. It is easy to
see that $p(\sigma)=d(\sigma)$ is the cardinality of the equivalent class
containing $\sigma$. Let

$\displaystyle T(\sigma)=\sigma_{1}+\cdots+\sigma_{p(\sigma)}$ (5.19)

be the sum of elements in a least period of $\sigma$. Since
$p(\sigma)=d(\sigma)$ and
$\frac{n}{T(\sigma)}=\frac{\ell(\sigma)}{p(\sigma)}$, we have

$\displaystyle T(\sigma)=\frac{nd(\sigma)}{\ell(\sigma)}.$ (5.20)

For example, if $\sigma=(4,3,4,3,4,3,4,3)$, then
$n=28,p(\sigma)=d(\sigma)=2,\ell(\sigma)=8,$ and $T(\sigma)=4+3=7$. If
$\sigma=(3,3,2,2)$, then $n=10,p(\sigma)=d(\sigma)=\ell(\sigma)=4$ and
$T(\sigma)=3+3+2+2=10$.

For $\mathbf{c}=(c_{1},\ldots,c_{n})\geq 0$ and $c_{n}\neq 0$, we associate a
unique composition

$\displaystyle\pi(\mathbf{c})=(\pi_{1},\ldots,\pi_{\ell})$ (5.21)

to $\mathbf{c}$ as follows. Assume that $\ell_{1}$ is the smallest index such
that $c_{1}+\cdots+c_{\ell_{1}}=0$ and $c_{\ell_{1}}<0$. Then let
$\pi_{1}=\ell_{1}$. Let $\ell_{2}$ be the smallest index such that
$c_{\ell_{1}+1}+\cdots+c_{\ell_{2}}=0$ and $c_{\ell_{2}}<0$. Then let
$\pi_{2}=\ell_{2}-\ell_{1}$. Continue this process, we can obtain
$\pi(\mathbf{c})$ eventually. Since $\mathbf{c}\geq 0$ and $c_{n}\neq 0$, it
is easy to see that $\pi_{i}\geq 2$ for each $1\leq i\leq\ell$ and
$\mathbf{c}\in\mathcal{\overline{C}}_{\pi(\mathbf{c})}^{a,b}$. Moreover,

$\displaystyle\\{\pi(\mathbf{c})\,|\,\mathbf{c}\geq 0,c_{n}\neq
0\\}=\Gamma_{n}\cup\\{(n)\\}.$ (5.22)

For example, let $\mathbf{c}=(0,0,3,-1,0,-2,0,1,-1,0,1,1,-2,1,-1)$. Then
$\pi(\mathbf{c})=(6,3,4,2)$, see Figure 5.5 for an illustration of the path
$\mathbf{c}$.

$\cdot$$\cdot$$0$$0$$3$$-1$$0$$-2$$0$$1$$-1$$0$$1$$1$$-2$$1$$-1$ Figure 5.5:
The path $\mathbf{c}$.

Given a composition $\sigma=(\sigma_{1},\ldots,\sigma_{s})$, arrange
$\sigma_{1},\ldots,\sigma_{s}$ on a directed circle, such that there is a
directed edge from $\sigma_{i}$ to $\sigma_{i+1}$ for $1\leq i\leq s-1$, and a
directed edge from $\sigma_{s}$ to $\sigma_{1}$. If $\sigma=(n)$ has only one
part, then there is a directed loop on the node $n$. We call such a
configuration the circle representation of $\sigma$, denoted as $G(\sigma)$.
We view all the edges in $G(\sigma)$ different, even if they have the same
nodes and directed edges. For example, Figure 5.6 displays the circle
representations of $(8),(4,4),(4,3,1),(4,1,3)$, respectively. There are two
different edges in Figure 5.6(b).

By contracting a directed edge, say $\sigma_{i}\rightarrow\sigma_{i+1}$, of
$G(\sigma)$, we mean delete this edge and form a new node labeled by
$\sigma_{i}+\sigma_{i+1}$, and keep all the other edges unchanged. Since all
the edges in $G(\sigma)$ are viewed different, it is quite possible that
different ways of contracting the edges lead to the same circle
representation. For example, Figure 5.6(b) can be viewed as obtained by
contracting the directed edge $3\rightarrow 1$ in Figure 5.6(c), or
contracting the directed edge $1\rightarrow 3$ in Figure 5.6(d). Moreover, we
can obtain Figure 5.6(a) twice by contracting the two different edges of
Figure 5.6(b).

$\bullet$8$\bullet$44$\bullet$$\bullet$$4$$\bullet$$1$$\bullet$$3$$\bullet$$4$$\bullet$$3$$\bullet$$1$$(a)$$(b)$$(c)$$(d)$
Figure 5.6: Circle representations of $(8),(4,4),(4,3,1),(4,1,3)$.

If $\sigma$ and $\sigma^{\prime}$ have the same circle representation, then
$\sigma\sim\sigma^{\prime}$ are equivalent. It is easy to see that
$T(\sigma)\cdot\mathcal{\overline{C}}_{\sigma}^{a,b}$ and
$T(\sigma^{\prime})\cdot\mathcal{\overline{C}}_{\sigma^{\prime}}^{a,b}$
contain the same number of appearances of each
$\mathbf{c}\in\mathcal{F}_{n}^{a,b}$. Given a composition $\tau$, after
contracting some edges of $G(\tau)$, we obtain a new circle representation,
which is $G(\sigma)$ for some composition $\sigma$. To read off a specific
$\sigma$, we can choose any node in $G(\sigma)$ as the first element
$\sigma_{1}$, and then read off $\sigma_{2},\sigma_{3}$, etc. of $\sigma$ from
$G(\sigma)$ clock-wisely.

######  Proposition 5.5.

Let $\mathbf{c}\geq 0$ and $c_{n}\neq 0$. Then the number of appearance of
$\mathbf{c}$ in $T(\sigma)\cdot\mathcal{\overline{C}}_{\sigma}^{a,b}$ is equal
to the number of ways that $G(\sigma)$ can be obtained by contracting edges in
$G(\pi(\mathbf{c}))$.

Proof. Let $\mathbf{c}=(c_{1},\ldots,c_{n})$ and
$\pi(\mathbf{c})=(\pi_{1},\ldots,\pi_{\ell})$. We first show that if there is
a way of contracting edges of $G(\pi(\mathbf{c}))$ to obtain $G(\sigma)$, then
$\mathbf{c}$ appears at least once in
$T(\sigma)\cdot\mathcal{\overline{C}}_{\sigma}^{a,b}$. Then we show that if
$\mathbf{c}$ appears once in
$T(\sigma)\cdot\mathcal{\overline{C}}_{\sigma}^{a,b}$, then there is a way of
contracting edges of $G(\pi(\mathbf{c}))$ to obtain $G(\sigma)$.

A contracting of edges of $G(\pi(\mathbf{c}))$ is equivalent to adding
consecutive elements of $\pi(\mathbf{c})$ together, where we arrange
$\pi(\mathbf{c})$ on a circle, thus $\pi_{1}$ and $\pi_{\ell}$ can be added
together. After contracting edges of $G(\pi(\mathbf{c}))$, we obtain
$G(\sigma)$. Since $\sigma$ may have a period, to read off $\sigma$, we need
to locate a position of $\sigma_{1}$, and then read off
$\sigma_{2},\sigma_{3},$ etc. from $G(\sigma)$ clock-wisely. There are two
cases, depending on whether $\pi_{1}$ and $\pi_{\ell}$ are added together or
not.

Case 1. There exist $1\leq j<i\leq{\ell}$ such that
$\pi_{i},\ldots,\pi_{\ell},\pi_{1},\ldots,\pi_{j}$ are added together. Let
$\sigma_{1}=\pi_{i}+\cdots+\pi_{\ell}+\pi_{1}+\cdots+\pi_{j}$.

Case 2. There exists $1\leq i\leq\ell$ such that $\pi_{i},\ldots,\pi_{\ell}$
are added together. Let $\sigma_{1}=\pi_{i}+\cdots+\pi_{\ell}$.

For both cases, let

$\mathbf{c}^{\prime}=L^{\pi_{i}+\cdots+\pi_{\ell}}(\mathbf{c}).$

One can check that
$\mathbf{c}^{\prime}\in\mathcal{\overline{C}}_{\sigma}^{a,b}$. Since
$\pi_{i}+\cdots+\pi_{\ell}\leq T(\sigma)$ and
$\mathbf{c}=R^{\pi_{i}+\cdots+\pi_{\ell}}(\mathbf{c}^{\prime})$, we find that
$\mathbf{c}$ will appear in
$\mathcal{R}^{T(\sigma)}_{\mathbf{c}^{\prime}}=(\mathbf{c}^{\prime},R(\mathbf{c}^{\prime}),\ldots,R^{T(\sigma)-1}(\mathbf{c}^{\prime}))$
at least once.

In the following, we show that if $\mathbf{c}$ appears in
$T(\sigma)\cdot\mathcal{\overline{C}}_{\sigma}^{a,b}$ once, then there is a
way of contracting edges of $G(\pi(\mathbf{c}))$ to obtain $G(\sigma)$.

Suppose that there exists
$\mathbf{c}^{\prime}\in\mathcal{\overline{C}}_{\sigma}^{a,b}$ such that
$\mathcal{R}^{T(\sigma)}_{\mathbf{c}^{\prime}}=(\mathbf{c}^{\prime},R(\mathbf{c}^{\prime}),\ldots,R^{T(\sigma)-1}(\mathbf{c}^{\prime}))$
contains $k_{0}$ copies of $\mathbf{c}$. We aim to construct $k_{0}$ different
ways of contracting edges of $G(\pi(\mathbf{c}))$ to obtain $G(\sigma)$. Let
$0\leq i_{1}<i_{2}<\cdots<i_{k_{0}}\leq T(\sigma)-1$ such that

$R^{i_{1}}(\mathbf{c}^{\prime})=R^{i_{2}}(\mathbf{c}^{\prime})=\cdots=R^{i_{k_{0}}}(\mathbf{c}^{\prime})=\mathbf{c}.$

Then
$\mathbf{c}^{\prime}=L^{i_{1}}(\mathbf{c})=\cdots=L^{i_{k_{0}}}(\mathbf{c})$
and there exist $i_{1}^{\prime}<i_{2}^{\prime}<\cdots<i_{k_{0}}^{\prime}$ such
that

$R^{i_{1}^{\prime}}(\pi(\mathbf{c}^{\prime}))=R^{i_{2}^{\prime}}(\pi(\mathbf{c}^{\prime}))=\cdots=R^{i_{k_{0}}^{\prime}}(\pi(\mathbf{c}^{\prime}))=\pi(\mathbf{c}).$

Since $\mathbf{c}^{\prime}\in\mathcal{\overline{C}}_{\sigma}^{a,b}$, we can
add consecutive elements of
$\pi(\mathbf{c}^{\prime})=(\pi_{1}^{\prime},\ldots,\pi_{z}^{\prime})$ to
obtain $\sigma=(\sigma_{1},\ldots,\sigma_{s})$. If we require that
$\pi_{1}^{\prime}$ and $\pi_{z}^{\prime}$ can not be added together, then
there are integers $j_{1}<j_{2}<\cdots<j_{s}=z$ such that

$\sigma_{1}=\pi_{1}^{\prime}+\cdots+\pi_{j_{1}}^{\prime},\sigma_{2}=\pi_{j_{1}+1}^{\prime}+\cdots+\pi_{j_{2}}^{\prime},\ldots,\sigma_{s}=\pi_{j_{s-1}+1}^{\prime}+\cdots+\pi_{j_{s}}^{\prime}.$

For the $k_{0}$ appearances of $\mathbf{c}$ in
$\mathcal{R}^{T(\sigma)}_{\mathbf{c}^{\prime}}$, we can construct $k_{0}$ ways
of contracting edges of $G(\pi(\mathbf{c}))$ as following. For each
$j\in\\{i_{1}^{\prime},\ldots,i_{k_{0}}^{\prime}\\}$, we can add the elements
in $L^{j}(\pi(\mathbf{c}))$ with the same positions of elements in
$\pi(\mathbf{c}^{\prime})$. More precisely, for
$j\in\\{i_{1}^{\prime},\ldots,i_{k_{0}}^{\prime}\\}$, let

$\sigma_{1}=\pi_{1-j}+\cdots+\pi_{j_{1}-j},\sigma_{2}=\pi_{j_{1}+1-j}+\cdots+\pi_{j_{2}-j},\ldots,\sigma_{s}=\pi_{j_{s-1}+1-j}+\cdots+\pi_{j_{s}-j},$

where the indices are taken modulo $j_{s}=z$. It is easy to see that these
$k_{0}$ constructions correspond to $k_{0}$ different ways of contracting
edges of $G(\pi(\mathbf{c}))$.

For example, let $\pi(\mathbf{c})=(2,3,2,2,3,2,2,3,2,2,3,2)$, $\sigma=(14,14)$
and $\pi(\mathbf{c}^{\prime})=(2,2,3,$ $2,2,3,2,2,3,2,2,3)$. Then
$i_{1}=2,i_{2}=9$, i.e.,
$R^{2}(\mathbf{c}^{\prime})=R^{9}(\mathbf{c}^{\prime})=\mathbf{c}$ and
$i_{1}^{\prime}=1,i_{2}^{\prime}=4$. Since $j_{1}=6,j_{2}=12$, for
$j=i_{1}^{\prime}=1$, let $\sigma_{1}=\pi_{12}+\pi_{1}+\cdots+\pi_{5}$ and
$\sigma_{2}=\pi_{6}+\cdots+\pi_{11}$. For $j=i_{2}^{\prime}=4$, let
$\sigma_{1}=\pi_{9}+\cdots+\pi_{12}+\pi_{1}+\pi_{2}$ and
$\sigma_{2}=\pi_{3}+\cdots+\pi_{8}$.

Moreover, if there is another
$\mathbf{c}^{\prime\prime}\in\mathcal{\overline{C}}_{\sigma}^{a,b}$ such that
$\mathcal{R}^{T(\sigma)}_{\mathbf{c}^{\prime\prime}}=(\mathbf{c}^{\prime\prime},R(\mathbf{c}^{\prime\prime}),\ldots,R^{T(\sigma)-1}(\mathbf{c}^{\prime\prime}))$
contains $m_{0}$ copies of $\mathbf{c}$. Let

$R^{i_{1}^{\prime}}(\mathbf{c}^{\prime\prime})=R^{i_{2}^{\prime}}(\mathbf{c}^{\prime\prime})=\cdots=R^{i_{m_{0}}^{\prime}}(\mathbf{c}^{\prime\prime})=\mathbf{c}.$

Then we must have
$\\{i_{1},\ldots,i_{k_{0}}\\}\cap\\{i_{1}^{\prime},\ldots,i_{m_{0}}^{\prime}\\}=\emptyset$.
In fact, if there exists
$j\in\\{i_{1},\ldots,i_{k_{0}}\\}\cap\\{i_{1}^{\prime},\ldots,i_{m_{0}}^{\prime}\\}$,
then $R^{j}(\mathbf{c}^{\prime})=R^{j}(\mathbf{c}^{\prime\prime})=\mathbf{c}$,
this implies $\mathbf{c}^{\prime}=\mathbf{c}^{\prime\prime}$. By the same
constructions for $\mathbf{c}^{\prime}$, we can obtain $m_{0}$ ways of
contracting edges of $G(\pi(\mathbf{c}))$, different from the above $k_{0}$
ways. This completes the proof.

Proof of Proposition 5.4. Assume that $\pi(\mathbf{c})$ has
$m=\ell(\pi(\mathbf{c}))$ parts, i.e., $G(\pi(\mathbf{c}))$ has $m$ edges. It
is clear that the number of appearance of $\mathbf{c}$ in
$(-1)^{m-1}T(\pi(\mathbf{c}))\cdot\mathcal{\overline{C}}_{\pi(\mathbf{c})}^{a,b}$
is $(-1)^{m-1}$, corresponding to contracting 0 edges in $G(\pi(\mathbf{c}))$.
By Proposition 5.5, if we contract one edge of $G(\pi(\mathbf{c}))$, then
$\mathbf{c}$ will be enumerated by $m$ times, with sign $(-1)^{m}$. Similarly,
if we contract any two edges of $G(\pi(\mathbf{c}))$, $\mathbf{c}$ will be
enumerated by ${m\choose 2}$ times with sign $(-1)^{m+1}$, etc. Therefore, the
total number of appearance of $\mathbf{c}$ is

$(-1)^{m-1}{m\choose 0}+(-1)^{m}{m\choose 1}+(-1)^{m+1}{m\choose
2}+\cdots+(-1)^{m+m-2}{m\choose m-1}=1,$

as required.

For the running example in Example 5.1, given $\mathbf{c}=(1,-1,2,-2,1,-1)$,
we have $\pi(\mathbf{c})=(2,2,2)$. We need to contract edges of $G((2,2,2))$
to obtain circle representations of $(6),(4,2),(3,3),(2,2,2)$. For
$\sigma=(6)$, there are 3 ways of contracting 2 edges among all 3 edges in
$G((2,2,2))$ to obtain $G((6))$, so $\mathbf{c}$ is counted $\binom{3}{2}$
times in $6\overline{C}^{2,3}_{(6)}$. For $\sigma=(4,2)$, there are 3 ways to
contract 1 edge of $G((2,2,2))$ to obtain $G((4,2))$, so $\mathbf{c}$ is
counted $\binom{3}{1}$ times in $6\overline{C}^{2,3}_{(4,2)}$ with minus sign.
Similarly, we can contract 0 edges in $G((2,2,2))$ to obtain $G((2,2,2))$,
which means $\mathbf{c}$ is counted $\binom{3}{0}$ times in
$2\overline{C}^{2,3}_{(2,2,2)}$. We can not obtain $G((3,3))$ by contracting
any edges of $G((2,2,2))$. Consequently, the total number of appearances of
$\mathbf{c}$ in (5.15) is

$\binom{3}{2}-\binom{3}{1}+\binom{3}{0}=1.$

In the following, we consider the case $\mathbf{c}=(c_{1},\ldots,c_{n})<0$.

######  Proposition 5.6.

If $\mathbf{c}<0$, then $\mathbf{c}$ appears in (5.14) exactly once.

Proof. For $1\leq j\leq n$, let $d_{j}=c_{1}+\cdots+c_{j}$. Let $k$ be the
largest index such that $d_{k}=\min\\{d_{1},\ldots,d_{n}\\}$. Define

$\mathbf{c}^{\prime}=L^{n-k}(\mathbf{c}).$

It is easy to see that
$\mathbf{c}^{\prime}\in\mathcal{\overline{C}}_{n}^{a,b}$ and $n-k$ is the
smallest integer $m$ such that $L^{m}(\mathbf{c})\geq 0$. By Proposition 5.4,
the total number of appearances of $\mathbf{c}^{\prime}$ in (5.14) is 1. For
example, let $\mathbf{c}=(2,-4,7,-7,4,-4,4,-2)$. Then $k=6$ and
$\mathbf{c}^{\prime}=(4,-2,2,-4,7,-7,4,-4)$. The paths $\mathbf{c}$ and
$\mathbf{c}^{\prime}$ are displayed in Figure 5.7.

$k$$k$$n$$n$$\mathbf{c}$$\mathbf{c}^{\prime}$ Figure 5.7: The paths
$\mathbf{c}$ and $\mathbf{c}^{\prime}$.

For any path
$\mathbf{c}^{\prime\prime}\in\mathcal{\overline{C}}_{\sigma}^{a,b}$, let

$\mathcal{R}^{T(\sigma)}(\mathbf{c}^{\prime\prime})=(\mathbf{c}^{\prime\prime},R(\mathbf{c}^{\prime\prime}),R^{2}(\mathbf{c}^{\prime\prime}),\ldots,R^{T(\sigma)-1}(\mathbf{c}^{\prime\prime})).$

We aim to show that the number of appearances of $\mathbf{c}$ and
$\mathbf{c}^{\prime}$ in $\mathcal{R}^{T(\sigma)}(\mathbf{c}^{\prime\prime})$
are the same. We first show that if there are two paths $\mathbf{c}$ in
$\mathcal{R}^{T(\sigma)}(\mathbf{c}^{\prime\prime})$, then there is a path
$\mathbf{c}^{\prime}$ between them. Suppose that there exist $i<j$ such that
$R^{i}(\mathbf{c}^{\prime\prime})=R^{j}(\mathbf{c}^{\prime\prime})=\mathbf{c}$.
Then

$\displaystyle\mathbf{c}^{\prime}=L^{n-k}(\mathbf{c})=L^{n-k}(R^{j}(\mathbf{c}^{\prime\prime}))=R^{j-(n-k)}(\mathbf{c}^{\prime\prime}).$
(5.23)

Since $j-i>n-k$, we have $i<j-(n-k)<j$, which means that $\mathbf{c}^{\prime}$
appears between $R^{i}(\mathbf{c}^{\prime\prime})$ and
$R^{j}(\mathbf{c}^{\prime\prime})$ at least once. Similarly, we can obtain
that there is a $\mathbf{c}$ between any two $\mathbf{c}^{\prime}$ in
$\mathcal{R}^{T(\sigma)}(\mathbf{c}^{\prime\prime})$.

At this moment, we can only conclude that the number of appearances of
$\mathbf{c}$ and $\mathbf{c}^{\prime}$ in
$\mathcal{R}^{T(\sigma)}(\mathbf{c}^{\prime\prime})$ are equal or differ by 1.
Let $i_{0}$ be the smallest index such that
$R^{i_{0}}(\mathbf{c}^{\prime\prime})=\mathbf{c}$ and $j_{0}$ be the largest
index such that $R^{j_{0}}(\mathbf{c}^{\prime\prime})=\mathbf{c}$. Since
$\mathbf{c}^{\prime\prime}=L^{i_{0}}(\mathbf{c})\geq 0$, we find that
$i_{0}\geq n-k$. Since $\mathbf{c}^{\prime}=L^{n-k}(\mathbf{c})$, we find that
$\mathbf{c}^{\prime}$ must appear in
$(\mathbf{c}^{\prime\prime},R(\mathbf{c}^{\prime\prime}),\ldots,R^{i_{0}}(\mathbf{c}^{\prime\prime}))$.
Similarly, we can show that there is a $\mathbf{c}$ appearing to the right of
the right-most $\mathbf{c}^{\prime}$. This completes the proof.

Finally, we consider the case $\mathbf{c}\geq 0,c_{n}=0$.

######  Proposition 5.7.

If $\mathbf{c}\geq 0,c_{n}=0$, then $\mathbf{c}$ appears in (5.14) exactly
once.

Proof. Let $q$ be the largest index such that $c_{q}\neq 0$ and
$c_{q+1}=\cdots=c_{n}=0$. Define

$\mathbf{c}^{\prime}=L^{n-q}(\mathbf{c})=(c_{q+1},\ldots,c_{n},c_{1},\ldots,c_{q}).$

Similar to the proof of Proposition 5.6, we can show that the number of
appearances of $\mathbf{c}$ and $\mathbf{c}^{\prime}$ are exactly the same in
each $T(\sigma)\cdot\mathcal{\overline{C}}_{\sigma}^{a,b}$.

##  6 Sparse paving Schubert matroids

In this section, we study a specific family of Schubert matroids, i.e., sparse
paving Schubert matroids. Recall that a matroid $M$ if sparse paving if and
only if every subset of cardinality ${\rm rk}(M)$ is either a basis or a
circuit-hyperplane.

Let $r=(k-1,1,1,n-k-1)$, where $n>k\geq 2$, we obtain a Schubert matroid,
denoted as ${\rm Sp}_{k,n}$.

######  Proposition 6.1.

A Schubert matroid ${\rm SM}_{n}(S)$ is sparse paving if and only if

$S=\\{k,k+2,\ldots,n\\}.$

Proof. Suppose that $S=\\{k,k+2,\ldots,n\\}$. Then we aim to show that every
$(n-k)$-subset $T$ of $[n]$ is either a basis of ${\rm SM}_{n}(S)$ or a
circuit-hyperplane. In fact, it is easy to see that there is exactly one
$(n-k)$-subset of $[n]$ which is not a basis of ${\rm SM}_{n}(S)$, i.e.,
$T=\\{k+1,\ldots,n\\}$. It is also straightforward to check that
$T=\\{k+1,\ldots,n\\}$ is both a circuit and a flat. Moreover, it is easy to
see that ${\rm rk}_{S}(T)=n-k-1$, which means $T$ is also a hyperplane. Thus
${\rm SM}_{n}(S)$ is sparse paving.

On the contrary, suppose that $S=\\{s_{1},s_{2},\ldots,s_{n-k}\\}\subseteq[n]$
such that ${\rm SM}_{n}(S)$ is sparse paving, where $s_{1}<\cdots<s_{n-k}=n$.
Assume that there is an $(n-k)$-subset $T=\\{t_{1},\ldots,t_{n-k}\\}$ of
$[n]$, where $t_{1}<\cdots<t_{n-k}$, which is not a basis. Then $T$ is both a
circuit and a flat and ${\rm rk}_{S}(T)=n-k-1$. Since $T$ is a circuit, every
proper subset of $T$ is independent, we see that there exists a unique index
$j$ such that $t_{j}>s_{j}$.

We claim that

$\\{t_{j+1},\ldots,t_{n-k}\\}=\\{k+j+1,\ldots,n\\}.$

First of all, there must have $t_{n-k}=s_{n-k}=n$, since otherwise ${\rm
rk}_{S}(T\cup\\{n\\})={\rm rk}_{S}(T)$, which is a contradiction. Since
$t_{j+1}\leq s_{j+1}\leq k+j+1,\ldots,t_{n-k}\leq s_{n-k}=n$, if there is some
$z\in\\{k+j+1,\ldots,n\\}-\\{t_{j+1},\ldots,t_{n-k}\\}$, then $z\notin T$,
$z<n$ and ${\rm rk}_{S}(T\cup\\{z\\})={\rm rk}_{S}(T)$, which contradicts with
$T$ being a flat. Thus the claim follows.

By the claim, we have $j=1$, $T=\\{t_{1},k+2,\ldots,n\\}$ and
$S=\\{s_{1},k+2,\ldots,n\\}$. If $s_{1}=k+1$, then $T$ must be a basis for any
$t_{1}$. If $s_{1}\leq k-1$, since $k+2>t_{1}>s_{1}$, then we can choose an
element $z\in\\{s_{1}+1,\ldots,k+1\\}-\\{t_{1}\\}$ such that ${\rm
rk}_{S}(T\cup\\{z\\})={\rm rk}_{S}(T)$, contradiction.

By the proof of Proposition 6.1, if $S=\\{k,k+2,\ldots,n\\}$, then its
corresponding sparse paving Schubert matroid ${\rm Sp}_{k,n}$ has exactly one
circuit-hyperplane, i.e., $\\{k+1,\ldots,n\\}$. Therefore, by Ferroni [13,
Corollary 4.6], we have $i({\rm Sp}_{k,n},t)=i(U_{k,n},t)-i(T_{k,n},t-1)$. We
give an self-contained proof of this property here.

######  Lemma 6.2.

We have

$i({\rm Sp}_{k,n},t)=i({\rm Sp}_{n-k,n},t)=i(U_{k,n},t)-i(T_{k,n},t-1).$

Proof. Since $r({\rm Sp}_{k,n})=(k-1,1,1,n-k-1)$ and
$r(T_{k,n})=(1,k-1,n-k-1,1)$, by (4.13) and (4), we have

$\displaystyle i({\rm Sp}_{k,n},t)$
$\displaystyle=F(k,n-k,0,t)+F(k-1,1,0,t)F(n-k-1,1,0,t)-i(T_{k,n},t)$
$\displaystyle=i(U_{k,n},t)-\sum_{j=0}^{t}{j+n-k-1\choose j}{j+k-1\choose
j}+{t+n-k-1\choose t}{t+k-1\choose t}$
$\displaystyle=i(U_{k,n},t)-i(T_{k,n},t-1).$

By (4.12), $i((k-1,1,1,n-k-1),t)=i((n-k-1,1,1,k-1),t)$, that is, $i({\rm
Sp}_{k,n},t)=i({\rm Sp}_{n-k,n},t)$.

In order to give a proof of Theorem 1.9, we need two lemmas further.

######  Lemma 6.3.

For $3\leq k\leq\frac{n}{2}$, we have the coefficient-wise relation

$i(U_{2,n},t)\leq i(U_{k,n},t).$

Proof. By (4.7), we have

$[t^{m}]i(U_{2,n},t)=\frac{1}{(n-1)!}(W(0,n,m+1)A(m,1)+W(1,n,m+1)A(m,0)).$

There are four cases to consider.

Case 1. $k<m$. By (4.7),

$[t^{m}]i(U_{k,n},t)\geq\frac{1}{(n-1)!}(W(0,n,m+1)A(m,k-1)+W(1,n,m+1)A(m,k-2)).$

Since the Eulerian numbers are unimodal and $k-1\geq 2$, we have $A(m,k-1)\geq
A(m,1)$ and $A(m,k-2)\geq A(m,0)$. So
$[t^{m}]i(U_{k,n},t)\geq[t^{m}]i(U_{2,n},t).$

Case 2. $k=m=3$. When $n=4,5$, the lemma holds obviously. When $n\geq 6$, it
is easy to see that

$W(0,n,4)\leq W(1,n,4)\ \text{and}\ W(1,n,4)\leq W(2,n,4).$

By (4.7),

$\displaystyle[t^{3}]i(U_{3,n},t)$
$\displaystyle=\frac{1}{(n-1)!}(W(0,n,4)+4W(1,n,4)+W(2,n,4))$
$\displaystyle\geq\frac{1}{(n-1)!}(4W(1,n,4)+W(2,n,4))$
$\displaystyle\geq\frac{1}{(n-1)!}(4W(0,n,4)+W(1,n,4)))$
$\displaystyle=[t^{3}]i(U_{2,n},t).$

Case 3. $k=m\geq 4$. By (4.7),

$\displaystyle[t^{m}]i(U_{k,n},t)$
$\displaystyle\geq\frac{1}{(n-1)!}(W(1,n,m+1)A(m,m-2)+W(m-2,n,m+1)A(m,1)).$

Since $A(m,m-2)\geq A(m,0)=1,$ it is enough to show that

$\displaystyle W(m-2,n,m+1)\geq W(0,n,m+1).$ (6.1)

We shall give a combinatorial proof of (6.1).

Denote $\mathcal{W}(\ell,n,m)$ by the set of partitions of weight $\ell$ of
$[n]$ into $m$ linearly ordered blocks, and let $W(\ell,n,m)$ be the
cardinality of $\mathcal{W}(\ell,n,m)$, see Ferroni [11]. For a partition
$\pi$ with linearly ordered blocks, the weight of $\pi$ is
$w(\pi)=\sum_{B\in\pi}w(B)$, where $w(B)$ is the number of elements in $B$
that are smaller than the first element in $B$. In order to prove (6.1), we
construct an injection from $\mathcal{W}(0,n,m+1)$ to
$\mathcal{W}(m-2,n,m+1)$.

By definition, $\mathcal{W}(0,n,m+1)$ is the set of partitions of $[n]$ into
$m+1$ blocks, the elements of each block are arranged increasingly. Suppose
that $\tau\in\mathcal{W}(0,n,m+1)$. We aim to construct a partition
$\tau^{\prime}\in\mathcal{W}(m-2,n,m+1)$ from $\tau$. Let $B_{1},\ldots,B_{j}$
be the blocks of $\tau$ having more than one element and the smallest element
of $B_{i}$ is smaller than the smallest element of $B_{i+1}$ for $1\leq i\leq
j-1$. Apparently,

$|B_{1}|+\cdots+|B_{j}|=n-(m+1-j).$

For any linearly ordered block $B=(b_{1},\ldots,b_{s})$ with $w(B)=0$, that
is, $b_{1}$ is the smallest element of $B$. Assume that $b_{m}$ is the largest
of element of $B$. Let $B^{\prime}$ be obtained from $B$ by cyclically
shifting $b_{m}$ to the first position, i.e.,
$B^{\prime}=(b_{m},\ldots,b_{s},b_{1},\ldots,b_{m-1})$. Then
$w(B^{\prime})=|B|-1$. Therefore,

$\displaystyle w(B_{1}^{\prime})+\cdots+w(B_{j}^{\prime})$
$\displaystyle=|B_{1}|-1+\cdots+|B_{j}|-1=n-(m+1).$

Since $k=m\leq\frac{n}{2}$, we have $n-(m+1)\geq m-1$. Thus we can construct a
partition $\tau^{\prime}\in\mathcal{W}(m-2,n,m+1)$ with weight $m-2$ from
$\tau$ as follows. There exists some index $i\,(1\leq i<j)$ such that

$w(B_{1}^{\prime})+\cdots+w(B_{i}^{\prime})\leq m-2\ \text{and}\
w(B_{1}^{\prime})+\cdots+w(B_{i+1}^{\prime})>m-2.$

We can cyclically shift a suitable element of $B_{i+1}$ to the first position
to obtain a new block $B_{i+1}^{\prime\prime}$, such that

$w(B_{1}^{\prime})+\cdots+w(B_{i}^{\prime})+w(B_{i+1}^{\prime\prime})=m-2.$

Keep the other blocks of $\tau^{\prime}$ the same with those of $\tau$. It is
easy to see that this construction is an injection from $\mathcal{W}(0,n,m+1)$
to $\mathcal{W}(m-2,n,m+1)$. This completes the proof of (6.1).

Case 4. $k>m$. By (4.7),

$[t^{m}]i(U_{k,n},t)\geq\frac{1}{(n-1)!}(W(k-1,n,m+1)A(m,0)+W(k-2,n,m+1)A(m,1)).$

We aim to show that

$\displaystyle\varphi(n,k,m):=W(k-2,n,m+1)-W(0,n,m+1)\geq 0$ (6.2)

and

$\displaystyle\psi(n,k,m):=W(k-1,n,m+1)-W(1,n,m+1)\geq 0.$ (6.3)

By Ferroni [11], $W(\ell,n,m)=W(n-m-\ell,n,m)$, then we have

$\varphi(n,k,m)=W(n-m-k+1,n,m+1)-W(0,n,m+1).$

Since $m<k\leq\frac{n}{2}$, we find $n-(m+1)\geq n-m-k+1>0$. By the same
arguments in the proof of (6.1), we can conclude that $W(n-m-k+1,n,m+1)\geq
W(0,n,m+1)$. Thus $\varphi(n,k,m)\geq 0$.

Similarly, since $n-(m+1)\geq k-1>1$, we can also utilize the same arguments
in the proof of (6.1) to show that $W(k-1,n,m+1)\geq W(1,n,m+1)$. That is,
$\psi(n,k,m)\geq 0$. This completes the proof.

######  Lemma 6.4.

For positive integers $m,n$, we have

${n+1\brack m+1}=\sum_{j=0}^{n}{j\brack m}\frac{n!}{j!}.$

Proof. Recall that ${n+1\brack m+1}$ represents the number of permutations on
$[n+1]$ with $m+1$ cycles. Alternatively, we can first choose $j$ numbers from
$1,2,\ldots,n$ to form $m$ cycles, there are ${n\choose j}{j\brack m}$ such
ways, then the left $n-j$ numbers and the number $n+1$ form another cycle,
there are $(n-j)!$ such ways.

Now we are ready to give a proof of Theorem 1.9.

Proof of Theorem 1.9. By Lemma 6.2 and Lemma 6.3, it suffices to show that

$i(U_{2,n},t)-i(T_{k,n},t-1)-i(T_{k,n},t)$

has positive coefficients. By Lemma 6.2 again, it is enough to only consider
$k\leq\frac{n}{2}$.

We first simplify $[t^{m}]i(U_{2,n},t)$, $[t^{m}]i(T_{k,n},t)$ and
$[t^{m}]i(T_{k,n},t-1)$ for $0\leq m\leq n$, separately.

By Ferroni [11, Corollary 3.13],

$W(\ell,n,m)=\sum_{j=0}^{\ell}\sum_{i=0}^{n-m}(-1)^{i+j}{n\choose
j}{m+\ell-j-1\choose m-1}{j\brack j-i}{n-j\brack m+i-j}.$

Then

$\displaystyle W(1,n,m+1)=(m+1){n\brack m+1}-n{n-1\brack m}.$ (6.4)

Since $A(m,1)=2^{m}-m-1$ and $A(m,0)=1$, by (4.7) and (6.4), we have

$\displaystyle(n-1)![t^{m}]i(U_{2,n},t)$
$\displaystyle=W(0,n,m+1)A(m,1)+W(1,n,m+1)A(m,0)$ $\displaystyle=2^{m}{n\brack
m+1}-n{n-1\brack m}$ (6.5) $\displaystyle=2^{m}\left((n-1){n-1\brack
m+1}+{n-1\brack m}\right)-n\left((n-2){n-2\brack m}+{n-2\brack m-1}\right)$
$\displaystyle=(n-2)\left(2^{m}{n-1\brack m+1}-(n-1){n-2\brack
m}\right)+2\left(2^{m-1}{n-1\brack m}-(n-1){n-2\brack m-1}\right)$
$\displaystyle\quad+2^{m}{n-1\brack m+1}-(n-2){n-2\brack m}+(n-2){n-2\brack
m-1}$ $\displaystyle\geq(n-2)\left(2^{m}{n-1\brack m+1}-(n-1){n-2\brack
m}\right)+2\left(2^{m-1}{n-1\brack m}-(n-1){n-2\brack m-1}\right)$
$\displaystyle\quad+2^{m}{n-1\brack m+1}-(n-2){n-2\brack m}.$ (6.6)

Replacing $t$ with $t-1$ in (1.9) and extracting the coefficient of $t^{m}$,
we find

$\displaystyle(n-1)!\cdot[t^{m}]i(T_{k,n},t-1)$
$\displaystyle=\sum_{j=0}^{k-1}\sum_{l=0}^{j}\frac{(k-1)!}{j!}\binom{n-k-1+j}{j}{j\brack
l}{n-k\brack m-l}$ (6.7)
$\displaystyle=\sum_{j=0}^{k-1}\sum_{l=0}^{j}\frac{(k-1)!}{j!}\frac{n-k-1+j}{n-k-1}\binom{n-k-2+j}{j}{j\brack
l}{n-k\brack m-l}.$

Since $n-k-1+j\leq n-2$ and $\frac{n-k-1+j}{n-k-1}\leq\frac{n-2}{n-k-1}\leq
2$, we have

$\displaystyle\frac{n-k-1+j}{n-k-1}{n-k\brack m-l}$
$\displaystyle=\frac{n-k-1+j}{n-k-1}\left((n-k-1){n-k-1\brack
m-l}+{n-k-1\brack m-l-1}\right)$ $\displaystyle\leq(n-2){n-k-1\brack
m-l}+2{n-k-1\brack m-l-1}.$

Then we conclude that

$\displaystyle(n-1)!\cdot[t^{m}]i(T_{k,n},t-1)$
$\displaystyle\leq\sum_{j=0}^{k-1}\sum_{l=0}^{j}\frac{(k-1)!}{j!}\binom{n-k-2+j}{j}\left((n-2){n-k-1\brack
m-l}+2{n-k-1\brack m-l-1}\right){j\brack l}.$ (6.8)

Similarly, by (1.9),

$\displaystyle(n-1)!\cdot[t^{m}]i(T_{k,n},t)$
$\displaystyle=\sum_{j=0}^{k-1}\sum_{l=0}^{j}\frac{(k-1)!}{j!}\binom{n-k-1+j}{j}{j+1\brack
l+1}{n-k+1\brack m-l+1}$ (6.9)
$\displaystyle=\sum_{j=0}^{k-1}\sum_{l=0}^{j}\frac{(k-1)!}{j!}\frac{n-k-1+j}{n-k-1}\binom{n-k-2+j}{j}{j+1\brack
l+1}{n-k+1\brack m-l+1}.$

Since $\frac{n-k-1+j}{n-k-1}(n-k)=(n-2)+(j-k+2+\frac{j}{n-k-1})$ and
$\frac{n-k-1+j}{n-k-1}\leq 2$, we have

$\displaystyle\frac{n-k-1+j}{n-k-1}{n-k+1\brack m-l+1}$
$\displaystyle=\frac{n-k-1+j}{n-k-1}\left((n-k){n-k\brack m-l+1}+{n-k\brack
m-l}\right)$ $\displaystyle\leq(n-2){n-k\brack
m-l+1}+\left(j-k+2+\frac{j}{n-k-1}\right){n-k\brack m-l+1}+2{n-k\brack m-l}.$

Therefore, we find

$\displaystyle(n-1)!\cdot[t^{m}]i(T_{k,n},t)$
$\displaystyle\leq\sum_{j=0}^{k-1}\sum_{l=0}^{j}\frac{(k-1)!}{j!}\binom{n-k-2+j}{j}\left((n-2){n-k\brack
m-l+1}+2{n-k\brack m-l}\right){j+1\brack l+1}+h(n,m),$ (6.10)

where

$h(n,m)=\sum_{j=0}^{k-1}\sum_{l=0}^{j}\frac{(k-1)!}{j!}\binom{n-k-2+j}{j}\left(j-k+2+\frac{j}{n-k-1}\right){n-k\brack
m-l+1}{j+1\brack l+1}.$

Consequently, by (6.5), (6.7) and (6.9), we have

$\displaystyle[t^{m}](i(U_{2,n},t)-i(T_{k,n},t-1)-i(T_{k,n},t))$
$\displaystyle=\frac{1}{(n-1)!}\left(2^{m}{n\brack m+1}-n{n-1\brack m}\right)$
$\displaystyle\quad-\frac{1}{(n-1)!}\sum_{j=0}^{k-1}\sum_{l=0}^{j}\frac{(k-1)!}{j!}\binom{n-k-1+j}{j}\left({j\brack
l}{n-k\brack m-l}+{j+1\brack l+1}{n-k+1\brack m-l+1}\right).$

Denote by

$\displaystyle f(n,m)$ $\displaystyle=2^{m}{n\brack m+1}-n{n-1\brack m}$
$\displaystyle\quad-\sum_{j=0}^{k-1}\sum_{l=0}^{j}\frac{(k-1)!}{j!}\binom{n-k-1+j}{j}\left({j\brack
l}{n-k\brack m-l}+{j+1\brack l+1}{n-k+1\brack m-l+1}\right).$

We aim to show that $f(n,m)\geq 0$ for $n\geq 4$ and $m\geq 0$ by induction on
$n$.

It is easy to check that $f(4,m)\geq 0$ for any $m\geq 0$. Moreover, since

$\sum_{j=0}^{k-1}\binom{n-k-1+j}{j}=\frac{k}{n-k}{n-1\choose k},$

we have

$\displaystyle f(n,0)$
$\displaystyle=(n-1)!-(k-1)!(n-k)!-(n-k)!(k-1)!\sum_{j=1}^{k-1}\binom{n-k-1+j}{j}$
$\displaystyle=(n-1)!-(k-1)!(n-k)!-(n-k)!(k-1)!\left(\frac{k}{n-k}{n-1\choose
k}-1\right)$ $\displaystyle=0.$

Assume that $f(n-1,m)\geq 0$ for $n\geq 5$ and $m\geq 0$. For $m\geq 1$, by
(6.6), (6.8) and (6.10), we derive that

$\displaystyle f(n,m)$ $\displaystyle\geq(n-2)\left(2^{m}{n-1\brack
m+1}-(n-1){n-2\brack m}\right)+2\left(2^{m-1}{n-1\brack m}-(n-1){n-2\brack
m-1}\right)$
$\displaystyle\quad-\sum_{j=0}^{k-1}\sum_{l=0}^{j}\frac{(k-1)!}{j!}\binom{n-k-2+j}{j}\left((n-2){n-k-1\brack
m-l}+2{n-k-1\brack m-l-1}\right){j\brack l}$
$\displaystyle\quad-\sum_{j=0}^{k-1}\sum_{l=0}^{j}\frac{(k-1)!}{j!}\binom{n-k-2+j}{j}\left((n-2){n-k\brack
m-l+1}+2{n-k\brack m-l}\right){j+1\brack l+1}$
$\displaystyle\quad+2^{m}{n-1\brack m+1}-(n-2){n-2\brack m}-h(n,m)$
$\displaystyle=(n-2)f(n-1,m)+2f(n-1,m-1)+2^{m}{n-1\brack m+1}-(n-2){n-2\brack
m}-h(n,m)$ $\displaystyle\geq 2^{m}{n-1\brack m+1}-(n-2){n-2\brack m}-h(n,m).$

To complete the proof, let

$g(n,m)=2^{m}{n-1\brack m+1}-(n-2){n-2\brack m}-h(n,m).$

We aim to prove that $g(n,m)\geq 0$ for any $n\geq 4$ and $m\geq 0$ by
induction on $n$.

It’s easy to check $g(4,m)=0$ for any $m\geq 0$ and $g(n,-1)=0$. Assume that
$g(n-1,m)\geq 0$ for $n\geq 5$ and $m\geq 0$. Then we have

$\displaystyle g(n,m)$ $\displaystyle=2^{m}{n-1\brack m+1}-(n-2){n-2\brack m}$
$\displaystyle\quad-\sum_{j=0}^{k-1}\sum_{l=0}^{j}\frac{(k-1)!}{j!}\left(j-k+2+\frac{j}{n-k-1}\right)\binom{n-k-2+j}{j}{j+1\brack
l+1}{n-k\brack m-l+1}$ $\displaystyle=2^{m}\left((n-2){n-2\brack
m+1}+{n-2\brack m}\right)-(n-2)\left((n-3){n-3\brack m}+{n-3\brack
m-1}\right)$
$\displaystyle\quad-\sum_{j=0}^{k-1}\sum_{l=0}^{j}\frac{(k-1)!}{j!}\left(j-k+2+\frac{j}{n-k-1}\right)$
$\displaystyle\quad\times\frac{n-k-2+j}{n-k-2}\binom{n-k-3+j}{j}\left((n-k-1){n-k-1\brack
m-l+1}+{n-k-1\brack m-l}\right){j+1\brack l+1}$
$\displaystyle\geq(n-2)\left(2^{m}{n-2\brack m+1}-(n-3){n-3\brack
m}\right)+2\left(2^{m-1}{n-2\brack m}-(n-3){n-3\brack m-1}\right)$
$\displaystyle\quad-\sum_{j=0}^{k-1}\sum_{l=0}^{j}\frac{(k-1)!}{j!}\left(j-k+2+\frac{j}{n-k-2}\right)$
$\displaystyle\quad\times\binom{n-k-3+j}{j}\left((n-2){n-k-1\brack
m-l+1}+2{n-k-1\brack m-l}\right){j+1\brack l+1}$
$\displaystyle\geq(n-2)g(n-1,m)+2g(n-1,m-1)$ $\displaystyle\geq 0,$

where the third step follows from the relations

$\left(j-k+2+\frac{j}{n-k-1}\right)\frac{n-k-2+j}{n-k-2}(n-k-1)\leq\left(j-k+2+\frac{j}{n-k-2}\right)(n-2)$

and

$\left(j-k+2+\frac{j}{n-k-1}\right)\frac{n-k-2+j}{n-k-2}\leq
2\left(j-k+2+\frac{j}{n-k-2}\right).$

This completes the proof.

Acknowledgments. Yao Li would like to thank the Research Experience for
Undergraduates (REU) program “Sparklet” of the Math Department at Sichuan
University. The authors are grateful to Shaoshi Chen, Peter Guo, Lisa Sun,
Matthew Xie, Sherry Yan and Arthur Yang for helpful conversations. This work
was supported by the National Natural Science Foundation of China (Grant No.
11971250, 12071320) and Sichuan Science and Technology Program (Grant No.
2020YJ0006).

## References

  * [1] F. Ardila, The Catalan matroid, J. Combin. Theory Ser. A 104 (2003), 49–62.
  * [2] F. Ardila, A. Fink and F. Rincón, Valuations for matroid polytope subdivisions, Canad. J. Math. 62 (2010), 1228–1245.
  * [3] J.E. Bonin, Basis-exchange properties of sparse paving matroids, Adv. in Appl. Math., 50(2013), 6–15.
  * [4] J.E. Bonin, A. de Mier and M. Noy, Lattice path matroids: enumerative aspects and Tutte polynomials, J. Combin. Theory Ser. A 104 (2003), 63–94.
  * [5] J.E. Bonin and A. de Mier. Lattice path matroids: structural properties, Europ. J. Combin., 27(5) (2006):701–738.
  * [6] F. Castillo and F. Liu, Berline-Vergne valuation and generalized permutohedra. Discrete Comput. Geom., 60(4) (2018):885–908.
  * [7] M. Demazure, Désingularisation des variétés de Schubert généralisées, Ann. Sci. École Norm. Sup. 7 (1974), 53–88.
  * [8] M. Demazure, Une nouvelle formule des caractéres, Bull. Sci. Math. (2) 98 (1974), 163–172.
  * [9] G. W. Dinolt, An extremal problem for non-separable matroids, In Théorie des matroïdes (Rencontre Franco-Britannique, Brest, 1970), pages 31–49. Lecture Notes in Math. Vol. 211. 1971.
  * [10] N.J.Y. Fan and P.L. Guo, Vertices of Schubitopes, J. Combin. Theory, Series A, 177, 105311, 2021.
  * [11] L. Ferroni, Hypersimplices are Ehrhart positive, J. Combin. Theory, series A, 178, 105365, 2021.
  * [12] L. Ferroni, On the Ehrhart polynomial of minimal matroids, Discrete Comput. Geom., to appear.
  * [13] L. Ferroni, Matroids are not Ehrhart positive, arXiv:2105.04465v2.
  * [14] L. Ferroni, K. Jochemko, B. Schröter, Ehrhart polynomials of rank two matroids, arXiv:2106.08183v1.
  * [15] A. Fink, K. Mészáros and A. St. Dizier, Schubert polynomials as integer point transforms of generalized permutahedra, Adv. Math. 332 (2018), 465–475.
  * [16] M. Katzman, The Hilbert series of algebras of the Veronese type, Comm. Algebra, vol. 33(2005), 1141–1146.
  * [17] K. Knauer, L. Martínez-Sandoval, J.L. Ramírez Alfonsín, On lattice path matroid polytopes: integer points and Ehrhart polynomial, Discrete Comput. Geom. 60(3) (2018), 698–719.
  * [18] A. Kohnert, Weintrauben, Polynome, Tableaux, Dissertation, Universität Bayreuth, Bayreuth, 1990. Bayreuth. Math. Schr. No. 38 (1991), 1–97.
  * [19] J. A. De Loera, D. C. Haws, and M. Köppe. Ehrhart polynomials of matroid polytopes and polymatroids. Discrete Comput. Geom., 42(4):670–702, erratum 703–704, 2009.
  * [20] C. Monical, N. Tokcan and A. Yong, Newton polytopes in algebraic combinatorics, Selecta Math. (N.S.) 25 (2019), no. 5, Paper No. 66.
  * [21] U.S.R. Murty, On the number of bases of a matroid, Proc. Second Lousiana Conf. on Combinatorics, Graph Theory and Computing, 225:387–410, 1971.
  * [22] S. Oh, Positroids and Schubert matroids, J. Combin. Theory Ser. A 118 (2011), 2426–2435.
  * [23] V. Reiner and M. Shimozono, Key polynomials and a flagged Littlewood-Richardson rule, J. Combin. Theory Ser. A 70 (1995), 107–143.

DEPARTMENT OF MATHEMATICS, SICHUAN UNIVERSITY, CHENGDU 610064, P.R. CHINA.

Email address<EMAIL_ADDRESS>(N.J.Y. Fan)

Email address<EMAIL_ADDRESS>(Y. Li)