simplify notation, we set $D(n,k,b,p):=D(n,k,r=1,b,p)$. Then we can rewrite
the above formula for $D(n,k,r,b,p)$ as follows

$\displaystyle
D(n,k,b,p)=\prod_{j=1}^{n+1}{((n+k-j+1)(p+1)+b)!((n-j+1)p+b+k)!(j-1)!\over((n-j+1)(p+1)+b)!((k+n-j+1)p+b+k)!(k+j-1)!}.$

$(1)$ If $k\leq n+1$, then

$\displaystyle D(n,k,b,p)=\prod_{j=1}^{k}{(n+k+1-j)(p+1)+b\choose
n-j+1}{(k-j)p+b+k\choose j}{j!(k-j)!(n-j+1)!\over(n+k-j+1)!}.$

In particular,

  * •

if $k=1$, then

$\displaystyle D(n,1,b,p)={1+b\over 1+b+(n+1)p}~{}{(p+1)(n+1)+b\choose
n+1}:=F_{n+1}^{(p+1)}(b),$

where $F_{n}^{p}(b):={1+b\over 1+b+(p-1)n}{pn+b\choose n}$ denotes the
generalized Fuss–Catalan number,

  * •

if $k=2$, then

$\displaystyle
D(n,2,b,p)={(2+b)(2+b+p)\over(1+b)(2+b+(n+1)p)(2+b+(n+2)p)}F_{n+1}^{(p+1)}(b)F_{n+2}^{(p+1)}(b),$

in particular,

$\displaystyle D(n,2,0,1)=\frac{6}{(n+3)(n+4)}{\rm Cat}_{n+1}{\rm Cat}_{n+2}.$

See [131, $A005700$] for several combinatorial interpretations of these
numbers.

$(2)$ Consider the Young diagram $($see R.A. Proctor [122])

$\displaystyle\lambda:=\lambda_{n,p,b}=\big{\\{}(i,j)\in\mathbb{Z}_{\geq
1}\times\mathbb{Z}_{\geq 1}\,|\,1\leq i\leq n+1,\,1\leq j\leq(n+1-i)p+b\\}.$

For each box $(i,j)\in\lambda$ define the numbers $c(i,j):=n+1-i+j$, and

$\displaystyle l_{(i,j)}(k)=\begin{cases}\dfrac{k+c(p,j)}{c(i,j)}&\text{if}\ \
j\leq(n+1-i)(p-1)+b,\vspace{1mm}\\\ \dfrac{(p+1)k+c(i,j)}{c(i,j)}&\text{if}\ \
(n+1-i)(p-1)<j-b\leq(n+1-i)p.\end{cases}$

Then

$\displaystyle D(n,k,b,p)=\prod_{(i,j)\in\lambda}l_{(i,j)}(k).$ (5.10)

Therefore, $D(n,k,b,p)$ is a polynomial in $k$ with rational coefficients.

$(3)$ If $p=0$, then

$\displaystyle D(n,k,b,0)=\dim
V_{(n+1)^{k}}^{\mathfrak{gl}(b+k)}=\prod_{j=1}^{n+k}\left({j+b\over
j}\right)^{\min(j,n+k+1-j)},$

where for any partition $\mu$, $\ell(\mu)\leq m$, $V_{\mu}^{\mathfrak{gl}(m)}$
denotes the irreducible $\mathfrak{gl}(m)$-module with the highest weight
$\mu$. In particular,

$\displaystyle D(n,2,b,0)={1\over n+2+b}{n+2+b\choose b}{n+2+b\choose b+1}$

is equal to the Narayana number $N(n+b+2,b)$,

$\displaystyle D(1,k,b,0)={(b+k)!(b+k+1)!\over k!b!(k+1)!(b+1)!}:=N(b+k+1,k),$

and therefore the number $D(1,k,b,0)$ counts the number of pairs of non-
crossing lattice paths inside a rectangular of size $(b+1)\times(k+1)$, which
go from the point $(1,0)$ $($resp. from that $(0,1))$ to the point $(b+1,k)$
$($resp. to that $(b,k+1))$, consisting of steps $U=(1,0)$ and $R=(0,1)$, see
[131, $A001263$], for some list of combinatorial interpretations of the
Narayana numbers.

$(4)$ If $p=b=1$, then

$\displaystyle D(n,k,1,1)=C^{(k)}_{n+k+1}:=\prod_{1\leq i\leq j\leq
n+1}{2k+i+j\over i+j}.$

$(5)$ If $p=1$ and $b$ is odd integer, then $D(n,k,b,1)$ is equal to the
dimension of the irreducible representation of the symplectic Lie algebra
${\rm Sp}(b+2n+1)$ with the highest weight $k\omega_{n+1}$ $($R.A. Proctor
[120, 121]).

$(6)$ If $p=1$ and $b=0$, then

$\displaystyle D(n,k,1,0)=D(n-1,k,1,1)=\prod_{1\leq i\leq j\leq n}{2k+i+j\over
i+j}=C_{n+k}^{(k)},$

see section on Grothendieck and Narayana polynomials.

$(7)$ Let $\varpi_{\lambda}$ be a unique dominant permutation of shape
$\lambda:=\lambda_{n,p,b}$ and $\ell:=\ell_{n,p,b}={1\over 2}(n+1)(np+2b)$ be
its length $($cf. [44]). Then

$\displaystyle\sum_{{\boldsymbol{a}}\in
R(\varpi_{\lambda})}\prod_{i=1}^{\ell}(x+a_{i})=\ell!B(n,x,p,b).$

Here for any permutation $w$ of length $l$, we denote by $R(w)$ the set
$\\{{\boldsymbol{a}}=(a_{1},\ldots,a_{l})\\}$ of all reduced decompositions of
$w$.

######  Exercises 5.43.

Show that

$\displaystyle\operatorname{DET}\big{|}F_{n+i+j-2}^{(2)}(0)\big{|}_{1\leq
i,j\leq k}=\prod_{j=1}^{k}F_{n+j-1}^{(2)}(0)\frac{{k+1\choose
2}!}{\prod\limits_{1\leq i\leq k-1\atop 1\leq j\leq k}(n+i+j)},$
$\displaystyle
D(n,k,b,1)=\prod_{j=1}^{k}F_{n+j}^{(2)}(b)\frac{\prod\limits_{1\leq i\leq
j\leq k}(b+i+j-1)}{\prod\limits_{1\leq i\leq k-1\atop 1\leq j\leq
k}(n+b+i+j+1)}.$

Clearly that if $b=0$, then $F_{n}^{(2)}(0)=C_{n}$, and $D(n,k,0,1)$ is equal
to the Catalan–Hankel determinant $C_{n}^{(k)}$.

Finally we recall that the generalized Fuss–Catalan number
$F_{n+1}^{(p+1)}(b)$ counts the number of lattice paths from $(0,0)$ to
$(b+np,n)$ that do not go above the line $x=py$, see, e.g., [81].

######  Comments 5.44.

It is well-known, see, e.g., [122] or [134, Vol. 2, Exercise 7.101.b], that
the number $D(n,k,b,p)$ is equal to the total number $pp^{\lambda_{n,p,b}}(k)$
of plane partitions555555Let $\lambda$ be a partition. A plane (ordinary)
partition bounded by $d$ and shape $\lambda$ is a filling of the shape
$\lambda$ by the numbers from the set $\\{0,1,\ldots,d\\}$ in such a way that
the numbers along columns and rows are weakly decreasing. A reverse plane
partition bounded by $d$ and shape $\lambda$ is a filling of the shape
$\lambda$ by the numbers from the set $\\{0,1,\ldots,d\\}$ in such a way that
the numbers along columns and rows are weakly increasing. bounded by $k$ and
contained in the shape $\lambda_{n,b,p}$.

More generally, see, e.g., [44], for any partition $\lambda$ denote by
$w_{\lambda}\in\mathfrak{S}_{\infty}$ a unique dominant permutation of shape
$\lambda$, that is a unique permutation with the code $c(w)=\lambda$. Now for
any non-negative integer $k$ consider the so-called shifted dominant
permutation $w_{\lambda}^{(k)}$ which has the shape $\lambda$ and the flag
$\phi=(\phi_{i}=k+i-1,\,i=1,\ldots,\ell(\lambda))$. Then

$\displaystyle{\mathfrak{S}}_{w_{\lambda}^{(k)}}(1)=pp^{\lambda}(\leq k),$

where $pp^{\lambda}(\leq k)$ denotes the number of all plane partitions
bounded by $k$ and contained in $\lambda$. Moreover,

$\displaystyle\sum_{\pi\in PP^{\lambda}(\leq
k)}q^{|\pi|}=q^{n(\lambda)}{\mathfrak{S}}_{w_{\lambda}^{(k)}}\big{(}1,q^{-1},q^{-2},\ldots\big{)},$

where $PP^{\lambda}(\leq k)$ denotes the set of all plane partitions bounded
by $k$ and contained in $\lambda$.

######  Exercises 5.45.

$(1)$ Show that

$\displaystyle\lim_{k\rightarrow\infty}~{}{\mathfrak{S}}_{w_{\lambda}^{(k)}}\big{(}1,q,q^{2},\ldots\big{)}=\frac{q^{n(\lambda)}}{H_{\lambda}(q)},$

where $H_{\lambda}(q)=\prod\limits_{x\in\lambda}(1-q^{h(x)})$ denotes the hook
polynomial corresponding to a given partition $\lambda$.

$(2)$ Let $\lambda=((n+\ell)^{\ell},\ell^{n})$ be a fat hook. Show that

$\displaystyle\lim_{k\rightarrow\infty}q^{n(\lambda)}{\mathfrak{S}}_{w_{\lambda}^{(k)}}\big{(}1,q^{-1},q^{-2},\ldots\big{)}=q^{s(\ell,n)}\frac{K_{\lambda}(q)}{M_{\ell}(2n+2\ell-1;q)},$

where $a(\ell,n)$ is a certain integer we don’t need to specify in what
follows,

$\displaystyle
M_{\ell}(N;q)=\prod_{j=1}^{N}\left(\frac{1}{1-q^{j}}\right)^{\min(j,N+1-j,\ell)}$

denotes the MacMahon generating function for the number of plane partitions
fit inside the box $N\times N\times\ell$, $K_{\lambda}(q)$ is a polynomial in
$q$ such that $K_{\lambda}(0)=1$.

$(a)$ Show that

$\displaystyle(1-q)^{|\lambda|}\frac{K_{\lambda}(q)}{M_{\ell}(2n+2\ell-1;q)}\bigg{|}_{q=1}={1\over\prod\limits_{x\in\lambda}h(x)}.$

$(b)$ Show that

$\displaystyle K_{\lambda}(q)\in\mathbb{N}[q]\qquad\text{and}\qquad
K_{\lambda}(1)=M(n,n,\ell),$

where $M(a,b,c)$ denotes the number of plane partitions fit inside the box
$a\times b\times c$. It is well-known, see, e.g., [93, p. 81], that

$\displaystyle M(a,b,c)=\prod_{\begin{subarray}{c}1\leq i\leq a\\\ 1\leq j\leq
b\\\ 1\leq k\leq
c\end{subarray}}\frac{i+j+k-1}{i+j+k-2}=\prod_{i=1}^{c}\frac{(a+b+i-1)!(i-1)!}{(a+i-1)!(b+1-1)!}=\dim
V_{(a^{c})}^{{\mathfrak{gl}}_{b+c}}.$

Show that

$\displaystyle K_{\lambda}(q)=\sum_{\pi\in B_{n,n,\ell}}q^{wt_{\ell}(\pi)},$

where the sum runs over the set of plane partitions $\pi=(\pi_{ij})_{1\leq
i,j\leq n}$ fit inside the box $B_{n,n,\ell}:=n\times n\times\ell$, and

$\displaystyle wt_{\ell}(\pi)=\sum_{i,j}\pi_{ij}+\ell\sum_{i}\pi_{ii}.$

$(c)$ Assume as before that $\lambda:=((n+\ell)^{\ell},\ell^{n})$. Show that

$\displaystyle\lim_{n\rightarrow\infty}K_{\lambda}(q)=M_{\ell}(q)\sum_{\mu\atop\ell(\mu)\leq\ell}q^{|\mu|}\left(\frac{q^{n(\mu)}}{\prod_{x\in\mu}(1-q^{h(x)})}\right)^{2},$

where the sum runs over the set of partitions $\mu$ with the number of parts
at most $\ell$, and $n(\mu)=\sum_{i}(i-1)\mu_{i}$,

$\displaystyle M_{\ell}(q):=\prod_{j\geq
1}\big{(}1-q^{j}\big{)}^{\min(j,\ell)}.$

Therefore the generating function $PP^{(\ell,0)}(q):=\sum\limits_{\pi\in
PP^{(\ell,0)}}q^{|\pi|}$ is equal to

$\displaystyle\sum_{\mu\atop\ell(\mu)\leq\ell}q^{|\mu|}\left(\frac{q^{n(\mu)}}{\prod\limits_{x\in\mu}(1-q^{h(x)})}\right)^{2},$

where $PP^{(\ell,k)}:=\\{\pi=(\pi_{ij})_{i,j\geq 1}\,|\,\pi_{ij}\geq
0,\pi_{\ell+1,\ell+1}\leq k\\}$, $|\pi|=\sum\limits_{i,j}\pi_{ij}$.

$(d)$ Show that

$\displaystyle
PP^{(\ell,0)}(q)=\frac{1}{M_{\ell}(q)^{2}}\sum_{\mu,\atop\ell(\mu)\leq\ell}(-q)^{|\mu|}q^{n(\mu)+n(\mu^{\prime})}\big{(}\dim_{q}V_{\mu}^{{\mathfrak{gl}}(\ell)}\big{)}^{2},$

where $\mu^{\prime}$ denotes the conjugate partition of $\mu$, therefore
$n(\mu^{\prime})=\sum\limits_{i\geq 1}{\mu_{i}\choose 2}$.

The formula (5.10) is the special case $n=m$ of [109, Theorem 1.2]. In
particular, if $\ell=1$ then one come to following identity

$\displaystyle\frac{1}{(q;q)_{\infty}^{2}}\sum_{k\geq 0}(-1)^{k}q^{{k+1\choose
2}}=\sum_{k\geq 0}q^{k}\left(\frac{1}{(q;q)_{k}}\right)^{2}.$

$(e)$ Let $k\geq 0$, $\ell\geq 1$ be integers. Show that the (fermionic)
generating function for the number of plane partitions $\pi=(\pi_{ij})\in
PP^{(\ell,k)}$ is equal to

$\displaystyle\sum_{\pi\in
PP^{(\ell,k)}}q^{|\pi|}=\sum_{\mu\atop\mu_{\ell+1}\leq
k}q^{|\mu|}\left(\frac{q^{n(\mu)}}{\prod\limits_{x\in\mu}(1-q^{h(x)})}\right)^{2}.$

$(B)$ The case $k=0$.

  1. (1)

$D(n,0,1,p,b)=1$ for all nonnegative $n$, $p$, $b$.

  2. (2)

$D(n,0,2,2,2)={\rm VSASM}(n)$, i.e., the number of alternating sign
$(2n+1)\times(2n+1)$ matrices symmetric about the vertical axis, see, e.g.,
[131, $A005156$].

  3. $(3)$

$D(n,0,2,1,2)={\rm CSTCPP}(n)$, i.e., the number of cyclically symmetric
transpose complement plane partitions, see, e.g., [131, $A051255$].

######  Theorem 5.46.

Let $\varpi_{n,k,p}$ be a unique vexillary permutation of the shape
$\lambda_{n.p}:=(n,n-1,\ldots,2,1)p$ and flag
$\phi_{n,k}:=(k+1,k+2,\ldots,k+n-1,k+n)$. Then

$\displaystyle\mathfrak{G}_{\varpi_{n,1,p}}^{(\beta-1)}(1)=\sum_{j=1}^{n+1}{1\over
n+1}{n+1\choose j}{(n+1)p\choose j-1}\beta^{j-1}.$

If $k\geq 2$, then
$G_{n,k,p}(\beta):=\mathfrak{G}_{\varpi_{n,k,p}}^{(\beta-1)}(1)$ is a
polynomial of degree $nk$ in $\beta$, and

$\displaystyle{\rm Coef\/f}_{[\beta^{nk}]}(G_{n,k,p}(\beta))=D(n,k,1,p-1,0).$

The polynomial

$\displaystyle\sum_{j=1}^{n}{1\over n}{n\choose j}{pn\choose
j-1}t^{j-1}:=\mathfrak{FN}_{n}(t)$

is known as the Fuss–Narayana polynomial and can be considered as a
$t$-deformation of the Fuss–Catalan number ${\rm FC}_{n}^{p}(0)$.

Recall that the number ${1\over n}{n\choose j}{pn\choose j-1}$ counts paths
from $(0,0)$ to $(np,0)$ in the first quadrant, consisting of steps $U=(1,1)$
and $D=(1,-p)$ and have $j$ peaks (i.e., $UD$’s), cf. [131, $A108767$].

For example, take $n=3$, $k=2$, $p=3$, $r=1$, $b=0$. Then

$\displaystyle\varpi_{3,2,3}=[1,2,12,9,6,3,4,5,7,8,10,11]\in\mathbb{S}_{12},$
$\displaystyle G_{3,2,3}(\beta)=(1,18,171,747,1767,1995,1001).$

Therefore,

$\displaystyle G_{3,2,3}(1)=5700=D(3,2,3,0)\qquad\text{and}\qquad{\rm
Coef\/f}_{[\beta^{6}]}(G_{3,2,3}(\beta))=1001=D(3,2,2,0).$

######  Proposition 5.47 ([110]).

The value of the Fuss–Catalan polynomial at $t=2$, that is the number

$\displaystyle\sum_{j=1}^{n}{1\over n}{n\choose j}{pn\choose j-1}2^{j-1}$

is equal to the number of hyperplactic classes of $p$-parking functions of
length $n$, see [110] for definition of $p$-parking functions, its properties
and connections with some combinatorial Hopf algebras.

Therefore, the value of the Grothendieck polynomial
$\mathfrak{G}_{\varpi_{n,1,p}}^{(\beta=1)}(1)$ at $\beta=1$ and $x_{i}=1$,
$\forall\,i$, is equal to the number of $p$-parking functions of length $n+1$.
It is an open problem to find combinatorial interpretations of the polynomials
$\mathfrak{G}_{\varpi_{n,k,p}}^{(\beta)}(1)$ in the case $k\geq 2$. Note
finally, that in the case $p=2,~{}k=1$ the values of the Fuss–Catalan
polynomials at $t=2$ one can find in [131, $A034015$].

######  Comments 5.48.

$(\Longrightarrow)$ The case $r=0$. It follows from Theorem 5.32 that in the
case $r=0$ and $k\geq n$, one has

$\displaystyle D(n,k,0,p,b)=\dim
V_{\lambda_{n,p,b}}^{\mathfrak{gl}(k+1)}=(1+p)^{{n+1\choose
2}}\prod_{j=1}^{n+1}{{(n-j+1)p+b+k-j+1\choose
k-j+1}\over{(n-j+1)(p+1)+b\choose n-j+1}}.$

Now consider the conjugate
$\nu:=\nu_{n,p,b}:=((n+1)^{b},n^{p},(n-1)^{p},\ldots,1^{p})$ of the partition
$\lambda_{n,p,b}$, and a rectangular shape partition
$\psi=(\underbrace{k,\ldots,k}_{np+b})$. If $k\geq np+b$, then there exists a
unique grassmannian permutation $\sigma:=\sigma_{n,k,p,b}$ of the shape $\nu$
and the flag $\psi$ [92]. It is easy to see from the above formula for
$D(n,k,0,p,b)$, that

$\displaystyle\mathfrak{S}_{\sigma_{n,k,p,b}}(1)=\dim
V_{\nu_{n,p,b}}^{\mathfrak{gl}(k-1)}$
$\displaystyle\hphantom{\mathfrak{S}_{\sigma_{n,k,p,b}}(1)}{}=(1+p)^{{n\choose
2}}{k+n-1\choose
b}\prod_{j=1}^{n}{(p+1)(n-j+1)\over(n-j+1)(p+1)+b}\prod_{j=1}^{n}{{k+j-2\choose(n-j+1)p+b}\over{(n-j+1)(p+1)+b-1\choose
n-j}}.$

After the substitution $k:=np+b+1$ in the above formula we will have

$\displaystyle\mathfrak{S}_{\sigma_{n,np+b+1,p,b}}(1)=(1+p)^{{n\choose
2}}\prod_{j=1}^{n}{{{np+b+j-1\choose(n-j+1)p}}\over{{j(p+1)-1\choose j-1}}}.$

In the case $b=0$ some simplifications are happened, namely,

$\displaystyle\mathfrak{S}_{\sigma_{n,k,p,0}}(1)=(1+p)^{{n\choose
2}}\prod_{j=1}^{n}{{k+j-2\choose(n-j+1)p}\over{(n-j+1)p+n-j\choose n-j}}.$

Finally we observe that if $k=np+1$, then

$\displaystyle\prod_{j=1}^{n}{{{np+j-1\choose(n-j+1)p}}\over{{(n-j+1)p+n-j\choose
n-j}}}={\prod_{j=2}^{n}{{np+j-1\choose(p+1)(j-1)}\over{j(p+1)-1\choose
j-1}}=\prod_{j=1}^{n-1}{j!(n(p+1)-j-1)!\over((n-j)(p+1))!((n-j)(p+1)-1)!}}:=A_{n}^{(p)},$

where the numbers $A_{n}^{(p)}$ are integers that generalize the numbers of
alternating sign matrices (ASM) of size $n\times n$, recovered in the case
$p=2$, see [33, 111] for details.

######  Examples 5.49.

$(1)$ Let us consider polynomials
$\mathfrak{G}_{n}(\beta):=\mathfrak{G}_{{\sigma_{n,2n,2,0}}}^{(\beta-1)}(1)$.

If $n=2$, then

$\displaystyle\sigma_{2,4,2,0}=235614\in\mathbb{S}_{6},\qquad\mathfrak{G}_{2}(\beta)=(1,2,{\bf
3}):=1+2\beta+{\bf 3}\beta^{2}.$

Moreover,

$\displaystyle\mathfrak{R}_{\sigma_{2,4,2,0}}(q;\beta)=(1,{\bf
2})_{\beta}+{\bf 3}q\beta^{2}.$

If $n=3$, then

$\displaystyle\sigma_{3,6,2,0}=235689147\in\mathbb{S}_{9},\qquad\mathfrak{G}_{3}(\beta)=(1,6,21,36,51,48,{\bf
26}).$

Moreover,

$\displaystyle\mathfrak{R}_{\sigma_{3,6,2,0}}(q;\beta)=(1,6,11,16,{\bf
11})_{\beta}+q\beta^{2}(10,20,35,34)_{\beta}+q^{2}\beta^{4}(5,14,{\bf
26})_{\beta},$
$\displaystyle\mathfrak{R}_{\sigma_{3,6,2,0}}(q;1)=(45,99,45)_{q}.$

If $n=4$, then

$\displaystyle\sigma_{4,8,2,0}=[2,3,5,6,8,9,11,12,1,4,7,10]\in\mathbb{S}_{12},$
$\displaystyle\mathfrak{G}_{4}(\beta)=(1,12,78,308,903,2016,3528,4944,5886,5696,4320,2280,{\bf
646}).$

Moreover,

$\displaystyle\mathfrak{R}_{\sigma_{4,8,2,0}}(q;\beta)=(1,12,57,182,392,602,763,730,493,{\bf
170})_{\beta}$
$\displaystyle\hphantom{\mathfrak{R}_{\sigma_{4,8,2,0}}(q;\beta)=}{}+q\beta^{2}(21,126,476,1190,1925,2626,2713,2026,804)_{\beta}$
$\displaystyle\hphantom{\mathfrak{R}_{\sigma_{4,8,2,0}}(q;\beta)=}{}+q^{2}\beta^{4}(35,224,833,1534,2446,2974,2607,1254)_{\beta}$
$\displaystyle\hphantom{\mathfrak{R}_{\sigma_{4,8,2,0}}(q;\beta)=}{}+q^{3}\beta^{6}(7,54,234,526,909,1026,{\bf
646})_{\beta},$
$\displaystyle\mathfrak{R}_{\sigma_{4,8,2,0}}(q;1)=(3402,11907,11907,3402)_{q}=1701~{}(2,7,7,2)_{q}.$

$\bullet$ If $n=5$, then

