Remixed Eulerian numbers

Abstract

Remixed Eulerian numbers are a polynomial q-deformation of Postnikov’s mixed Eulerian numbers. They arose naturally in previous work by the authors concerning the permutahedral variety and subsume well-known families of polynomials such as q-binomial coefficients and Garsia–Remmel’s q-hit numbers. We study their combinatorics in more depth. As polynomials in q, they are shown to be symmetric and unimodal. By interpreting them as computing success probabilities in a simple probabilistic process we arrive at a combinatorial interpretation involving weighted trees. By decomposing the permutahedron into certain combinatorial cubes, we obtain a second combinatorial interpretation. At $q=1$, the former recovers Postnikov’s interpretation whereas the latter recovers Liu’s interpretation, both of which were obtained via methods different from ours.

1 Introduction

This article studies a large family of polynomials, the remixed Eulerian numbers, which were introduced in a previous work of the authors [18]. The terminology follows that of Postnikov [21, Section 16] where mixed Eulerian numbers were introduced. We first recall their original geometric definition.

Throughout this article, r is a positive integer. Consider real numbers $\lambda _1\geq \cdots \geq \lambda _{r+1}$ and let . The permutahedron $\mathrm {Perm}(\lambda )$ is the convex hull of the points , where $\sigma $ is a permutation in the symmetric group $\mathbb {S}_{r+1}$ . It sits in the hyperplane $\{(z_i)\in \mathbb {R}^{r+1}\;|\; z_1+\cdots +z_{r+1}=\lambda _1+\cdots +\lambda _{r+1}\}$ . After projecting it to $\mathbb {R}^r\times \{0\}$ , one can compute its volume $\mathrm {vol}(\mathrm {Perm}(\lambda ))$ . The latter is known to be a polynomial in the differences , homogeneous of degree r. It can thus be written as

(1.1) $$ \begin{align} \mathrm{vol}(\mathrm{Perm}(\lambda))=\sum_{{c}=(c_1,\ldots,c_r)}A_{c}\;\frac{\mu_1^{c_1}\cdots \mu_r^{c_r}}{c_1!\cdots c_r!} \end{align} $$

with ${c}$ in .

Definition 1.1 [21, Section 16].

For $c\in \mathcal {W}_{r}^{}$ , $A_c$ is called a mixed Eulerian number.

We now recall the definition of remixed Eulerian numbers $A_c(q)$ introduced in [18, Section 4.3], where it is also pointed out why $A_c(1)=A_c$ .

Let $\mathbb {S}_{r+1}$ act on $\mathbb {C}[q,x_1,\dots ,x_{r+1}]$ by permuting the indices of the indeterminates $x_1$ through $x_{r+1}$ . Consider the operator $\partial _{w_o}$ that acts on polynomials $f\in \mathbb {C}[q,x_1,\dots ,x_{r+1}]$ as

(1.2) $$ \begin{align} \partial_{w_o}(f)=\frac{1}{\displaystyle\prod_{1\leq i<j\leq r+1}(x_i-x_j)}\sum_{\sigma\in\mathbb{S}_{r+1}}\epsilon(\sigma)\sigma(f), \end{align} $$

where $\epsilon (\sigma )$ is the sign of $\sigma $ . Then $\partial _{w_o}(f)$ is a symmetric polynomial in $x_1,\ldots ,x_{r+1}$ . If f is homogeneous of degree d in $x_1,\ldots ,x_{r+1}$ , then $\partial _{w_o}(f)$ vanishes if $d<\binom {r+1}{2}$ and has degree $d-\binom {r+1}{2}$ in $x_1,\ldots ,x_{r+1}$ otherwise.

Given $f\in \mathbb {C}[q,x_1,\dots ,x_{r+1}]$ , define the q-divided symmetrization operator by

(1.3) $$ \begin{align} \big\langle {f}\big\rangle_{r+1}^q=\partial_{w_o}\left(f\prod_{1\leq i<j-1\leq r}(qx_i-x_j)\right). \end{align} $$

Now, assume f has total degree r in $x_1,\ldots ,x_{r+1}$ . Then $f\left (\displaystyle \prod _{1\leq i<j-1\leq r}(qx_i-x_j)\right )$ has degree $\binom {r+1}{2}$ , and thus $\big \langle {f}\big \rangle _{r+1}^q$ is a polynomial in $\mathbb {C}[q]$ by the property of $\partial _{w_o}$ recalled above. In particular, for $c\in \mathcal {W}_{r}^{}$ we consider the degree r polynomial $y_c$ defined as:

(1.4) $$ \begin{align} y_c=x_1^{c_1}(x_1+x_2)^{c_2}\dots (x_1+\dots+x_r)^{c_r}. \end{align} $$

Definition 1.2 (Remixed Eulerian number $A_c(q)$ ).

For $c\in \mathcal {W}_{r}^{}$ , the remixed Eulerian number $A_{c}(q)\in \mathbb {C}[q]$ is defined as

$$ \begin{align*} A_{c}(q)=\big\langle {y_c}\big\rangle_{r+1}^q. \end{align*} $$

The polynomials $A_{c}(q)$ may be equivalently defined in a number of other ways; see Section 2.

Several properties of mixed Eulerian numbers $A_c$ were given by Postnikov in a long list [21, Theorem 16.3] that exhibits the rich combinatorics attached to them. The theorem was reproduced by Liu [15, Theorem 4.1] who used his combinatorial interpretation of $A_c$ to reprove several items on the list (and add some more).

The next theorem shows that all of these properties of Postnikov’s theorem q-deform nicely to $A_c(q)$ . We have kept exactly the order in which Postnikov stated the properties in his statement. Where necessary, we appeal to standard notation (as can be found in [22, 23] for instance) for various permutation statistics and q-analogs.

Theorem 1.3. Let $c=(c_1,\dots ,c_{r})\in \mathcal {W}_{r}^{}$ .

1. (1) $A_{c}(q)$ is a polynomial in q with nonnegative integer coefficients.

2. (2) $A_{(c_1,\dots ,c_{r})}(q)=q^{\binom {r}{2}}A_{(c_r,\dots ,c_{1})}(q^{-1})$ .

3. (3) $A_{(\ldots ,0,r,0,\ldots )}(q)$ with r in the ith position equals

   $$\begin{align*}\sum_{\substack{\sigma\in \mathbb{S}_r\\ \mathrm{des}(\sigma)=i-1}}q^{\mathrm{maj}(\sigma)}. \end{align*}$$

4. (4) $\displaystyle \sum _{c\in \mathcal {W}_{r}^{}}\frac {A_{c_1,\dots ,c_{r}}(q)}{c_1!\cdots c_r!}=\frac {(r)_q!}{r!}(r+1)^{r-1}$ .

5. (5) $\displaystyle \sum _{c\in \mathcal {W}_{r}^{}}A_{c_1,\dots ,c_{r}}(q)=(r)_q!\,\mathrm {Cat}_r$ where $\mathrm {Cat}_r=\frac {1}{r+1}\binom {2r}{r}$ is the rth Catalan number.

6. (6) $A_{(\ldots ,0,k,r-k,0,\ldots )}(q)$ , with k in ith position, equals

   $$\begin{align*}\sum_{\substack{\sigma\in \mathbb{S}_{r+1},\mathrm{des}(\sigma)=i\\ \sigma(r+1)=r+1-k}}q^{\mathrm{maj}(\sigma)-k}. \end{align*}$$

7. (7) $A_{1,\dots ,1}(q)=(r)_q!$ .

8. (8) $A_{k,0,\dots ,0,r-k}(q)=q^{\binom {k}{2}} \genfrac (){0pt}{}{r}{k}_q$ .

9. (9) Assume that c satisfies $\sum _{i\leq j} c_i\geq j$ for $j=1,\dots ,r$ . Then one has

   $$\begin{align*}A_c(q)=(1)_q^{c_1}(2)_q^{c_2}\cdots(r)_q^{c_r}.\end{align*}$$

Some of these properties were already given in [18], while the others will be proved at various locations in the text: (1) is [18, Proposition 5.4]. (2) is Lemma 5.1. (3), as well as (6), (8) and (9), are treated in Section 4. For (4), we refer to Section 6. (5) follows from the sum rule [18, Proposition 5.4], as explained in Remark 2.1. Finally, (7) is part of [18, Theorem 4.8].

Combinatorial interpretations for the case $q=1$ have been given in previous works: in [21, Section 17] Postnikov defined certain weighted trees to give a combinatorial interpretation for $A_c$ . Another interpretation was given by Liu [15], in terms of C-compatible permutations. As we will argue in this work, such permutations can be naturally seen as bilabeled trees with leaf labels $1,c_1+2,c_1+c_2+3,\dots ,c_1+\cdots +c_r+r+1=2r+1$ . Both these interpretations come from finding functional equations for the volume polynomial (1.1) and extracting coefficients.

We will refine both these combinatorial interpretations by interpreting the powers of q in each, by fairly different methods. These are stated in terms of certain families of trees that are described in detail in Sections 3 and 6.

• • $A_{c}(q)$ is the total weight of all ‘Postnikov trees’ with a fixed associated sequence $\mathbf {i}$ of content c (Theorem 3.5).

• • $A_{c}(q)$ is the total weight of all ‘bilabeled trees’ with leaf labels $1,c_1+2,c_1+c_2+3,\dots ,c_1+\cdots +c_r+r+1=2r+1$ (Theorem 7.1).

Outline of the article

We recall some alternative definitions of $A_c(q)$ in Section 2; these have already appeared in [18]. The last one is probabilistic in nature and is used in Section 3 to give a first combinatorial interpretation of $A_c(q)$ . In Section 4, we distinguish two large subfamilies of indices c that give particularly nice polynomials $A_c(q)$ . In Section 5, we show that the sequence of coefficients of $A_c(q)$ is always symmetric and unimodal. This requires the determination of the degree and valuation of $A_c(q)$ . In Section 6, we link $A_c(q)$ with the original geometry for $q=1$ , as the parameter q is interpreted via a certain cubical dissection of the permutahedron. From this, a second combinatorial interpretation of $A_c(q)$ follows; see Section 7.

2 Alternative definitions of remixed Eulerian numbers

For $n\in \mathbb {Z}_{\geq 0}$ and $0\leq k\leq n$ , set

(2.1)

These are the q-integers, q-factorials and q-binomial coefficients. Given integers $a\leq b$ , we denote the interval $\{a,a+1,\dots ,b\}$ by $[a,b]$ . If $a=1$ , we often shorten this to $[b]$ . For any undefined combinatorial terminology, we refer the reader to standard texts such as [22, 23].

In contrast to the computational perspective provided in Definition 1.2, we offer three more perspectives that may be treated as alternative definitions.

The reader will note the similarity between the perspectives that follow: They are indeed easily seen to be equivalent. In contrast, the fact that any of these definitions is equivalent to Definition 1.2 is not obvious, and this was a key result in [18].

2.1 Coefficients in the Klyachko algebra

The q-Klyachko algebra $\mathcal {K}$ is the commutative algebra over $\mathbb {C}(q)$ on the generators $\{u_i\;|\; i\in \mathbb {Z}\}$ subject to the following relations for all $i\in \mathbb {Z}$ :

$$ \begin{align*} (q+1)u_i^2=qu_iu_{i-1}+u_iu_{i+1}. \end{align*} $$

For a finite subset $I\subset \mathbb {Z}$ , let . By [18, Proposition 3.9], the set $\mathcal {B}$ of such square-free monomials forms a linear basis for $\mathcal {K}$ . Given $c\in \mathcal {W}_r$ , we have

(2.2) $$ \begin{align} A_c(q)=(r)_q!\times\mathrm{ coefficient\ of}\ u_{[r]}\ \mathrm{ in\ the\ expansion\ of }\ u_1^{c_1}\cdots u_r^{c_r} \mathrm{ in }\ \mathcal{B}. \end{align} $$