$\displaystyle\sigma_{5,10,2}=[2,3,5,6,8,9,11,12,14,15,1,4,7,10,13]\in\mathbb{S}_{15},$
$\displaystyle\mathfrak{G}_{5}(\beta)=(1,20,210,1420,7085,27636,87430,230240,516375,997790,1676587,2466840,$
$\displaystyle\hphantom{\mathfrak{G}_{5}(\beta)=(}{}3204065,3695650,3778095,3371612,2569795,1610910,782175,262200,{\bf
45885}).$

Moreover,

$\displaystyle\mathfrak{R}_{\sigma_{5,10,2,0}}(q;\beta)=(1,20,174,988,4025,12516,31402,64760,111510,162170,$
$\displaystyle\hphantom{\mathfrak{R}_{\sigma_{5,10,2,0}}(q;\beta)=(}{}202957,220200,202493,153106,89355,35972,{\bf
7429})_{\beta}$
$\displaystyle\hphantom{\mathfrak{R}_{\sigma_{5,10,2,0}}(q;\beta)=}{}+q\beta^{2}(36,432,2934,13608,45990,123516,269703,487908,738927,$
$\displaystyle\hphantom{\mathfrak{R}_{\sigma_{5,10,2,0}}(q;\beta)=(}{}956430,1076265,1028808,813177,499374,213597,47538)_{\beta}$
$\displaystyle\hphantom{\mathfrak{R}_{\sigma_{5,10,2,0}}(q;\beta)=}{}+q^{2}\beta^{4}(126,1512,9954,40860,127359,314172,627831,1029726,1421253,$
$\displaystyle\hphantom{\mathfrak{R}_{\sigma_{5,10,2,0}}(q;\beta)=(}{}1711728,1753893,1492974,991809,461322,112860)_{\beta}$
$\displaystyle\hphantom{\mathfrak{R}_{\sigma_{5,10,2,0}}(q;\beta)=}{}+q^{3}\beta^{6}(84,1104,7794,33408,105840,255492,486324,753984,1019538,$
$\displaystyle\hphantom{\mathfrak{R}_{\sigma_{5,10,2,0}}(q;\beta)=(}{}1169520,1112340,825930,428895,117990)_{\beta}$
$\displaystyle\hphantom{\mathfrak{R}_{\sigma_{5,10,2,0}}(q;\beta)=}{}+q^{4}\beta^{8}(9,132,1032,4992,17730,48024,102132,173772,244620,276120,$
$\displaystyle\hphantom{\mathfrak{R}_{\sigma_{5,10,2,0}}(q;\beta)=(}{}240420,144210,{\bf
45885})_{\beta},$
$\displaystyle\mathfrak{R}_{\sigma_{5,10,2,0}}(q;1)=(1299078,6318243,10097379,6318243,1299078)_{q}$
$\displaystyle\hphantom{\mathfrak{R}_{\sigma_{5,10,2,0}}(q;1)}{}=59049(22,107,171,107,22)_{q}.$

We are reminded that over the paper we have used the notation

$\displaystyle(a_{0},a_{1},\ldots,a_{r})_{\beta}:=\sum\limits_{j=0}^{r}a_{j}\beta^{j},$

etc.

One can show that $\deg_{[\beta]}\mathfrak{G}_{n}(\beta)=n(n-1)$,
$\deg_{[q]}\mathfrak{R}_{\sigma_{n,2n,2,0}}(q,1)=n-1$, and looking on the
numbers $3$, $26$, $646$, $45885$ we made

######  Conjecture 5.50.

Let $a(n):={\rm Coef\/f}[\beta^{n(n-1)}]~{}(\mathfrak{G}_{n}(\beta))$. Then

$\displaystyle a(n)={\rm VSASM}(n)={\rm
OSASM}(n)=\prod_{j=1}^{n-1}{(3j+2)(6j+3)!(2j+1)!\over(4j+2)!(4j+3)!},$

where ${\rm VSASM}(n)$ is the number of alternating sign $(2n+1)\times(2n+1)$
matrices symmetric about the vertical axis, ${\rm OSASM}(n)$ is the number of
$2n\times 2n$ off-diagonal symmetric alternating sign matrices. See [131,
$A005156$], [111] and references therein, for details.

######  Conjecture 5.51.

Polynomial $\mathfrak{R}_{\sigma_{n,2n,2,0}}(q;1)$ is symmetric and

$\displaystyle\mathfrak{R}_{\sigma_{n,2n,2,0}}(0;1)=A20342(2n-1),$

see [131].

$(2)$ Let us consider polynomials
$\mathfrak{F}_{n}(\beta):=\mathfrak{G}_{{\sigma_{n,2n+1,2,0}}}^{(\beta-1)}(1)$.

If $n=1$, then

$\displaystyle\sigma_{1,3,2,0}=1342\in\mathbb{S}_{4},\qquad\mathfrak{F}_{2}(\beta)=(1,{\bf
2}):=1+{\bf 2}\beta.$

If $n=2$, then

$\displaystyle\sigma_{2,5,2,0}=1346725\in\mathbb{S}_{7},\qquad\mathfrak{F}_{3}(\beta)=(1,6,11,16,{\bf
11}).$

Moreover,

$\displaystyle\mathfrak{R}_{\sigma_{2,5,2,0}}(q;\beta)=(1,2,{\bf
3})_{\beta}+q\beta(4,8,12)_{\beta}+q^{2}\beta^{3}(4,{\bf 11})_{\beta}.$

If $n=3$, then

$\displaystyle\sigma_{3,7,2,0}=[1,3,4,6,7,9,10,2,5,8]\in\mathbb{S}_{10},$
$\displaystyle\mathfrak{F}_{4}(\beta)=(1,12,57,182,392,602,763,730,493,{\bf
170}).$

Moreover,

$\displaystyle\mathfrak{R}_{\sigma_{3,7,2,0}}(q;\beta)=(1,6,21,36,51,48,{\bf
26})_{\beta}+q\beta(6,36,126,216,306,288,156)_{\beta}$
$\displaystyle\hphantom{\mathfrak{R}_{\sigma_{3,7,2,0}}(q;\beta)=}{}+q^{2}\beta^{3}(20,125,242,403,460,289)_{\beta}+q^{3}\beta^{5}(6,46,114,204,{\bf
170})_{\beta},$
$\displaystyle\mathfrak{R}_{\sigma_{3,7,2,0}}(q;1)=(189,1134,1539,540)_{q}=27(7,42,57,20)_{q}.$

If $n=4$, then

$\displaystyle\sigma_{4,9,2,0}=[1,3,4,6,7,9,10,12,13,2,5,8,11]\in\mathbb{S}_{13},$
$\displaystyle\mathfrak{F}_{5}(\beta)=(1,20,174,988,4025,12516,31402,64760,111510,162170,202957,$
$\displaystyle\hphantom{\mathfrak{F}_{5}(\beta)=(}{}220200,202493,153106,89355,35972,{\bf
7429}).$

Moreover,

$\displaystyle\mathfrak{R}_{\sigma_{4,9,2,0}}(q;\beta)=(1,12,78,308,903,2016,3528,4944,5886,5696,4320,2280,{\bf
646})_{\beta}$
$\displaystyle\hphantom{\mathfrak{R}_{\sigma_{4,9,2,0}}(q;\beta)=}{}+q\beta(8,96,624,2464,7224,16128,28224,39552,47088,45568,$
$\displaystyle\hphantom{\mathfrak{R}_{\sigma_{4,9,2,0}}(q;\beta)=(}{}34560,18240,5168)_{\beta}$
$\displaystyle\hphantom{\mathfrak{R}_{\sigma_{4,9,2,0}}(q;\beta)=}{}+q^{2}\beta^{3}(56,658,3220,11018,27848,53135,78902,100109,103436,$
$\displaystyle\hphantom{\mathfrak{R}_{\sigma_{4,9,2,0}}(q;\beta)=(}{}84201,47830,14467)_{\beta}$
$\displaystyle\hphantom{\mathfrak{R}_{\sigma_{4,9,2,0}}(q;\beta)=}{}+q^{3}\beta^{5}(56,728,3736,12820,29788,50236,72652,85444,78868,$
$\displaystyle\hphantom{\mathfrak{R}_{\sigma_{4,9,2,0}}(q;\beta)=(}{}50876,17204)_{\beta}$
$\displaystyle\hphantom{\mathfrak{R}_{\sigma_{4,9,2,0}}(q;\beta)=}{}+q^{4}\beta^{7}(8,117,696,2724,7272,13962,21240,24012,18768,{\bf
7429})_{\beta},$
$\displaystyle\mathfrak{R}_{\sigma_{4,9,2,0}}(q;1)=(30618,244944,524880,402408,96228)_{q}=4374(7,56,120,92,22)_{q}.$

One can show that $\mathfrak{F}_{n}(\beta)$ is a polynomial in $\beta$ of
degree $n^{2}$, and looking on the numbers $2$, $11$, $170$, $7429$ we made

######  Conjecture 5.52.

Let $b(n):={\rm Coef\/f}_{[\beta^{(n-1)^{2}}]}(\mathfrak{F}_{n}(\beta))$. Then
$b(n)={\rm CSTCPP}(n)$. In other words, $b(n)$ is equal to the number of
cyclically symmetric transpose complement plane partitions in an $2n\times
2n\times 2n$ box. This number is known to be

$\displaystyle\prod_{j}^{n-1}{{(3j+1)(6j)!(2j)!\over(4j+1)!(4j)!}},$

see [131, $A051255$], [18, p. 199].

It ease to see that polynomial $\mathfrak{R}_{\sigma_{n,2n+1,2,0}}(q;1)$ has
degree $n$.

######  Conjecture 5.53.

$\displaystyle{\rm
Coef\/f}_{[\beta^{n}]}\big{(}\mathfrak{R}_{\sigma_{n,2n+1,2,0}}(q;1)\big{)}=A20342(2n),$

see [131];

$\displaystyle\mathfrak{R}_{\sigma_{n,2n+1,2,0}}(0;1)=A_{\rm
QT}^{(1)}(4n;3)=3^{n(n-1)/2}{\rm ASM}(n),$

see [83, Theorem 5] or [131, $A059491$].

######  Proposition 5.54.

One has

$\displaystyle\mathfrak{R}_{\sigma_{4,2n+1,2,0}}(0;\beta)=\mathfrak{G}_{n}(\beta)=\mathfrak{G}_{\sigma_{n,2n,2,0}}^{(\beta-1)}(1),\qquad\mathfrak{R}_{\sigma_{n,2n,2,0}}(0,\beta)=\mathfrak{F}_{n}(\beta)=\mathfrak{G}_{\sigma_{n,2n+1,2,0}}^{(\beta-1)}(1).$

Finally we define $(\beta,q)$-deformations of the numbers ${\rm VSASM}(n)$ and
${\rm CSCTPP}(n)$. To accomplish these ends, let us consider permutations

$\displaystyle w_{k}^{-}=(2,4,\ldots,2k,2k-1,2k-3,\ldots,3,1),$ $\displaystyle
w_{k}^{+}=(2,4,\ldots,2k,2k+1,2k-1,\ldots,3,1).$

######  Proposition 5.55.

One has

$\displaystyle\mathfrak{S}_{{w_{k}^{-}}}(1)={\rm
VSAM}(k),\qquad\mathfrak{S}_{{w_{k}^{+}}}(1)={\rm CSTCPP}(k).$

Therefore the polynomials
$\mathfrak{G}_{{w_{k}^{-}}}^{(\beta-1)}(x_{1}=q,\,x_{j}=1,\,\forall\,j\geq 2)$
and $\mathfrak{G}_{{w_{k}^{+}}}^{(\beta-1)}(x_{1}=q,\,x_{j}=1$,
$\forall\,j\geq 2)$ define $(\beta,q)$-deformations of the numbers ${\rm
VSAM}(k)$ and ${\rm CSTCPP}(k)$ respectively. Note that the inverse
permutations

$\displaystyle(w_{k}^{-})^{-1}=(\underbrace{2k,1},\ldots,\underbrace{2k+1-i,i},\ldots,\underbrace{k+1,k}),$
$\displaystyle(w_{k}^{+})^{-1}=(\underbrace{2k+1,1},\ldots,\underbrace{2k+2-j,j},\ldots,\underbrace{k+2,k},k+1)$

also define a $(\beta,q)$-deformation of the numbers considered above.

######  Problem 5.56.

It is well-known, see, e.g., [37, p. 43], that the set ${\cal{VSASM}}(n)$ of
alternating sign $(2n+1)\times(2n+1)$ matrices symmetric about the vertical
axis has the same cardinality as the set ${\rm SYT}_{2}(\lambda(n),\leq n)$ of
semistandard Young tableaux of the shape $\lambda(n):=(2n-1,2n-3,\ldots,3,1)$
filled by the numbers from the set $\\{1,2,\ldots,n\\}$, and such that the
entries are weakly increasing down the anti-diagonals.

On the other hand, consider the set ${\cal{CS}}(w_{k}^{-})$ of compatible
sequences, see, e.g., [13, 42], corresponding to the permutation
$w_{k}^{-}\in{\mathbb{S}}_{2k}$.

######  Challenge 5.57.

Construct bijections between the sets ${\cal{CS}}(w_{k}^{-})$, ${\rm
SYT}_{2}(\lambda(k),\leq k)$ and${\cal{VSASM}}(k)$.

######  Remark 5.58.

One can compute the principal specialization of the Schubert polynomial
corresponding to the transposition $t_{k,n}:=(k,n-k)\in\mathbb{S}_{n}$ that
interchanges $k$ and $n-k$, and fixes all other elements of $[1,n]$.

######  Proposition 5.59.

$\displaystyle
q^{(n-1)(k-1)}\mathfrak{S}_{t_{k,n-k}}\big{(}1,q^{-1},q^{-2},q^{-3},\ldots\big{)}$
$\displaystyle\qquad{}=\sum_{j=1}^{k}(-1)^{j-1}q^{{j\choose 2}}{n-1\brack
k-j}_{q}~{}{n-2+j\brack k+j-1}_{q}=\sum_{j=1}^{n-2}q^{j}\left({j+k-2\brack
k-1}_{q}\right)^{2}.$

######  Exercises 5.60.

(1) Show that if $k\geq 1$, then

$\displaystyle{\rm
Coef\/f}_{[q^{k}\beta^{2k}]}({\mathfrak{R}}_{{\sigma_{n,2n,2,0}}}(q;t))={2n-1\choose
2k},$ $\displaystyle{\rm
Coef\/f}_{[q^{k}\beta^{2k-1}]}({\mathfrak{R}}_{{\sigma_{n,2n+1,2,0}}}(q;t))={2n\choose
2k-1}.$

(2) Let $n\geq 1$ be a positive integer, consider “zig-zag” permutation

$\displaystyle w=\begin{pmatrix}1&2&3&4&\ldots&2k+1&2k+2&\ldots&{2n-1}&2n\\\
2&1&4&3&\ldots&{2k+2}&{2k+1}&\ldots&2n&{2n-1}\end{pmatrix}\in\mathbb{S}_{2n}.$

Show that

$\displaystyle\mathfrak{R}_{w}(q,\beta)=\prod_{k=0}^{n-1}\left({1-\beta^{2k}\over
1-\beta}+q\beta^{2k}\right).$

(3) Let $\sigma_{k,n,m}$ be grassmannian permutation with shape
$\lambda=(n^{m})$ and flag $\phi=(k+1)^{m}$, i.e.,

$\displaystyle\sigma_{k,n,m}=\begin{pmatrix}1&2&\ldots&k&{k+1}&\ldots&{k+n}&{k+n+1}&\ldots&{k+n+m}\\\
1&2&\ldots&k&{k+m+1}&\ldots&{k+m+n}&{k+1}&\ldots&{k+m}\end{pmatrix}.$

Clearly $\sigma_{k+1,n,m}=1\times\sigma_{k,n,m}$.

Show that the coefficient ${\rm
Coef\/f}_{\beta^{m}}(\mathfrak{R}_{\sigma_{k,n,m}}(1,\beta))$ is equal to the
Narayana number $N(k+n+m,k)$.

(4) Consider permutation $w:=w^{(n)}=(w_{1},\ldots,w_{2n+1})$, where
$w_{2k-1}=2k+1$ for $k=1,\ldots,n$, $w_{2n+1}=2n$, $w_{2}=1$ and $w_{2k}=2k-2$
for $k=2,\ldots,n$. For example, $w^{(3)}=(3152746)$. We set $w^{(0)}=1$. Show
that the polynomial ${\mathfrak{S}}_{w}^{(\beta)}(x_{i}=1,\forall i)$ has
degree $n(n-1)$ and the coefficient ${\rm
Coef\/f}_{\beta^{n(n-1)}}({\mathfrak{S}}_{w}^{(\beta)}(x_{i}=1,\,\forall\,i))$
is equal to the $n$-th Catalan number $C_{n}$.

Note that the specialization
${\mathfrak{S}}_{w}^{(\beta)}(x_{i}=1)|_{\beta=1}$ is equal to the $2n$-th
Euler (or up/down) number, see [131, $A000111$].

More generally, consider permutation $w^{(n)}_{k}:=1^{k}\times
w^{(n)}\in{\mathbb{S}}_{k+2n+1}$, and polynomials

$\displaystyle P_{k}(z)=\sum_{j\geq
0}(-1)^{j}{\mathfrak{S}}_{w^{(j)}_{k-2j}}(x_{i}=1)z^{k-2j},\qquad k\geq 0.$

Show that

$\displaystyle\sum_{k\geq 0}P_{k}(z){t^{k}\over
k!}=\exp(tz)\operatorname{sech}(t).$

The polynomials $P_{k}(z)$ are well-known as Swiss–Knife polynomials, see
[131, $A153641$], where one can find an overview of some properties of the
Swiss–Knife polynomials.

(5) Assume that $n=2k+3$, $k\geq 1$, and consider permutation
$v_{n}=(v_{1},\ldots,v_{n})\in\mathbb{S}_{n}$, where $v_{2a+1}=2a+3$,
$a=0,\ldots,n-1$, $w_{2}=1$ and $w_{2a}=2a-2$, $a=2,\ldots,k+1$. For example,
$v_{4}=[31527496,11,8,10]$ and ${\mathfrak{S}}_{v_{4}}(1)=50521=E_{10}$.

Show that

$\displaystyle{\mathfrak{S}}_{v_{n}}(q,\,x_{i}=1,\,\forall\,i\geq
2)=(n-2)E_{n-3}q^{2}+\cdots+2^{k-1}(k-1)!q^{k+2},$
$\displaystyle{\mathfrak{S}}_{v_{n}}(x_{i}=1,\,\forall\,i\geq 1)=E_{n-1}.$

Set $\beta=d-1$, consider polynomials
${\cal{E}}_{n}(q,d)={\mathfrak{G}}_{v_{n}}^{(\beta)}(x_{1}=q,\,x_{i}=1,\,\forall\,i\geq
2)$. Clearly, see the latter formula, ${\cal{E}}_{n}(1,1)=E_{n-1}$. Give a
combinatorial prove that ${\cal{E}}_{n}(q,d)\in\mathbb{N}[q,d]$, that is to
give combinatorial interpretation(s) of coefficients of the polynomial
${\cal{E}}_{n}(q,d)$.

Show that $\deg_{d}{\cal{E}}_{n}(1,d)=n(n+1)$ and the leading coefficient is
equal to the Catalan number $C_{n+1}$.

(6) Consider permutation $u:=u_{n}=(u_{1},\ldots,u_{2n})\in{\mathbb{S}}_{2n}$,
$n\geq 2$, where $u_{1}=2$, $u_{2k+1}=2k-1$, $k=1,\ldots,n$, $u_{2k}=2k+2$,
$k=1,\ldots,n-1$, $u_{2n}=2n-1$. For example, $u_{4}=(24163857)$.

Now consider polynomial

$\displaystyle R_{n}^{(k)}(q)={\mathfrak{S}}_{1^{k}\times
u_{n}}(x_{1}=q,\,x_{i}=1,\,\forall\,i\geq 2).$

Show that $R_{n}^{(k)}(1)={2n+k-1\choose k}E_{2n-1}$, where $E_{2k-1}$, $k\geq
1$, denotes the Euler number, see [131, $A00111$]. In particular,
$R_{n}^{(1)}(1)=2^{2n-1}G_{n}$, where $G_{n}$ denotes the unsigned Genocchi
number, see [131, $A110501$].

Show that $\deg_{q}R_{n}^{(k)}(q)=n$ and ${\rm
Coef\/f}_{q^{n}}\big{(}R_{n}^{(0)}(q)\big{)}=(2n-3)!!$.

(7) Consider permutation $w_{n}\in\mathbb{S}_{2n+2}$, where $w_{2}=1$,
$w_{4}=2$, and

$\displaystyle w_{2k-1}=2k+2,\quad 1\leq k\leq n,\qquad w_{2k}=2k-3,\quad
3\leq k\leq n,$ $\displaystyle w_{2n+1}=2n-3,\qquad w_{2n+2}=2n-1.$

For example, $w_{5}=[4,1,6,2,8,3,10,5,12,7,9,11]$.

Show that

$\displaystyle{\mathfrak{S}}_{w_{n}}(x_{i}=1,\,\forall\,i)=(2n+1)!!\big{(}2^{2n}-2\big{)}|B_{2n}|,$

where $B_{2n}$ denotes the Bernoulli numbers565656See, e.g.,
https://en.wikipedia.org/wiki/Bernoulli_number..

(8) Consider permutation
$w_{k}:=(2k+1,2k-1,\ldots,3,1,2k,2k-2,\ldots,4,2)\in{\mathbb{S}}_{2k+1}$. Show
that

$\displaystyle{\mathfrak{S}}_{w_{k}}^{(\beta-1)}(x_{1}=q,\,x_{j}=1,\,\forall\,j\geq
2)=q^{2k}(1+\beta)^{{n\choose 2}}.$

(9) Consider permutations
$\sigma_{k}^{+}=(1,3,5,\ldots,2k+1,2k+2,2k,\ldots,4,2)$ and
$\sigma_{k}^{-}=(1,3,5,\ldots$, $2k+1,2k,2k-2,\ldots,4,2)$, and define
polynomials

$\displaystyle
S_{k}^{\pm}(q)={\mathfrak{S}}_{\sigma_{k}^{\pm}}(x_{1}=q,\,x_{j}=1,\,\forall\,j\geq
2).$

Show that

$\displaystyle S_{k}^{+}(0)={\rm VSASM}(k),\qquad S_{k}^{+}(1)={\rm
VSASM}(k+1),$ $\displaystyle{\partial\over\partial
q}S_{k}^{+}(q)|_{q=0}=2kS_{k}^{+}(0),\qquad{\rm
Coef\/f}_{q^{k}}(S_{k}^{+}(q))={\rm CSTCPP}(k+1),$ $\displaystyle
S_{k}^{-}(0)={\rm CSTCPP}(k),\qquad S_{k}^{-}(1)={\rm CSTCPP}(k+1),$
$\displaystyle{\partial\over\partial
q}S_{k}^{-}(q)|_{q=0}=(2k-1)S_{k}^{-}(0),\qquad{\rm
Coef\/f}_{q^{k}}(S_{k}^{-}(q))={\rm VSASM}(k).$

Let’s observe that $\sigma_{k}^{\pm}=1\times\tau_{k-1}^{\pm}$, where
$\tau_{k}^{+}=(2,4,\ldots,2k,2k+1,2k-1,\ldots,3,1)$ and
$\tau_{k}^{-}=(2,4,\ldots,2k,2k-1,2k-3,\ldots,3,1)$. Therefore,

$\displaystyle{\mathfrak{S}}_{\tau_{k}^{\pm}}(x_{1}=q,\,x_{j}=1,\,\forall
j\geq 2)=qS_{k-1}^{\pm}(q).$

Recall that ${\rm CSTCPP}(n)$ denotes the number of cyclically symmetric
transpose compliment plane partitions in a $2n\times 2n$ box, see, e.g., [131,
$A051255$], and ${\rm VSASM}(n)$ denotes the number of alternating sign
$(2n+1)\times(2n+1)$ matrices symmetric the vertical axis, see, e.g., [131,
$A005156$].

It might be well to point out that

$\displaystyle{\mathfrak{S}}_{\sigma_{n-1}^{+}}(x_{1}=x,\,x_{i}=1,\,\forall\,i\geq
2)=G_{2n-1,n-1}(x,y=1),$
$\displaystyle{\mathfrak{S}}_{\sigma_{n}^{-}}(x_{1}=x,\,x_{i}=1,\,\forall\,i\geq
2)=F_{2n,n-1}(x,y=1),$

where (homogeneous) polynomials $G_{m,n}(x,y)$ and $F_{m,n}(x,y)$ are defined
in [123], and related with integral solutions to Pascal’s hexagon relations

$\displaystyle
f_{m-1,n}f_{m+1,n}+f_{m,n-1}f_{m,n+1}=f_{m-1,n-1}f_{m+1,n+1},\qquad(m,n)\in\mathbb{Z}^{2}.$

(10) Consider permutation

$\displaystyle u_{n}=\begin{pmatrix}1&2&\ldots&n&n+1&n+2&n+3&\ldots&2n\\\
2&4&\ldots&2n&1&3&5&\ldots&2n-1\end{pmatrix},$

and set $u_{n}^{(k)}:=1^{2k+1}\times u_{n}$. Show that

$\displaystyle{\mathfrak{G}}_{u_{n}^{(k)}}^{(\beta-1)}(x_{i}=1,\,\forall\,i\geq
1)=(1+\beta)^{{n+1\choose 2}}{\mathfrak{G}}_{1^{k}\times
w_{0}^{(n+1)}}^{((\beta)^{2}-1)}(x_{i}=1,\,\forall\,i\geq 1),$

where $w_{0}^{(n+)}$ denotes the permutation $(n+1,n,n-1,\ldots,2,1)$.

(11) Let $n\geq 0$ be an integer. Consider permutation $u_{n}=1^{n}\times
321\in{\mathbb{S}}_{3+n}$. Show that

$\displaystyle{\mathfrak{S}}_{u_{n}}(x_{1}=t,\,x_{i}=1,\,\forall\,i\geq
2)={\frac{1}{4}}{2n+2\choose 3}+{\frac{n}{2}}{2n+2\choose
1}t+{\frac{1}{2}}{2n+2\choose 1}t^{2}.$

Consider permutation $v_{n}:=1^{n}\times 4321\in{\mathbb{S}}_{n+4}$. Show that

$\displaystyle{\mathfrak{S}}_{v_{n}}(x_{1}=t,\,x_{i}=1,\,\forall\,i\geq 2)$
$\displaystyle\qquad{}={\frac{1}{24}}{2n+4\choose 5}{2n+2\choose
1}+{\frac{1}{2}}{2n+4\choose 5}t+{\frac{n}{4}}{2n+4\choose
3}t^{2}+{\frac{1}{4}}{2n+4\choose 3}t^{3}.$

(12) Show that

$\displaystyle\sum_{(a,b,c)\in(\mathbb{Z}_{\geq 0})^{3}}q^{a+b+c}{a+b\brack
b}_{q}{a+c\brack c}_{q}{b+c\brack
b}_{q}={1\over(q;q)_{\infty}^{3}}\left(\sum_{k\geq 2}(-1)^{k}{k\choose
2}q^{{k\choose 2}-1}\right).$

It is not difficult to see that the left hand side sum of the above identity
counts the weighted number of plane partitions $\pi=(\pi_{ij})$ such that

$\displaystyle\pi_{i,j}\geq
0,\qquad\pi_{ij}\geq\max(\pi_{i+1,j},\pi_{i,j+1}),\qquad\pi_{ij}\leq
1\quad\text{if}\quad i\geq 2\quad\text{and}\quad j\geq 2,$

and the weight $wt(\pi):=\sum\limits_{i,j}\pi_{ij}$.

$(13)$ Let $\lambda=(\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{p}>0)$
be a partition of size $n$. For an integer $k$ such that $1\leq k\leq n-p$
define a grassmannian permutation

$\displaystyle
w_{\lambda}^{(k)}=[1,\ldots,k,\lambda_{p}+k+1,\lambda_{p-1}+k+2,\ldots,\lambda_{1}+k+p,a_{1},\ldots,a_{n-p-k}],$

where we denote by $(a_{1}<a_{2}<\cdots<a_{n-k-p})$ the complement
$[1,n]\backslash(1,\ldots,k,\lambda_{p}+k+1,\lambda_{p-1}+k+2,\ldots,\lambda_{1}+k+p)]$.

Show that the Grothendieck polynomial

$\displaystyle
G_{\lambda}(\beta):={\mathfrak{G}}_{{w_{\lambda}}^{k}}^{\beta-1}(1^{n})$

is a polynomial of $\beta$ with nonnegative coefficients. Clearly,
$G_{\lambda}(1)=\dim V_{\lambda}^{\mathfrak{Gl}(k+\ell(\lambda))}$.

Find a combinatorial interpretations of polynomial $G_{\lambda}(\beta)$.

Final remark, it follows from the seventh exercise listed above, that the
polynomials
${\mathfrak{S}}_{\sigma_{k}^{\pm}}^{(\beta)}(x_{1}=q,\,x_{j}=1,\,\forall\,j\geq
2)$ define a $(q,\beta)$-deformation of the number ${\rm VSASM}(k)$ (the case
$\sigma_{k}^{+}$) and the number ${\rm CSTCPP}(k)$ (the case
$\sigma_{k}^{-}$), respectively.

####  5.2.5 Specialization of Grothendieck polynomials

Let $p$, $b$, $n$ and $i$, $2i<n$ be positive integers. Denote by
${\cal{T}}_{p,b,n}^{(i)}$ the trapezoid, i.e., a convex quadrangle having
vertices at the points

$\displaystyle(ip,i),\quad(ip,n-i),\quad(b+ip,i)\quad\text{and}\quad(b+(n-i)p,n-i).$

######  Definition 5.61.

Denote by ${\rm FC}_{b,p,n}^{(i)}$ the set of lattice path from the point
$(ip,i)$ to that $(b+(n-i)p,n-i)$ with east steps $E=(0,1)$ and north steps
$N=(1,0)$, which are located inside of the trapezoid
${\cal{T}}_{p,b,n}^{(i)}$.

If $\mathfrak{p}\in{\rm FC}_{b,p,n}^{(i)}$ is a path, we denote by
$p(\mathfrak{p})$ the number of peaks, i.e.,

$\displaystyle p(\mathfrak{p})=NE(\mathfrak{p})+E_{\rm
in}(\mathfrak{p})+N_{\rm end}(\mathfrak{p}),$

where $NE(\mathfrak{p})$ is equal to the number of steps $NE$ resting on path
$\mathfrak{p}$; $E_{\rm in}(\mathfrak{p})$ is equal to $1$, if the path
$\mathfrak{p}$ starts with step $E$ and $0$ otherwise; $N_{\rm
end}(\mathfrak{p})$ is equal to $1$, if the path $\mathfrak{p}$ ends by the
step $N$ and $0$ otherwise.

Note that the equality $N_{\rm end}(\mathfrak{p})=1$ may happened only in the
case $b=0$.

######  Definition 5.62.

Denote by ${\rm FC}_{b,p,n}^{(k)}$ the set of $k$-tuples
${\mathfrak{P}}=(\mathfrak{p}_{1},\ldots,\mathfrak{p}_{k})$ of non-crossing
lattice paths, where for each $i=1,\ldots,k$, $\mathfrak{p}_{i}\in{\rm
FC}_{b,p,n}^{(i)}$.

Let

$\displaystyle{\rm FC}^{(k)}_{b,p,n}(\beta):=\sum_{\mathfrak{P}\in{\rm
FC}_{b,p,n}^{(k)}}\beta^{p(\mathfrak{P})}$

denotes the generating function of the statistics
$p(\mathfrak{P}):=\sum\limits_{i=1}^{k}p(\mathfrak{p_{i}})-k$.

######  Theorem 5.63.

The following equality holds

$\displaystyle\mathfrak{G}_{\sigma_{n,k,p,b}}^{(\beta)}(x_{1}=1,x_{2}=1,\ldots)={\rm
FC}_{p,b,n+k}^{(k)}(\beta+1),$

where $\sigma_{n,k,p,b}$ is a unique grassmannian permutation with shape
$((n+1)^{b},n^{p},(n-1)^{p},\ldots,1^{p})$ and flag
$(\underbrace{k,\ldots,k)}_{np+b}$.

###  5.3 The “longest element” and Chan–Robbins–Yuen polytope575757Some
results of this section, e.g., Theorems 5.63 and 5.65, has been proved
independently and in greater generality in [102].

####  5.3.1 The Chan–Robbins–Yuen polytope $\boldsymbol{{\cal{CRY}}_{n}}$

Assume additionally, cf. [133, Exercise 6.C8(d)], that the condition $(a)$ in
Definition 5.1 is replaced by that

  1. $(a^{\prime})$

$x_{ij}$ and $x_{kl}$ commute for all $i$, $j$, $k$ and $l$.

Consider the element $w_{0}^{(n)}:=\prod\limits_{1\leq i<j\leq n}x_{ij}$. Let
us bring the element $w_{0}^{(n)}$ to the reduced form, that is, let us
consecutively apply the defining relations $(a^{\prime})$ and $(b)$ to the
element $w_{0}^{(n)}$ in any order until unable to do so. Denote the resulting
polynomial by $Q_{n}(x_{ij};\alpha,\beta)$. Note that the polynomial itself
depends on the order in which the relations $(a^{\prime})$ and $(b)$ are
applied.

We denote by $Q_{n}(\beta)$ the specialization

$\displaystyle x_{ij}=1\qquad\text{for all $i$ and $j$},$

of the polynomial $Q_{n}(x_{ij};\alpha=0,\beta)$.

######  Example 5.64.

$\displaystyle Q_{3}(\beta)=(2,1)=1+(\beta+1),\qquad
Q_{4}(\beta)=(10,13,4)=1+5(\beta+1)+4(\beta+1)^{2},$ $\displaystyle
Q_{5}(\beta)=(140,336,280,92,9)=1+16(\beta+1)+58(\beta+1)^{2}+56(\beta+1)^{3}+9(\beta+1)^{4},$
$\displaystyle
Q_{6}(\beta)=1+42(\beta+1)+448(\beta+1)^{2}+1674(\beta+1)^{3}+2364(\beta+1)^{4}$
$\displaystyle\hphantom{Q_{6}(\beta)=}{}+1182(\beta+1)^{5}+169(\beta+1)^{6},$
$\displaystyle
Q_{7}(\beta)=(1,99,2569,25587,114005,242415,248817,118587,22924,1156)_{\beta+1},$
$\displaystyle
Q_{8}(\beta)=(1,219,12444,279616,2990335,16804401,52421688,93221276,94803125,$
$\displaystyle\hphantom{Q_{8}(\beta)=(}{}53910939,16163947,2255749,108900)_{\beta+1}.$

What one can say about the polynomial
$Q_{n}(\beta):=Q_{n}(x_{ij};\beta)\arrowvert_{x_{ij}=1,\,\forall\,i,j}$?

It is known, [133, Exercise 6.C8(d)], that the constant term of the polynomial
$Q_{n}(\beta)$ is equal to the product of Catalan numbers
$\prod\limits_{j=1}^{n-1}C_{j}$. It is not difficult to see that if $n\geq 3$,
then ${\rm Coef\/f}_{[\beta+1]}(Q_{n}(\beta))=2^{n}-1-{n+1\choose 2}$, see
[131, $A002662$], for a number of combinatorial interpretations of the numbers
$2^{n}-1-{n+1\choose 2}$.

######  Theorem 5.65.

One has

$\displaystyle Q_{n}(\beta-1)=\left(\sum_{m\geq
0}\iota({\cal{CRY}}_{n+1},m)\beta^{m}\right)(1-\beta)^{{n+1\choose 2}+1},$

where ${\cal{CRY}}_{m}$ denotes the Chan–Robbins–Yuen polytope [20, 21], i.e.,
the convex polytope given by the following conditions:

$\displaystyle{\cal{CRY}}_{m}=\bigl{\\{}(a_{ij})\in\operatorname{Mat}_{m\times
m}(\mathbb{Z}_{\geq 0})\bigr{\\}}$

such that

  1. $(1)$

$\sum_{i}a_{ij}=1$, $\sum_{j}a_{ij}=1$,

  2. $(2)$

$a_{ij}=0$ if $j>i+1$.

Here for any integral convex polytope ${\cal P}\subset\mathbb{Z}^{d}$,
$\iota({\cal P},n)$ denotes the number of integer points in the set $n{\cal
P}\cap\mathbb{Z}^{d}$.

In particular, the polynomial $Q_{n}(\beta)$ does not depend on the order in
which the relations $(a^{\prime})$ and $(b)$ have been applied.

Now let us denote by ${\widehat{Q}}_{n}(q,t;\alpha,\beta)$ the specialization

$\displaystyle x_{ij}=1,\quad i<j<n,\qquad\text{and}\qquad
x_{i,n}=q\quad\text{if}\quad i=2,\ldots,n-1,\qquad x_{1,n}=t$

of the (reduced) polynomial $Q_{n}(x_{ij};\alpha,\beta)$ obtained by applying
the relations $(a^{\prime})$ and $(b)$ in a certain order. The polynomial
$Q_{n}(x_{ij};\alpha,\beta)$ itself depends on the order selected. To define
polynomials which are frequently appear in Section 5, we apply the rules $(a)$
and $(b)$ stated in Definition 5.1 to a given monomial $x_{i_{1},j_{1}}\cdots
x_{i_{p},j_{p}}\in{\widehat{{\rm ACYB}}}_{n}(\alpha,\beta)$ consequently
according to the order in which the monomial taken has been written. We set
$Q_{n}(t,\alpha,\beta):={\widehat{Q}}_{n}(q=t,t;\alpha,\beta)$.

######  Conjecture 5.66.

Let $n\geq 3$ and write

$\displaystyle Q_{n}(t=1;\alpha,\beta)=\sum_{k\geq
0}(1+\beta)^{k}c_{k,n}(\alpha),$

then $c_{k,n}(\alpha)\in\mathbb{Z}_{\geq 0}[\alpha]$.

The polynomial $Q_{n}(t,\beta,\alpha=0)$ has degree
$d_{n}:=[\frac{(n-1)^{2}}{4}]$ with respect to $\beta$. Write

$\displaystyle
Q_{n}(t,\beta):=Q_{n}(t;\alpha=0,\beta)=t^{n-2}\sum_{k=0}^{d_{n}}c_{n}^{(k)}(t)\beta^{k}.$

Then $c_{n}^{(d_{n})}(1)=a_{n}^{2}$ for some non-negative integer $a_{n}$.
Moreover, there exists a polynomial $a_{n}(t)\in\mathbb{N}[t]$ such that

$\displaystyle c_{n}^{(d_{n})}(t)=a_{n}(1)a_{n}(t),\qquad a_{n}(0)=a_{n-1}.$

The all roots of the polynomial $Q_{n}(\beta)$ belong to the set
$\mathbb{R}_{<-1}$.

For example,

$\displaystyle
Q_{4}(t=1;\alpha,\beta)=(1,5,4)_{\beta+1}+\alpha(5,7)_{\beta+1}+3\alpha^{2},$
$\displaystyle
Q_{5}(t=1;\alpha,\beta)=(1,16,58,56,9)_{\beta+1}+\alpha(16,109,146,29)_{\beta+1}$
$\displaystyle\hphantom{Q_{5}(t=1;\alpha,\beta)=}{}+\alpha^{2}(51,125,34)_{\beta+1}+\alpha^{3}(35,17)_{\beta+1},$
$\displaystyle c_{6}^{(6)}=13(2,3,3,3,2),\qquad
c_{7}^{(9)}(t)=34(3,5,6,6,6,5,3),$ $\displaystyle
c_{8}^{(12)}(t)=330(13,27,37,43,45,45,43,37,27,13),$ $\displaystyle
Q_{4}(t,\beta,\alpha=0)t^{-1}=t^{2}+(\beta+1)\big{(}3t+2t^{2}\big{)}+(\beta+1)^{2}(t+1)^{2},$
$\displaystyle{\widehat{Q}}_{4}(q,t;\alpha=0,\beta)=\big{(}qt^{2}+t^{3}+2qt^{3}+q^{2}t^{3}+q^{3}t^{3}+t^{4}+2qt^{4}+q^{2}t^{4}\big{)}$
$\displaystyle\hphantom{{\widehat{Q}}_{4}(q,t;\alpha=0,\beta)=}{}+\big{(}2qt^{2}+2t^{3}+3qt^{3}+2q^{2}t^{3}+2t^{4}+2qt^{4}\big{)}\beta+\big{(}t^{2}+t^{3}\big{)}(q+t)\beta^{2},$
$\displaystyle{\widehat{Q}}_{5}(q,t;\alpha=0,\beta)=\big{(}3q^{2}t+q^{3}t+5qt^{2}+6q^{2}t^{2}+2q^{3}t^{2}+2t^{3}+10qt^{3}+10q^{2}t^{3}+6q^{3}t^{3}$
$\displaystyle\hphantom{{\widehat{Q}}_{5}(q,t;\alpha=0,\beta)=}{}+3q^{4}t^{3}+3q^{5}t^{3}+2q^{6}t^{3}+3t^{4}+11qt^{4}+11q^{2}t^{4}+8q^{3}t^{4}+5q^{4}t^{4}+3q^{5}t^{4}$
$\displaystyle\hphantom{{\widehat{Q}}_{5}(q,t;\alpha=0,\beta)=}{}+3t^{5}+9qt^{5}+9q^{2}t^{5}+6q^{3}t^{5}+3q^{4}t^{5}+2t^{6}+6qt^{6}+6q^{2}t^{6}+2q^{3}t^{6}\big{)}$
$\displaystyle\hphantom{{\widehat{Q}}_{5}(q,t;\alpha=0,\beta)=}{}+\big{(}9q^{2}t+2q^{3}t+17qt^{2}+18q^{2}t^{2}+4q^{3}t^{2}+7t^{3}+31qt^{3}+29q^{2}t^{3}$
$\displaystyle\hphantom{{\widehat{Q}}_{5}(q,t;\alpha=0,\beta)=}{}+15q^{3}t^{3}+10q^{4}t^{3}+7q^{5}t^{3}+10t^{4}+31qt^{4}+29q^{2}t^{4}+18q^{3}t^{4}$
$\displaystyle\hphantom{{\widehat{Q}}_{5}(q,t;\alpha=0,\beta)=}{}+10q^{4}t^{4}+10t^{5}+24qt^{5}+21q^{2}t^{5}+10q^{3}t^{5}+6t^{6}+12qt^{6}+6q^{2}t^{6}\big{)}\beta$
$\displaystyle\hphantom{{\widehat{Q}}_{5}(q,t;\alpha=0,\beta)=}{}+\big{(}9q^{2}t+q^{3}t+21qt^{2}+18q^{2}t^{2}+2q^{3}t^{2}+9t^{3}+34qt^{3}+28q^{2}t^{3}$
$\displaystyle\hphantom{{\widehat{Q}}_{5}(q,t;\alpha=0,\beta)=}{}+14q^{3}t^{3}+9q^{4}t^{3}+12t^{4}+30qt^{4}+24q^{2}t^{4}+12q^{3}t^{4}+12t^{5}+21qt^{5}$
$\displaystyle\hphantom{{\widehat{Q}}_{5}(q,t;\alpha=0,\beta)=}{}+12q^{2}t^{5}+6t^{6}+6qt^{6}\big{)}\beta^{2}+\big{(}3q^{2}t+11qt^{2}+6q^{2}t^{2}+5t^{3}+15qt^{3}$
$\displaystyle\hphantom{{\widehat{Q}}_{5}(q,t;\alpha=0,\beta)=}{}+10q^{2}t^{3}+5q^{3}t^{3}+6t^{4}+11qt^{4}+6q^{2}t^{4}+6t^{5}+6qt^{5}+2t^{6}\big{)}\beta^{3}$
$\displaystyle\hphantom{{\widehat{Q}}_{5}(q,t;\alpha=0,\beta)=}{}+\big{(}2qt^{2}+t^{3}+2qt^{3}+q^{2}t^{3}+t^{4}+qt^{4}+t^{5}\big{)}\beta^{4}.$

Note that polynomials ${\widehat{Q}}_{n}(q,t;\alpha=0,\beta=0)$ give rise to a
two parameters deformation of the product of Catalan’s numbers
$C_{1}C_{2}\cdots C_{n-1}$. Are there combinatorial interpretations of these
polynomials and polynomials ${\widehat{Q}}_{n}(q,t;\alpha=0,\beta)$?

######  Comments 5.67.

We expect that for each integer $n\geq 2$ the set

$\displaystyle\Psi_{n+1}:=\left\\{w\in\mathbb{S}_{2n-1}\,|\,\mathfrak{S}_{w}(1)=\prod_{j=1}^{n}{\rm
Cat}_{j}\right\\}$

is non empty, whereas the set

$\displaystyle\left\\{w\in\mathbb{S}_{2n-2}\,|\,\mathfrak{S}_{w}(1)=\prod_{j=1}^{n}{\rm
Cat}_{j}\right\\}$

is empty. For example,

$\displaystyle\Psi_{4}=\\{[1,5,3,4,2]\\},\qquad\Psi_{5}=\\{[1,5,7,3,2,6,4],~{}[1,5,4,7,2,6,3]\\},$
$\displaystyle\Psi_{6}=\big{\\{}w:=[1,3,2,8,6,9,4,5,7],w^{-1},\dots\big{\\}},\qquad\Psi_{7}=\\{???\\},$

but one can check that for $w=[2358,10,549,12,11]\in{\mathbb{S}}_{12}$

$\displaystyle{\mathfrak{S}}_{w}(1)=776160=\prod_{j=2}^{6}{\rm Cat}_{j}.$

More generally, for any positive integer $N$ define

$\displaystyle\kappa(N)=\min\\{n\,|\,\exists\,w\in{\mathbb{S}}_{n}\ \text{such
that}\ {\mathfrak{S}}_{w}(1)=N\\}.$

It is clear that $\kappa(N)\leq N+1$.

######  Problem 5.68.

Compute the following numbers

$\displaystyle\kappa(n!),\quad\kappa\left(\prod_{j=1}^{n}{\rm
Cat}_{j}\right),\quad\kappa({\rm
ASM}(n)),\quad\kappa\big{(}(n+1)^{n-1}\big{)}.$

For example, $10\leq\kappa({\rm ASM}(6)=7436)\leq 12$. Indeed, take
$w=[716983254,10,12,11]\in\mathbb{S}_{12}$. One can show that

$\displaystyle{\mathfrak{S}}_{w}(x_{1}=t,\,x_{i}=1,\,\forall\,i\geq
2)=13t^{6}(t+10)(15t+37),$

so that ${\mathfrak{S}}_{w}(1)=ASM(6)$; $\kappa(6^{4})=9$, namely, one can
take $w=[157364298]$.

######  Question 5.69.

Let $N$ be a positive integer. Does there exist a vexillary
$($grassmannian?$)$ permutation $w\in\mathbb{S}_{n}$ such that $n\leq
2\kappa(N)$ and $\mathfrak{S}_{w}(1)=N$?

For example, $w=[1,4,5,6,8,3,5,7]\in\mathbb{S}_{8}$ is a grassmannian
permutation such that $\mathfrak{S}_{w}(1)=140$, and
$\mathfrak{R}_{w}(1,\beta)=(1,9,27,43,38,18,4)$.

######  Remark 5.70.

We expect that for $n\geq 5$ there are no permutations
$w\in{\mathbb{S}}_{\infty}$ such that
$Q_{n}(\beta)=\mathfrak{S}_{w}^{(\beta)}(1)$.

The numbers $\mathfrak{C}_{n}:=\prod\limits_{j=1}^{n}{\rm Cat}_{j}$ appear
also as the values of the Kostant partition function of the type $A_{n-1}$ on
some special vectors. Namely,

$\displaystyle\mathfrak{C}_{n}=K_{\Phi(1^{n})}(\gamma_{n}),\qquad\text{where}\quad\gamma_{n}=\left(1,2,3,\ldots,n-1,-{n\choose
2}\right),$

see, e.g., [133, Exercise 6.C10], and [69, pp. 173–178]. More generally [69,
Exercise g, p. 177, (7.25)], one has

$\displaystyle
K_{\Phi(1^{n})}(\gamma_{n,d})=pp^{\delta_{n}}(d)\mathfrak{C}_{n-1}=\prod_{j=d}^{n+d-2}{1\over
2j+1}~{}{n+d+j\choose 2j},$

where $\gamma_{n,d}=(d+1,d+2,\ldots,d+n-1,-n(2d+n-1)/2)$, $pp^{\delta_{n}}(d)$
denotes the set of reversed (weak) plane partitions bounded by $d$ and
contained in the shape $\delta_{n}=(n-1,n-2,\ldots,1)$. Clearly,
$pp^{\delta_{n}}(1)=\prod\limits_{{1\leq i<j\leq n}}{i+j+1\over i+j-1}=C_{n}$,
where $C_{n}$ is the $n$-th Catalan number585858For example, if $n=3$, there
exist $5$ reverse (weak) plane partitions of shape $\delta_{3}=(2,1)$ bounded
by $1$, namely reverse plane partitions $\left\\{\begin{pmatrix}0&0\\\
0\end{pmatrix},\,\begin{pmatrix}0&0\\\ 1\end{pmatrix},\,\begin{pmatrix}0&1\\\
0&\end{pmatrix},\,\begin{pmatrix}0&1\\\ 1\end{pmatrix},\,\begin{pmatrix}1&1\\\
1\end{pmatrix}\right\\}$..

######  Conjecture 5.71.

For any permutation $w\in\mathbb{S}_{n}$ there exists a graph
$\Gamma_{w}=(V,E)$, possibly with multiple edges, such that the reduced volume
$\widetilde{{\rm vol}}({\cal{F}}_{\Gamma_{w}})$ of the flow polytope
${\cal{F}}_{\Gamma_{w}}$, see, e.g., [132] for a definition of the former, is
equal to $\mathfrak{S}_{w}(1)$.

For a family of vexillary permutations $w_{n,p}$ of the shape
$\lambda=p\delta_{n+1}$ and flag $\phi=(1,2,\ldots$, $n-1,n)$ the
corresponding graphs $\Gamma_{n,p}$ have been constructed in [101, Section 6].
In this case the reduced volume of the flow polytope
${\cal{F}}_{\Gamma_{n,p}}$ is equal to the Fuss–Catalan number

$\displaystyle{1\over 1+(n+1)p}{(n+1)(p+1)\choose
n+1}=\mathfrak{S}_{w_{n,p}}(1),$

cf. Corollary 5.33.

######  Exercises 5.72.

  1. $(a)$

Show that the polynomial $R_{n}(t):=t^{1-n}Q_{n}(t;0,0)$ is symmetric
(unimodal?), and $R_{n}(0)=\prod\limits_{k=1}^{n-2}{\rm Cat}_{k}$. For
example,

$\displaystyle R_{4}(t)=(1+t)\big{(}2+t+2t^{2}\big{)},\qquad
R_{5}(t)=2(5,10,13,14,13,10,5)_{t},$ $\displaystyle
R_{6}(t)=10(2,3,2)_{t}(7,7,10,13,10,13,10,7,7)_{t},\qquad
R_{7}(t)=30\big{(}196+\cdots+196t^{15}\big{)}.$

Note that $R_{n}(1)=\prod\limits_{k=1}^{n-1}{\rm Cat}_{k}$.

  2. $(b)$

More generally, write as before,

$\displaystyle Q_{n}(t;0,\beta)=t^{n-2}\sum_{k\geq 0}c_{n}^{(k)}(t)\beta^{k}.$

Show that the polynomials $c_{n}^{(k)}(t)$ are symmetric (unimodal?) for all
$k$ and $n$.

  3. $(c)$

Consider a reduced polynomial ${\overline{R}}_{n}(\\{x_{ij}\\})$ of the
element

$\displaystyle\prod_{1\leq i<j\leq
n\atop(i,j)\not=(n-1,n)}x_{ij}\in{\widehat{{\rm ACYB}}}(\alpha=\beta=0)^{ab},$

see Definition 5.1. Here we assume additionally, that all elements
$\\{x_{ij}\\}$ are mutually commute. Define polynomial
${\widetilde{R}}_{n}(q,t)$ to be the following specialization

$\displaystyle x_{ij}\longrightarrow 1\quad\text{if}\quad i<j<n-1,\qquad
x_{i,n-1}\longrightarrow q,\qquad x_{i,n}\longrightarrow t,\quad\forall\,i$

of the polynomial ${\overline{R}}_{n}(\\{x_{ij}\\})$ in question. Show that
polynomials ${\widetilde{R}}_{n}(q,t)$ are well-defined, and

$\displaystyle{\widetilde{R}}_{n}(q,t)={\widetilde{R}}_{n}(t,q).$

######  Examples 5.73.

$\displaystyle
R_{4}(t,\beta)=(2,3,3,2)_{t}+(4,5,4)_{t}\beta+(2,2)_{t}\beta^{2},$
$\displaystyle
R_{5}(t,\beta)=(10,20,26,28,26,20,10)_{t}+(33,61,74,74,61,33)_{t}\beta+(39,65,72,65,39)_{t}\beta^{2}$
$\displaystyle\hphantom{R_{5}(t,\beta)=}{}+(19,27,27,19)_{t}\beta^{3}+(3,3,3)_{t}\beta^{4},$
$\displaystyle
R_{6}(t,\beta)=(140,350,550,700,790,820,790,700,550,350,140)_{t}$
$\displaystyle\hphantom{R_{6}(t,\beta)=}{}+(686,1640,2478,3044,3322,3322,3044,2478,1640,686)_{t}\beta$
$\displaystyle\hphantom{R_{6}(t,\beta)=}{}+(1370,3106,4480,5280,5537,5280,4480,3106,1370)_{t}\beta^{2}$
$\displaystyle\hphantom{R_{6}(t,\beta)=}{}+(1420,3017,4113,4615,4615,4113,3017,1420)_{t}\beta^{3}$
$\displaystyle\hphantom{R_{6}(t,\beta)=}{}+(800,1565,1987,2105,1987,1565,800)_{t}\beta^{4}+(230,403,465,465,403,230)_{t}\beta^{5}$
$\displaystyle\hphantom{R_{6}(t,\beta)=}{}+(26,39,39,39,26)_{t}\beta^{6},$
$\displaystyle
R_{6}(1,\beta)=(5880,22340,34009,26330,10809,2196,169)_{\beta},$
$\displaystyle
R_{7}(t,\beta)=(5880,17640,32340,47040,59790,69630,76230,79530,79530,76230,69630,$
$\displaystyle\hphantom{R_{7}(t,\beta)=(}{}59790,47040,32340,17640,5880)_{t}+(39980,116510,208196,295954,368410,$
$\displaystyle\hphantom{R_{7}(t,\beta)=(}{}420850,452226,462648,452226,420850,368410,295954,208196,116510,$
$\displaystyle\hphantom{R_{7}(t,\beta)=(}{}39980)_{t}\beta+(118179,333345,578812,802004,975555,1090913,1147982,$
$\displaystyle\hphantom{R_{7}(t,\beta)=(}{}1147982,1090913,975555,802004,578812,333345,118179)_{t}\beta^{2}$
$\displaystyle\hphantom{R_{7}(t,\beta)=}{}+(198519,539551,906940,1221060,1447565,1580835,1624550,1580835,$
$\displaystyle\hphantom{R_{7}(t,\beta)=(}{}1447565,1221060,906940,539551,198519)_{t}\beta^{3}$
$\displaystyle\hphantom{R_{7}(t,\beta)=}{}+(207712,540840,875969,1141589,1314942,1398556,1398556,1314942,$
$\displaystyle\hphantom{R_{7}(t,\beta)=(}{}1141589,875969,540840,207712)_{t}\beta^{4}$
$\displaystyle\hphantom{R_{7}(t,\beta)=}{}+(139320,344910,535107,671897,749338,773900,749338,671897,535107,$
$\displaystyle\hphantom{R_{7}(t,\beta)=(}{}344910,139320)_{t}\beta^{5}+(59235,137985,203527,244815,263389,263389,244815,$
$\displaystyle\hphantom{R_{7}(t,\beta)=(}{}203527,137985,59235)_{t}\beta^{6}+(15119,32635,45333,51865,53691,51865,45333,$
$\displaystyle\hphantom{R_{7}(t,\beta)=(}{}32635,15119)_{t}\beta^{7}+(2034,3966,5132,5532,5532,5132,3966,2034)\beta^{8}$
$\displaystyle\hphantom{R_{7}(t,\beta)=}{}+(102,170,204,204,204,170,102)_{t}\beta^{9},$
$\displaystyle
R_{7}(1,\beta)=(776160,4266900,10093580,13413490,10959216,5655044,1817902,$
$\displaystyle\hphantom{R_{7}(1,\beta)=(}{}343595,33328,1156)_{\beta}.$

####  5.3.2 The Chan–Robbins–Mészáros polytope $\boldsymbol{{\cal{P}}_{n,m}}$

Let $m\geq 0$ and $n\geq 2$ be integers, consider the reduced polynomial
$Q_{n,m}(t,\beta)$ corresponding to the element

$\displaystyle
M_{n.m}:=\left(\prod_{j=2}^{n}x_{1j}\right)^{m+1}\prod_{j=2}^{n-2}\prod_{k=j+2}^{n}x_{jk}.$

For example,

$\displaystyle
Q_{2,4}(t,\beta)=(4,7,9,10,10,9,7,4)_{t}+(10,17,21,22,21,17,10)_{t}\beta$
$\displaystyle\hphantom{Q_{2,4}(t,\beta)=}{}+(8,13,15,15,13,8)_{t}\beta^{2}+(2,3,3,3,2)_{t}\beta^{3},$
$\displaystyle Q_{2,4}(1,\beta)=(60,118,72,13)_{\beta},$ $\displaystyle
Q_{2,5}(t,\beta)=(60,144,228,298,348,378,388,378,348,298,228,144,60)_{t}$
$\displaystyle\hphantom{Q_{2,5}(t,\beta)=}{}+(262,614,948,1208,1378,1462,1462,1378,1208,948,614,262)_{t}\beta$
$\displaystyle\hphantom{Q_{2,5}(t,\beta)=}{}+(458,1042,1560,1930,2142,2211,2142,1930,1560,1042,458)_{t}\beta^{2}$
$\displaystyle\hphantom{Q_{2,5}(t,\beta)=}{}+(405,887,1278,1526,1640,1640,1526,1278,887,405)_{t}\beta^{4}$
$\displaystyle\hphantom{Q_{2,5}(t,\beta)=}{}+(187,389,534,610,632,610,534,389,187)_{t}\beta^{4}$
$\displaystyle\hphantom{Q_{2,5}(t,\beta)=}{}+(41,79,102,110,110,102,79,41)_{t}\beta^{5}+(3,5,6,6,6,5,3)_{t}\beta^{6},$
$\displaystyle Q_{2,5}(1,\beta)=(3300,11744,16475,11472,4072,664,34)_{\beta},$
$\displaystyle
Q_{2,6}(1,\beta)=(660660,3626584,8574762,11407812,9355194,4866708,1589799,$
$\displaystyle\hphantom{Q_{2,6}(1,\beta)=(}{}310172,32182,1320)_{\beta},$
$\displaystyle
Q_{2,7}(\beta)=(1,213,12145,279189,3102220,18400252,61726264,120846096,139463706,$
$\displaystyle\hphantom{Q_{2,7}(\beta)=(}{}93866194,5567810,7053370,626730,16290)_{\beta+1}.$

######  Theorem 5.74.

One has

$\displaystyle Q_{m,n}(1,1)=\prod_{k=1}^{n-2}{\rm Cat}_{k}\prod_{1\leq i<j\leq
n-1}\frac{2(m+1)+i+j-1}{i+j-1},$ $\displaystyle\sum_{k\geq
0}\iota({\cal{P}}_{n,m};k)\beta^{k}=\frac{Q_{m,n}(1,\beta-1)}{(1-\beta)^{{n+1\choose
2}+1}},$

where ${\cal{P}}_{n,m}$ denotes the generalized Chan–Robbins–Yuen polytope
defined in [101], and for any integral convex polytope $\cal{P}$,
$\iota({\cal{P}},k)$ denotes the Ehrhart polynomial of polytope $\cal{P}$.

######  Conjecture 5.75.

Let $n\geq 3$, $m\geq 0$ be integers, , write

$\displaystyle Q_{m,n}(t,\beta)=\sum_{k\geq
0}c_{m,n}^{(k)}(t)\beta^{k},\qquad\text{and set}\qquad
b(m,n):=\max\big{(}k\,|\,c_{m,n}^{(k)}(t)\not=0\big{)}.$

Denote by ${\tilde{c}}_{m,n}(t)$ the polynomial obtained from that
$c_{m,n}^{(b(m,n)}(t)$ by dividing the all coefficients of the latter on their
GCD. Then

$\displaystyle{\tilde{c}}_{n,m}(t)=a_{n+m}(t),$

where the polynomials $a_{n}(t):=c_{0,n}(t)$ have been defined in Conjecture
5.66.

For example,

$\displaystyle c_{2,5}(t)=4a_{7}(t),\qquad c_{2,6}(t)=10a_{8}(t),\qquad
c_{3,5}(t)=a_{8}(t),$ $\displaystyle
c_{2,7}(t)=10(34,78,118,148,168,178,181,178,168,148,118,78,34)\stackrel{{\scriptstyle?}}{{=}}10a_{9}(t).$

It is known [69, 99, 100] that

$\displaystyle\prod_{k=1}^{n-2}{\rm Cat}_{k}\prod_{1\leq i<j\leq
n-1}\frac{2(m+1)+i+j-1}{i+j-1}=\prod_{j=m+1}^{m+n-2}\frac{1}{2j+1}{n+m+j\choose
2j}$ $\displaystyle\qquad{}=K_{A_{n+1}}\left(m+1,m+2,\ldots,n+m,-mn-{n\choose
2}\right).$

######  Conjecture 5.76.

Let ${\boldsymbol{a}}=(a_{2},a_{3},\ldots,a_{n})$ be a sequence of non-
negative integers, consider the following element

$\displaystyle
M_{({\boldsymbol{a}})}=\left(\prod_{j=2}^{n}x_{1j}^{a_{j}}\right)\prod_{j=2}^{n-1}\left(\prod_{k=j+1}^{n}x_{jk}\right).$

Let $R_{{\boldsymbol{a}}}(t_{1},\ldots,t_{n-1},\alpha,\beta)$ be the following
specialization $x_{ij}\longrightarrow t_{j-1}$ for all $1\leq i<j\leq n$ of
the reduced polynomial $R_{{\boldsymbol{a}}}(x_{ij})$ of monomial
$M_{{\boldsymbol{a}}}\in{\widehat{{\rm ACYB}}}_{n}(\alpha,\beta)$. Then the
polynomial $R_{{\boldsymbol{a}}}(t_{1},\ldots,t_{n-1},\alpha,\beta)$ is well-
defined, i.e., does not depend on an order in which relations $(a^{\prime})$
and $(b)$, Definition 5.1, have been applied.

$\displaystyle
Q_{M_{\boldsymbol{a}}}(1,\beta=0)=K_{A_{n+1}}\left(a_{2}+1,a_{3}+2,\ldots,a_{n}+n-1,-{n\choose
2}-\sum_{j=2}^{n}a_{j}\right).$

Write

$\displaystyle Q_{M_{\boldsymbol{a}}}(t,\beta)=\sum_{k\geq
0}c_{{\boldsymbol{a}}}^{(k)}(t)\beta^{k}.$

The polynomials $c_{{\boldsymbol{a}}}^{(k)}(t)$ are symmetric $($unimodal?$)$
for all $k$.

######  Example 5.77.

Let’s take $n=5$, ${\boldsymbol{a}}=(2,1,1,0)$. One can show that the value of
the Kostant partition function $K_{A_{5}}(3,3,4,4,-14)$ is equal to $1967$. On
the other hand, one has

$\displaystyle
Q_{(2,1,1,0)}(t,\beta)t^{-3}=(50,118,183,233,263,273,263,233,183,118,50)_{t}$
$\displaystyle\hphantom{Q_{(2,1,1,0)}(t,\beta)t^{-3}=}{}+(214,491,738,908,992,992,908,738,491,214)_{t}\beta$
$\displaystyle\hphantom{Q_{(2,1,1,0)}(t,\beta)t^{-3}=}{}+(365,808,1167,1379,1448,1379,1167,808,365)_{t}\beta^{2}$
$\displaystyle\hphantom{Q_{(2,1,1,0)}(t,\beta)t^{-3}=}{}+(313,661,906,1020,1020,906,661,313)_{t}\beta^{3}$
$\displaystyle\hphantom{Q_{(2,1,1,0)}(t,\beta)t^{-3}=}{}+(139,275,351,373,351,275,139)_{t}\beta^{4}$
$\displaystyle\hphantom{Q_{(2,1,1,0)}(t,\beta)t^{-3}=}{}+(29,52,60,60,52,29)_{t}\beta^{5}+(2,3,3,3,2)_{t}\beta^{6},$
$\displaystyle
Q_{(2,1,1,0)}(1,\beta)=(1967,6686,8886,5800,1903,282,13)=(1,34,279,748,688,204,13)_{\beta+1}.$

It might be well to point out that since we know, see Theorem 5.63, that
polynomials $Q_{M_{\boldsymbol{a}}}(1,\beta)$ in face are polynomials of
$\beta+1$ with non-negative integer coefficients, we can treat the polynomial
${\widetilde{Q}}_{M_{\boldsymbol{a}}}(\beta):=Q_{M_{\boldsymbol{a}}}(1,\beta-1)$
as a $\beta$-analogue of the Kostant partition function in the dominant
chamber. It seems an interesting problem to find an interpretation of
polynomials ${\widetilde{Q}}_{M_{\boldsymbol{a}}}(\beta)$ in the framework of
the representation theory of Lie algebras. For example,

$\displaystyle{\widetilde{Q}}_{(2,1,1,0)}(\beta)=(1,34,279,748,688,204,13)_{\beta},$
$\displaystyle{\widetilde{Q}}_{(2,1,1,0)}(\beta=1)=1967=K_{A_{5}}(3,3,4,4,-14).$

######  Exercises 5.78.

  1. (1)

Show that

$\displaystyle R_{n}(t,-1)=t^{2(n-2)}R_{n-1}\big{(}{-}t^{-1},1\big{)}.$

  2. (2)

Show that the ratio

$\displaystyle\frac{R_{n}(0,\beta)}{(1+\beta)^{n-2}}$

is a polynomial in $(\beta+1)$ with non-negative coefficients.

  3. (3)

Show that polynomial $R_{n}(t,1)$ has degree $e_{n}:=(n+1)(n-2)/2$, and

$\displaystyle{\rm Coef\/f}[t^{e_{n}}]R_{n}(t,1)=\prod_{k=1}^{n-1}{\rm
Cat}_{k}.$

  4. (4)

Show that

$\displaystyle{\widetilde{Q}}_{(n,2,3,0)}(\beta)=\left(1,3n+2,\binom{n+1}{2}+n,\binom{n+1}{3}+\binom{n}{2}\right)_{\beta},$

and

$\displaystyle K_{A_{4}}(n,3,4,-n-7)=\frac{(n+2)(n+3)(n+9)}{6}.$

######  Problems 5.79.

  1. $(1)$

Assume additionally to the conditions $(a^{\prime})$ and $(b)$ above that

$\displaystyle x_{ij}^{2}=\beta x_{ij}+1\qquad\text{if}\quad 1\leq i<j\leq n.$

What one can say about a reduced form of the element $w_{0}$ in this case?

  2. (2)

According to a result by S. Matsumoto and J. Novak [97], if
$\pi\in{\mathbb{S}}_{n}$ is a permutation of the cyclic type $\lambda\vdash
n$, then the total number of primitive factorizations $($see definition in
[97]) of $\pi$ into product of $n-\ell(\lambda)$ transpositions, denoted by
$\operatorname{Prim}_{n-\ell(\lambda)}(\lambda)$, is equal to the product of
Catalan numbers:

$\displaystyle\operatorname{Prim}_{n-\ell(\lambda)}(\lambda)=\prod_{i=1}^{\ell(\lambda)}{\rm
Cat}_{\lambda_{i}-1}.$

Recall that the Catalan number ${\rm Cat}_{n}:=C_{n}={1\over n}{2n\choose n}$.
Now take $\lambda=(2,3,\ldots,n+1)$. Then

$\displaystyle Q_{n}(1)=\prod_{a=1}^{n}{\rm
Cat}_{a}=\operatorname{Prim}_{{n\choose 2}}(\lambda).$

Does there exist “a natural” bijection between the primitive factorizations
and monomials which appear in the polynomial $Q_{n}(x_{ij};\beta)$?

  3. $(3)$

Compute in the algebra ${\widehat{{\rm ACYB}}}_{n}(\alpha,\beta)$ the
specialization

$\displaystyle x_{ij}\longrightarrow 1,\quad j<n,\qquad x_{ij}\longrightarrow
t,\quad 1\leq i<n,$

denoted by $P_{w{{}_{n}}}(t,\alpha,\beta)$, of the reduced polynomial
$P_{s_{ij}}(\\{x_{ij}\\},\alpha,\beta)$ corresponding to the transposition

$\displaystyle
s_{ij}:=\left(\prod_{k=i}^{j-2}x_{k,k+1}\right)x_{j-1,j}\left(\prod_{k=j-2}^{i}x_{k,k+1}\right)\in{\widehat{{\rm
ACYB}}}_{n}(\alpha,\beta).$

For example,

$\displaystyle
P_{s_{14}}(t,\alpha,\beta)=t^{5}+3(1+\beta)t^{4}+((3,5,2)_{\beta}+3\alpha)t^{3}+(2(1+\beta)^{2}+\alpha(5+4\beta))t^{2}$
$\displaystyle\hphantom{P_{s_{14}}(t,\alpha,\beta)=}{}+((1+\beta((1+3\alpha)+2\alpha^{2})t+\alpha+\alpha^{2}.$

###  5.4 Reduced polynomials of certain monomials

In this subsection we compute the reduced polynomials corresponding to
dominant monomials of the form

$\displaystyle x_{{\boldsymbol{m}}}:=x_{1,2}^{m_{1}}x_{23}^{m_{2}}\cdots
x_{n-1,n}^{m_{n-1}}\in\big{(}{\widehat{{\rm ACYB}}}_{n}(\beta)\big{)}^{ab},$

where ${\boldsymbol{m}}=(m_{1}\geq m_{2}\geq\cdots\geq m_{n-1}\geq 0)$ is a
partition, and we apply the relations $(a^{\prime})$ and $(b)$ in the algebra
$({\widehat{{\rm ACYB}}}_{n}(\beta))^{ab}$, see Definition 5.1 and Section
5.3.1, successively, starting from $x_{12}^{m_{1}}x_{23}$.

######  Proposition 5.80.

The function

$\displaystyle\mathbb{Z}_{\geq 0}^{n-1}\longrightarrow\mathbb{Z}_{\geq
0}^{n-1},\qquad{\boldsymbol{m}}\longrightarrow
P_{{\boldsymbol{m}}}(t=1;\beta=1)$

can be extended to a piece-wise polynomial function on the space
$\mathbb{R}_{\geq 0}^{n-1}$.

We start with the study of powers of Coxeter elements. Namely, for powers of
Coxeter elements, one has595959To simplify notation we set
$P_{w}(\beta):=P_{w}(x_{ij}=1;\beta)$.

$\displaystyle P_{(x_{12}x_{23})^{2}}(\beta)=(6,6,1),\qquad
P_{(x_{12}x_{23}x_{34})^{2}}(\beta)=(71,142,91,20,1)=(1,16,37,16,1)_{\beta+1},$
$\displaystyle
P_{(x_{12}x_{23}x_{34})^{3}}(\beta)=(1301,3903,4407,2309,555,51,1)=(1,45,315,579,315,45,1)_{\beta+1},$
$\displaystyle
P_{(x_{12}x_{23}x_{34}x_{45})^{2}}(\beta)=(1266,3798,4289,2248,541,50,1)=(1,44,306,564,306,44,1)_{\beta+1},$
$\displaystyle P_{(x_{12}x_{23}x_{34})^{3}}(\beta=1)=12527,\qquad
P_{(x_{12}x_{23}x_{34})^{4}}(\beta=0)=26599,$ $\displaystyle
P_{(x_{12}x_{23}x_{34})^{4}}(\beta=1)=539601,\qquad
P_{(x_{12}x_{23}x_{34}x_{45})^{2}}(\beta=1)=12193,$ $\displaystyle
P_{(x_{12}x_{23}x_{34}x_{45})^{3}}(\beta=0)=50000,\qquad
P_{(x_{12}x_{23}x_{34}x_{45})^{3}}(\beta=1)=1090199.$

######  Lemma 5.81.

One has

$\displaystyle
P_{x_{12}^{n}x_{23}^{m}}(\beta)=\sum_{k=0}^{\min(n,m)}{n+m-k\choose
m}{m\choose k}\beta^{k}=\sum_{k=0}^{\min(n,m)}{n\choose k}{m\choose
k}(1+\beta)^{k}.$

Moreover,

  * •

polynomial $P_{(x_{12}x_{23}\cdots x_{n-1,n})^{m}}(\beta-1)$ is a symmetric
polynomial in $\beta$ with non-negative coefficients.

  * •

polynomial $P_{x_{12}^{n}x_{23}^{m}}(\beta)$ counts the number of
$(n,m)$-Delannoy paths according to the number of $NE$ steps606060Recall that
a $(n,m)$-Delannoy path is a lattice paths from $(0,0)$ to $(n,m)$ with steps
$E=(1,0)$, $N=(0,1)$ and $NE=(1,1)$ only. For the definition and examples of
the Delannoy paths and numbers, see [131, $A001850$, $A008288$] and
http://mathworld.wolfram.com/DelannoyNumber.html. .

######  Proposition 5.82.

Let $n$ and $k$, $0\leq k\leq n$, be integers. The number

$\displaystyle P_{(x_{12}x_{23})^{n}(x_{34})^{k}}(\beta=0)$

is equal to the number of $n$ up, $n$ down permutations in the symmetric group
${\mathbb{S}}_{2n+k+1}$, see [131, $A229892$] and Exercises 5.30(2).

######  Conjecture 5.83.

Let $n$, $m$, $k$ be nonnegative integers. Then the number

$\displaystyle P_{x_{12}^{n}x_{23}^{m}x_{34}^{k}}(\beta=0)$

is equal to the number of $n$ up, $m$ down and $k$ up permutations in the
symmetric group $\mathbb{S}_{n+m+k+1}$.

For example,

  * •

Take $n=2$, $k=0$, the six permutations in $\mathbb{S}_{5}$ with $2$ up, $2$
down are 12543, 13542, 14532, 23541, 24531, 34521.

  * •

Take $n=3$, $k=1$, the twenty permutations in $\mathbb{S}_{7}$ with $3$ up,
$3$ down are 1237654, 1247653, 1257643, 1267543, 1347652, 1357642, 1367542,
1457632, 1467532, 1567432, 2347651, 2357641, 2367541, 2457631, 2467531,
2567431, 3457621, 3467521, 3567421, 4567321, see [131, $A229892$].

  * •

Take $n=3$, $m=2$, $k=1$, the number of $3$ up, $2$ down and $1$ up
permutations in $\mathbb{S}_{7}$ is equal to $50=P_{321}(0)$: 1237645,
1237546, …, 4567312.

  * •

Take $n=1$, $m=3$, $k=2$, the number of $1$ up, $3$ down and $2$ up
permutations in $\mathbb{S}_{7}$ is equal to $55=P_{132}(0)$, as it can be
easily checked.

On the other hand,
$P_{x_{12}^{4}x_{23}^{3}x_{34}^{2}x_{45}}(\beta=0)=7203<7910$, where $7910$ is
the number of $4$ up, $3$ down, $2$ up and $1$ down permutations in the
symmetric group $\mathbb{S}_{11}$.

######  Conjecture 5.84.

Let $k_{1},\ldots,k_{n-1}$ be a sequence of non-negative integer numbers,
consider monomial $M:=x_{12}^{k_{1}}x_{23}^{k_{2}}\cdots x_{n-1,n}^{k_{n-1}}$.
Then reduced polynomial $P_{M}(\beta-1)$ is a unimodal polynomial in $\beta$
with non-negative coefficients.

######  Example 5.85.

$\displaystyle P_{3,2,1}(\beta)=(1,14,27,8)_{\beta+1}=P_{1,2,3}(\beta),\qquad
P_{2,3,1}(\beta)=(1,15,30,9)_{\beta+1}=P_{1,3,2}(\beta),$ $\displaystyle
P_{3,1,2}(\beta)=(1,11,18,4)_{\beta+1}=P_{2,1,3}(\beta),$ $\displaystyle
P_{4,3,2,1}(\beta)=(1,74,837,2630,2708,885,68)_{\beta+1},\qquad
P_{4,3,2,1}(0)=7203=3\cdot 7^{4},$ $\displaystyle
P_{5,4,3,2,1}(\beta)=(1,394,19177,270210,1485163,3638790,4198361,2282942,$
$\displaystyle\hphantom{P_{5,4,3,2,1}(\beta)=(}{}553828,51945,1300)_{\beta+1},$
$\displaystyle P_{5,4,3,2,1}(0)=12502111=1019\times 12269.$

######  Exercises 5.86.

(1) Show that if $n\geq m$, then

$\displaystyle
x_{ij}^{n}x_{jk}^{m}\Big{\arrowvert}_{x_{ij}=1=x_{jk}}=\sum_{a=0}^{n}{m+a-1\choose
a}\left(\sum_{p=0}^{n-a}{m\choose p}\beta^{p}\right)x_{ik}^{m+a}.$

(2) Show that if $n\geq m\geq k$, then

$\displaystyle
P_{x_{12}^{n}x_{23}^{m}x_{34}^{k}}(\beta)=P_{x_{12}^{n}x_{23}^{m}}(\beta)$
$\displaystyle\hphantom{P_{x_{12}^{n}x_{23}^{m}x_{34}^{k}}(\beta)=}{}+\sum_{a\geq
1\atop b,p\geq 0}{m\choose p}{k\choose a}{a-1\choose b}{n+1\choose
p+a-b}{m+a-1-b\choose a}(\beta+1)^{p+a}.$

In particular, if $n\geq m\geq k$, then

$\displaystyle P_{x_{12}^{n}x_{23}^{m}x_{34}^{k}}(0)={m+n\choose
n}+\sum_{a\geq 1}{k\choose a}\left(\sum_{b=1}^{a}{m+n+1\choose m+b}{a-1\choose
b-1}{m+b-1\choose a}\right).$

Note that the set of relations from the item $(1)$ allows to give an explicit
formula for the polynomial $P_{M}(\beta)$ for any dominant sequence
$M=(m_{1}\geq m_{2}\geq\cdots\geq m_{k})\in(\mathbb{Z}_{>0})^{k}$. Namely,

$\displaystyle
P_{M}(\beta+1)=\sum_{\boldsymbol{a}}\prod_{j=2}^{k}{m_{j}+a_{j-1}-1\choose
a_{j-1}}\left(\sum_{\boldsymbol{b}}\prod_{j=1}^{k-1}{m_{j+1}\choose
b_{j}}\beta^{b_{j}}\right),$

where the first sum runs over the following set ${\cal A}(M)$ of integer
sequences ${\boldsymbol{a}}=(a_{1},\ldots,a_{k-1})$

$\displaystyle{\cal{A}}(M):=\\{0\leq a_{j}\leq
m_{j}+a_{j-1},\,j=1,\ldots,k-1\\},\qquad a_{0}=0,$

and the second sum runs over the set ${\cal B}(M)$ of all integer sequences
${\boldsymbol{b}}=(b_{1},\ldots,b_{k-1})$

$\displaystyle{\cal B}(M):=\bigcup_{{\boldsymbol{a}}\in{\cal A}(M)}\\{0\leq
b_{j}\leq\min(m_{j+1},m_{j}-a_{j}+a_{j-1})\\},\qquad j=1,\ldots,k-1.$

(3) Show that

$\displaystyle\\#\big{|}{\cal A}\big{(}n,1^{k-1}\big{)}\big{|}={n+1\over
k}{2k+n\choose k-1}=f^{(n+k,k)},$

where $f^{(n+k,k)}$ denotes the number of standard Young tableaux of shape
$(n+k,k)$. In particular, $\\#|{\cal A}(1^{k})|=C_{k+1}$.

(4) Let $n\geq m\geq 1$ be integers and set $M=(n,m,1^{k})$. Show that

$\displaystyle P_{M}(x_{ij}=1;\beta=0)=\sum_{p=0}^{n}{m+p+1\over
k}~{}{m+p-1\choose p}{m+2k+p\choose k-1}:=P_{k}(n,m).$

In particular, $P_{1}(n,m)={n+m\choose n}+m{n+m+1\choose n}$,

$\displaystyle P_{k}(n,1)={n+1\over k+1}{2k+2+n\choose k},\qquad
P_{k}(2,2)=\big{(}79k^{2}+341k+360\big{)}{(2k+2)!\over k!(k+5)!}.$

Let us remark that

$\displaystyle
P_{k}(n,1)={\frac{n+1}{n+k+2}}{\binom{2(k+1)+n}{k+1}}=F_{k+1}^{(2)}(n)=D(k,1,n,2),$

where the $D(k,1,n,2)$ and $F_{k+1}^{(2)}(n)$ are defined in Section 5.2.4.

(5) Let $T\in{\rm STY}((n+k,k))$ be a standard Young tableau of shape
$(n+k,k)$. Denote by $r(T)$ the number of integers $j\in[1,n+k]$ such that the
integer $j$ belongs to the second row of tableau $T$, whereas the number $j+1$
belongs to the first row of $T$.

Show that

$\displaystyle P_{x_{12}^{n}x_{23}\cdots x_{k+1,k+2}}(\beta-1)=\sum_{T\in{\rm
STY}((n+k,k))}\beta^{r(T)}.$

(6) Let $M=(m_{1},m_{2},\ldots,m_{k-1})\in\mathbb{Z}_{>0}^{k-1}$ be a
composition. Denote by $\overleftarrow{M}$ the composition
$(m_{k-1},m_{k-2},\ldots,m_{2},m_{1})$, and set for short

$\displaystyle
P_{M}(\beta):=P_{\prod_{i=1}^{k-1}x_{i,i+1}^{m_{i}}}(x_{ij}=1;\beta).$

Show that $P_{M}(\beta)=P_{\overleftarrow{M}}(\beta)$. Note that in general,

$\displaystyle
P_{\prod\limits_{i=1}^{k-1}x_{i,i+1}^{{m_{i}}}}(x_{ij};\beta)\not=P_{\prod\limits_{i=1}^{k-1}x_{i,i+1}^{m_{k-i}}}(x_{ij};\beta).$

(7) Define polynomial $P_{M}(t,\beta)$ to be the following specialization

$\displaystyle x_{ij}\longrightarrow 1,\quad i<j<n,\qquad
x_{in}\longrightarrow t,\quad i=1,\ldots,n-1$

of a polynomial $P_{\prod\limits_{i=1}^{k-1}x_{i,i+1}^{m_{i}}}(x_{ij};\beta)$.

Show that if $n\geq m$, then

$\displaystyle P_{x_{12}^{n}x_{23}^{m}}(t,\beta)=\sum_{j=0}^{m}{m\choose
j}\left(\sum_{k=m-1}^{n+m-j-1}{k\choose m-1}t^{k-m+1}\right)\beta^{j}.$

See Lemma 5.31 for the case $t=1$.

(8) Define polynomials ${\widetilde{R}}_{n}(t)$ as follows

$\displaystyle{\widetilde{R}}_{n}(t):=P_{(x_{12}x_{23}x_{34})^{n}}\big{(}{-}t^{-1},\beta=-1\big{)}(-t)^{3n}.$

Show that polynomials ${\widetilde{R}}_{n}(t)$ have non-negative coefficients,
and

$\displaystyle{\widetilde{R}}_{n}(0)=\frac{(3n)!}{6(n!)^{3}}.$

$(9)$ Consider reduced polynomial $P_{n,2,2}(\beta)$ corresponding to monomial
$x_{12}^{n}(x_{23}x_{34})^{2}$ and set
${\tilde{P}}_{n,2,2}(\beta):=P_{n,2,2}(\beta-1)$. Show that

$\displaystyle{\tilde{P}}_{n,2,2}(\beta)\in\mathbb{N}[\beta]\qquad\text{and}\qquad{\tilde{P}}_{n,2,2}(1)=T(n+5,3),$

where the numbers $T(n,k)$ are defined in [131, $A110952$, $A001701$].

######  Conjecture 5.87.

Let $\lambda$ be a partition. The element
$s_{\lambda}(\theta_{1}^{(n)},\ldots,\theta_{m}^{(n)})$ of the algebra
$3T_{n}^{(0)}$ can be written in this algebra as a sum of

$\displaystyle\left(\prod_{x\in\lambda}h(x)\right)\times\dim{V_{\lambda^{\prime}}}^{({\mathfrak{gl}}(n-m))}\times\dim{V_{\lambda}}^{({\mathfrak{gl}}(m))}$

monomials with all coefficients are equal to $1$.

Here $s_{\lambda}(x_{1},\ldots,x_{m})$ denotes the Schur function
corresponding to the partition $\lambda$ and the set of variables
$\\{x_{1},\ldots,x_{m}\\}$; for $x\in\lambda,$ $h(x)$ denotes the hook length
corresponding to a box $x$; $V_{\lambda}^{({\mathfrak{gl}}(n))}$ denotes the
highest weight $\lambda$ irreducible representation of the Lie algebra
${\mathfrak{gl}}(n)$.

######  Problems 5.88.

  1. $(1)$

Define a bijection between monomials of the form
$\prod\limits_{a=1}^{s}x_{i_{a},j_{a}}$ involved in the polynomial
$P(x_{ij};\beta)$, and dissections of a convex $(n+2)$-gon by $s$ diagonals,
such that no two diagonals intersect their interior.

  2. $(2)$

Describe permutations $w\in\mathbb{S}_{n}$ such that the Grothendieck
polynomial $\mathfrak{G}_{w}(t_{1},\ldots,t_{n})$ is equal to the “reduced
polynomial” for a some monomial in the associative quasi-classical Yang–Baxter
algebra $\widehat{{\rm ACYB}}_{n}(\beta)$.

  3. $(3)$

Study “reduced polynomials” corresponding to the monomials

     * •

transposition: $s_{1n}:=(x_{12}x_{23}\cdots x_{n-2,n-1})^{2}x_{n-1,n}$,

     * •

powers of the Coxeter element: $(x_{12}x_{23}\cdots x_{n-1,n})^{k}$,

in the algebra $\widehat{{\rm ACYB}}_{n}(\alpha,\beta)^{ab}$.

  4. $(4)$

Construct a bijection between the set of $k$-dissections of a convex
$(n+k+1)$-gon and “pipe dreams” corresponding to the Grothendieck polynomial
$\mathfrak{G}_{\pi_{k}^{(n)}}^{(\beta)}(x_{1},\ldots,x_{n})$. As for a
definition of “pipe dreams” for Grothendieck polynomials, see [78] and [42].

######  Comments 5.89.

We don’t know any “good” combinatorial interpretation of polynomials which
appear in Problem 5.88(3) for general $n$ and $k$. For example,

$\displaystyle P_{s_{13}}(x_{ij}=1;\beta)=(3,2)_{\beta},\qquad
P_{s_{14}}(x_{ij}=1;\beta)=(26,42,19,2)_{\beta},$ $\displaystyle
P_{s_{15}}(x_{ij}=1;\beta)=(381,988,917,362,55,2)_{\beta},\qquad
P_{s_{15}}(x_{ij}=1;1)=2705.$

On the other hand,

$\displaystyle
P_{(x_{12}x_{23})^{2}x_{34}(x_{45})^{2}}(x_{ij}=1;\beta)=(252,633,565,212,30,1),$

that is in deciding on different reduced decompositions of the transposition
$s_{1n}$. one obtains in general different reduced polynomials.

One can compare these formulas for polynomials $P_{s_{ab}}(x_{ij}=1;\beta)$
with those for the $\beta$-Grothendieck polynomials corresponding to
transpositions $(a,b)$, see Comments 5.37.

####  5.4.1 Reduced polynomials, Motzkin and Riordan numbers

In this subsection we investigate reduced polynomials associated with Coxeter
element $C_{n}=u_{12}u_{23}\cdots u_{n-1,n}$ in commutative algebra
${\widehat{{\rm ACYB}}}_{n}(\alpha,\beta)$ in more detail. Recall that this
algebra is generated over the ring $\mathbb{Z}[z,\alpha,\beta]$ by the set of
elements $\\{u_{i,j},\,1\leq i<j\leq n\\}$ subject to the following relations

$\displaystyle u_{ij}u_{jk}=u_{ik}u_{ij}+u_{jk}u_{ik}+\beta
u_{ik}+\alpha,\qquad i<j<k.$

Show that

$\displaystyle P_{n}(1,1,\beta=-1)=M_{n},$

where $M_{n}$ denotes the $n$-th Motzkin number that is the number of Motzkin
$n$-paths: paths from $(0,0)$ to $(n,0)$ in an $n\times n$ grid using only
steps $U=(1,1)$, $(1,0)$ and $(1,-1)$. It is also the number of Dyck
$(n+1)$-paths with no steps $UUU$, see [131, $A001006$] for a wide variety of
combinatorial interpretations, and vast literature concerning the Motzkin
numbers. For example,

$\displaystyle P_{7}(0,1,\beta=-1)=36+37+24+18+5+6+0+1=127=M_{7}.$

Therefore we treat the polynomials $P_{n}(t,\alpha,\beta=-1)$ as the
$(t,\alpha)$-Motzkin numbers. For example,

$\displaystyle P_{7}(t,\alpha,\beta=-1)=t^{7}+6\alpha t^{5}+5\alpha
t^{4}+(0,4,14)_{\alpha}t^{3}+(0,3,21)_{\alpha}t^{2}+(0,2,21,14)_{\alpha}t$
$\displaystyle\qquad{}+(0,1,14,21)_{\alpha}=t^{7}+\alpha(1,2,3,4,5,6)_{t}+\alpha^{2}(14,21,21,14)_{t}+\alpha^{3}(21,14)_{t}.$

Therefore

$\displaystyle P_{7}(t,1,\beta=-1)=1+21\alpha+70\alpha^{2}+35\alpha^{3},\qquad
P_{7}(1,1,\beta=-1)=127=M_{7}.$

Show that

$\displaystyle P_{n}(0,1,\beta=-1)=A005043(n),$

known as the Riordan number, or Motzkin sum [131]. This number, denoted by
$MS_{n}$, counts the number of Motzkin paths of length $n$ with no horizontal
steps at level zero; it is also equal to the number of Dyck paths of
semilenght $n$ with no peaks at odd level, see [131, $A005043$] for a bit more
combinatorial interpretations, and literature concerning the Motzkin sum or
Riordan numbers. For example,

$\displaystyle P_{7}(t,1,-1)=({\bf 36},37,24,18,5,6,0,1),\qquad 36=MS_{7}.$

Show that the Riordan number $MS_{n}$ is equal to the number of underdiagonal
paths from $(0,0)$ to the line $x=n-2$, using only steps $(1,0)$, $(0,1)$ and
$NE=(2,1)$ and beginning with the step $NE=(2,1)$. Note that the number of
such paths with no steps $NE$ is equal to the Catalan number ${\rm
Cat}_{n-1}$.

Let ${\cal{MS}}=\\{n\in\mathbb{N}\,|\,n=2^{2k}(2r+1)-1,\,k\geq 1,\,r\geq 0\\}$
be a subset of the set of all odd integers [31]. Show that

$(a)$ $MS_{n}\equiv 1$ $({\rm mod}~{}2)$, if either $n\equiv 0$ $({\rm
mod}~{}2)$ or $n\in{\cal{MS}}_{n}$,

$(b)$ $MS_{n}\equiv 0$ $({\rm mod}~{}2)$, if $n$ is an odd integer and
$n\notin{\cal{MS}}$.

Show that

$\displaystyle\frac{P_{n}(0,\alpha,\beta)}{\alpha}\Big{|}_{\alpha=0}=N_{n-1}(\beta+1),$

where as before, $N_{n}(t)$ denotes the Narayana polynomial.

Let us set

$\displaystyle P_{n}(0,\alpha,\beta)=\sum_{k\geq 0}c_{k}(\beta+1)\alpha^{k}.$

Show that polynomials $c_{k}(\beta+1)$, $k\geq 0$ are symmetric (unimodal?)
polynomials of the variable $\beta+1$.

Show that [131]

$\displaystyle P_{n}(1,1,0)=A052709(n+1).$

Show that [131]

$\displaystyle P_{n}(0,1,0)=A052705(n)$

that is the number of underdiagonal paths from $(0,0)$ to the line $x=n-2$,
using only steps $R=(1,0)$, $V=(0,1)$ and $NE=(2,1)$.

For example,

$\displaystyle P_{7}(0,10)={\bf 36}+106+120+64+15+1=342=A052705(7).$

Show that [131]

$\displaystyle{\frac{\partial}{\partial\alpha}}P_{n}(t,\alpha,\beta)\Big{|}_{{\alpha=0,\atop\beta=0,}\atop
t=1}=A05775(n-1),$

that is the number of paths in the half-plane $x\geq 0$ from $(0,0)$ to
$(n-1,2)$ or $(n-1,-3)$, and consisting of steps $U=(1,1)$, $D=(1,-1)$ and
$H=(1,0)$. For example,

$\displaystyle{\rm l.h.s.}=106+130+99+48+5+6=427=A05775(6).$

Let us set

$\displaystyle P_{n}(t,\alpha,\beta=1):=\sum_{k,l\geq
0}c_{k,l}^{(n)}t^{k}\alpha^{l}.$

Show that

$\displaystyle(a)\quad\sum_{k=1}^{n}c_{k,n-k}^{(n)}t^{k}\alpha^{n-k}=(t+\alpha)^{n-1},$
$\displaystyle(b)\quad c_{k,n-k-1}^{(n)}=(k+1)\binom{n-1}{k+2},\qquad 0\leq
k\leq n-3,$ $\displaystyle(c)\quad
c_{1,0}^{(n)}=c_{0,0}^{(n)}+(-1)^{n-1},\qquad n\geq 3.$

####  5.4.2 Reduced polynomials, dissections and Lagrange inversion formula

Let $\\{a_{i},b_{i},\beta_{i},\alpha_{i},\,1\leq i\leq n-1\\}$ be a set of
parameters, consider non commutative algebra generated over the ring
$Z[\\{a_{i},b_{i},\beta_{i},\alpha_{i}\\}_{1\leq i\leq n-1}]$ by the set of
generators $\\{u_{ij},\,1\leq i<j\leq n\\}$ subject to the set of relations

$\displaystyle u_{ij}u_{jk}=a_{i}u_{ik}u_{ij}+b_{i}u_{jk}u_{ik}+\beta
u_{ik}+\alpha_{i},\qquad 1\leq i<j<k\leq n.$

Consider reduced expression $R_{n}(\\{u_{ij}\\}_{1\leq i<j\leq n})$ in the
above algebra which corresponds to the “Coxeter element”

$\displaystyle C_{n}:=u_{12}u_{23}\cdots u_{n-1,n}.$

Note that the reduced expression $R_{n}(\\{u_{ij}\\})$ is a linear combination
of noncommutative monomials in the generators $\\{u_{ij},\,1\leq i<j\leq n\\}$
with coefficients from the ring

$\displaystyle K_{n}:=\mathbb{Z}[\\{a_{i},b_{i},\beta_{i},\alpha_{i}\\}_{1\leq
i<n}].$

Now to each monomial $U$ which appears in the reduced expression
$R_{n}(\\{u_{ij}\\})$ we associate a dissection ${\cal D}:={\cal D}_{U}$ of a
convex $(n+1)$-gon as follows. First of all let us label the vertices of a
convex $(n+1)$-gon selected, by the numbers $n+1,n,\ldots,1$, written
consequently and clockwise, starting from a fixed vertex, from here on named
by $(n+1)$-vertex.

Next, let us take a monomial $U=u_{i_{1},j_{1}}\cdots u_{i_{p},j_{p}}$ which
appears in the reduced expression $R_{n}(\\{u_{ij}\\})$ with coefficient
$c(U)\in K_{n}$. We draw diagonals in a convex $(n+1)$-gon chosen which
connect vertices labeled correspondingly by numbers $i_{s}$ and $j_{s}+1$,
$s=1,\ldots,p$. It is clearly seen from the defining relations in the algebra
in question when being applied to the Coxeter element above, that in fact, the
diagonals we have drawn in a convex $(n+1)$-gon selected, do not meet at
interior points of our convex $(n+1)$-gon. Therefore, to each monomial $U$
which appears in the reduced polynomial associated with the Coxeter element
$C_{n}$ above, one can associate a dissecion ${\cal D}:={\cal D}_{U}$ of a
convex $(n+1)$-gon selected. Moreover, it is not difficult to see (e.g., cf.
[58]) that there exists a natural bijection $U\Longleftrightarrow{\cal D}_{U}$
between monomials which appear in the reduced expression $R_{n}(\\{u_{ij}\\})$
and the set of dissections of a convex $(n+1)$-gon. As a corollary, to each
dissection ${\cal D}:={\cal D}_{U}$ of a conves $(n+1)$-gon one can attache
the element $c({\cal D}):=c(U)\in K_{n}$ which is equal to the coefficient in
front of monomial $U$ in the reduced expression corresponding to the Coxeter
element $C_{n}$.

To continue, let ${\boldsymbol{x}}=(x_{1},\ldots,x_{n-1})$,
${\boldsymbol{y}}=(y_{1},\ldots,y_{n-1})$ and
${\boldsymbol{z}}=(z_{1},\ldots,z_{n-1})$ be three sets of variables, and
${\cal D}$ be a dissection of a convex $(n+1)$-gon. We associate with
dissection ${\cal D}$ a monomial $m({\cal D})\in K_{n}$ as follows

$\displaystyle m({\cal
D}):=\prod_{k=1}^{n-1}x_{k}^{n(k)}y_{k}^{m(k)}z_{r(k)},$

where $m(k):=m_{k}({\cal D})$ (resp. $r(k):=r_{k}({\cal D})$ and
$n(k):=n_{k}({\cal D})$) denotes the number of (convex) $(m_{k}+2)$-gons
constituent a dissection ${\cal D}$ taken (resp. the number of diagonals issue
out of the vertex labeled by $(n+1)$; $n_{k}({\cal D}))$ stands for the number
of (oriented) diagonals and edges which issue out of the vertex labeled by
$k$, $k=1,\ldots,n$). Therefore we associate with the reduced polynomial
corresponding to the Coxeter element $u_{12},\dots,u_{n-1,n}$ the following
polynomial

$\displaystyle{\rm
PL}_{n}({\boldsymbol{a}},{\boldsymbol{b}},{\boldsymbol{\beta}},{\boldsymbol{\alpha}},{\boldsymbol{x}},{\boldsymbol{y}},{\boldsymbol{z}})=\sum_{\cal
D}m({\cal D}){c({\cal D})},$

where the sum runs over all dissections ${\cal D}$ of a convex $(n+1)$-gon.

To begin with we set ${\boldsymbol{x}}={\bf 1}$ and consider the following
specializations

$\displaystyle B_{n}({\boldsymbol{a}},{\boldsymbol{y}})={\rm
PL}_{n}({\boldsymbol{a}},{\boldsymbol{b}}={\bf 1},{\boldsymbol{\beta}}={\bf
1},{\boldsymbol{\alpha}}={\bf 0},{\boldsymbol{y}},{\boldsymbol{z}}={\bf 1}),$
$\displaystyle
P_{n}({\boldsymbol{z}},{\boldsymbol{a}},{\boldsymbol{b}},{\boldsymbol{\beta}})={\rm
PL}_{n}({\boldsymbol{a}},{\boldsymbol{b}},{\boldsymbol{\beta}},{\boldsymbol{\alpha}}={\bf
0},{\boldsymbol{y}}={\bf 1},{\boldsymbol{z}}),$

Show that

$\displaystyle B_{n-1}({\boldsymbol{a}},{\boldsymbol{y}}))={\rm
Coef\/f}_{t^{n}}\big{(}z-f(ty_{1},\ldots,ty_{n})\big{)}^{[-1]},$

where $f(y_{1},\ldots,y_{n})=\sum\limits_{k=1}^{n-1}y_{k}u^{k+1}$, and for any
formal power series $g(u)$, ${\frac{d}{du}}g(u)|_{u=0}=1$, we denote by
$g(u)^{[-1]}$ the Lagrange Inverse formal power series associated with that
$g(u)$ that is a unique formal power series such that
$g(g^{[-1]}(u))=u=g^{[-1]}(g(u))$.

Now let us recall the statement of Lagrange’s inversion theorem. Namely, let

$\displaystyle f(x)=x-\sum_{k\geq 1}y_{k}x^{k+1}$

be a formal power series. Then the inverse power series $f^{[-1]}(u)$ is given
by the following formula

$\displaystyle f^{[-1]}(y)=\sum_{n\geq 1}w_{n}u^{n},$

where

$\displaystyle
w_{n}:=w_{n}(p_{1},\ldots,p_{n})={\frac{1}{n+1}}\sum_{p_{1},\ldots,p_{n}\geq
0\atop\sum jp_{j}=n}\binom{n+\sum
p_{j}}{n,p_{1},\ldots,p_{n}}y_{1}^{p_{1}}y_{2}^{p_{2}}\cdots y_{n}^{p_{n}},$

where if $N=m_{1}+\cdots+m_{n}$, then

$\displaystyle\binom{N}{m_{1},\ldots,m_{n}}=\frac{N!}{m_{1}!m_{2}!\cdots
m_{n}!}$

denotes the multinomial coefficient.

Therefore, the coefficient

$\displaystyle b_{n}(p_{1},\ldots,p_{n}):={\frac{1}{n+1}}\binom{n+\sum
p_{j}}{n,p_{1},\ldots,p_{n}},\qquad\sum_{j}jp_{j}=n$

is equal to the number of dissections of a convex $(n+2)$-gon which contain
exactly $p_{j}$ convex $(j+2)$-gons, see, e.g., [38]. Equivalently, the number
$b_{n}(p_{1},\ldots,p_{n})$ is equal to the number of cells of the
associahedron ${\cal K}^{n-1}$ which are isomorphic to the cartesian product
$({\cal{K}}^{0})^{p_{1}}\times\cdots\times({\cal{K}}^{n-1})^{p_{n}}$ [90, 91].
Based on a natural and well-known bijection between the set of dissections of
a convex $(n+2)$-gon and the set of plane trees with $(n+1)$ ends and such
that the all other vertices have degree at least $2$, see, e.g., [134], one
can readily seen that the number $w_{n}(p_{1},\ldots,p_{n})$ defined above
under constraint $\sum_{j}jp_{j}=n$, is equal to the number of plane trees
with $n+1$ ends and having $p_{j}$ vertices of degree $j+1$.

######  Example 5.90.

For short we set $B_{n}={\rm
PL}_{n}({\boldsymbol{a}},{\boldsymbol{b}},{\boldsymbol{\beta}},{\boldsymbol{\alpha}},{\boldsymbol{x}},{\boldsymbol{y}})$.

(1) Quadrangular:

$\displaystyle
B_{2}=y_{1}^{2}(a_{1}z_{1}+b_{1}z_{1}z_{2})+y_{2}(\beta_{1}z_{1}+\alpha_{1}).$

(2) Pentagon:

$\displaystyle
B_{3}=y_{1}^{3}\big{(}a_{1}^{2}z_{1}+a_{1}b_{1}z_{1}+a_{2}b_{1}^{2}z_{1}z_{2}+a_{1}b_{1}z_{1}z_{3}+b_{1}^{2}b_{2}z_{1}z_{2}z_{3}\big{)}$
$\displaystyle\hphantom{B_{3}=}{}+y_{1}y_{2}\big{(}2a_{1}\beta_{1}z_{1}+b_{1}\beta_{1}z_{1}+b_{1}^{2}\beta_{2}z_{1}z_{2}+b_{1}\beta_{1}z_{1}z_{3}+a_{1}\alpha_{1}b_{1}\alpha_{1}+\alpha_{1}z_{3}\big{)}$
$\displaystyle\hphantom{B_{3}=}{}+y_{3}\big{(}\beta_{1}\alpha_{1}+\beta_{1}^{2}z_{1}+b_{1}^{2}\alpha_{2}z_{1}\big{)}.$

(3) Hexagon:

$\displaystyle
B_{4}={y_{1}^{4}}\big{(}\big{(}a_{1}^{3}+2a_{1}^{2}b_{1}+a_{1}a_{2}b_{1}^{2}+a_{1}b_{1}^{2}b_{2}\big{)}z_{1}$
$\displaystyle\hphantom{B_{4}=}{}+a_{1}^{2}b_{1}b_{2}z_{1}z_{2}+a_{2}b_{1}^{3}b_{2}z_{1}z_{2}+a_{1}a_{3}b_{1}^{2}z_{1}z_{3}+a_{1}^{2}b_{1}z_{1}z_{4}+a_{1}b_{1}^{2}z_{1}z_{4}+a_{3}b_{1}^{3}b_{2}^{2}z_{1}z_{2}z_{3}$
$\displaystyle\hphantom{B_{4}=}{}+a_{2}b_{1}^{2}b_{2}z_{1}z_{2}z_{4}+a_{1}b_{1}^{2}b_{3}z_{1}z_{3}z_{4}+b_{1}^{3}b_{2}^{2}b_{3}z_{1}z_{2}z_{3}z_{4}\big{)}+{y_{1}^{2}y_{2}}\big{(}a_{1}^{2}\alpha_{1}+2a_{1}b_{1}\alpha_{1}+a_{2}b_{1}^{2}\alpha_{1}$
$\displaystyle\hphantom{B_{4}=}{}+b_{1}^{2}b_{2}\alpha_{1}+(3a_{1}^{2}b\beta_{1}+4a_{1}b_{1}\beta_{1}+a_{2}b_{1}^{2}\beta_{1}+b_{1}^{2}+b_{2}\beta_{1}+a_{1}b_{1}^{2}\beta_{2})z_{1}+a_{2}b_{1}^{2}\beta_{2}z_{1}z_{2}$
$\displaystyle\hphantom{B_{4}=}{}+b_{1}^{3}b_{2}\beta_{2}z_{1}z_{2}+a_{2}b_{1}^{3}\beta_{2}z_{1}z_{2}+a_{1}b_{1}^{2}b_{3}z_{1}z_{3}+a_{1}b_{1}\beta_{1}z_{1}z_{3}+a_{3}b_{1}^{2}z_{1}z_{3}+b_{1}^{2}\beta_{1}z_{1}z_{4}$
$\displaystyle\hphantom{B_{4}=}{}+a_{1}b_{1}\beta_{1}z_{1}z_{4}+b_{1}^{2}b_{2}\beta_{3}z_{1}z_{2}z_{3}+b_{1}^{3}b_{2}\beta_{2}z_{1}z_{2}z_{4}+b_{1}^{2}b_{3}\beta_{1}z_{1}z_{3}z_{4}\big{)}+{y_{1}y_{3}}\big{(}a_{1}\beta_{1}\alpha_{1}$
$\displaystyle\hphantom{B_{4}=}{}+2b_{1}\beta_{1}\alpha_{1}+\big{(}2a_{1}\beta_{1}^{2}+2b_{1}\beta_{1}^{2}a_{1}b_{1}^{2}\alpha_{3}+a_{2}b_{1}^{2}\alpha_{2}+b_{1}^{3}b_{2}\alpha_{2}\big{)}z_{1}+b_{1}^{3}b_{2}\alpha_{3}z_{1}z_{2}+b_{1}^{3}\beta_{2}^{2}z_{1}z_{2}$
$\displaystyle\hphantom{B_{4}=}{}+b_{1}^{3}\alpha_{3}z_{1}z_{4}+b_{3}\alpha_{1}z_{3}z_{3}z_{4}+a_{3}\alpha_{1}z_{3}+a_{1}\alpha_{1}z_{4}+b_{1}\alpha_{1}z_{4}+\beta_{1}\alpha_{1}z_{4}\big{)}+{y_{2}^{2}}\big{(}a_{1}\beta_{1}\alpha_{1}$
$\displaystyle\hphantom{B_{4}=}{}+b_{1}^{2}\beta_{2}\alpha_{2}+\big{(}b_{1}^{2}\beta_{1}\beta_{2}+a_{1}\beta_{1}^{2}+a_{1}\beta_{1}^{2}\alpha_{2}\big{)}z_{1}+\beta_{3}\alpha_{1}z_{3}+b_{1}\beta_{1}\beta_{3}z_{1}z_{3}\big{)}+{y_{4}}(\alpha_{1}\alpha_{3}+\beta_{1}^{2}\alpha_{1}$
$\displaystyle\hphantom{B_{4}=}{}+b_{1}^{2}\alpha_{1}\alpha_{2}\big{(}b_{1}^{2}\beta_{1}\alpha_{2}+b_{1}^{3}\beta_{2}\alpha_{2}+\beta_{1}^{3}+b_{1}^{2}\beta_{1}\alpha_{3}\big{)}z_{1}\big{)}.$

_Special cases._ Generalized Schröder or Lagrange polynomials:

$\displaystyle
P_{n}({\boldsymbol{a}},{\boldsymbol{b}},{\boldsymbol{\beta}},{\boldsymbol{y}},{\boldsymbol{z}})=B_{n}\big{|}_{{\boldsymbol{\alpha}}={\bf
0}}.$

For example,

$\displaystyle
P_{4}({\boldsymbol{a}},{\boldsymbol{b}},{\boldsymbol{y}})={y_{1}^{4}}\big{(}\big{(}a_{1}^{3}+2a_{1}^{2}b_{1}+a_{1}a_{2}b_{1}^{2}+a_{1}b_{1}^{2}b_{2}\big{)}z_{1}+a_{1}^{2}b_{1}b_{2}z_{1}z_{2}+a_{2}b_{1}^{3}b_{2}z_{1}z_{2}+a_{1}a_{3}b_{1}^{2}z_{1}z_{3}$
$\displaystyle\hphantom{P_{4}({\boldsymbol{a}},{\boldsymbol{b}},{\boldsymbol{y}})=}{}+a_{1}^{2}b_{1}z_{1}z_{4}+a_{1}b_{1}^{2}z_{1}z_{4}+a_{3}b_{1}^{3}b_{2}^{2}z_{1}z_{2}z_{3}+a_{2}b_{1}^{2}b_{2}z_{1}z_{2}z_{4}+a_{1}b_{1}^{2}b_{3}z_{1}z_{3}z_{4}$
$\displaystyle\hphantom{P_{4}({\boldsymbol{a}},{\boldsymbol{b}},{\boldsymbol{y}})=}{}+b_{1}^{3}b_{2}^{2}b_{3}z_{1}z_{2}z_{3}z_{4}\big{)}+{y_{1}^{2}y_{2}}\big{(}\big{(}3a_{1}^{2}b\beta_{1}+4a_{1}b_{1}\beta_{1}+a_{2}b_{1}^{2}\beta_{1}+b_{1}^{2}+b_{2}\beta_{1}$
$\displaystyle\hphantom{P_{4}({\boldsymbol{a}},{\boldsymbol{b}},{\boldsymbol{y}})=}{}+a_{1}b_{1}^{2}\beta_{2}\big{)}z_{1}+a_{2}b_{1}^{2}\beta_{2}z_{1}z_{2}+b_{1}^{3}b_{2}\beta_{2}z_{1}z_{2}+a_{2}b_{1}^{3}\beta_{2}z_{1}z_{2}+a_{1}b_{1}^{2}b_{3}z_{1}z_{3}$
$\displaystyle\hphantom{P_{4}({\boldsymbol{a}},{\boldsymbol{b}},{\boldsymbol{y}})=}{}+a_{1}b_{1}\beta_{1}z_{1}z_{3}+a_{3}b_{1}^{2}z_{1}z_{3}+b_{1}^{2}\beta_{1}z_{1}z_{4}+a_{1}b_{1}\beta_{1}z_{1}z_{4}+b_{1}^{2}b_{2}\beta_{3}z_{1}z_{2}z_{3}$
$\displaystyle\hphantom{P_{4}({\boldsymbol{a}},{\boldsymbol{b}},{\boldsymbol{y}})=}{}+b_{1}^{3}b_{2}\beta_{2}z_{1}z_{2}z_{4}+b_{1}^{2}b_{3}\beta_{1}z_{1}z_{3}z_{4}\big{)}+{y_{1}y_{3}}\big{(}2a_{1}\beta_{1}^{2}+2b_{1}\beta_{1}^{2}+b_{1}^{3}\beta_{2}^{2}z_{1}z_{2}$
$\displaystyle\hphantom{P_{4}({\boldsymbol{a}},{\boldsymbol{b}},{\boldsymbol{y}})=}{}+b_{1}\beta_{1}^{2}z_{1}z_{4}\big{)}+{y_{2}^{2}}\big{(}\big{(}b_{1}^{2}\beta_{1}\beta_{2}+a_{1}\beta_{1}^{2}\big{)}z_{1}+b_{1}\beta_{1}\beta_{3}z_{1}z_{3}\big{)}+{y_{4}}\beta_{1}^{3}z_{1}.$

After the specialization $a_{i}=b_{i}=\beta_{i}=z_{i}=1$, $i=1,2,3,4$, one
will obtain

$\displaystyle P_{4}({\boldsymbol{a}}={\bf 1},{\boldsymbol{b}}={\bf
1},{\boldsymbol{\beta}}={\bf 1},{\boldsymbol{y}},{\boldsymbol{z}}={\bf
1})=14y_{1}^{4}+21y_{1}^{2}y_{2}+6y_{1}y_{3}+3y_{2}^{2}+y_{4}.$

Generalized Narayana polynomials:

$\displaystyle
P_{n}({\boldsymbol{a}},{\boldsymbol{b}},{\boldsymbol{y}},{\boldsymbol{z}})=B_{n}\big{|}_{{\boldsymbol{\alpha}}={\bf
0}\atop{\boldsymbol{\beta}}={\bf 0}},$ $\displaystyle
P_{n}({\boldsymbol{a}},{\boldsymbol{b}},{\boldsymbol{y}},{\boldsymbol{z}})={y_{1}^{4}}\big{(}\big{(}a_{1}^{3}+2a_{1}^{2}b_{1}+a_{1}a_{2}b_{1}^{2}+a_{1}b_{1}^{2}b_{2}\big{)}z_{1}+a_{1}^{2}b_{1}b_{2}z_{1}z_{2}+a_{2}b_{1}^{3}b_{2}z_{1}z_{2}$
$\displaystyle\hphantom{P_{n}({\boldsymbol{a}},{\boldsymbol{b}},{\boldsymbol{y}},{\boldsymbol{z}})=}{}+a_{1}a_{3}b_{1}^{2}z_{1}z_{3}+a_{1}^{2}b_{1}z_{1}z_{4}+a_{1}b_{1}^{2}z_{1}z_{4}+a_{3}b_{1}^{3}b_{2}^{2}z_{1}z_{2}z_{3}+a_{2}b_{1}^{2}b_{2}z_{1}z_{2}z_{4}$
$\displaystyle\hphantom{P_{n}({\boldsymbol{a}},{\boldsymbol{b}},{\boldsymbol{y}},{\boldsymbol{z}})=}{}+a_{1}b_{1}^{2}b_{3}z_{1}z_{3}z_{4}+b_{1}^{3}b_{2}^{2}b_{3}z_{1}z_{2}z_{3}z_{4}\big{)}.$

Generalized Motzkin–Schröder polynomials:

$\displaystyle{\rm
MS}_{n}({\boldsymbol{a}},{\boldsymbol{b}},{\boldsymbol{y}},{\boldsymbol{z}})=B_{n}\big{|}_{{\boldsymbol{a}}={\bf
0}}.$

For example,

$\displaystyle{\rm
MS}_{4}({\boldsymbol{a}},{\boldsymbol{b}},{\boldsymbol{y}},{\boldsymbol{z}})={y_{1}^{1}y_{2}}\big{(}a_{1}^{2}\alpha_{1}+2a_{1}b_{1}\alpha_{1}+a_{2}b_{1}^{2}\alpha_{1}+b_{1}^{2}b_{2}\alpha_{1}\big{)}+{y_{1}y_{3}}(a_{1}\beta_{1}\alpha_{1}+2b_{1}\beta_{1}\alpha_{1})$
$\displaystyle\hphantom{{\rm
MS}_{4}({\boldsymbol{a}},{\boldsymbol{b}},{\boldsymbol{y}},{\boldsymbol{z}})=}{}+{y_{2}^{2}}\big{(}a_{1}\beta_{1}\alpha_{1}+b_{1}^{2}\beta_{2}\alpha_{2}\big{)}+{y_{4}}\big{(}\alpha_{1}\alpha_{3}+b_{1}^{2}\alpha_{1}\alpha_{2}+\beta_{1}^{2}\alpha_{1}\big{)}.$

Generalized Motzkin polynomials:

$\displaystyle
M_{n}({\boldsymbol{b}},{\boldsymbol{y}},{\boldsymbol{z}})=B_{n}\big{|}_{{\boldsymbol{a}}={\bf
0}\atop{\boldsymbol{\beta}}={\bf 0}}.$

For example,

$\displaystyle
M_{4}({\boldsymbol{b}},{\boldsymbol{y}},{\boldsymbol{z}})={y_{1}^{4}}b_{1}^{3}b_{2}^{2}b_{3}z_{1}z_{2}z_{3}z_{4}+{y_{1}^{2}y_{2}}b_{1}^{2}b_{2}\alpha_{1}+{y_{1}y_{3}}\big{(}b_{1}^{3}b_{2}\alpha_{2}+b_{1}\alpha_{1}z_{4}+b_{1}^{3}b_{2}z_{1}z_{3}$
$\displaystyle\hphantom{M_{4}({\boldsymbol{b}},{\boldsymbol{y}},{\boldsymbol{z}})=}{}+b_{1}^{3}\alpha_{2}z_{1}z_{4}+b_{3}\alpha_{1}z_{3}z_{4}\big{)}+{y_{4}}\big{(}\alpha_{2}\alpha_{3}+b_{1}^{2}\alpha_{1}\alpha_{2}\big{)}.$

Generalized Motzkin–Riordan polynomials:

$\displaystyle{\rm
MR}_{n}({\boldsymbol{a}},{\boldsymbol{b}},{\boldsymbol{\beta}},{\boldsymbol{\alpha}},{\boldsymbol{y}})=B_{n}\big{|}_{{\boldsymbol{z}}={\bf
0}}.$

Generalized Riordan polynomials:

$\displaystyle{\rm
RI}_{n}({\boldsymbol{b}},{\boldsymbol{\alpha}},{\boldsymbol{y}})=B_{n}\big{|}_{{\boldsymbol{z}}={\bf
0}{\top{\boldsymbol{a}}={\bf 0}}\atop{\boldsymbol{\beta}}={\bf 0}}.$

For example,

$\displaystyle{\rm
RI}_{4}({\boldsymbol{b}},{\boldsymbol{\alpha}},{\boldsymbol{y}})={y_{1}^{2}y_{2}}b_{1}^{2}b_{2}\alpha_{1}+{y_{4}}\big{(}\alpha_{2}\alpha_{3}+b_{1}^{2}\alpha_{1}\alpha_{2}\big{)}.$

Let us set $B_{n}(y_{1},\ldots,y_{n})=B_{n}({\boldsymbol{a}}={\bf
1},{\boldsymbol{b}}={\bf 1},{\boldsymbol{\beta}}={\bf 1},{\boldsymbol{y}})$.
Let $\beta$ be a new parameter. Show that

$\displaystyle B(1,\beta,\ldots,\beta^{n-1})=\mathfrak{G}_{1\times
w_{0}^{(n-1)}}^{(\beta)}(\underbrace{1,\ldots,1}_{n}),$

where $\mathfrak{G}_{w}^{(\beta)}(X)$ denotes the $\beta$-Grothendieck
polynomial corresponding to a permutation $w\in\mathbb{S}_{n}$. In particular,

$\displaystyle B_{n}(\underbrace{1,\ldots,1}_{n})={\rm Sch}_{n},$

where ${\rm Sch}_{n}$ denotes the $n$-th Schröder number, that is the numbers
of paths from $(0,0)$ to $(2n,0)$, using only steps northeast $U=(1,1)$ or or
$D=(1,-1)$) or double $H=(2,0)$, that never fall below the $x$-axis.

Assume that $n$ is devisible by an integer $d\geq 1$. Show that if
${\boldsymbol{y}}=(y_{j}=\delta_{j+1,d})$, then

$\displaystyle B_{n}(0,\ldots,0,\underbrace{1}_{d-1},0,\ldots,0)={\rm
FC}_{n/d}^{(d+1)},$

where ${\rm FC}_{m}^{p}$ denotes the Fuss–Catalan number, see, e.g., [134],
and [131, $A001764$] for a variety of combinatorial interpretations the
Fuss–Catalan numbers ${\rm FC}_{n}^{(3)}$.

More generally, let $2<d_{1}<\cdots<d_{k}$ be a sequence of integers, and set

$\displaystyle{\boldsymbol{y}}=(\delta_{i+1,d_{j}},\,1\leq j\leq k).$

Show that the specialization $B_{n}({\boldsymbol{y}})$ counts the number of
dissections of a convex $(n+2)$-gon on parts which are convex $(d+2)$-gons,
where each $d$ belongs to the set $\\{d_{1},\ldots,d_{k}\\}$. We would like to
point out that the polynomials

$\displaystyle{\rm FS}_{n}^{(d)}:={\rm
Coef\/f}_{y_{d}^{n}}\big{(}P_{nd}({\boldsymbol{a}},{\boldsymbol{b}},{\boldsymbol{\beta}},{\boldsymbol{y}}=(\delta_{i+1,d}),{\boldsymbol{z}})\big{)}.$

can be treated as a multi-parameter analogue of the Fuss–Catalan numbers ${\rm
FC}_{n}^{(d+1)}$.

Colored dissections [127]. A colored dissection of a convex polygon is a
dissection where each $(d+1)$-gon appearing in the dissection can be colored
by one of $b_{d}$ possible colors616161We assume that if $b_{d}=0$, then the
dissection in question doesn’t contain parts which are $(d+1)$-gons., $d\geq
2$ [127]. Show [127] that if $b_{2},\ldots,b_{n}$ be a sequence of non-
negative integers, $B_{n}(b_{2},\ldots,\ldots,b_{n})$ is equal to the number
of colored dissections of a convex $(n+2)$-gon.

Consider the specialization $y_{i}=i-1$, $i=1,\ldots,n$. Show that

$\displaystyle B_{n}(y):={\rm SL}(0,1,\ldots,n-1)={\rm Fine}(n+1),$

where ${\rm Fine}(m)$ denotes the $m$-th Fine number, that is the number of
ordered rooted trees with $m$ edges having root of even degree [131,
$A000957$]. Therefore, the Fine number $Fine(n+1)$ counts the number of
dissections of a convex $(n+2)$-gon such that each $(d+3)$-gon appearing in
the dissection can be colored by $d$ possible colors, $d\geq 1$.

Consider the specialization $y_{3k+1}=1$, $y_{3k+2}=0$, $y_{3k+3}=-1$, $k\geq
0$. Show that

$\displaystyle B_{n}(y_{1},\ldots,y_{n})=M_{n},$

where $M_{n}$ denotes the $n$-th Motzkin number [131, $A001006$].

Recall that it is the number of ways to draw any number of nonintersecting
chord joining $n$ labeled points on a circle. The number $M_{n}$ is also
equals to the number of Motzkin paths, that is paths from $(0,0)$ to $(n,n)$
in the $n\times n$ grid using only steps $U=(1,1)$, $H=(1,0)$ and $D=(1,-1)$,
see [131, $A001006$] for references and a wide variety of combinatorial
interpretations of Motzkin’s numbers.

Consider the specialization $y_{3k+1}=0$, $y_{3k+2}=(-1)^{k}$,
$y_{3k+3}=(-1)^{k}$, $k\geq 0$. Show that

$\displaystyle B_{n}(y_{1},\ldots,y_{n})={\rm MS}_{n},$

where ${\rm MS}_{n}$ denotes the Motzkin sum or Riordan number [131,
$A005043$].

Recall that it is the number of Motzkin paths of length $n$ with no horizontal
steps $H=(1,0)$ at level zero, see [131, $A005043$] for references and a wide
variety of combinatorial interpretations of Riordan’s numbers.

Consider the specialization $y_{2k+1}=(-1)^{k}$, $y_{2k}=(-1)^{k+1}$, $k\geq
0$. Show that [131]

$\displaystyle B_{n}(y_{1},\ldots,y_{n})=A052709(n),$

that is the number of underdiagonal lattice paths from $(0,0)$ to $(n-1,n-1)$
and such that each step is either $H=(1,0)$, $V=(0,1)$, or $D=(2,1)$.

Consider specialization $y_{k}=(-1)^{k}\frac{n!}{k!}$, $k\geq 1$. Show that

$\displaystyle B_{n}(y_{1},\ldots,y_{n})=n^{n-2},$

that is the number of parking functions, see, e.g., [55, 134] and the
literature quoted therein.

Consider the specialization $y_{k}=\frac{n!}{k!}$. Show that [131]

$\displaystyle B_{n}(y_{1},\ldots,y_{n})=A052894(n),$

where $A052894(n)$ denotes the number of Schröder trees626262Schröder trees
have been introduced in a paper by W.Y.C. Chen [23]. Namely, these are trees
for which the set of subtrees at any vertex is endowed with the structure of
ordered partition. Recall that an ordered partition of a set in which the
blocks are linearly ordered [23]..

##  Appendix A Appendixes

###  A.1 Grothendieck polynomials

######  Definition A.1.

Let $\beta$ be a parameter. The Id-Coxeter algebra ${\rm IdC}_{n}(\beta)$ is
an associative algebra over the ring of polynomials $\mathbb{Z}[\beta]$
generated by elements $\langle e_{1},\ldots,e_{n-1}\rangle$ subject to the set
of relations

  * •

$e_{i}e_{j}=e_{j}e_{i}$ if $|i-j|\geq 2$,

  * •

$e_{i}e_{j}e_{i}=e_{j}e_{i}e_{j}$ if $|i-j|=1$,

  * •

$e_{i}^{2}=\beta e_{i}$ $1\leq i\leq{n-1}$.

It is well-known that the elements $\\{e_{w},\,w\in\mathbb{S}_{n}\\}$ form a
$\mathbb{Z}[\beta]$-linear basis of the algebra ${\rm IdC}_{n}(\beta)$. Here
for a permutation $w\in\mathbb{S}_{n}$ we denoted by $e_{w}$ the product
$e_{i_{1}}e_{i_{2}}\cdots e_{i_{\ell}}\in{\rm IdC}_{n}(\beta)$, where
$(i_{1},i_{2},\ldots,i_{\ell})$ is any reduced word for a permutation $w$,
i.e., $w=s_{i_{1}}s_{i_{2}}\cdots s_{i_{\ell}}$ and $\ell=\ell(w)$ is the
length of $w$.

Let $x_{1},x_{2},\ldots,x_{n-1},x_{n}=y,x_{n+1}=z,\ldots$ be a set of mutually
commuting variables. We assume that $x_{i}$ and $e_{j}$ commute for all values
of $i$ and $j$. Let us define

$\displaystyle h_{i}(x)=1+xe_{i},\qquad
A_{i}(x)=\prod_{a=n-1}^{i}h_{a}(x),\qquad i=1,\ldots,n-1.$

######  Lemma A.2.

One has

  1. $(1)$

addition formula:

$\displaystyle h_{i}(x)h_{i}(y)=h_{i}(x\oplus y),$

where we set $(x\oplus y):=x+y+\beta xy$;

  2. $(2)$

Yang–Baxter relation:

$\displaystyle h_{i}(x)h_{i+1}(x\oplus y)h_{i}(y)=h_{i+1}(y)h_{i}(x\oplus
y)h_{i+1}(x).$

######  Corollary A.3.

  1. $(1)$

$[h_{i+1}(x)h_{i}(x),h_{i+1}(y)h_{i}(y)]=0$.

  2. $(2)$

$[A_{i}(x),A_{i}(y)]=0$, $i=1,2,\ldots,n-1$.

The second equality follows from the first one by induction using the addition
formula, whereas the fist equality follows directly from the Yang–Baxter
relation.

######  Definition A.4 (Grothendieck expression).

$\displaystyle\mathfrak{G}_{n}(x_{1},\ldots,x_{n-1}):=A_{1}(x_{1})A_{2}(x_{2})\cdots
A_{n-1}(x_{n-1}).$

######  Theorem A.5 ([42]).

The following identity

$\displaystyle\mathfrak{G}_{n}(x_{1},\ldots,x_{n-1})=\sum_{w\in\mathbb{S}_{n}}\mathfrak{G}_{w}^{(\beta)}(X_{n-1})e_{w}$

holds in the algebra ${\rm IdC}_{n}\otimes\mathbb{Z}[x_{1},\ldots,x_{n-1}]$.

######  Definition A.6.

We will call polynomial $\mathfrak{G}_{w}^{(\beta)}(X_{n-1})$ as the
$\beta$-Grothendieck polynomial corresponding to a permutation $w$.

######  Corollary A.7.

  1. $(1)$

If $\beta=-1$, the polynomials $\mathfrak{G}_{w}^{(-1)}(X_{n-1})$ coincide
with the Grothendieck polynomials introduced by Lascoux and M.-P.
Schützenberger [86].

  2. $(2)$

The $\beta$-Grothendieck polynomial $\mathfrak{G}_{w}^{(\beta)}(X_{n-1})$ is
divisible by $x_{1}^{w(1)-1}$.

  3. $(3)$

For any integer $k\in[1,n-1]$ the polynomial
$\mathfrak{G}_{w}^{(\beta-1)}(x_{k}=q,\,x_{a}=1,\,\forall\,a\not=k)$ is a
polynomial in the variables $q$ and $\beta$ with non-negative integer
coefficients.

###### Sketch of proof.

It is enough to show that the specialized Grothendieck expression
$\mathfrak{G}_{n}(x_{k}=q$, $x_{a}=1,\,\forall\,a\not=k)$ can be written in
the algebra $IdC_{n}(\beta-1)\otimes\mathbb{Z}[q,\beta]$ as a linear
combination of elements $\\{e_{w}\\}_{w\in\mathbb{S}_{n}}$ with coefficients
which are polynomials in the variables $q$ and $\beta$ with non-negative
coefficients. Observe that one can rewrite the relation
$e_{k}^{2}=(\beta-1)e_{k}$ in the following form $e_{k}(e_{k}+1)=\beta e_{k}$.
Now, all possible negative contributions to the expression
$\mathfrak{G}_{n}(x_{k}=q$, $x_{a}=1,\,\forall\,a\not=k)$ can appear only from
products of a form $c_{a}(q):=(1+qe_{k})(1+e_{k})^{a}$. But using the Addition
formula one can see that $(1+qe_{k})(1+e_{k})=1+(1+q\beta)e_{k}$. It follows
by induction on $a$ that $c_{a}(q)$ is a polynomial in the variables $q$ and
$\beta$ with non-negative coefficients. ∎

######  Definition A.8.

  * •

The double $\beta$-Grothendieck expression $\mathfrak{G}_{n}(X_{n},Y_{n})$ is
defined as follows

$\displaystyle\mathfrak{G}_{n}(X_{n},Y_{n})=\mathfrak{G}_{n}(X_{n})\mathfrak{G}_{n}(-Y_{n})^{-1}\in{\rm
IdC}_{n}(\beta)\otimes\mathbb{Z}[X_{n},Y_{n}].$

  * •

The double $\beta$-Grothendieck polynomials
$\\{\mathfrak{G}_{w}(X_{n},Y_{n})\\}_{w\in\mathbb{S}_{n}}$ are defined from
the decomposition

$\displaystyle\mathfrak{G}_{n}(X_{n},Y_{n})=\sum_{w\in\mathbb{S}_{n}}\mathfrak{G}_{w}(X_{n},Y_{n})e_{w}$

of the double $\beta$-Grothendieck expression in the algebra ${\rm
IdC}_{n}(\beta)$.

More details about $\beta$-Grothendieck and related polynomials can be found
in [71, 84].

###  A.2 Cohomology of partial flag varieties

Let $n=n_{1}+\cdots+n_{k}$, $n_{i}\in\mathbb{Z}_{\geq 1}\forall i$, be a
composition of $n$, $k\geq 2$. For each $j=1,\ldots,k$ define the numbers
$N_{j}=n_{1}+\cdots+n_{j},N_{0}=0$, and $M_{j}=n_{j}+\cdots+n_{k}$. Denote by
${\boldsymbol{X}}:={\boldsymbol{X}}_{n_{1},\ldots,n_{k}}=\\{x_{a}^{(i)}\,|\,i=1,\ldots,k,\,1\leq
a\leq n_{i}\\}$ (resp. ${\boldsymbol{Y}}$, …) a set of variables of the
cardinality $n$. We set $\deg(x_{a}^{(i)})=a$, $i=1,\ldots,k$. For each
$i=1,\ldots,k$ define quasihomogeneous polynomial of degree $n_{i}$ in
variables ${\boldsymbol{X}}^{(i)}=\big{\\{}x_{a}^{(i)}\,|\,1\leq a\leq
n_{i}\big{\\}}$

$\displaystyle
p_{n_{i}}\big{(}{\boldsymbol{X}}^{(i)},t\big{)}=t^{n_{i}}+\sum_{a=1}^{n_{i}}x_{a}^{(i)}t^{n_{i}-a},$

and put

$\displaystyle
p_{n_{1},\ldots,n_{k}}({\boldsymbol{X}},t)=\prod_{i=1}^{k}p_{n_{i}}({\boldsymbol{X}}^{(i)},t).$

We summarize in the theorem below some well-known results about the classical
and quantum cohomology and $K$-theory rings of type $A_{n-1}$ partial flag
varieties ${\cal F}l_{n_{1},\ldots,n_{k}}$. Let $q_{1},\ldots,q_{k-1}$,
$\deg(q_{i})=n_{i}+n_{i+1}$, $i=1,\ldots,k-1$, be a set of “quantum
parameters”.

######  Theorem A.9.

There are canonical isomorphisms

$\displaystyle H^{*}({\cal
F}l_{n_{1},\ldots,n_{k}},\mathbb{Z})\cong\mathbb{Z}[{\boldsymbol{X}}_{n_{1},\ldots,n_{k}}]\big{/}\big{\langle}p_{n_{1},\ldots,n_{k}}({\boldsymbol{X}},t)-t^{n}\big{\rangle},$
$\displaystyle K^{\bullet}({\cal
F}l_{n_{1},\ldots,n_{k}},\mathbb{Z})\cong\mathbb{Z}[{\boldsymbol{Y}}^{\pm
1}]\big{/}\big{\langle}p_{n_{1},\ldots,n_{k}}({\boldsymbol{Y}},t)-(1+t)^{n}\big{\rangle},$
$\displaystyle H^{*}_{T}({\cal
F}l_{n_{1},\ldots,n_{k}},\mathbb{Z})\cong\mathbb{Z}[{\boldsymbol{X}},{\boldsymbol{Y}}]\Big{/}\left\langle\prod_{i=1}^{k}\prod_{a=1}^{n_{i}}(x_{a}^{(i)}+t)-p_{n_{1},\ldots,n_{k}}({\boldsymbol{Y}},t)\right\rangle,$
$\displaystyle QH^{*}({\cal
F}l_{n_{1},\ldots,n_{k}})\cong\mathbb{Z}[{\boldsymbol{X}}_{n_{1},\ldots,n_{k}},q_{1},\ldots,q_{k-1}]\big{/}\big{\langle}\Delta_{n_{1},\ldots,n_{k}}({\boldsymbol{X}},t)-t^{n}\big{\rangle}\quad\text{\rm(cf.~{}\cite[cite]{[\@@bibref{}{ASS}{}{}]})},$
$\displaystyle QH_{T}^{*}({\cal
F}l_{n_{1},\ldots,n_{k}})\cong\mathbb{Z}[{\boldsymbol{X}},{\boldsymbol{Y}},q_{1},\ldots,q_{k-1}]\big{/}\big{\langle}\Delta_{n_{1},\ldots,n_{k}}({\boldsymbol{X}},t)-p_{n_{1},\ldots,n_{k}}({\boldsymbol{Y}},t)\big{\rangle}\quad\text{\rm(cf.~{}\cite[cite]{[\@@bibref{}{ASS}{}{}]})},$

where636363We prefer to use quantum parameters $\\{q_{i}\,|\,1\leq i\leq
k-1\\}$ instead of the parameters $\\{(-1)^{n_{i}}q_{i}\,|\,1\leq i\leq
k-1\\}$ have been used in [4].

$\displaystyle\Delta_{n_{1},\ldots,n_{k}}({\boldsymbol{X}},t)=$
$\displaystyle\det\begin{vmatrix}p_{n_{1}}({\boldsymbol{X}}^{(1)},t)&q_{1}&0&\cdots&\cdots&\cdots&0\\\
-1&p_{n_{2}}({\boldsymbol{X}}^{(2)},t)&q_{2}&0&\cdots&\cdots&0\\\
0&-1&p_{n_{3}}({\boldsymbol{X}}^{(3)},t)&q_{3}&0&\cdots&0\\\
\vdots&\ddots&\ddots&\ddots&\ddots&\ddots&\vdots\\\
0&\cdots&\cdots&0&-1&p_{n_{k-1}}({\boldsymbol{X}}^{(k-1)},t)&q_{k-1}\\\
0&\cdots&\cdots&\cdots&0&-1&p_{n_{k}}({\boldsymbol{X}}^{(k)},t)\end{vmatrix}.$

Here for any polynomial
$P({\boldsymbol{x}},t)=\sum\limits_{j=0}^{r}b_{j}({\boldsymbol{x}})t^{r-j}$ in
variables ${\boldsymbol{x}}=(x_{1},x_{2},\ldots)$, we denote by $\langle
P({\boldsymbol{x}},t)\rangle$ the ideal in the ring
$\mathbb{Z}[{\boldsymbol{x}}]$ generated by the coefficients
$b_{0}({\boldsymbol{x}}),\ldots,b_{r}({\boldsymbol{x}})$. A similar meaning
have the symbols

$\displaystyle\left\langle\prod_{i=1}^{k}\prod_{a=1}^{n_{i}}(x_{a}^{(i)}+t)-p_{n_{1},\ldots,n_{k}}({\boldsymbol{y}},t)\right\rangle,\qquad\big{\langle}\Delta_{n_{1},\ldots,n_{k}}({\boldsymbol{x}},t)-t^{n}\big{\rangle}$

and so on.

Note that $\dim({\cal F}_{n_{1},\dots,n_{k}})=\sum\limits_{i<j}n_{i}n_{j}$ and
the Hilbert polynomial ${\rm Hilb}({\cal F}_{n_{1},\dots,n_{k}},q)$ of the
partial flag variety ${\cal F}_{n_{1},\ldots,n_{k}}$ is equal to the
$q$-multinomial coefficient ${n\brack n_{1},\ldots,n_{k}}_{q}$, and also is
equal to the $q$-dimension of the weight $(n_{1},\ldots,n_{k})$ subspace of
the $n$-th tensor power $(\mathbb{C}^{n})^{\otimes n}$ of the fundamental
representation of the Lie algebra ${\mathfrak{gl}}(n)$.

######  Comments A.10.

The cohomology and (small) quantum cohomology rings $H^{*}({\cal
F}_{n_{1},\dots,n_{k}},\mathbb{Z})$ and $QH^{*}({\cal
F}_{n_{1},\dots,n_{k}},\mathbb{Z})$, of the partial flag variety ${\cal
F}_{n_{1},\dots,n_{k}}$ admit yet another representations we are going to
present. To start with, let as before $n=n_{1}+\cdots+n_{k}$,
$n_{i}\in\mathbb{Z}_{\geq 1}$, $\forall\,i$, be a composition. Consider the
set of variables
$\widehat{\boldsymbol{X}}=X_{n_{1},\ldots,n_{k-1}}:=\\{x_{a}^{(i)}\,|\,1\leq
i\leq n_{a},\,a=1,\ldots,k-1\\},$ and set as before $\deg x_{a}^{(i)}=a$. Note
that the number of variables $\widehat{\boldsymbol{X}}$ is equal to $n-n_{k}$.
To continue, let’s define elementary quasihomogeneous polynomials of degree
$r$

$\displaystyle
e_{r}\big{(}\widehat{\boldsymbol{X}}\big{)}=\sum_{I,A}x_{a_{1}}^{(i_{1})}\cdots
x_{a_{s}}^{(i_{s})},\qquad
e_{0}\big{(}\widehat{\boldsymbol{X}}\big{)}=1,\qquad
e_{-r}\big{(}\widehat{\boldsymbol{X}}\big{)}=0,\qquad r>0,$

where the sum runs over sequences of integers $I=(i_{1},\ldots,i_{s})$ and
$A=(a_{1},\ldots,a_{s})$ such that

  * •

$1\leq i_{1}<\cdots<i_{s}\leq k-1$,

  * •

$1\leq a_{j}\leq n_{i_{j}}$, $j=1,\ldots,s$, and $r=a_{1}+\cdots+a_{s}$,

and complete homogeneous polynomials of degree $p$

$\displaystyle
h_{p}\big{(}\widehat{\boldsymbol{X}}\big{)}=\det\big{|}e_{j-i+1}\big{(}\widehat{\boldsymbol{X}}\big{)}\big{|}_{1\leq
i,j\leq p}.$

Finally, let’s define the ideal $J_{n_{1},\ldots,n_{k}}$ in the ring of
polynomials $\mathbb{Z}[X_{n_{1},\ldots,n_{k-1}}]$ generated by polynomials

$\displaystyle h_{n_{k}+1}\big{(}\widehat{\boldsymbol{X}}\big{)},\ \ldots,\
h_{n}\big{(}\widehat{\boldsymbol{X}}\big{)}.$

Note that the ideal $J_{n_{1},\ldots,n_{k}}$ is generated by
$n-n_{k}=\\#(X_{n_{1},\ldots,n_{k-1}})$ elements.

######  Proposition A.11.

There exists an isomorphism of rings

$\displaystyle H^{*}({\cal
F}_{n_{1},\dots,n_{k}},\mathbb{Z})\cong\mathbb{Z}[X_{n_{1},\ldots,n_{k-1}}]/J_{n_{1},\ldots,n_{k}}.$

In a similar way one can describe relations in the (small) quantum cohomology
ring of the partial flag variety ${\cal F}_{n_{1},\dots,n_{k}}$. To accomplish
this let’s introduce quantum quasihomogeneous elementary polynomials of degree
$j$ $e_{j}^{({\boldsymbol{q}})}({\boldsymbol{X}}_{n_{1},\ldots,n_{r}})$
through the decomposition

$\displaystyle\Delta_{n_{1},\ldots,n_{r}}({\boldsymbol{X}}_{n_{1},\ldots,n_{r}})=\sum_{j=0}^{N_{r}}e_{j}^{({\boldsymbol{q}})}({\boldsymbol{X}}_{n_{1},\ldots,n_{r}})t^{N_{r}-j},\\!\qquad
e_{0}^{({\boldsymbol{q}})}({\boldsymbol{x}})=1,\\!\qquad
e_{-p}^{({\boldsymbol{q}})}({\boldsymbol{x}})=0,\\!\qquad p>0.$

To exclude redundant variables $\big{\\{}x^{(k)}_{a},\,1\leq a\leq
n_{k}\big{\\}}$, let us define quantum quasihomogeneous Schur polynomials
$s_{\alpha}^{({\boldsymbol{q}})}({\boldsymbol{X}}_{n_{1},\ldots,n_{r}})$
corresponding to a composition
$\alpha=(\alpha_{1}\leq\alpha_{2}\leq\cdots\leq\alpha_{p})$ as follows

$\displaystyle
s_{\alpha}^{({\boldsymbol{q}})}({\boldsymbol{X}}_{n_{1},\ldots,n_{r}})=\det\big{|}e_{j-i+\alpha_{i}}^{({\boldsymbol{q}})}({\boldsymbol{X}}_{n_{1},\ldots,n_{r}})\big{|}_{1\leq
i,j\leq p}.$

######  Proposition A.12.

The $($small$)$ quantum cohomology ring $QH^{*}({\cal
F}_{n_{1},\dots,n_{k}},\mathbb{Z})$ is isomorphic to the quotient of the ring
of polynomials $\mathbb{Z}[q_{1},\ldots,q_{k-1}]~{}[{\bf
X}_{n_{1},\ldots,n_{k-1}}]$ by the ideal $I_{n_{1},\ldots,n_{k-1}}$ generated
by the elements

$\displaystyle
g_{r}({\boldsymbol{X}}_{n_{1},\ldots,n_{k-1}}):=s_{(1^{n_{k}},r)}^{(q_{1},\ldots,q_{k-1})}({\boldsymbol{X}}_{n_{1},\ldots,n_{k-1}})-q_{k-1}e_{r-n_{k-1}}^{(q_{1},\ldots,q_{k-2})}({\boldsymbol{X}}_{n_{1},\ldots,n_{k-2}}),$

where $n_{k}+1\leq r\leq n$.

It is easy to see that the Jacobi matrix

$\displaystyle\left({\partial\over\partial
x^{(i)}_{a}}g_{r}({\boldsymbol{X}}_{n_{1},\ldots,n_{k-1}})\right)_{\\{a=1,\ldots,k-1,\,1\leq
i\leq n_{a}\atop n_{k}+1\leq r\leq n\\}}$

corresponding to the set of polynomials
$g_{r}({\boldsymbol{X}}_{n_{1},\ldots,n_{k-1}})$, $n_{k}\leq r\leq n$, has
nonzero determinant, and the component of maximal degree
$n_{\max}:=\sum\limits_{l<j}n_{i}n_{j}$ in the ring $QH^{*}({\cal
F}_{n_{1},\dots,n_{k}},\mathbb{Z})$ is a
$\mathbb{Z}[q_{1},\ldots,q_{k-1}]$-module of rank one with generator

$\displaystyle\Lambda=\prod_{i=1}^{k-1}\prod_{a=1}^{n_{a}}\big{(}x^{(i)}_{a}\big{)}^{M_{i}}.$

Therefore, one can define a scalar product (the Grothendieck residue)

$\displaystyle\langle\bullet,\bullet\rangle\colon\ HQ^{*}({\cal
F}_{n_{1},\dots,n_{k}},\mathbb{Z})\times HQ^{*}({\cal
F}_{n_{1},\dots,n_{k}},\mathbb{Z})\longrightarrow\mathbb{Z}[q_{1},\ldots,q_{k-1}]$

setting for elements $f$ and $g$ of degrees $a$ and $b$, $\langle
f,h\rangle=0$, if $a+b\not=n_{\max}$, and $\langle f,h\rangle=\lambda(q)$, if
$a+b=n_{\max}$ and $fh=\lambda(q)\Lambda$. It is well known that the
Grothendieck pairing $\langle\bullet,\bullet\rangle$ is nondegenerate (for any
choice of parameters $q_{1},\ldots,q_{k-1})$.

Finally we state “a mirror presentation” of the small quantum cohomology ring
of partial flag varieties. To start with, let $n=n_{1}+\cdots+n_{k}$,
$k\in\mathbb{Z}_{ge2}$ be a composition of size $n$, and consider the set

$\displaystyle\Sigma({\boldsymbol{n}})=\big{\\{}(i,j)\in\mathbb{Z}\times\mathbb{Z}\,|\,1\leq
i\leq N_{a},\,M_{a+1}+1\leq j\leq M_{a},\,a=1,\ldots,k-1\\},$

where $N_{a}=n_{1}+\cdots+n_{a}$, $N_{0}=0,N_{k}=n$
$M_{a}=n_{a+1}+\cdots+n_{k}$, $M_{0}=n,M_{k}=0$.

With these data given, let us introduce the set of variables

$\displaystyle
Z_{\boldsymbol{n}}=\\{z_{i,j}\,|\,(i,j)\in\Sigma({\boldsymbol{n}})\\},$

and define “boundary conditions” as follows

  * •

$z_{i,M_{a}+1}=0$, if $N_{a-1}+2\leq i\leq N_{a}$, $a=1,\ldots,k-1$,

  * •

$z_{N_{a}+1,j}=\infty$, if $M_{a+1}+2\leq j\leq M_{a}$, $a=1,\ldots,k-1$,

  * •

$z_{N_{a-1}+1,M_{a}+1}=q_{a}$, $a=1,\ldots,k$, where $q_{1},\ldots,q_{k}$ are
“quantum parameters.

Now we are ready, follow [53], to define superpotential

$\displaystyle
W_{q,{\boldsymbol{n}}}=\sum_{(p,j)\in\Sigma({\boldsymbol{n}})}\left({z_{i,j+1}\over
z_{i,j}}+{z_{i,j}\over z_{i+1,j}}\right).$

######  Conjecture A.13 (cf. [53]).

There exists an isomorphism of rings

$\displaystyle QH^{*}_{[2]}({\cal
F}l_{n_{1},\ldots,n_{k}},\mathbb{Z})\cong\mathbb{Z}\big{[}q_{1}^{\pm
1},\ldots,q_{k}^{\pm 1}\big{]}\big{[}Z_{\boldsymbol{n}}^{\pm
1}\big{]}/J(W_{q,{\boldsymbol{n}}}),$

where $QH^{*}_{[2]}({\cal F}l_{n_{1},\ldots,n_{k}},\mathbb{Z})$ denotes the
subring of the ring $QH^{*}({\cal F}l_{n_{1},\ldots,n_{k}},\mathbb{Z})$
generated by the elements from $H^{2}({\cal
F}l_{n_{1},\ldots,n_{k}},\mathbb{Z})$.

$J(W_{q,{\boldsymbol{n}}})$ stands for the ideal generated by the partial
derivatives of the superpotential $W_{q,{\boldsymbol{n}}}$:

$\displaystyle J(W_{q,{\boldsymbol{n}}})=\left\langle{\partial
W_{q}\over\partial
z_{i,j}}\right\rangle,\qquad(i,j)\in\Sigma({\boldsymbol{n}}).$

Note that variables
$\\{z_{i,j}\in\Sigma({\boldsymbol{n}}),\,i\not=N_{a}+1,\,a=0,\ldots,k-2\\}$
are redundant, whereas the variables
$\\{z_{a,j}:=z_{N_{a}+1,j}^{-1},\,j=1,\ldots,n_{a},\,a=0,\ldots,k-2\\}$
satisfy the system of algebraic equations.

In the case of complete flag variety ${\cal F}l_{n}$ corresponds to partition
${\boldsymbol{n}}=(1^{n})$ and the superpotential $W_{q,1^{n}}$ is equal to

$\displaystyle W_{q,1^{n}}=\sum_{1\leq i<j\leq n-1}\left({{z_{i,j+1}\over
z_{i,j}}}+{{z_{i,j}\over z_{i-1,j+1}}}\right),$

where we set $z_{i,n}:=q_{i}$, $i=1,\dots,n$. The ideal $J(W_{q,1^{n}})$ is
generated by elements

$\displaystyle{{\partial W_{q,1^{n}}\over z_{i,j}}}={{{1\over
z_{i,j-1}}}}+{{1\over z_{i-1,j+1}}}-{{z_{i,j+1}+z_{i-1,j-1}\over
z_{i,j}^{2}}}.$

One can check that the ideal $J(W_{q,1^{n}})$ can be also generated by
elements of the form

$\displaystyle\sum_{j=0}^{i}A_{j}^{(i)}(q_{1},\ldots,q_{n-i+1},z_{n-1},\ldots,z_{n-i+1})z_{n-i}^{j-i-1}=1,\qquad
A^{(i)}_{0}=q_{1}\cdots q_{n-i+1},$

where $z_{i}:=z_{1,i}^{-1}$, $i=1,\ldots n-1$. For example,

$\displaystyle z_{1}^{n}q_{1}\cdots q_{n}=1,\qquad
q_{1}q_{2}z_{n-1}^{2}-q_{2}z_{n-2}=1,$ $\displaystyle
q_{1}q_{2}q_{3}z_{n-2}^{3}-2q_{1}q_{2}q_{3}z_{n-1}z_{n-2}z_{n-3}+q_{2}q_{3}z_{n-3}^{2}+q_{3}z_{n-4}=1.$

Therefore the number of critical points of the superpotential $W_{q}$ is equal
to $n!=\dim H^{*}({\cal F}l_{n},\mathbb{Z})$, as it should be. Note also that
$QH^{*}({\cal F}l_{n},\mathbb{Z})=QH^{*}_{[2]}({\cal F}l_{n},\mathbb{Z})$.

###  A.3 Multiparamater 3-term relations algebras

####  A.3.1 Equivariant multiparameter 3-term relations algebras

Let ${\boldsymbol{q}}=\\{q_{ij}\\}_{1\leq i\not=j\leq n}$, $q_{ij}=q_{ji}$, be
a collection of mutually commuting parameters and
${\boldsymbol{\beta}}=\\{\beta_{ij}\\}_{1\leq i\not=j\leq n}$,
$\beta_{ij}=\beta_{ji}$ and ${\boldsymbol{\ell}}=\\{\ell_{ij}\\}_{1\leq
i\not=j\leq n}$, $\ell_{ij}=\ell_{ji}$, be two sets of mutually commuting
variables each.

######  Definition A.14.

Denote by $3QT_{n}({\boldsymbol{\beta}},{\boldsymbol{\ell}},{\boldsymbol{q}})$
an associative algebra generated over the ring
$\mathbb{Z}[{\boldsymbol{\beta}},{\boldsymbol{\ell}},{\boldsymbol{q}}]$ by the
set of generators $\\{x_{1},\ldots,x_{n}\\}$ and that $\\{u_{ij}\\}_{1\leq
i\not=j\leq n}$ subject to the set of relations

  1. (1)

locality conditions: $[x_{i},x_{j}]=0$, $[u_{ij},u_{kl}]=0$,
$[x_{k},u_{ij}]=0$ if $i$, $j$, $k$, $l$ are pairwise distinct,

  2. (2)

generalized unitarity conditions: $u_{ij}+u_{ji}=\beta_{ij}$,

  3. (3)

Hecke type conditions: $u_{ij}u_{ji}=-q_{ij}$ if $i\not=j$,

  4. (4)

twisted $3$-term relations:
$u_{ij}u_{jk}=u_{jk}u_{ik}-u_{ik}u_{ji},u_{jk}u_{ij}=u_{ik}u_{jk}-u_{ji}u_{ik}$
if $i$, $j$, $k$ are distinct,

  5. (5)

crossing relations: $x_{i}u_{ji}=-u_{ij}x_{j}-\ell_{ij}$ if $i\not=j$.

As before we define the (additive) Dunkl elements to be

$\displaystyle\theta_{i}=x_{i}+\sum_{j\not=i}u_{ij},\qquad i=1,\ldots,n.$
(A.1)

It should be pointed out that the Dunkl elements do not commute with variables
$\\{x_{i}\\}$, $\\{\beta_{ij}\\}$ and $\\{\ell_{ij}\\}$.

It is clearly seen from the defining relations listed in Definition A.14 that
for any triple of distinct indices $(i,j,k)$ the elements
$\\{x_{i},x_{j},x_{k},u_{ji},u_{ik},u_{jk}\\}$ satisfy the twisted dynamical
Yang–Baxter relations, and thus the Dunkl elements $\\{\theta_{i}\\}_{1\leq
i\leq n}$ generate a commutative subalgebra in the algebra
$3QT_{n}({\boldsymbol{\beta}},{\boldsymbol{\ell}})$.

On the other hand, one can show that the set of defining relations involve in
the definition of algebra $3QT_{n}({\boldsymbol{\beta}},{\boldsymbol{\ell}})$
implies the following set of compatibility relations among the set of
generators $\\{u_{ij}\\}$ and the set of variables $\\{\beta_{ij}\\}$ and
$\\{\ell_{ij}\\}$

$\displaystyle\ell_{ij}u_{jk}+u_{ij}\ell_{jk}+\beta_{ij}u_{jk}x_{i}+u_{ij}\beta_{jk}x_{j}=u_{jk}\ell_{ik}+\ell_{ik}u_{ij}+u_{jk}\beta_{ik}x_{i}+\beta_{ij}x_{i}u_{ij},$

if $i$, $j$, $k$ are distinct.

These relations are satisfied, for example, if either $\beta_{ij}=\beta$, and
$\ell_{ij}=h$, $\forall\,i,j$ for some parameters (i.e., a central elements)
$\beta$ and $h$, or variables $\\{\beta_{ij}\\}$ and $\\{\ell_{ij}\\}$ satisfy
the exchange relations with generators $\\{u_{ij}\\}$, namely, the
commutativity relations

$\displaystyle[\beta_{ij},u_{km}]=0,\qquad[\ell_{ij},u_{km}]=0\qquad\text{if}\quad\\{i,j\\}\cap\\{k,m\\}=\varnothing$

and the exchange relations

$\displaystyle\beta_{ij}u_{jk}=u_{jk}\beta_{ik},\qquad\ell_{ij}u_{jk}=u_{jk}\ell_{ik}\qquad\text{if}\quad
k\not=i,j.$

It happens that in the first case, if $\beta=0$, then the (commutative)
algebra generated by additive Dunkl’s elements and elementary symmetric
polynomials $\\{e_{k}(X_{n})\\}_{1\leq k\leq n}$ (resp. multiplicative Dunkl’s
elements) is isomorphic to the equivariant quantum cohomology ring (resp. to
the equivariant quantum $K$-theory ring) of the type $A_{n-1}$ complete flag
variety. In the second case a geometric interpretation of the algebra
generated by Dunkl’s elements is missing.

Our main objective in this section is to to describe (part of) relations among
Dunkl’s element using defining relations involve in the Definition A.14 of the
algebra $3QT_{n}({\boldsymbol{\beta}},{\boldsymbol{\ell}},{\boldsymbol{q}})$,
under the following constraints

$\displaystyle\ell_{ij}=h_{\max(i,j)},\qquad h_{2},\ldots,h_{n}\quad\text{are
all central}.$

Note, that except the case $\beta_{j}=\beta$ and $h_{i}=h_{j}$,
$\forall\,i,j$, our assumption violates the crossing relations between the
elements $\beta_{ij}$, $\ell_{ij}$ and $u_{j,k}$, but nevertheless allows to
compute explicitly (part of) relations among the Dunkl’s elements. We expect
that an abstract algebra generated over
$\mathbb{Q}[{\boldsymbol{\beta}},{\boldsymbol{h}}]$ by a set of mutually
commuting elements $\theta_{1},\ldots,\theta_{n}$ and elementary symmetric
polynomials $\\{e_{k}(X_{n})\\}_{1\leq k\leq n}$ subject to the set of
relations descending from those for Dunkl’s elements which were mentioned
above, has some interesting combinatorial/geometric interpretations. Below we
state some results concerning relations among Dunkl elements in the algebra
$3QT_{n}({\boldsymbol{\beta}},{\boldsymbol{\ell}},{\boldsymbol{q}})$.

######  Theorem A.15 (cf. Theorem 3.17, Section 3).

Let $k\geq 1$ be an integer. There exist polynomials

$\displaystyle
R_{k}({\boldsymbol{q}},{\boldsymbol{h}},z_{1},\ldots,z_{n})\in\mathbb{Z}[\beta,{\boldsymbol{q}},\\{h_{j}-h_{i}\\}_{1\leq
i<j\leq n}][Z_{n}],$ $\displaystyle
T_{k}(\beta,{\boldsymbol{h}},z_{1},\ldots,z_{n})\in\mathbb{Z}[\beta,{\boldsymbol{h}}][Z_{n}]^{{\mathbb{S}}_{n}}$

such that

$\displaystyle
R_{k}({\boldsymbol{q}},{\boldsymbol{h}},z_{1},\ldots,z_{n})=e_{k}^{({\boldsymbol{q}}+{\boldsymbol{h}})}(z_{1},\ldots,z_{n})+\text{monomials~{}of~{}total~{}degree}$
$\displaystyle\hphantom{R_{k}({\boldsymbol{q}},{\boldsymbol{h}},z_{1},\ldots,z_{n})=}{}\leq
k-2\qquad\text{w.r.t. variables $\\{z_{i}\\}_{1\leq i\leq n}$},$
$\displaystyle
T_{k}(\beta,{\boldsymbol{h}},z_{1},\ldots,z_{n})=e_{k}(z_{1},\ldots,z_{n})+\sum_{j<k}c_{j,k}e_{j}(X_{n}),c_{j,k}\in\mathbb{Z}[\beta,{\boldsymbol{h}}],$
$\displaystyle R_{k}(\theta_{1},\ldots,\theta_{n})=T_{k}(x_{1},\ldots,x_{n}),$

where $e_{k}^{({\boldsymbol{q}}+{\boldsymbol{h}})}(z_{1},\ldots,z_{n})$
denotes the multiparameter quantum elementary polynomial corresponding to the
set of parameters
$\\{({\boldsymbol{q}}+{\boldsymbol{h}})\\}=\\{q_{ij}+h_{j}\\}_{1\leq i<j\leq
n}$.

It is not difficult to see that the unitarity and crossing conditions imply
the following relations

$\displaystyle[x_{i}+x_{j},u_{kl}]=0=[x_{i}x_{j},u_{kl}],\qquad[x_{i}^{2},u_{kl}]=0$

are valid for all indices $i\not=j$, $k\not=l$. As a consequence of these
relations one can deduce that the all symmetric polynomials
$e_{k}(X_{n}):=e_{k}(x_{1},\ldots,x_{n})$, $k=1,\ldots,n$, belong to the
center of the algebra $3QT_{n}({\boldsymbol{q}},{\boldsymbol{h}})$, and
therefore one has $[\theta_{i},e_{k}(X_{n})]=0$ for all $i$ and $k$. Let us
denote by $QH(\beta,{\boldsymbol{h}})$ a commutative subalgebra in the algebra
$3QT_{n}(\beta,{\boldsymbol{h}})$ generated by the elementary symmetric
polynomials $\\{e_{k}(X_{n})\\}_{1\leq k\leq n}$ and the Dunkl elements
$\\{\theta_{i}\\}_{1\leq i\leq n}$. It is an interesting problem to give a
geometric/cohomological interpretation of the commutative algebra
$QH(\beta,{\boldsymbol{h}})$. We don’t know any geometric interpretation of
that commutative algebra, except the special case [75]

$\displaystyle\beta=0,\qquad h_{j}=1,\quad\forall\,j,\qquad
q_{ij}:=q_{i}\delta_{i+1,j}.$ (A.2)

######  Proposition A.16 ([75]).

Under assumptions (A.2), the algebra $QH(0,{\bf 0})$ isomorphic to the
equivariant quantum cohomology $QH^{*}_{T}({\cal{F}}l_{n})$ of the complete
flag variety ${\cal{F}}l_{n}$.

######  Examples A.17.

Let us list the relations among the Dunkl elements in the algebra
$3QT_{n}(\beta,{\boldsymbol{h}})$ for $n=3,4$, and $\beta_{j}=\beta$, $\forall
j$.

$\displaystyle(1)\ $ $\displaystyle
e_{1}(\theta_{1},\ldots,\theta_{n})=e_{1}(X_{n})+{n\choose 2}\beta,$
$\displaystyle(2)\ $ $\displaystyle
e_{2}^{({\boldsymbol{q}}+{\boldsymbol{h}})}(\theta_{1},\ldots,\theta_{n})=e_{2}(X_{n})+(n-1)\beta
e_{1}(X_{n})+\frac{n(n-1)(n-2)(3n-1)}{24}\beta^{2},\quad n\geq 3,$
$\displaystyle(3)\ $ $\displaystyle
e_{3}^{({\boldsymbol{q}}+{\boldsymbol{h}})}(\theta_{1},\theta_{2},\theta_{3})=e_{3}(X_{3})+h_{3}\beta,$
$\displaystyle
e_{3}^{({\boldsymbol{q}}+{\boldsymbol{h}})}(\theta_{1},\theta_{2},\theta_{3},\theta_{4})=e_{3}(X_{4})+\beta
e_{2}(X_{4})+2\beta^{2}e_{1}(X_{4})+6\beta^{3}+\beta(h_{3}+3h_{4}),$
$\displaystyle(4)\ $ $\displaystyle
e_{4}^{({\boldsymbol{q}}+{\boldsymbol{h}})}(\theta_{1},\theta_{2},\theta_{3},\theta_{4})+\beta(h_{4}-h_{3})\theta_{4}=e_{4}(X_{4})+\beta
h_{4}e_{1}(X_{4})+5\beta^{2}h_{4}.$

Note that $\frac{n(n-1)(n-2)(3n-1)}{24}=s(n-2,2)=e_{2}(1,2,\ldots,n-1)$ is
equal to the Stirling number of the first kind.

######  Conjecture A.18.

The polynomial $R_{k}({\boldsymbol{q}},{\boldsymbol{h}},Z_{n})$, see Theorem
2.29, can be written as a polynomial in the variables
$\\{h_{ij}:=h_{j}-h_{i},\,1\leq i<j\leq
n,\,z_{1},\ldots,z_{n},\,\beta,\,q_{ij},\,1\leq i<j\leq n\\}$ with nonnegative
coefficients.

######  Exercises A.19 (Pieri formula in the algebra $3T_{n}(0,h)$, [75]).

Assume that $\beta=0$ and $h_{2}=\cdots=h_{n}=h$, and denote by
$\theta_{i}^{(n)}$, $i=1,\ldots,n$ the Dunkl elements (A.1) in the algebra
$3T_{n}(0,h)$. Show that

$\displaystyle
e_{k}\big{(}\theta_{1}^{(n)},\ldots,\theta_{m}^{(n)}\big{)}=\sum_{r\geq
0}(-h)^{r}N(m-k,2~{}r)\left\\{\sum_{S\subset[1,m]\atop
I=\\{i_{a}\\},\,J=\\{j_{a}\\}}X_{S}u_{i_{1},j_{1}}\cdots
u_{i_{|I|},j_{|J|}}\right\\},$

where

$\displaystyle N(a,2b)=(2b-1)!!{a+2b\choose 2b},$

$X_{S}=\prod\limits_{s\in S}x_{s}$, and the second summation runs over triples
of sets $\\{S,I,J\\}$ such that $S\subset[1,m]$, $I\subset[1,m]{\setminus}S$,
$|I|+|S|+2r=k$, $|I|=|J|$, $1\leq i_{a}<m<j_{a}\leq n$ and
$j_{1}\leq\cdots\leq j_{|I|}$.

####  A.3.2 Algebra
$\boldsymbol{3QT_{n}({\boldsymbol{\beta}},{\boldsymbol{h}})}$, generalized
unitary case

Let ${\boldsymbol{\beta}}=(\beta_{1},\ldots,\beta_{n-1})$,
${\boldsymbol{h}}=(h_{2},\ldots,h_{n})$ and $\\{q_{ij}\\}_{1\leq i<j\leq n}$
be collections of mutually commuting parameters as in the previous section. As
before we define the Dunkl elements $\theta_{i}$, $i=1,\ldots,n$, by the
formula (A.1). It is necessary to stress that the Dunkl elements
$\\{\theta\\}_{1\leq i\leq n}$ do not commute in the algebra
$3QT_{n}(\boldsymbol{\beta},{\boldsymbol{h}})$ but satisfy a noncommutative
analogue of the relations displayed in Theorem A.15. Namely, one needs to
replace the both elementary polynomials $e_{k}(Z_{n})$ and the quantum
multiparameter elementary polynomials $e_{k}^{({\boldsymbol{q}})}(Z_{n})$ by
its noncommutative versions. Recall that the noncommutative elementary
polynomial $\underline{e}_{k}(Z_{n})$ is equal to

$\displaystyle\sum_{1\leq j_{1}<j_{2}<\cdots<j_{k}\leq
n}z_{j_{1}}~{}z_{j_{2}}\cdots z_{j_{k}}$

and the noncommutative quantum multiparameters elementary polynomial
$\underline{e}_{k}^{({\boldsymbol{q}})}(Z_{n})$ is equal to

$\displaystyle\sum_{\ell}\sum_{1\leq i_{1}<\cdots<j_{\ell}\leq n\atop
i_{1}<j_{1},\ldots,i_{\ell}<j_{\ell}}\underline{e}_{k-2\ell}(Z_{\overline{I\cup
J}})\prod_{a=1}^{\ell}u_{i_{a},j_{a}},$

where $I=(i_{1},\ldots,i_{\ell})$, $J=(j_{1},\ldots,j_{\ell})$ should be
distinct elements of the set $\\{1,\ldots,n\\}$, and $Z_{\overline{I\cup J}}$
denotes set of variables $z_{a}$ for which the subscript $a$ is neither one of
$i_{m}$ nor one of the $j_{m}$.

######  Example A.20.

$\displaystyle\underline{e}_{2}^{({\boldsymbol{q}}+{\boldsymbol{h}})}(\theta_{1},\ldots,\theta_{n})=e_{2}(X_{n})+\left(\sum_{j=1}^{n-1}\beta_{j}\right)e_{1}(X_{n})+\sum_{1\leq
a<b\leq n-1}ab\beta_{a}\beta_{b},$
$\displaystyle\underline{e}_{3}^{({\boldsymbol{q}}+{\boldsymbol{h}})}(\theta_{1},\theta_{2},\theta_{3},\theta_{4})+(\beta_{3}-\beta_{1})(\theta_{3}\theta_{4}+q_{34}+h_{4}+\beta_{2}(\theta_{1}+\theta_{2}))+(\beta_{3}-\beta_{2})((\theta_{1}+\theta_{2})\theta_{4}$
$\displaystyle\qquad{}+q_{14}+q_{24}+2h_{4}+\beta_{1}\theta_{3})=e_{3}(X_{4})+\beta_{3}e_{2}(X_{4})+(\beta_{1}\beta_{3}+\beta_{2}\beta_{3}+\beta_{3}^{2}-\beta_{1}\beta_{2})e_{1}(X_{4})$
$\displaystyle\qquad{}+(3\beta_{3}^{2}-\beta_{1}\beta_{2})(\beta_{1}+2\beta_{2})+\beta_{1}(h_{3}+h_{4})+2\beta_{2}h_{4},$
$\displaystyle\underline{e}_{4}^{({\boldsymbol{q}}+{\boldsymbol{h}})}(\theta_{1},\theta_{2},\theta_{3},\theta_{4})+(\beta_{2}h_{4}-\beta_{1}h_{3})\theta_{4}+h_{4}(\beta_{2}-\beta_{1})\theta_{3}$
$\displaystyle\qquad{}=e_{4}(X_{4})+\beta_{2}h_{4}e_{1}(X_{4})+\beta_{2}h_{4}(2\beta_{2}+3\beta_{3}).$

######  Project A.21 (noncommutative universal Schubert polynomials).

Let $w\in\mathbb{S}_{n}$ be a permutation and $\mathfrak{S}_{w}(Z_{n})$ be the
corresponding Schubert polynomial.

$(1)$ There exists a $($noncommutative$)$ polynomial
$\mathfrak{Sh}_{w}(\\{u_{ij}\\}_{1\leq i<j\leq n})$ with non-negative integer
coefficients such that the following identity

$\displaystyle\mathfrak{S}_{w}(\theta_{1},\ldots,\theta_{n})=\mathfrak{Sh}_{w}(\\{u_{ij}\\}_{1\leq
i<j\leq n})$

holds in the algebra $3T_{n}^{(0)}$, where $\\{\theta_{j}\\}_{1\leq j\leq n}$
are the Dunkl elements in the algebra $3T_{n}^{(0)}$.

$(2)$ There exist polynomials
$R_{w}(\beta,{\boldsymbol{q}},{\boldsymbol{h}},Z_{n})\in\mathbb{N}[\beta,{\boldsymbol{q}},{h_{j}-h_{i}}_{1\leq
i<j\leq n}][Z_{n}]$ and
$T_{w}(\beta,{\boldsymbol{h}},Z_{n})\in\mathbb{Z}[\beta,{\boldsymbol{h}}][Z_{n}]$
such that the following identity

$\displaystyle
R_{w}(\beta,{\boldsymbol{q}},{\boldsymbol{h}},\theta_{1},\ldots,\theta_{n})=T_{w}(\beta,{\boldsymbol{h}},X_{n})+\mathfrak{Sh}_{w}(\\{u_{ij}\\}_{1\leq
i<j\leq n})$

holds in the algebra $3QT_{n}(\beta,{\boldsymbol{h}})$.

$3)$ Let $r\in\mathbb{Z}_{\geq 2}$ and $N=n_{1}+\cdots+n_{r}$,
$n_{j}\in\mathbb{Z}_{\geq 1}$, $\forall\,j$, be a composition of $N$, and set
$N_{j}=n_{1}+\cdots+n_{j}$, $j\geq 1$, $N_{0}=0$. Eliminate the Dunkl elements
$\theta_{N_{r-1}+1}^{(N)},\ldots,\theta_{N}^{(N)}$ from the set of relations
among the Dunkl elements $\theta_{1}^{(N)},\ldots,\theta_{N}^{(N)}$ in the
algebra $3QT_{n}(\beta,{\boldsymbol{h}})$, by the use of the degree
$1,\dots,n_{r}$ relations among the former. As a result one obtains a set
consisting of $N_{r-1}$ relations among the $N_{r-1}$ elements