2.2 Recurrence relation

The remixed Eulerian number $A_c(q)$ for $c=(c_1,\dots ,c_r)\in \mathcal {W}_{r}^{}$ is the unique polynomial satisfying the initial condition $A_{(1^{r})}(q)=(r)_q!$ and the relation

(2.3) $$ \begin{align} (q+1)A_c(q)=q A_{(\dots,c_{i-1}+1,c_{i}-1,\dots)}(q)+A_{(\dots,c_{i}-1,c_{i+1}+1,\dots)}(q)\ \mathrm{ for\ any }\ i\ \mathrm{ satisfying }\ c_i\geq 2. \end{align} $$

On the right-hand side we ignore the ill-defined terms in the case $i=1$ or $i=r$ .

A more efficient recurrence based approach is as follows. The initial condition continues to be $A_{(1^r)}(q)=(r)_q!$ . Otherwise, consider i such that $c_i\geq 2$ . Let $\mathrm {Supp}(c)$ denote the support of c, that is, the set of all indices j such that $c_j>0$ . Let $[a,b]$ be the maximal interval in $\mathrm {Supp}(c)$ containing i. We let $L_i(c)$ (resp. $ R_i(c)$ ) denote the composition obtained by decrementing $c_i$ by $1$ and incrementing $c_{a-1}$ (resp. $c_{b+1}$ ) by $1$ . Then we have

(2.4) $$ \begin{align} (b-a+2)_qA_{c}(q)=q^{i-a+1}(b-i+1)_qA_{L_i(c)}(q)+(i-a+1)_qA_{R_i(c)}(q). \end{align} $$

Again, if $a=1$ (resp. $b=r$ ), then $L_i(c)$ (resp. $R_i(c)$ ) is not well defined, and the corresponding remixed Eulerians are $0$ .

2.3 Probabilistic interpretation

Consider the integer line $\mathbb {Z}$ as a set of sites. A configuration is an $\mathbb {N}$ -vector $c=(c_i)_{i\in \mathbb {Z}}$ with $\sum _ic_i<\infty $ , which we visualize as a finite set of particles with $c_i$ particles stacked at site i. Stable configurations are those for which $c_i\leq 1$ for all i. They are identified with finite subsets of $\mathbb {Z}$ via their support.

Given jump probabilities $q_L,q_R\geq 0$ satisfying $q_L+q_R=1$ , consider the following process with state space the set of configurations. Suppose we are in a configuration c. If c is stable, the process stops. Otherwise, pick any i such that $c_i>1$ and move the top particle at site i to the top of site $i-1$ (resp. $i+1$ ) with probability $q_L$ (resp. $q_R$ ). The process ends in a stable configuration with probability $1$ . Furthermore, it is known that the probability of ending in a particular stable configuration does not depend on the choice of site i at each step.

For a finite subset $I\subset \mathbb {Z}$ , we can then define $\mathbb {P}_c(I)$ to be the probability that the process starting at configuration c ends in the stable configuration given by I. Assume $q_R>0$ and let . By [18, Proposition 5.1], for $c\in \mathcal {W}_{r}^{}$ we have

(2.5) $$ \begin{align} \mathbb{P}_c([r])=\frac{A_c(q)}{(r)_q!}. \end{align} $$

Note that we have then $q_L=\frac {q}{1+q}$ and $q_R=\frac {1}{1+q}$ .

Remark 2.1. Using this interpretation one has the following ‘cyclic sum rule’ [18, Proposition 5.3]: Given $c=(c_1,\dots ,c_{r})\in \mathcal {W}_{r}^{}$ , let $\mathsf {Cyc}(c)$ be the set of all $c'\in \mathcal {W}_{r}^{}$ such that $(c',0)$ is a cyclic rotation of $(c,0)$ . Then

(2.6) $$ \begin{align} \sum_{c'\in \mathsf{Cyc}(c)}A_{c'}(q)=(r)_q!. \end{align} $$

There are $\mathrm {Cat}_r$ sets of the form $\mathsf {Cyc}(c)$ so that summing equation (2.6) over all of them proves Theorem 1.3 (8).

We record a slightly different way to think about the previous process as it will be particularly helpful.

Sequential process: Fix any word $\mathbf {i}=(i_1,\ldots ,i_r)\in [r]^r$ . Starting with the empty configuration, drop particles one at a time at sites $i_1,i_{2},\ldots , i_r$ , and stabilize at every step. Each such step involves the particle either landing on an interval of occupied sites in the current stable configuration, and then proceeding to exit either to the left or to the right, or landing on an unoccupied site in which case it stabilizes immediately. We denote by $\mathbb {P}^{\mathbf {i}}(I)$ the probability to end up with the stable set I.

Let $\mathrm {cont}(\mathbf {i})=(c_1,\dots ,c_r)\in \mathcal {W}_{r}^{}$ , where $c_j$ is the the number of instances of j in $\mathbf {i}$ for $j\in [r]$ . Then we have

(2.7) $$ \begin{align}\mathbb{P}^{\mathbf{i}}(I)=\mathbb{P}_{\mathrm{cont}(\mathbf{i})}(I)\end{align} $$

and thus by equation (2.5),

(2.8) $$ \begin{align} \mathbb{P}^{\mathbf{i}}([r])=\frac{A_{\mathrm{cont}(\mathbf{i})}(q)}{(r)_q!}. \end{align} $$

3 Combinatorial interpretation via Postnikov trees

Postnikov showed that mixed Eulerian numbers $A_c$ enumerate a certain family of trees [21]. His proof uses an equation for the volume of the permutahedron $\mathrm {vol}(\mathrm {Perm}(\lambda ))$ , proved purely geometrically (and valid for any ‘root system’). Using the expansion (1.1) and differentiation, he then obtains a combinatorial interpretation of the numbers $A_c$ as enumerating certain weighted trees. Here, we will define a q-deformation of these weights, based on the probability process, that turns out to give a combinatorial interpretation of $A_c(q)$ . Postnikov’s trees can then be reinterpreted naturally as recording possible histories of the process.

3.1 A recursive formula for $\mathbb {P}^{\mathbf {i}}([a,b])$

Consider $\mathbf {i}=i_1\cdots i_r$ , and let us compute $\mathbb {P}^{\mathbf {i}}([a,b])$ , where we assume that $b-a+1=r$ and $i_j\in [a,b]$ for all j since $\mathbb {P}^{\mathbf {i}}([a,b])=0$ otherwise.

Let us condition on the stable set obtained just before dropping the last particle $i_r$ . This set is necessarily of the form $[a,b]\setminus \{j\}=[a,j-1]\sqcup [j+1,b]$ for $j\in [a,b]$ in order to have $\mathbb {P}^{\mathbf {i}}([a,b])\neq 0$ . We thus get

(3.1) $$ \begin{align} \mathbb{P}^{\mathbf{i}}([a,b])=\sum_{j=a}^b\mathbb{P}^{i_1\cdots i_{r-1}}([a,b]\setminus\{j\})\,\mathbb{P}^{i_r}([a,b],j), \end{align} $$

where $\mathbb {P}^i([a,b],j)$ is the probability to reach the stable set $[a,b]$ from $[a,b]\setminus \{j\}$ after dropping a particle at the site $i\in [a,b]$ and stabilizing.

The probability $\mathbb {P}^{i_1\cdots i_{r-1}}([a,b]\setminus \{j\})$ is clearly zero unless

• (*) there are $j-a$ indices t such that $i_t\in [a,j-1]$ and $b-j$ indices t such that $i_t\in [j+1,b]$ .

Indeed, the site j is empty at all times before the last step, so the particles that are dropped on either side of it stay on that side during the process. Assuming (*) is satisfied, let $\mathbf {i'},\mathbf {i"}$ be the two subsequences of $\mathbf {i}$ consisting of $i_t<j$ and $i_t>j$ , respectively. Then we have

(3.2) $$ \begin{align} \mathbb{P}^{i_1\cdots i_{r-1}}([a,b]\setminus\{j\})=\mathbb{P}^{\mathbf{i'}}([a,j-1])\;\mathbb{P}^{\mathbf{i"}}([j+1,b]). \end{align} $$

The other factor $\mathbb {P}^{i_r}([a,b],j)$ in equation (3.1) is also straightforward to compute: If $i_r>j$ , then the particle must exit to the left of the interval $[j+1,b]$ while if $i_r\leq j$ , it must exit to the right of the interval $[a,j-1]$ . These are the well-known exit probabilities of a biased discrete random walk on an interval [4]. We thus obtain explicitly $\mathbb {P}^{i_r}([a,b],j)=\mathrm {wt}_q([a,b],j,i_r)$ , where for any $i\in [a,b]$ ,

(3.3) $$ \begin{align} \mathrm{wt}_q([a,b],j,i)=\left\lbrace \begin{array}{ll}\frac{(b-i+1)_q}{(b-j+1)_q}q^{(i-j)} & i> j, \\ \frac{(i-a+1)_q}{(j-a+1)_q} & i \leq j. \end{array} \right. \end{align} $$

The reader may recognize these as q-deformations of the weights $\mathrm {wt}(i,j)$ in [21, Equation 17.1], which can therefore be interpreted as exit probabilities in the symmetric case $q=1$ .

Substituting equations (3.2) and (3.3) in equation (3.1) gives a recursive way to compute $\mathbb {P}^{\mathbf {i}}([a,b])$ :

(3.4) $$ \begin{align} \mathbb{P}^{\mathbf{i}}([a,b])=\sum_{j\mathrm{ satisfying} {(\ast)}}\mathbb{P}^{\mathbf{i'}}([a,j-1])\,\mathbb{P}^{\mathbf{i"}}([j+1,b])\,\mathrm{wt}_q([a,b],j,i_r). \end{align} $$

The initial condition is simply $\mathbb {P}^{\epsilon }(\emptyset )=1$ , where $\epsilon $ is the empty word.

3.2 Postnikov trees

Given a binary tree T, we let $\mathrm {Nodes}(T)$ denote its set of nodes. A standard labeling of a binary tree T with r nodes is a bijective labeling of $\mathrm {Nodes}(T)$ with integers drawn from $[r]$ . The binary search labeling of T is the standard labeling given recursively by traversing the left subtree first, then the root, then the right subtree, and assigning a node the label $i\in [r]$ if it is the ith node encountered in this traversal. This is illustrated in Figure 1 by the labels inside the nodes. Let the bs-label of a node be this label .

Figure 1 With $\mathbf {i}=34717843$ , a Postnikov tree is represented on the left: The binary search labeling is pictured inside the nodes, while the unique decreasing labeling is between brackets in blue. The associated history of the sequential process is illustrated in the second and third panels, reading each panel from top to bottom.

Given a node v in T, let $[l_v,r_v]$ refer to the set of bs-labels of its descendants in T (itself included). A coloring $f:\mathrm {Nodes}(T)\to \mathbb {Z}$ is compatible if for all v, we have $f(v)\in [l_v,r_v]$ . In particular, if v has no children, then $f(v)$ is necessarily the bs-label of v. The weight $\mathrm {wt}(T,f)$ is then defined as

$$\begin{align*}\mathrm{wt}(T,f)=\prod_{v\in T}\mathrm{wt}_q([l_v, r_v],v,f(v)).\end{align*}$$

We call a labeled tree decreasing if it has a standard labeling such that the label of a node is larger than the labels of all its descendants. On the leftmost panel in Figure 1, the exterior labels (in blue) give a decreasing labeling of the underlying tree.

Definition 3.1. Given $\mathbf {i}=i_1\cdots i_r\in [r]^r$ , a tree T is $\mathbf {i}$ -compatible if it has a decreasing labeling $\mathrm {dec}:\mathrm {Nodes}(T)\to [r]$ such that $v\mapsto i_{\mathrm {dec}(v)}$ is a compatible labeling. The weight $\mathrm {wt}(T,\mathbf {i})$ is the weight of this compatible labeling.

The decreasing labeling is necessarily unique if it exists. Indeed, suppose T is $\mathbf {i}$ -compatible, and let $\mathrm {dec}$ be as in the definition. The root receives the greatest label. Let the bs-label of the root be j. By the definition of compatibility, if t is the $\mathrm {dec}$ -label of a node in the left (resp. right) subtree, then $i_t<j$ (resp. $i_t>j$ ). Thus, the sets of $\mathrm {dec}$ -labels in both subtrees are determined by $\mathbf {i}$ . One can then conclude by induction that the whole $\mathrm {dec}$ -labeling of T is determined by $\mathbf {i}$ .

For instance, the tree T in Figure 1 is $\mathbf {i}$ -compatible, where $\mathbf {i}=34717843$ . Furthermore, we have

$$\begin{align*}\mathrm{wt}(T,\mathbf{i})=\frac{(1)_q }{(1)_q}\cdot \frac{(1)_q }{(1)_q} \cdot \frac{(1)_q }{(1)_q}\cdot \frac{(1)_q }{(1)_q}\cdot \frac{(1)_q }{(2)_q}\cdot q^2\frac{(1)_q }{(3)_q}\cdot q^2\frac{(1)_q }{(3)_q}\cdot\frac{(3)_q }{(5)_q}=\frac{q^4}{(2)_q(3)_q(5)_q}. \end{align*}$$

The order of the terms on the right-hand side is obtained by considering the weights of nodes v encountered according to the decreasing labeling.

Remark 3.2. Postnikov uses increasing trees instead of decreasing ones. Our notion of $\mathbf {i}$ -compatibility corresponds to $\mathrm {rev}(\mathbf {i})$ -compatibility in his sense, where $\mathrm {rev}(\mathbf {i})$ is obtained by reversing $\mathbf {i}$ . This choice changes nothing of the underlying combinatorics and was made by us because it matches more naturally with the probabilistic process. In addition, his trees record the decreasing labeling together with the $\mathbf {i}$ -labeling. As we pointed out in the previous definition, given $(T,\mathbf {i})$ , such a decreasing labeling is in fact necessarily unique and can thus safely be removed from the definition.

Let $\mathcal {P}(\mathbf {i})$ be the set of $\mathbf {i}$ -compatible trees. These are referred to as Postnikov trees in the introduction, with content $\mathrm {cont}(\mathbf {i})$ determined by the multiplicity of each letter in $\mathbf {i}$ .

Theorem 3.3. For any $\mathbf {i}\in [r]^r$ , we have

$$ \begin{align*} \mathbb{P}^{\mathbf{i}}([r])=\sum_{T\in\mathcal{P}(\mathbf{i})}\mathrm{wt}(T,\mathbf{i}). \end{align*} $$

Proof. This follows from the recurrence (3.4). Let us specify that recurrence to the case $a=1,b=r$ and simply write $\mathbb {P}^{\mathbf {i}}$ instead of $\mathbb {P}^{\mathbf {i}}([r])$ . Write also $\mathbf {i^2}$ for the word $\mathbf {i"}$ , where all letters are decreased by j, so that they are between $1$ and $r-j$ . We obtain the recurrence

$$\begin{align*}\mathbb{P}^{\mathbf{i}}=\sum_{j\mathrm{ satisfying}{(\ast)}}\mathbb{P}^{\mathbf{i'}}\,\mathbb{P}^{\mathbf{i^2}}\,\mathrm{wt}_q([r],j,i_r). \end{align*}$$

We need to show that also satisfies such a recurrence. Given a tree in $\mathcal {P}(\mathbf {i})$ , let $j-1$ and $r-j$ be the sizes of its left and right subtrees, respectively. The root has necessarily label $i_r$ and thus weight $\mathrm {wt}_q([r],j,i_r)$ . The compatibility condition imposes that all labels of the left subtree $T'$ are between $1$ and $j-1$ , while all labels on the right subtree $T"$ are between $j+1$ and r. This corresponds precisely to the condition (*) that has to be satisfied, and we let $\mathbf {i'},\mathbf {i"}$ be the subsequences of $\mathbf {i}$ corresponding to $T'$ and $T"$ . Then $T'$ is in $\mathcal {P}(\mathbf {i'})$ , while $T"$ is in $\mathcal {P}(\mathbf {i"})$ . By subtracting j from all labels in $T"$ , we obtain a tree $T^2$ in $\mathcal {P}(\mathbf {i^2})$ , and the recurrence

$$\begin{align*}S(\mathbf{i})=\sum_{j\mathrm{ satisfying}{(\ast)}}S(\mathbf{i'})\,S(\mathbf{i^2})\,\mathrm{wt}_q([r],j,i_r). \end{align*}$$

This is precisely the recurrence satisfied by the $\mathbb {P}^{\mathbf {i}}$ , and we obtain the desired result since the initial conditions match: for $i\in \mathbb {Z}$ , $\mathbb {P}^{i}=S(i)=1$ if $i=1$ and $0$ otherwise.

A direct byproduct of the proof is that trees in $\mathcal {P}(\mathbf {i})$ correspond precisely to a ‘history’ of the sequential process started with $\mathbf {i}$ . The decreasing tree encodes the filling order in which sites get occupied along the process: The kth site to be occupied is $j=bs(v)$ , where v is the node with $\mathrm {dec}(v)=k$ . This is nothing but the standard bijection between decreasing trees and permutations, which we recall at the beginning of Section 6.2. Such a filling order is possible with $\mathbf {i}$ as initial word precisely when the corresponding decreasing tree is $\mathbf {i}$ -compatible. In that case, the weight of the tree is the probability of that ordering.

Example 3.4. For ease of comparison with Postnikov’s interpretation, we revisit [21, Example 17.6]. Consider $\mathbf {i}=34717843$ . The process of dropping particles and stabilizing at each step is depicted in Figure 1 on the right, and the corresponding Postnikov tree is on the left. The labels inside record the binary search labeling, whereas the decreasing labeling is on the outside in parentheses.

Equation (2.8) now immediately yields the following q-analogue of [21, Theorem 17.7].

Theorem 3.5. For any $c\in \mathcal {W}_{r}^{}$ and any $\mathbf {i}\in [r]^r$ such that $\mathrm {cont}(\mathbf {i})=c$ , we have

$$ \begin{align*} A_{c}(q)=\sum_{T\in\mathcal{P}(\mathbf{i})} (r)_q!\,\mathrm{wt}(T,\mathbf{i}). \end{align*} $$

Example 3.6. Consider $\mathbf {i}=2244$ . Then $\mathrm {cont}(\mathbf {i})=(0,2,0,2)$ . Figure 2 shows the relevant Postnikov trees.

Figure 2 The two Postnikov trees for $\mathbf {i}=2244$ .

Theorem 3.5 now tells us that

$$\begin{align*}A_{(0,2,0,2)}(q)=(4)_q!\cdot\frac{1}{(2)_q}\cdot q^3\frac{(1)_q}{(4)_q}+ (4)_q!\cdot q\frac{1}{(2)_q}\cdot q\frac{(1)_q}{(2)_q}=q^2(1+q+q^2)^2. \end{align*}$$

Remark 3.7. Note that each of the two summands above belong to $\mathbb {N}[q]$ . This is the case in general indeed. Keeping with the theme, one simply needs to ‘q-ify’ [21, Lemma 17.5]. Consider $(r)_q!$ times all denominators in $\mathrm {wt}(T,\mathbf {i})$ times the power of q accumulated in the numerator. This rational function is a polynomial which tracks $q^{\ell (w)}$ over the following set of permutations w, contingent on T and $\mathbf {i}$ naturally. As in loc. cit., consider labelings of the underlying tree T with permutations $w\in \mathbb {S}_r$ such that if we are in the first case (resp. second case) of equation (3.3) for some node j, then $w(j)$ exceeds the labels $w(k)$ for all k in its right (resp. left) subtree. ¹

Remark 3.8. Since different choices of $\mathbf {i}$ with same $\mathrm {cont}(\mathbf {i})$ determined the same remixed Eulerian number, smart choices can optimize computations a bit. For instance, starting the sequence $\mathbf {i}$ with all elements of $\mathrm {Supp}(c)$ (in any order) gives simpler trees in general. This corresponds of course to starting the particle process by dropping one particle at each site of the support.

4 Two special subfamilies

We consider two large subfamilies of $A_c(q)$ by restricting the possible indices in $\mathrm {Supp}(c)$ . These families encompass all special cases listed in Theorem 1.3. They have specific properties that make them particularly nice from an enumerative standpoint: Elements of the first family have elementary product formulas that generalize q-binomial coefficients, cf. Proposition 4.2. Elements of the second subfamily have certain generating functions whose coefficients have simple product formulas, cf. equation (4.4), and coincide with the family of q-hit polynomials.

4.1 An extension of q-binomial coefficients

Definition 4.1. We define $EB_r\subset \mathcal {W}_{r}^{}$ to be the set of $c=(c_1,\dots ,c_{r})$ such that there exists a $k\in \{0,\ldots ,r\}$ satisfying $\displaystyle\sum _{i\leq j}c_i\geq j$ for $j=1,\ldots ,k$ and $\displaystyle\sum _{i\leq j}c_{r+1-i}\geq j$ for $j=1,\dots ,r-k$ .

Remark that both items (8) and (9) of Theorem 1.3 are in this subfamily $EB_r$ . The following explicit product formula proves and generalizes them.

Proposition 4.2. For any $c\in EB_r$ with k as in Definition 4.1, we have

(4.1) $$ \begin{align} A_{c}(q)=q^{d_c}\genfrac(){0pt}{}{r}{k}_q\;\prod_{i=1}^k (i)_q^{c_i}\; \prod_{i=1}^{r-k} (i)_q^{c_{r+1-i}}, \end{align} $$

where $d_c=\displaystyle \sum _{j=1}^{r-k}\sum _{i=1}^j(c_{r+1-i}-1)$ .

Note that by equation (4.1), $d_c$ is the smallest exponent of q occurring in $A_c(q)$ . We give a formula for this exponent in equation (5.3) that is valid for any $c\in \mathcal {W}_{r}^{}$ , and specializes to the expression above when $c\in EB_r$ .

Proof. We use the probabilistic interpretation of $A_c(q)$ in Section 2.3 in its sequential version. We choose the word

$$\begin{align*}\mathbf{i}=1^{c_1}2^{c_2}\cdots k^{c_k} \;r^{c_r} (r-1)^{c_{r-1}}\cdots (k+1)^{c_{k+1}}.\end{align*}$$

It corresponds to the following dropping order of particles: Start with all $c_1$ particles at site $1$ , then all $c_2$ particles at site $2$ , and so on until we drop $c_k$ particles at site k. Then, drop all particles at site r, then at site $r-1$ , and so on down to $k+1$ .

The first part of the definition of $EB_r$ implies that in order to end with the stable configuration $\{1,\ldots ,r\}$ , the following must hold: For $i\leq k-1$ , the intermediate stable configuration after the ith step is the interval $\{1,\ldots ,i\}$ , and the $(i+1)$ -st particle either drops at site $i+1$ or drops on the previous interval and exits to the right. The probability of this happening is $\frac {1}{(k)_q!}\displaystyle \prod _{i=1}^k(i)_q^{c_i}$ by equation (3.3).

For the remaining particles, the situation is symmetric of the first part, since the stable interval $\{1,\ldots ,k\}$ does not interfere with the analysis. The probability of success in this second half is worked out to be $\frac {q^{d_c}}{(r-k)_q!}\displaystyle \prod _{i=1}^{r-k} (i)_q^{c_{r+1-i}}$ by equation (3.3) again.

Now, by equation (2.5), we obtain $A_c(q)$ by multiplying these two expressions together with $(r)_q!$ , thus giving the desired expression.

In terms of the tree interpretation from Section 3, we have in fact shown that for words $\mathbf {i}$ considered in the preceding proof, there is a unique compatible tree. We further note that Proposition 4.2 is the q-analogue of [15, Theorem 4.4]. Finally, the expression for $A_c(q)$ for $c\in EB_r$ motivates understanding the valuation $d_c$ in general; we return to this in Section 5.

Example 4.3. Consider $c=(2,0,1,0,2,1)\in EB_6$ . Then the k in Definition 4.1 equals $3$ . We have $d_c=c_6-1+c_6+c_5-2+c_6+c_5+c_4-3=1$ . The reader may verify that

$$\begin{align*}A_c(q)=q^{1}\genfrac(){0pt}{}{6}{3}_q(1)_q^2(3)_q\,(2)_q^2(1)_q. \end{align*}$$

4.2 Interval support and q-hit numbers

We now focus on the case where $\mathrm {Supp}(c)$ is an interval. That is, c can be written as $c=0^i\beta 0^{r-k-i}$ where $\beta \vDash r$ is a (strong) composition with . Thus, the first i and the last $r-k-i$ entries in c are all $0$ .

By [18, Proposition 5.6], we have

(4.2) $$ \begin{align} \sum_{j\geq 0}t^j\prod_{i=1}^k(j+i)_q^{\beta_i}=\frac{\displaystyle\sum_{i=0}^{r-k}A_{0^i\beta 0^{r-k-i}}(q) t^i}{(t;q)_{r+1}}. \end{align} $$

Here, .

Remark 4.4. If $\beta $ has a single part, so $\beta =(r)$ , we get

(4.3) $$ \begin{align} \sum_{j\geq 0}(j+1)_q^{r}t^j=\frac{\displaystyle\sum_{i=0}^{r-k}A_{0^i,r, 0^{r-k-i}}(q) t^i}{(t;q)_{r+1}}. \end{align} $$

This shows Theorem 1.3 (3), since the left-hand side was already considered by Carlitz [1] and this shows by comparison that $A_{0^i,r, 0^{r-k-i}}(q)$ counts permutations in $\mathbb {S}_r$ with i descents with q-weight given by the major index. An alternative proof of this is given in [17].

As briefly touched upon in [18, Section 5.3], the family of remixed Eulerian numbers $A_{0^i\beta 0^{r-k-i}}(q)$ coincides with polynomials enumerating q-hit numbers appearing in the work of Garsia–Remmel [5]. This observation is also instrumental in order to relate these numbers to recent work around chromatic symmetric functions; see [19]. We now justify this claim.

Fix r and consider $\lambda =(\lambda _1,\lambda _2,\ldots ,\lambda _r)$ with $\lambda _i$ integers satisfying $r\geq \lambda _1\geq \cdots \geq \lambda _r\geq 0$ . So $\lambda $ can be seen as a Young diagram in an $r\times r$ square; see Figure 3 with $r=6$ and $\lambda =(5,5,3,3,3,0)$ . Following [5], the q-hit numbers $H_j(\lambda ,q)$ can be defined by:

(4.4) $$ \begin{align} \sum_{j\geq 0}t^j\prod_{i=1}^{r}(i-\lambda_{r+1-i}+j)_q=\frac{\displaystyle\sum_{j=0}^r H_j(\lambda,q)t^j}{(t;q)_{r+1}}. \end{align} $$

Figure 3 Partition in a square (left), superimposition with the graph of a permutation.

Remark 4.5. For $q=1$ , the hit numbers enumerate permutations in $\mathbb {S}_{r}$ whose associated graph has exactly j points inside of the shape $\lambda $ . Figure 3 (right) shows a permutation contributing to $H_2(\lambda )$ .

There exists a refinement of this interpretation that gives the q-hit numbers [3]. We refrain from stating it given its technicality and particularly as we do not need it in the sequel and simply note that Theorem 1.3 (6) can be deduced from this combinatorial interpretation.

We will now compare the left-hand sides of equations (4.2) and (4.4). We will show that every nonzero q-hit polynomial is a remixed Eulerian number $A_c(q)$ where c has interval support and vice versa.

For $i=1,2,\dots , r$ , the values $i-\lambda _{r+1-i}$ occurring in equation (4.4) go from $1-\lambda _r\leq 1$ to $r-\lambda _1\geq 0$ with successive differences in $\{1,0,-1,-2,\dots \}$ . Geometrically, these values express the algebraic distance in each row between $\lambda $ and the staircase , computed from bottom to top. In our running example, we have the sequence of values $1,-1,0,1,0,1$ , as Figure 3 reveals.

A moment’s thought shows that these values must thus form an interval, say $[a,a+k-1]$ with $k\geq 1$ , that necessarily contains $0$ or $1$ . Define $\beta _i(=\beta _i(\lambda ))$ to be the number of times that the values $a+i-1$ is obtained so that is a composition of length k. The coefficient $C_j$ of $t^j$ on the left-hand side of equation (4.4) can be rewritten as

$$\begin{align*}\prod_{i=1}^k(j+a+i-1)_q^{\beta_i}. \end{align*}$$

If $a=1$ , we recognize this as the coefficient of $t^j$ on the left-hand side of equation (4.2) with $\beta =B(\lambda )$ . We thus have $H_j(\lambda ,q)=A_{0^j\beta 0^{r-k-j}}(q)$ for $j=0,\ldots ,r-k$ and is zero otherwise.

If $a\neq 1$ , one has $a\leq 0$ to ensure that $0$ or $1$ belong to $[a,a+k-1]$ , which also implies $k\geq 1-a$ . Thus $C_j=0$ for $j=0,\ldots ,-a$ and $C_{j-a+1}= \displaystyle \prod _{i=1}^k(j+i)_q^{\beta _i}$ . The left-hand side of equation (4.4) is then $t^{1-a}$ times the left-hand side of equation (4.2). It follows that $H_j(\lambda ,q)=A_{0^{j-1+a}\beta 0^{r-k+1-a-j}}(q)$ for $j=1-a,\ldots ,r-k+1-a$ and is zero otherwise.

We have shown that every nonzero q-hit polynomial is a remixed Eulerian number $A_c(q)$ , where c has interval support. Conversely, given a composition $\beta =(\beta _1,\ldots ,\beta _k)$ , it is always possible to construct $\lambda $ such that $B(\lambda )=\beta $ , and thus, $H_j(\lambda ,q)=A_{0^j\beta 0^{r-k-j}}(q)$ as above.

Indeed, let $l^r(\beta )=(l_1,\ldots ,l_r)$ be obtained by concatenating $\beta _k$ occurrences of k, $\beta _{k-1}$ occurrences of $k-1$ and so on until $\beta _1$ occurrences of $1$ . If one defines with componentwise subtraction, then $\lambda $ corresponds to a Young diagram inside an $r\times r$ square that satisfies $B(\lambda )=\beta $ .

5 Degree, symmetry, unimodality

In this section, we study the $A_{c}(q)$ as polynomials in q. They are known to have nonnegative integer coefficients, cf. [18, Proposition 5.4]. We will revisit the proof of this fact to show that the $A_{c}(q)$ are symmetric and unimodal. To do this, we first need to determine the degree and valuation of $A_{c}(q)$ .

5.1 Degree and valuation

The following simple relation was recorded as Theorem 1.3 (2) in the introduction. For any finite sequence $a=(a_1,a_2,\ldots ,a_k)$ , define $\mathrm {rev}(a)=(a_k,a_{k-1},\ldots ,a_1)$ .

Lemma 5.1. Let $c=(c_1,\dots ,c_{r})\in \mathcal {W}_{r}^{}$ . Then we have

$$\begin{align*}A_c(q)=q^{\binom{r}{2}}A_{\mathrm{rev}(c)}(q^{-1}). \end{align*}$$

Proof. This is straightforward from the probabilistic perspective. Indeed, we can reverse the lattice of sites $\mathbb {Z}$ , and then consider the IDLA ² process obtained by swapping $q_L$ and $q_R$ . The probability of reaching the stable configuration $[r]$ starting from $\mathrm {rev}(c)$ in this flipped process (with $q=q_R/q_L$ ) is the same as that of reaching $[r]$ starting from c in the original description (with $q^{-1}=q_L/q_R$ ). This implies the equality in question.

Given $c\in \mathcal {W}_{r}^{}$ , we let $D_c$ denote the degree of $A_c(q)$ . We also define $d_c$ as the valuation of $A_c(q)$ , that is, the smallest exponent of q with a nonzero coefficient.

Remark 5.2. Before the general case, let us characterize the c such that $d_c=0$ . Equivalently, we need to determine when the constant term $A_c(0)$ vanishes. From the probabilistic process point of view, $q=0$ corresponds to particles only jumping right. It is then easily shown that $A_c(0)$ is zero unless c satisfies $\displaystyle \sum _{i\leq j} c_i\geq j$ for $j=1,\dots ,r$ , in which case $A_c(0)=1$ . It follows immediately that $d_c=0$ if and only if that condition is satisfied.

It turns out that $A_c(q)$ is symmetric with respect to the interval $[d_c,D_c]$ , as we shall show in Theorem 5.6. To this end, we collect some notation that helps describe $D_c$ and $d_c$ combinatorially. For $t\in \mathbb {R}$ , we use

The following pictorial perspective for $c\in \mathcal {W}_{r}^{}$ is occasionally useful. Recall that a Łukasiewicz path is a (finite) lattice path beginning at the origin that takes steps corresponding to translations by $(1,k)$ for $k\geq -1$ . Attach a Łukasiewicz path $P_c$ with $c=(c_1,\dots ,c_r)$ by starting at the origin and translating by $(1,c_i-1)$ as c is read from left to right. See Figure 4. For $i\in [r]$ , we define $h_i(c)$ to be the ordinate on $P_c$ after the ith step. More precisely, $h_i(c)=\displaystyle\sum _{1\leq j\leq i}(c_j-1)$ . Note that $h_r(c)$ is necessarily $0$ . We let

(5.1)

(5.2)

Figure 4 $P_{c}$ when ${c}=(0,3,0,0,0,1,3)$ .

Theorem 5.3. Let $c=(c_1,\dots ,c_{r})\in \mathcal {W}_{r}^{}$ . The following equalities hold:

(5.3) $$ \begin{align}d_c&=H^{-}(c),\end{align} $$

(5.4) $$ \begin{align}D_c&=\binom{r}{2}-\sum_{1\leq i\leq r-1} (h_i(c))^+.\end{align} $$

The reader will note that equation (5.3) generalizes the result of Remark 5.2, as well as the power of q in Proposition 4.2.

Proof. First, we establish equation (5.3). The claim is true when $c=(1^{r})$ . In this case, $A_c(q)=(r)_q!$ and we have $d_c=0=H^{-}(c)$ . We proceed by (downward) induction on the number of parts in c that equal $1$ .

Consider $i\in [r]$ such that $c_i\geq 2$ . Let $[a,b]$ be the maximal interval in $\mathrm {Supp}(c)$ containing i. We have by equation (2.4) that

(5.5) $$ \begin{align} (b-a+2)_qA_{c}(q)=q^{i-a+1}(b-i+1)_qA_{L_i(c)}(q)+(i-a+1)_qA_{R_i(c)}(q). \end{align} $$

It follows that the following relation holds

(5.6) $$ \begin{align} d_c=\min(i-a+1+d_{L_i(c)}, d_{R_i(c)}). \end{align} $$

We want to check that $H^-(c)$ satisfies the same recurrence. Consider the boundary cases first. If $a=1$ , only $R_i(c)$ is defined, and it is easily checked that $H^{-}(c)=H^{-}(R_i(c))$ . If $b=r$ , only $L_i(c)$ is defined and we need to check that $H^{-}(c)=i-a+1+H^{-}(L_i(c))$ . Note that we have $c_{j}>0$ for all $j\in [a,r]$ and $c_{a-1}=0$ . From this, and the fact that $h_{r}(c)=0$ , it follows that $h_j(c)\leq 0$ for all $j\in [a-1,r]$ . Furthermore since $c_i\geq 2$ we are in fact guaranteed that $h_{j}(c)<0$ for $j\in [a-1,i-1]$ . Now, $h(L_i(c))$ is obtained from $h(c)$ by adding $1$ to all entries $h_j(c)$ for $j\in [a-1,i-1]$ and leaving the rest unchanged. Since $h_j(c)<0$ for such j, we still have $h_j(L_i(c))\leq 0$ . It follows that $H^{-}(c)=i-a+1+H^{-}(L_i(c))$ in this case.

We now consider the generic situation where $1<a\leq b<r$ . The arguments are similar to those just presented, and we keep the exposition terse. We set $h_0(c)=0$ . Now, note that the hypotheses on $a,b,i$ are equivalent to

$$\begin{align*}h_{a-2}>h_{a-1}\leq h_{a}\leq \dots \leq h_{b-1}\leq h_b>h_{b+1}\end{align*}$$

and $h_{i-1}<h_{i}$ . Then $h(L_i(c))$ is obtained by adding from $h(c)$ by adding $1$ to $h_{a-1},\ldots ,h_{i-1}$ , while $h(R_i(c))$ is obtained from $h(c)$ by subtracting $1$ from $h_{i},\ldots ,h_{b}$ .

It is clear from this description that $H^-(c) \leq i-a+1+H^-({L_i(c)})$ and $H^-(c)\leq H^-({R_i(c)})$ . To show that it is equal to one of them, consider the sign of $h_i$ . If $h_i>0$ , then $h_i,\ldots ,h_b>0$ from which it follows $H^-(c)=H^-(R_i(c))$ . If $h_i\leq 0$ , then $h_{a-1},\ldots ,h_{i-1}< 0$ , and so these $i-a+1$ values imply $H^-(c)=i-a+1+H^-({L_i(c)})$ .

We finally establish equation (5.4). It follows from Lemma 5.1 that

$$\begin{align*}d_{\mathrm{rev}(c)}+D_c=\binom{r}{2}. \end{align*}$$

Now, $h_i(\mathrm {rev}(c))=-h_{r-i}(c)$ for $i\in [0,r]$ by a direct computation. Using equation (5.3), the claim follows.

In terms of the path $P_c$ , we have that $d_c$ equals the sum of the absolute values of the heights of all lattice points that lie strictly below the x-axis, and $D_c$ equals $\binom {r}{2}-$ sum of the heights of all lattice points that are strictly above the x-axis.

Example 5.4. For $c=(0,3,0,0,0,1,3)$ , the Łukasiewicz path in Figure 4 tells us that

$$ \begin{align*} d_c&=1+1+2+2=6\\ D_c&=\binom{7}{2}-1=20. \end{align*} $$

As a matter of fact, the full polynomial $A_{c}(q)$ is given by

$$\begin{align*}2 q^{20} + 6 q^{19} + 11 q^{18} + 18 q^{17} + 27 q^{16} + 35 q^{15} + 40 q^{14} &+ 42 q^{13} + 40 q^{12} + 35 q^{11}\\ &+ 27 q^{10} + 18 q^{9} + 11 q^{8} + 6 q^{7} + 2 q^{6}. \end{align*}$$

We remark that we have a symmetric polynomial above. This is quite surprising, as no symmetry is apparent in c. It turns out to be a general fact, valid for all polynomials $A_c(q)$ , that we will now prove together with unimodality.

5.2 Symmetry and unimodality

Let us say that a polynomial $P(q)$ is $\mathrm {psu}(N)$ if it has positive coefficients and is unimodal and symmetric with respect to $N/2$ . Note that N is then the sum of the degree and valuation of P. We have the following classical properties; see [7] for instance.

Lemma 5.5. If P and Q are $\mathrm {psu}(N)$ , then $P+Q$ is $\mathrm {psu}(N)$ .

If P is $\mathrm {psu}(N)$ and Q is $\mathrm {psu}(N')$ , then $PQ$ is $\mathrm {psu}(N+N')$ .

We introduce the reduced remixed Eulerian numbers [18]

(5.7)

where $m_1,\dots ,m_p$ are the cardinalities of the maximal intervals $I_1,\dots ,I_p$ in $\mathrm {Supp}(c)$ , ordered from left to right. Using the notations $i,a,b,L_i(c),R_i(c)$ in the recurrence relations (2.4) for ${A}_{c}(q)$ , the $\tilde {A}_{c}(q)$ satisfy the modified recurrence relation ([18, Proof of Prop. 5.4])

(5.8) $$ \begin{align} \tilde{A}_{c}(q)=b_L\;q^{i-a+1}(b-i+1)_q\;\tilde{A}_{L_i(c)}(q)+b_R\;(i-a+1)_q\;\tilde{A}_{R_i(c)}(q), \end{align} $$

where $b_L,b_R$ are defined as follows. Let j be the index such that $I_j=[a,b]$ .

• • If $j>1$ and $I_{j-1}=[f,a-2]$ for a certain f, then $b_L=\genfrac (){0pt}{}{b-f+1}{b-a+2}_q$ . Otherwise, $b_L=1$ .

• • If $j<p$ and $I_{j+1}=[b+2,g]$ for some $g\leq r$ , then $b_R=\genfrac (){0pt}{}{g-a+1}{b-a+2}_q$ . Otherwise, $b_R=1$ .

In any case, note that both $b_R$ and $b_L$ are $\mathrm {psu}(N)$ for some N (in general distinct): Indeed, the Gaussian binomial coefficient $\genfrac (){0pt}{}{n}{k}_q$ is known to be $\mathrm {psu}(k(n-k))$ .

Theorem 5.6. For any $c\in \mathcal {W}_{r}^{}$ , we have that $\tilde {A}_c(q)$ is $\mathrm {psu}\left (\binom {r}{2}-H(c)-\sum _j\binom {m_j}{2}\right )$ . It follows that $A_c(q)$ is $\mathrm {psu}\left (\binom {r}{2}-H(c)\right )$ .

Proof. We establish some notation for convenience. Suppose the lengths of the maximal intervals in $\mathrm {Supp}(c)$ are $m_1$ through $m_p$ . We let

(5.9)

We have $A_{c}=\tilde {A}_{c}\prod _j (m_j)_q!$ , and each $(m_j)_q!$ is $\mathrm {psu}(\binom {m_j}{2})$ . By Lemma 5.5, the result for $A_c$ thus follows from the one for $\tilde {A}_{c}$ . We proceed to prove the latter by induction on .

The base case corresponds to $c=(1^r)$ , for which $\tilde {A}_{c}(q)=1$ and the claim is clearly true. Now, assume $e(c)>0$ , and consider the recurrence (5.8) for a fixed i with $c_i\geq 2$ : we retain the notations $a,b,L_i(c),R_i(c)$ . Note first that $d_c+D_c=\binom {r}{2}-H(c)$ by summing the expressions in equations (5.3) and (5.4). It then follows from the description of $h(L_i(c))$ and $h(R_i(c))$ given in the proof of equation (5.3) that $d_{L_i(c)}+D_{L_i(c)}=d_c+D_c-(i-a+1)$ and $d_{R_i(c)}+D_{R_i(c)}=d_c+D_c+(b-i+1)$ .

Since $e(L_i(c))=e(R_i(c))=e(c)-1$ , we can apply induction to conclude that $\tilde {A}_{L_i(c)}(q)$ and $\tilde {A}_{R_i(c)}(q)$ are $\mathrm {psu}\left (\binom {r}{2}-H(L_i(c))-n(L_i(c))\right )$ and $\mathrm {psu}\left (\binom {r}{2}-H(R_i(c))-n(R_i(c))\right )$ , respectively. Let $B_i$ and $C_i$ denote the left and right summands on the right-hand side of equation (5.8). It will suffice to show that $B_i$ and $C_i$ are both $\mathrm {psu}\left (\binom {r}{2}-H(c)-n(c)\right )$ ; by Lemma 5.5 so is their sum $\tilde {A}_c$ which then completes the proof.

We focus on $B_i$ , the proof for $C_i$ being entirely similar. Assume first that $b_L=1$ . Then

(5.10) $$ \begin{align} \deg(B_i)+\mathrm{val}(B_i)&=2(i-a+1)+b-i+\binom{r}{2}-H(L_i(c))-n(L_i(c))\nonumber\\ &=b+i-2a+2+\binom{r}{2}-H(L_i(c))-n(L_i(c)). \end{align} $$

Note that $H(L_i(c))-H(c)=i-a+1$ . Since $b_L=1$ , we know that $n(L_i(c))-n(c)=b-a+1$ . Thus, we may rewrite equation (5.10) as

(5.11) $$ \begin{align} \deg(B_i)+\mathrm{val}(B_i)=\binom{r}{2}-H(c)-n(c), \end{align} $$

which disposes off the case $b_L=1$ .

To finish this proof, we finally consider the case where $b_L=\genfrac (){0pt}{}{b-f+1}{b-a+2}_q$ . This time we get

(5.12) $$ \begin{align} \deg(B_i)+\mathrm{val}(B_i)&=b+i-2a+2+(a-f-1)(b-a+2)+\binom{r}{2}-H(L_i(c))-n(L_i(c))\nonumber\\ &=i-a+(a-f)(b-a+2)+\binom{r}{2}-H(L_i(c))-n(L_i(c)). \end{align} $$

Like before, the equality $H(L_i(c))-H(c)=i-a+1$ holds. Unlike before, we have

(5.13) $$ \begin{align} n(L_i(c))-n(c)&=\binom{b-f+1}{2}-\binom{a-f-1}{2}-\binom{b-a+1}{2}\\ &=(a-f)(b-a+2)-1. \nonumber \end{align} $$

We leave it to the reader to put the pieces together and conclude that equation (5.11) holds.

Example 5.7. Recall that we computed $A_c(q)$ for $c=(0,3,0,0,0,1,3)$ in Example 5.4, and it is seen to be $\mathrm {psu}(26)$ , which is in accordance with Theorem 5.6. Indeed, $\binom {7}{2}-H(c)=21+5=26$ .

6 q-volumes and a dissection of the permutahedron

In this section and the next, we will give a second combinatorial interpretation of $A_c(q)$ after the one in Section 3. As we will show in Section 7, it can be interpreted as extending the one given by Liu [15] for $q=1$ . In order to interpret the parameter q, we will use a decomposition of the permutahedron into cubes which is of independent interest.

6.1 The polytopes $\mathbf {C}_\lambda (u)$

Fix $\lambda \in \mathbb {R}^{r+1}=(\lambda _1,\lambda _2,\dots ,\lambda _{r+1})$ such that $\lambda _i\geq \lambda _{i+1}$ for $i=1,\ldots ,r$ . For the next definition, we embed $\mathbb {S}_{r}$ into $\mathbb {S}_{r+1}$ as usual by treating $r+1$ as a fixed point. Recall that $s_i$ for $1\leq i\leq r$ is the simple transposition that swaps i and $i+1$ . Recall further from the introduction that given $v\in \mathbb {S}_{r+1}$ , we let .

Definition 6.1. For $u\in \mathbb {S}_{r}$ , consider the interval $I_u=[u,s_1s_2\cdots s_{r}u]$ in the Bruhat order on $\mathbb {S}_{r+1}$ . The polytope $\mathbf {C}_\lambda (u)$ is defined as the convex hull in $\mathbb {R}^{r+1}$ of the points $\lambda _v$ for $v\in I_u$ .

We multiply permutations from right to left, so if $u=u_1,\ldots ,u_r,r+1$ in one-line notation, then $s_1s_2\cdots s_{r}u=u_1+1,\ldots ,u_r+1,1$ .

Example 6.2. For $r=1$ , we have $u=1$ which $I_1=[12,21]=\{12,21\}\subseteq \mathbb {S}_2$ .

For $r=2$ , we get $I_{12}=[123,231]=\{123,213,132,231\}$ and $I_{21}=[213,321]=\{213,231,312,321\}$ .

For $r=3$ and $\lambda =(3,2,1,0)$ , the six polytopes $\mathbf {C}_\lambda (u)$ for $u\in \mathbb {S}_r$ are illustrated at the bottom left of Figure 5. They are all Bruhat interval polytopes introduced by Tsukerman–Williams [25].

Figure 5 Slicing of the three dimensional permutahedron (top), its full dissection into cubes (bottom left) and the associated cubical complex (bottom right).

Remark 6.3. Recall that the $\lambda _v$ for $v\in \mathbb {S}_{r+1}$ are the vertices of the permutahedron $\mathrm {Perm}(\lambda )$ . It follows that the $\lambda _v$ for $v\in I_u$ are the vertices of $\mathbf {C}_\lambda (u)$ for any $u\in \mathbb {S}_r$ .

This description of $\mathbf {C}_{\lambda }(u)$ , while possessing the virtue of brevity, is not entirely convenient in practice as it requires listing elements of $I_u$ . We now proceed to give another perspective on $I_u$ which is more enlightening.

Recall that the code $\mathrm {code}(w)$ of a permutation $w\in \mathbb {S}_{r+1}$ is the weak composition $(c_1,\dots ,c_{r+1})$ where $c_i=|\{j>i\;|\; w_i>w_j\}|$ . For instance, $\mathrm {code}(23514)=(1,1,2,0,0)$ . It sends $\mathbb {S}_{r+1}$ bijectively to the sequences $(c_1,\dots ,c_{r+1})$ such that $0\leq c_i\leq r+1-i$ for all i.

Lemma 6.4. For any $u\in \mathbb {S}_{r}$ , the Bruhat interval $I_u$ of $\mathbb {S}_{r+1}$ is isomorphic to the Boolean lattice $\mathbb {B}_{r}$ of cardinality $2^r$ .

Proof. Denote the bottom and top element of $I_u$ , respectively, by $u_-=u_1,\dots ,u_r,r+1$ and $u_+=u_1+1,\dots ,u_r+1,1$ in one-line notation.

Given $S\subset [r]$ , let $\mathbf {e}_S\in \mathbb {R}^{r+1}$ denote the indicator vector of S, that is, $\mathbf {e}_S$ equals the sum of the standard basis vectors $e_i$ (in $\mathbb {R}^{r+1}$ ) for $i\in S$ . Define

We claim that $v\in I_u$ (i.e., $u_-\leq v\leq u_+$ in Bruhat order) if and only $\mathrm {code}(v)\in J_u$ , and that this gives a poset isomorphism (the order on weak compositions is componentwise). Note that this proves the lemma since $J_u$ is clearly order isomorphic to $\mathbb {B}_r$ .

We have $\mathrm {code}(u_+)=\mathrm {code}(u_-)+\mathbf {e}_{[r]}$ as is checked immediately. Therefore, $J_u$ consists of all weak compositions c such that $\mathrm {code}(u_-)\leq c \leq \mathrm {code}(u_+)$ .

We leave it to the reader to check that the full claim follows from invoking the following well-known tableau criterion: $u\leq v$ in Bruhat order if for any i, the weakly increasing rearrangement of $u_1\ldots u_i$ is smaller, componentwise, than the weakly increasing rearrangement of $v_1\ldots v_i$ . In view of this, the condition $u_-\leq v\leq u_+$ translates to exactly two choices for each $v_i$ as i goes from $1$ through r.

6.2 The cube decomposition

We recall the classical bijection $u\mapsto \mathrm {T}(u)$ between $\mathbb {S}_{r}$ and decreasing binary trees. $\mathrm {T}(u)$ is defined more generally for u a word with distinct letters in $\mathbb {Z}_{>0}$ . Assume $u=u_LMu_R$ , where M is the maximal integer in u. Then $\mathrm {T}(u)$ is constructed recursively as the binary tree with root label M whose left (resp. right) subtree is $\mathrm {T}(u_L)$ (resp. $\mathrm {T}(u_R)$ ). For instance, the tree in Figure 6 corresponds to the permutation $u=47128635$ .

Figure 6 Decreasing tree $\mathrm {T}(u)$ for $u=47128635$ .

Given $u\in \mathbb {S}_{r}$ and $i\in [r]$ , let and , where $f_i,g_i\geq 0$ are maximal such that $u_j<u_i$ for $j\in L(u,i)\cup R(u,i)$ . These are the labels of the descendants of the node i in $\mathrm {T}(u)$ : More precisely, $L(u,i)$ (resp. $R(u,i)$ ) is the set of labels of the left (resp. right) subtree of that node.

We now assume $\lambda _i>\lambda _{i+1}$ for $i=1,\ldots ,r$ . Although the next theorem can be adapted for cases with identical values, we do not need it since we will be interested in the volume of $\mathrm {Perm}(\lambda )$ , for which we will obtain polynomial formulas in the $\lambda _i$ that will still be valid in the general case.

Theorem 6.5. The $r!$ polytopes $\{\mathbf {C}_\lambda (u)\}_{u\in \mathbb {S}_{r}}$ are combinatorial cubes that are the maximal faces of a polyhedral subdivision of $\mathrm {Perm}(\lambda )$ .

The facet description of $\mathbf {C}_\lambda (u)$ is given by

(6.1) $$ \begin{align} \hspace{-11pt}\mathrm{(left)} \hspace{5mm} t_{u_i}+\sum_{j\in L(u,i)}t_{u_j}&\leq \lambda_{i-f_i}+\dots+\lambda_i; \end{align} $$

(6.2) $$ \begin{align} \mathrm{(right)}\hspace{5mm} t_{u_i}+\sum_{j\in R(u,i)}t_{u_j}&\geq \lambda_{i+1}+\dots+\lambda_{i+g_i+1}, \end{align} $$

for $i=1,\ldots ,r$ .

Proof. Recall that we assume $\lambda _i>\lambda _{i+1}$ for $i=1,\ldots ,r$ . We have that $\mathrm {Perm}(\lambda )$ is contained between the hyperplanes $x_1=\lambda _1$ and $x_1=\lambda _{r+1}$ .

Now, fix i satisfying $1\leq i\leq r$ , and consider the slice . The sections of $P_i$ for $\lambda _i\geq t\geq \lambda _{i+1}$ are explicitly described in Liu’s work [15, Proposition 3.7]:

$$\begin{align*}S_t=\{t\}\times\mathrm{Perm}(\lambda_1,\dots,\lambda_{i-1},\lambda_i+\lambda_{i+1}-t,\lambda_{i+2},\ldots,\lambda_{r+1}). \end{align*}$$

Note that $\lambda _{i-1}>\lambda _{i}+\lambda _{i+1}-t>\lambda _{i+2}$ for $\lambda _i\geq t\geq \lambda _{i+1}$ . It follows from that result that the slice $P_i$ is in particular combinatorially equivalent to the product of $[0,1]$ with a permutahedron of dimension one less. Proceeding inductively, one can decompose into cubes the two permutahedra that appear as intersections with the hyperplanes $x_1=\lambda _i$ and $x_1=\lambda _{i+1}$ . By taking the direct product with $[0,1]$ , we obtain the decomposition of $\mathrm {Perm}(\lambda )$ into cubes.

It is then easily checked inductively that these cubes are precisely the cubes $\mathbf {C}_{\lambda }(u)$ and that the facet description is as described in equations (6.1) and (6.2).

See Figure 5 for an illustration of the decomposition in the case of the three-dimensional standard permutahedron. We analyze the cube $\mathbf {C}_{\lambda }(213)$ to illustrate the preceding theorem. The table next displays all the relevant information along with the facet-defining inequalities. Each vertex of the cube is obtained by forcing exactly one of the two inequalities in any column to be an equality. Forcing all left (resp. right) inequalities to be equalities produce the vertex $\lambda _{u_-}$ (resp. $\lambda _{u_+}$ ) in the notation of Lemma 6.4.

Remark 6.6. When $u=id$ the polytope $\mathbf {C}_{\lambda }(u)$ is the Pitman–Stanley polytope [24], and the latter is well known to be a combinatorial cube. As we shall see in the next section, this is directly related to setting $q=0$ in our framework.

Remark 6.7. For any $\lambda ,u$ , the polytope $\mathbf {C}_{\lambda }(u)$ is a generalized permutahedron [21]. One needs to check that each edge of $\mathbf {C}_{\lambda }(u)$ is parallel to $e_i-e_j$ for some $i,j$ . Now, we know that the face poset of $\mathbf {C}_{\lambda }(u)$ corresponds to an interval in the Bruhat order, so adjacent vertices of $\mathbf {C}_{\lambda }(u)$ have coordinates $\lambda _v$ and $\lambda _{v'}$ , where v covers $v'$ in Bruhat order, which implies that $\lambda _v-\lambda _{v'}$ is parallel to $e_i-e_j$ for some $i,j$ as desired.

6.3 q-volume

We now recall the notion of q-volume of the permutahedron introduced by the authors [18, Section 9]. Given $\lambda $ , we define the q-volume of $\mathrm {Perm}(\lambda )$ as

(6.3) $$ \begin{align} V^q(\lambda)=\frac{1}{(r)_q!} \big\langle {(\lambda_1x_1+\cdots +\lambda_{r+1}x_{r+1})^{r}}\big\rangle_{r+1}^q. \end{align} $$

The remixed Eulerians arise as follows:

(6.4) $$ \begin{align} V^q(\lambda)&= \sum_{c\in \mathcal{W}_{r}^{}}A_{c}(q)\;\frac{(\lambda_1-\lambda_2)^{c_1}}{c_1!}\cdots \frac{(\lambda_{r}-\lambda_{r+1})^{c_{r}}}{c_r!}. \end{align} $$

At $q=1$ , this recovers $V^{1}(\lambda )=\mathrm {vol}(\mathrm {Perm}(\lambda ))$ [21]. From the subdivision of $\mathrm {Perm}(\lambda )$ into cubes $(\mathbf {C}_{\lambda }(u))_{u\in \mathbb {S}_r}$ it follows that

(6.5) $$ \begin{align} V^{1}(\lambda)=\mathrm{vol}(\mathrm{Perm}(\lambda))=\sum_{u\in \mathbb{S}_r} \mathrm{vol}(\mathbf{C}_{\lambda}(u)). \end{align} $$

Theorem 6.8 below is a q-deformation of this equality by weighing each summand by $q^{\ell (u)}$ . To prove it, we will need some results from [8, Section 6].

To each $u\in \mathbb {S}_r$ , one can associate a Richardson variety

(6.6) $$ \begin{align} R(u)=X_{1\times w_o^{r}u}\cap X^{u} \end{align} $$

in the variety of complete flags of $\mathbb {C}^{r+1}$ . Its cohomology class can be represented by the product of Schubert polynomials $\mathfrak {S}_{u}\mathfrak {S}_{1\times w_o^{r}u}$ , and its volume polynomial is then given by:

(6.7) $$ \begin{align} \mathrm{Vol}_{\lambda}(R(u))=\frac{1}{(r)_q!}\;\partial_{w_o}\left(\left(\sum_i\lambda_ix_i\right)^r\mathfrak{S}_{u}\mathfrak{S}_{1\times w_o^{r}u}\right). \end{align} $$

It is shown in [8, Remark 6.5] that $R(u)$ is a toric variety and that $\mathrm {Vol}_{\lambda }(R(u))=\mathrm {vol}(\mathbf {C}_\lambda (u))$ . We emphasize here that $w_o$ is the longest element in $\mathbb {S}_{r+1}$ while $w_o^r$ is the longest element in $\mathbb {S}_r$ .

Theorem 6.8. For any $\lambda $ , we have

(6.8) $$ \begin{align} V^q(\lambda)=\sum_{u\in \mathbb{S}_r}q^{\ell(u)} \,\mathrm{vol}(\mathbf{C}_\lambda(u)). \end{align} $$

Proof. Throughout this proof, set and . By definition of q-divided symmetrization (1.3), we have

(6.9) $$ \begin{align} V^q(\lambda)=\frac{1}{(r)_q!}\;\partial_{w_o}\left(L^rP_r\right). \end{align} $$

We now link $P_r$ to double Schubert polynomials. Letting $w_o^r$ denote the longest element in $\mathbb {S}_r$ interpreted as a permutation in $\mathbb {S}_{r+1}$ by affixing $r+1$ as a fixed point, we have the following equality for the dominant double Schubert polynomial

(6.10) $$ \begin{align} \mathfrak{S}_{w_o^{r}}(x_1,\ldots,x_{r+1};y_1,\ldots,y_{r+1})=\prod_{i+j\leq r}(x_i-y_j). \end{align} $$

This by comparison yields

(6.11) $$ \begin{align} P_r=\mathfrak{S}_{w_o^{r}}(qx_1,\ldots,qx_{r+1};x_{r+1},\ldots,x_{1}). \end{align} $$

Now, by Cauchy’s formula [16, Proposition 2.4.7], for any permutation $w\in \mathbb {S}_{r+1}$ , one has

(6.12) $$ \begin{align} \mathfrak{S}_{w}(x_1,\dots,x_{r+1};y_1,\dots,y_{r+1})&=\sum_{\substack{u,v\in\mathbb{S}_{r+1}\\ v^{-1}u=w\\ \ell(v)+\ell(u)=\ell(w)}}\mathfrak{S}_{u}(x_1,\ldots,x_{r+1})\mathfrak{S}_{v}(-y_1,\ldots,-y_{r+1})\nonumber\\ &= \sum_{\substack{u,v\in\mathbb{S}_{r+1}\\ v^{-1}u=w\\ \ell(v)+\ell(u)=\ell(w)}}\mathfrak{S}_{u}(x_1,\ldots,x_{r+1})\mathfrak{S}_{w_ovw_o}(y_{r+1},\ldots,y_{1}), \end{align} $$

where the second equality is modulo the ideal $I_{r+1}$ in $\mathbb {Q}[x_1,\dots ,x_{r+1}]$ generated by symmetric polynomials with zero constant term. Indeed, $\mathfrak {S}_{v}(-y_1,\dots ,-y_{r+1})=\mathfrak {S}_{w_ovw_o}(y_{r+1},\dots ,y_1)\ \mod I_{r+1}$ .

Now, on setting $w=w_0^r$ in (6.12) and combining with equation (6.11), we get:

(6.13) $$ \begin{align} P_r=\sum_{\substack{u,v\in\mathbb{S}_{r+1}\\ v^{-1}u=w_o^r\\ \ell(v)+\ell(u)=\ell(w_o^r)}}q^{\ell(u)}\mathfrak{S}_{u}(x_1,\ldots,x_{r+1})\mathfrak{S}_{w_ovw_o}(x_1,\ldots,x_{r+1})\ \mod I_{r+1}. \end{align} $$

As explained in [20, Section 9.5], the indexing set in equation (6.13) may be simplified to give

(6.14) $$ \begin{align} P_r=\sum_{u\in \mathbb{S}_r} q^{\ell(u)}\mathfrak{S}_{u}\mathfrak{S}_{1\times w_o^ru}\quad \mod I_{r+1}. \end{align} $$

Now, note that we may replace $P_r$ in equation (6.9) by any homogeneous polynomial of the same degree equivalent modulo $I_{r+1}$ . Substituting in equation (6.9), we get

(6.15) $$ \begin{align}V^q(\lambda)=\sum_{u\in \mathbb{S}_r}q^{\ell(u)} \frac{1}{(r)_q!}\;\partial_{w_o}\left(L^r\mathfrak{S}_{u}\mathfrak{S}_{1\times w_o^{r}u}\right)=\sum_uq^{\ell(u)}\mathrm{Vol}_\lambda(R(u)), \end{align} $$

where we used equation (6.7) in the last equality. We can then conclude since $\mathrm {Vol}_\lambda (R(u))=\mathrm {vol}(\mathbf {C}_\lambda (u))$ as recalled before the theorem.

Theorem 6.8 further justifies dubbing $V^q(\lambda )$ a q-volume. Based on this result and the expansion (1.1), we give a combinatorial interpretation of remixed Eulerian numbers in Section 7. We end this section with some remarks.

Remark 6.9. Setting $q=0$ in equation (6.8), we have that $V^0(\lambda )$ is the volume of $\mathbf {C}_\lambda (id)$ . This polytope is the Pitman–Stanley polytope as noticed in Remark 6.6. Using Remark 5.2, it is then immediate that the expansion (6.4) at $q=0$ recovers the well-known expansion in [24, Theorem 1].

Remark 6.10. It would be nice to have a more direct proof of the previous result, avoiding the use of the Richardson variety $R(u)$ . A possibility would be to show by a direct computation that

$$\begin{align*}v_q(\mu)=\sum_{i=1}^{r}q^{i-1}\int_{0}^{\mu_i}v_q(\mu_1,\dots,\mu_{i-2},\mu_{i-1}+\mu_i-t,t+\mu_{i+1},\mu_{i+2},\dots,\mu_r) \,\mathrm{d}t, \end{align*}$$

where $v_q(\mu )$ is the expression of $V^q(\lambda )$ in terms of $\mu _i=\lambda _{i}-\lambda _{i+1}$ . ³ Indeed, this recurrence relation is satisfied by the right-hand side in Theorem 6.8 by slicing the permutahedron as in the proof of Theorem 6.5. This is in fact the q-deformation of [15, Proposition 3.9]; we come back to this in Section 7.2.

Remark 6.11. Let $\mathcal {T}_{r}$ denote the set of (rooted) complete binary trees with r internal nodes. Fix $T\in \mathcal {T}_{r}$ . We denote by $\mathcal {S}_T$ the set of all permutations in $\mathbb {S}_{r}$ whose decreasing tree (completed so that it has $r+1$ unlabeled leaves) has underlying shape T. Theorem 6.5 implies that as u ranges over $\mathcal {S}_T$ , the cubes $\mathbf {C}_{\lambda }(u)$ are all congruent, that is, they differ only up to a permutation of coordinates. Thus, we may without any harm consider our cubes to be indexed by trees in $\mathcal {T}_{r}$ .

Endow T with the binary search labeling. This has the advantage that rewriting inequalities in Theorem 6.5 with the new coordinates results in inequalities of the form $t_{i}+\cdots +t_j \geq \lambda _{i+1}+\cdots + \lambda _{j+1}$ or $t_{i}+\cdots +t_j\leq \lambda _{i}+\cdots +\lambda _{j}$ . It follows from [14, Definition 3.3] that $\mathbf {C}_{\lambda }(T)$ is an alcoved polytope. Since $\mathbf {C}_{\lambda }(T)$ is also a generalized permutahedron, we infer that $\mathbf {C}_{\lambda }(T)$ is a polypositroid [14, Definition 3.8]. In particular, each $\mathbf {C}_{\lambda }(u)$ is obtained by permuting coordinates in $\mathbf {C}_{\lambda }(T)$ according to u.

Remark 6.12. In view of the preceding remark, we may compactify the $V^q(\lambda )$ as a sum over $\mathcal {T}_{r}$ :

(6.16) $$ \begin{align} V^q(\lambda)=\sum_{u\in \mathbb{S}_{r}} q^{\ell(u)}\mathrm{vol}(\mathbf{C}_{\lambda}(u))=\sum_{T\in \mathcal{T}_{r}} \mathrm{vol}(\mathbf{C}_{\lambda}(T))\sum_{u\in \mathcal{S}_T}q^{\ell(u)}. \end{align} $$

Appealing to the q-hook length formula for binary trees we get

(6.17) $$ \begin{align} V^q(\lambda)=\sum_{T\in \mathcal{T}_{r}} \mathrm{vol}(\mathbf{C}_{\lambda}(T))\times q^{\mathrm{stat}(T)}\frac{(r)_q!}{\prod_{v\in T}(h_v)_q!}, \end{align} $$

where $\mathrm {stat}(T)$ is the sum over all internal nodes of the number of right edges in the unique path from root to node, though this precise description is not relevant for the discussion at hand. Given the expression for q-volume in equation (6.17) as a sum over binary trees involving the hook length formula, it is natural to compare it with [21, Theorem 17.1] that expresses the ordinary volume of the permutahedron as a sum over binary trees as well. When we set $q=1$ and specialize to the case of the standard permutahedron, it can be checked that $\mathrm {vol}(\mathbf {C}_{\lambda }(T))$ does not become the product on the right-hand expression in loc. cit.. In particular, our expansion does not yield Postnikov’s hook length formula [21, Corollary 17.3] despite the similarity.

7 Combinatorial interpretation via bilabeled trees

We turn our attention to providing a combinatorial interpretation for $A_c(q)$ using the q-volume perspective coupled with work of [8]. The overarching idea is that the cubes $\mathbf {C}_{\lambda }(u)$ are obtained as images of certain special faces of the Gelfand–Tsetlin polytope $\mathrm {GT}(\lambda )$ under a simple volume-preserving map.

7.1 Gelfand–Tsetlin polytope, face diagrams and shifted tableaux

The Gelfand–Tsetlin polytope $\mathrm {GT}(\lambda ) \subset \mathbb {R}^{\binom {n}{2}}$ contains all points $(x_{ij})_{1\leq i\leq j\leq n}$ , where

(7.1) $$ \begin{align} x_{i,j-1}\geq x_{i,j} \geq x_{i+1,j} \end{align} $$

holds for all $1\leq i<j\leq n$ . Here, we assume that $x_{ii}=\lambda _i$ for all $i\in [n]$ . Points in $\mathrm {GT}(\lambda )$ can be interpreted as fillings of a triangular array as shown in Figure 7 subject to conditions in equation (7.1).

Figure 7 Gelfand–Tsetlin pattern.

The authors of [8] take inspiration from work of Kogan [13], Kiritchenko [11], Kiritchenko–Smirnov–Timorin [10], and use a combinatorial gadget called face diagrams to emphasize equalities defining faces of $\mathrm {GT}(\lambda )$ .

Consider a graph on a set of $\binom {n+1}{2}$ vertices, each placed at the centre of the boxes in Figure 7. We address the vertex in row i from the top and column j from the left by $(i,j)$ . Faces of $\mathrm {GT}(\lambda )$ of interest to us are determined by declaring at most one inequality among $x_{i,j} \leq x_{i,j+1}\leq x_{i+1,j+1}$ to be an equality. Pictorially, we emphasize this equality by drawing an edge between the appropriate vertices. The resulting graphs are called face diagrams.

The face diagrams we are interested in are indexed by permutations. Pick $u\in \mathbb {S}_{r}$ , and let $(d_1,\dots ,d_r)$ be such that $\mathrm {code}(u^{-1})=(d_1-1,\dots ,d_{r}-1)$ . Consider the face $\mathsf {F}(u)$ of $\mathrm {GT}(\lambda )$ (and face diagram $\mathrm {FD}(u)$ ) defined by the equalities

(7.2) $$ \begin{align} x_{i,i+j}=x_{i,i+j-1}\ \mathrm{for}\ 1\leq i<d_j; x_{i,i+j}=x_{i+1,i+j}\ \mathrm{for}\ d_j<i\leq r+1-j. \end{align} $$

Then $\mathsf {F}(u)$ is r dimensional. We now observe that the association $\mathrm {FD}(u)\leftrightarrow u$ is essentially the folklore bijection between decreasing binary trees and permutations described in Section 6.2.

Indeed, note the following aspect of $\mathrm {FD}(u)$ . For a fixed $j\in [r]$ , there exists a unique $i\in [r+1-j]$ such that the vertex $(i,i+j)$ is neither connected to the vertex immediately below nor connected to the vertex immediately to the left. Indeed this vertex is given by $(d_j,d_j+j)$ . We enrich $\mathrm {FD}(u)$ by introducing edges joining $(d_j,d_j+j)$ to $(d_j+1,d_j+j)$ and $(d_j,d_j+j-1)$ for each $j\in [r]$ . Additionally, we label the vertices $(d_j,d_j+j)$ by j. The resulting graph is connected and has $\binom {n+1}{2}-1$ edges and hence must be a tree (in a planar representation). One can treat it as a rooted binary tree with root given by the vertex $(1,n)$ . See Figure 8 (middle) for the enriched face diagram for $u=2647351 \in \mathbb {S}_7$ .

Figure 8 $\mathrm {FD}(u)$ for $u=2647351 \in \mathbb {S}_7$ (left) and the corresponding $(T,\mathrm {dec})$ (right).

Shrinking all paths present in the original $\mathrm {FD}(u)$ to length $0$ , we get a complete binary tree with r labeled internal nodes and $r+1$ unlabeled leaves. Ignoring leaves, one obtains the decreasing tree $(T,\mathrm {dec})$ attached to u. ⁴ Here, T records the unlabeled underlying tree and $\mathrm {dec}$ the decreasing labeling. See the decreasing tree on the right in Figure 8.

To give a combinatorial interpretation to $A_c(q)$ , we endow a decreasing tree (completed with unlabeled leaves) with an additional labeling $\mathrm {lr}$ of the nodes and leaves with distinct positive integers drawn from $\{1,\dots ,2r+1\}$ such that the label of any node is larger (resp. smaller) than that of its left (resp. right) child. Furthermore, the labels on the leaves increase when read from left to right. We call the triple $(T,\mathrm {dec},\mathrm {lr})$ a bilabeled tree. If the sequence of labels read off the leaves is $(1=\ell _1<\cdots < \ell _{r+1}=2r+1)$ , we define the content of the bilabeled tree by setting $c_i=\ell _{i+1}-\ell _i-1$ for $i\in [r]$ .

Theorem 7.1. For $c\in \mathcal {W}_{r}^{}$ , let $B(c)$ be the set of bilabeled trees with content c. We have

$$\begin{align*}A_c(q)=\sum_{(T,\mathrm{dec},\mathrm{lr})\in B(c)}q^{\ell(u)}, \end{align*}$$

where $u\in \mathbb {S}_r$ is the permutation determined by $(T,\mathrm {dec})$ .

Proof. It is shown in [8] that, under a simple transformation, the faces $\mathsf {F}(u)$ of $\mathrm {GT}(\lambda )$ are the $\mathbf {C}_{\lambda }(u)$ ; see [8, Theorem 5.4] and results in Section 6 in loc. cit. Therefore, $\mathrm {vol}(\mathsf {F}(u))=\mathrm {vol}(\mathbf {C}_{\lambda }(u))$ . The former quantity can be described in terms of shifted tableaux, which we then recast.

A shifted Young tableau P associated with $\mathsf {F}(u)$ is a filling of the cells in Figure 7 with entries from $\{1,\dots ,2r+1\}$ so that they increase weakly from left to right and top to bottom, and neighboring entries are equal if and only if the corresponding vertices are connected by an edge in $\mathrm {FD}(u )$ . The diagonal vector of P is the sequence of entries in the cells $(i,i)$ as i ranges from $1$ through $r+1$ .

By [8, Proposition 3.1]

(7.3) $$ \begin{align} \mathrm{vol}(\mathsf{F}(u))=\sum_{c\in \mathcal{W}_{r}^{}}\sum_{P\in \mathrm{ShT}(u,c)} \frac{(\lambda_1-\lambda_2)^{c_1}}{c_1!}\cdots\frac{(\lambda_r-\lambda_{r+1})^{c_r}}{c_r!}, \end{align} $$

where $\mathrm {ShT}(u,c)$ is the set of shifted tableaux associated to $\mathsf {F}(u)$ with prescribed diagonal vector $(1,c_1+2,c_1+c_2+3,\dots ,c_1+\dots +c_r+r+1)$ . Theorem 6.8 then becomes

(7.4) $$ \begin{align} V^q(\lambda)=\sum_{u\in \mathbb{S}_r}q^{\ell(u)} \sum_{c\in \mathcal{W}_{r}^{}}\sum_{P\in \mathrm{ShT}(u,c)} \frac{(\lambda_1-\lambda_2)^{c_1}}{c_1!}\cdots\frac{(\lambda_r-\lambda_{r+1})^{c_r}}{c_r!}. \end{align} $$

Comparing with equation (6.4) yields the following interpretation:

(7.5) $$ \begin{align} A_c(q)=\sum_{u\in \mathbb{S}_r}\sum_{P\in\mathrm{ShT}(u,c)} q^{\ell(u)}. \end{align} $$

Mimicking how we went from $\mathrm {FD}(u)$ to $(T,\mathrm {dec})$ , we can translate shifted tableaux to bilabeled trees— the inequalities defining the former translate into the ‘local binary search’ condition on the labeling $\mathrm {lr}$ while the diagonal vector gives the leaf labeling.

Example 7.2. Consider $c=(2,0,1)\in \mathcal {W}_{3}^{} $ . Figure 9 shows all bilabeled trees with content c. The blue labels on the outside record the $\mathrm {lr}$ labeling whereas the interior labels record the decreasing labeling. We get

$$ \begin{align*} A_{201}(q)=q^{\ell(123)}+q^{\ell(132)}+q^{\ell(231)}=1+q+q^2. \end{align*} $$

Figure 9 All bilabeled trees with content $(2,0,1)$ .

7.2 Connection with Liu’s work

We now demonstrate how the bilabeled tree construction is related to work of Liu [15].

Given a bilabeled tree $(T,\mathrm {dec},\mathrm {lr})$ with content c, consider the node $v_1$ labeled $1$ in the decreasing labeling; its children are leaves, say with labels $\ell _i<\ell _{i+1}$ in the labeling $\mathrm {lr}$ . Then we must have $c_i=\ell _{i+1}-\ell _i-1$ . Let j be the $\mathrm {lr}$ -label of $v_1$ . The local binary search condition tells us that $\ell _i<j<\ell _{i+1}$ .

If $i=1$ , then necessarily $j=2$ since $v_1$ is the only possible node with this label; similarly, if $i=r$ , then $j=2r$ . We obtain a bilabeled tree $(T',\mathrm {dec}',\mathrm {lr}')$ as follows:

• • $T'$ is obtained by replacing the node $v_1$ , and its two attached leaves by a single new leaf $leaf$ .

• • $\mathrm {dec}'$ is obtained by decreasing $\mathrm {dec}$ by one on the remaining nodes in $T'$ .

• • $\mathrm {lr}'$ is obtained by labeling the new leaf $leaf$ by j, and then relabeling via the unique increasing bijection $\{1,\dots ,2r+1\}\setminus \{\ell _i,\ell _{i+1}\}\to \{1,\dots ,2r-1\}$ .

Figure 10 shows an example of this procedure.

Figure 10 An example of $(T,\mathrm {dec},\mathrm {lr})\to (T',\mathrm {dec}',\mathrm {lr}') $ .

Note that the content of $(T',\mathrm {dec}',\mathrm {lr}')$ is $(c_1,\dots ,c_{i-2},c_{i-1}+(j-l_{i}-1),c_{i+1}+(l_{i+1}-j-1),c_{i+2},\dots ,c_r)$ . Also, all bilabeled trees with this content are obtained in the manner described above. We thus get

(7.6) $$ \begin{align} A_c=A_{(c_1+c_2-1,c_3,\dots,c_r)}+A_{(c_1,\dots,c_{r-2},c_{r-1}+c_r-1)} +\sum_{i=2}^{r-1}\sum_{t=0}^{c_i-1}A_{(c_1,\dots,c_{i-2},c_{i-1}+t,c_{i+1}+c_i-1-t,c_{i+2}\dots,c_r)}, \end{align} $$

where $A_c=A_c(1)$ now. This is precisely Liu’s recurrence [15, p. 8] (where $A_c=A_c(1)$ ). Using the same approach, one can in fact obtain a bijection between bilabeled trees with content c and Liu’s C-permutations.

8 Concluding remarks

We conclude this article with some brief remarks that further demonstrate the combinatorial richness of the $A_c(q)$ and hopefully motivate the reader to investigate.

1. 1. The statement of Theorem 1.3 (4) has the mildly unattractive aspect in that both the ordinary factorial and the q-factorial show up. In fact, appealing to Theorem 1.3 (7), one can establish another q-analogue:

   (8.1) $$ \begin{align} \sum_{c\in \mathcal{W}_{r}^{}}\frac{A_{c_1,\dots,c_{r}}(q)}{(c_1)_q!\cdots (c_r)_q!}=\sum_{\substack{c\in \mathcal{W}_{r}^{}\\\forall i\leq r,c_1+\cdots+c_i\geq i}}\frac{(r)_q!}{(c_1)_q!\cdots (c_r)_q!}=\sum_{f \in \mathrm{PF}(r)}q^{\mathrm{inv}(f)}. \end{align} $$

   Here, $\mathrm {PF}(r)$ is the set of parking functions of length r. The first equality in equation (8.1) is simply invoking Theorem 1.3 (7), whereas the second follows since the q-multinomial coefficient $\frac {(r)_q!}{(c_1)_q!\cdots (c_r)_q!}$ for $c\in \mathcal {W}_{r}^{}$ satisfying $c_1+\cdots +c_i\geq i$ for all $i\leq r$ tracks the inversion (equivalently the major index) statistic over parking functions with content c. Note that each individual summand on the left-hand side in equation (8.1) is not necessarily a polynomial in q. Furthermore, one could argue that the appearance of parking functions in the last step is contrived.

   We say more on this matter in upcoming work that describes another (multivariate) perspective on the $A_c(q)$ wherein parking procedures come up organically. In that same work, the combinatorial interpretation for $A_c(q)$ as counting bilabeled trees, obtained in Sections 6 and 7 via geometric means, will be derived purely algebraically.

2. 2. As mentioned earlier, the authors’ inspiration to introduce, and study, the $A_c(q)$ came from Schubert calculus [18, 20]. In particular, the Schubert class expansion of the cohomology class of the type A permutahedral variety naturally involves mixed Eulerian numbers once the connection between ordinary divided symmetrization and coefficient extraction Klyachko’s algebra [12] is made. Since the latter algebra also arises as the cohomology ring of a regular nilpotent Hessenberg variety known as the Peterson variety, it is not surprising that mixed Eulerian numbers arise in that context.

   We make note of their occurrence in two recent works. Goldin–Gorbutt [6] compute structure coefficients in the Peterson Schubert basis and give explicit expression for them in certain cases. In particular, Corollary 2 in loc. cit. describes mixed Eulerian numbers $A_c(1)$ , where c is a composition of the form $(0^p1^q2^r1^s0^t)$ for the appropriate $p,q,r,s,$ and t, even though these numbers are not explicitly identified as mixed Eulerian numbers in said work. More generally, several structural constants in their work are products of $A_c$ where the c satisfy $c_i\leq 2$ . The type A story in this context is also present in [9].

3. 3. Finally, other subfamilies of $A_c(q)$ of interest are currently being investigated by Solal Gaudin, a student of the first author, as part of his thesis: as an example, weak compositions c whose support has size two, that is particle configurations with two piles. Note that these are not in general elements of the two subfamilies studied in Section 4.