# Mixed volumes of hypersimplices

Gaku Liu

► To cite this version:

Gaku Liu. Mixed volumes of hypersimplices. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.997-1006, 10.46298/dmtcs.2488. hal-01337752

HAL Id: hal-01337752

https://hal.science/hal-01337752

Submitted on 27 Jun 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Mixed volumes of hypersimplices

Gaku Liu¹†

¹Massachusetts Institute of Technology, USA

**Abstract.** In this extended abstract we consider mixed volumes of combinations of hypersimplices. These numbers, called mixed Eulerian numbers, were first considered by A. Postnikov and were shown to satisfy many properties related to Eulerian numbers, Catalan numbers, binomial coefficients, etc. We give a general combinatorial interpretation for mixed Eulerian numbers and prove the above properties combinatorially. In particular, we show that each mixed Eulerian number enumerates a certain set of permutations in $S_n$. We also prove several new properties of mixed Eulerian numbers using our methods. Finally, we consider a type B analogue of mixed Eulerian numbers and give an analogous combinatorial interpretation for these numbers.

**Résumé.** Dans ce résumé étendu nous considérons les volumes mixtes de combinaisons d'hyper-simplexes. Ces nombres, appelés les nombres Eulériens mixtes, ont été pour la première fois étudiés par A. Postnikov, et il a été montré qu'ils satisfait à de nombreuses propriétés reliées aux nombres Eulériens, au nombres de Catalan, aux coefficients binomiaux, etc. Nous donnons une interprétation combinatoire générale des nombres Eulériens mixtes, et nous prouvons combinatoirement les propriétés mentionnées ci-dessus. En particulier, nous montrons que chaque nombre Eulérien mixte compte les éléments d'un certain sous-ensemble de l'ensemble des permutations $S_n$. Nous établissons également plusieurs nouvelles propriétés des nombres Eulériens mixtes grâce à notre méthode. Pour finir, nous introduisons une généralisation en type B des nombres Eulériens mixtes, et nous en donnons une interprétation combinatoire analogue.

**Keywords:** Hypersimplex, mixed volume, Eulerian numbers

## 1 Introduction

The classical Eulerian number $A(n, k)$ counts the number of permutations in $S_n$ with $k-1$ descents. They arise as the coefficients of Eulerian polynomials and as volumes of hypersimplices. These numbers have been shown to satisfy many properties which appear combinatorial in nature; see [6]. In this extended abstract we give a combinatorial definition of mixed Eulerian numbers, which we use to prove both previous and new results.

For integers $1 \le k \le n$, the hypersimplex $\Delta_{k,n} \subset \mathbb{R}^{n+1}$ is the convex hull of all points of the form

$$e_{i_1} + e_{i_2} + \cdots + e_{i_k}$$

<footnote>†Email: gakuliu@gmail.com. This material is based upon work supported by the National Science Foundation Graduate Research Fellowship under Grant No. 1122374.</footnote>
where $1 \le i_1 < i_2 < \dots < i_k \le n+1$ and $e_i$ is the $i$-th standard basis vector. Thus, $\Delta_{k,n}$ is an $n$-dimensional polytope which lies in the hyperplane $x_1 + \dots + x_{n+1} = k$. Given a polytope $P \subset \mathbb{R}^{n+1}$ which lies in a hyperplane $x_1 + \dots + x_{n+1} = \alpha$ for some $\alpha \in \mathbb{R}$, we define its (normalized) volume Vol $P$ to be the usual $n$-dimensional volume of the projection of $P$ onto the first $n$ coordinates. It is a classical result [4] that $n! \text{Vol} \Delta_{k,n}$ equals the Eulerian number $A(n, k)$.

We now define the mixed volume of a set of polytopes. Given a polytope $P$ and a real number $\lambda \ge 0$, let $\lambda P = \{\lambda x \mid x \in P\}$. Given polytopes $P_1, \dots, P_m \subset \mathbb{R}^n$, let their Minkowski sum be

$$P_1 + \dots + P_m = \{x_1 + \dots + x_m \mid x_i \in P \text{ for all } i\}.$$

For nonnegative real numbers $\lambda_1, \dots, \lambda_m$, the function

$$f(\lambda_1, \dots, \lambda_m) = \text{Vol}(\lambda_1 P_1 + \dots + \lambda_m P_m)$$

is known to be a homogeneous polynomial of degree $n$ in the variables $\lambda_1, \dots, \lambda_m$. Hence there is a unique symmetric function Vol defines on $n$-tuples of polytopes in $\mathbb{R}^n$ such that

$$f(\lambda_1, \dots, \lambda_m) = \sum_{i_1, \dots, i_n = 1}^{m} \text{Vol}(P_{i_1}, \dots, P_{i_n}) \lambda_{i_1} \cdots \lambda_{i_n}.$$

The number Vol($P_1, \dots, P_n$) is called the mixed volume of $P_1, \dots, P_n$. Mixed volumes of lattice polytopes have important connections to algebraic geometry, where they count the number of solutions to generic systems of polynomial equations; see [1]. If $P_1 = \dots = P_n = P$, then Vol($P_1, \dots, P_n$) equals the ordinary volume Vol($P$). If $P_1, \dots, P_m \subset \mathbb{R}^{n+1}$ and each $P_i$ lies in a hyperplane $x_1 + \dots + x_{n+1} = \alpha_i$ for some $\alpha_i \in \mathbb{R}$, then we define

$$f(\lambda_1, \dots, \lambda_m) = \text{Vol}(\lambda_1 P_1 + \dots + \lambda_m P_m)$$

in terms of the normalized volume defined previously, and we define the mixed volume Vol($P_1, \dots, P_n$) analogously.

Let $c_1, c_2, \dots, c_n$ be nonnegative integers such that $c_1 + \dots + c_n = n$. We define

$$A_{c_1, \dots, c_n} = n! \text{Vol}(\Delta_{1,n}^{c_1}, \Delta_{2,n}^{c_2}, \dots, \Delta_{n,n}^{c_n})$$

where $(\Delta_{1,n}^{c_1}, \Delta_{2,n}^{c_2}, \dots, \Delta_{n,n}^{c_n})$ denotes the $n$-tuple with $c_1$ entries $\Delta_{1,n}$, $c_2$ entries $\Delta_{2,n}$, and so on. The numbers $A_{c_1, \dots, c_n}$ are called mixed Eulerian numbers, and were introduced by Postnikov in [6]. It is immediate that if $c_k = n$ and $c_i = 0$ for all $i \ne k$, then $A_{c_1, \dots, c_n} = A(n, k)$. Furthermore, the result of Ehrenborg, Readdy, and Steingrímsson [3] states that if $c_{k-1} = r$, $c_k = n-r$, and $c_i = 0$ for $i \ne k-1$, $k$, then $A_{c_1, \dots, c_n}$ equals the number of permutations $w \in S_{n+1}$ with $k-1$ descents and $w_1 = r+1$. The mixed Eulerian numbers satisfy many other remarkable properties; for example, we have $A_{1, \dots, 1} = n!$, $A_{k, 0, \dots, 0, n-k} = \binom{n}{k}$, and $A_{c_1, \dots, c_n} = 1^{c_1} 2^{c_2} \dots n^{c_n}$ if $c_1 + \dots + c_i \ge i$ for all $i$. These results were proven in [6] using algebraic and geometric methods. Additional formulas involving mixed Eulerian numbers and their generalizations to other root systems were derived by Croitoru in [2].

In this extended abstract, the main result is that each mixed Eulerian number enumerates a certain well-define set of permutations in $S_n$. (When $c_k = n$ and $c_i = 0$ for all $i \ne k$, this set of permutations is precisely the set of permutations with $k-1$ descents.) We sketch how the above results arise from this
combinatorial interpretation. We also give some new identities which follow from this interpretation. For example, we have that $A_{c_1,...,c_n} \le 1^{c_1} 2^{c_2} ... n^{c_n}$ for every mixed Eulerian number. We also give a simple formula for $A_{c_1,...,c_n}$ when the only nonzero $c_i$ are $c_1$ and $c_k$ for some $k \ne 1$. This number appeared in the work of Michałek et. al. [5] during their study of exponential families arising from elementary symmetric polynomials.

In addition, we define the polytope $\Gamma_{k,n} \subset \mathbb{R}^n$ to be the convex hull of all points of the form $\pm e_{i_1} \pm e_{i_2} \pm \cdots \pm e_{i_k}$ where $1 \le i_1 < \cdots < i_k \le n$. In terms of Coxeter groups, the $\Delta_{k,n}$ correspond to the group $A_n$ and the $\Gamma_{k,n}$ correspond to the group $B_n$. For nonnegative integers $c_1, \dots, c_n$ such that $c_1 + \cdots + c_n = n$, define

$$B_{c_1,...,c_n} = n! \mathrm{Vol}(\Gamma_{1,n}^{c_1}, \Gamma_{2,n}^{c_2}, \dots, \Gamma_{n,n}^{c_n}).$$

We refer to the $B_{c_1,...,c_n}$ as the type B mixed Eulerian numbers, whereas the $A_{c_1,...,c_n}$ are type A mixed Eulerian numbers. We give a combinatorial interpretation for the $B_{c_1,...,c_n}$ analogous to that of the $A_{c_1,...,c_n}$ and list several identities that follow from this interpretation.

## 2 The main theorem

Let $n$ be a positive integer, and let $S$ be a totally ordered set with $|S| = n$. Let $C = (C_1, \dots, C_n)$ be a sequence of $n$ pairwise disjoint sets such that

* $C_1 \cup \cdots \cup C_n = S$, and

* $s < t$ whenever $s \in C_i, t \in C_j$, and $i < j$.

We will call such a $C$ a division of $S$. Let $|C|$ denote the sequence $(|C_1|, \dots, |C_n|)$.

We say that an element $s \in S$ is admissible with respect to $C$ if either $s$ is the smallest element of $C_1$, $s$ is the largest element of $C_n$, or $s \in C_i$ for $i \ne 1, n$. Given an admissible element $s$, we define the deletion of $s$ from $C$ as follows. Let $i$ be such that $s \in C_i$, and let $C_i^- = \{t \in C_i | t < s\}$ and $C_i^+ = \{t \in C_i | t > s\}$. The deletion of admissible $s$ from $C$ results in a sequence of $n-1$ sets, denoted by $C^s = (C_1^s, \dots, C_{n-1}^s)$, given as follows:

* If $i=1$, then $C^s = (C_1^+ \cup C_2, C_3, \dots, C_n)$.

* If $i \ne 1, n$, then $C^s = (C_1, \dots, C_{i-2}, C_{i-1} \cup C_i^-, C_i^+ \cup C_{i+1}, C_{i+2}, \dots, C_n)$.

* If $i=n$, then $C^s = (C_1, \dots, C_{n-2}, C_{n-1} \cup C_n^-)$.

In any case, $C^s$ is a division of $S \setminus \{s\}$.

Now suppose $s_1$ is admissible with respect to $C$, $s_2$ is admissible with respect to $C^{s_1}$, $s_3$ is admissible with respect to $(C^{s_1})^{s_2}$, $s_4$ is admissible with respect to $((C^{s_1})^{s_2})^{s_3}$, and so on, until $s_n$. We obtain a permutation $s_1 s_2 \dots s_n$ of $S$. Call any permutation constructed in this way a C-permutation. Note that the number of C-permutations depends only on $|C|$.

**Example 2.1.** Suppose $n=5$ and $C = (\{1\}, \emptyset, \{2,3\}, \{4\}, \{5\})$. The element 2 is admissible with respect to $C$, and $C^2 = (\{1\}, \emptyset, \{3,4\}, \{5\})$. The element 3 is admissible with respect to $C^2$, and $(C^2)^3 = (\{1\}, \emptyset, \{4,5\})$. The element 1 is admissible with respect to $(C^2)^3$, and $((C^2)^3)^1 = (\emptyset, \{4,5\})$. The element 5 is admissible with respect to $((C^2)^3)^1$, and $(((C^2)^3)^1)^5 = (\{4\})$. The element 4 is admissible with respect to $(((C^2)^3)^1)^5$. Hence 23154 is a C-permutation. The construction of this permutation is visualized below.
$$
\begin{array}{cccccc}
1 & \emptyset & \mathbf{23} & 4 & 5 \\
1 & \emptyset & \mathbf{34} & 5 \\
\mathbf{1} & \emptyset & 45 \\
\emptyset & \mathbf{45} \\
\mathbf{4}
\end{array}
$$

On the other hand, 23145 is not a C-permutation because 4 is not admissible with respect to ((C^2)^3)^1 = (\emptyset, \{4, 5\}).

**Example 2.2.** Suppose $C = (\{1, \dots, n\}, \emptyset, \dots, \emptyset)$. The only element admissible with respect to $C$ is 1, and $C^1 = (\{2, \dots, n\}, \emptyset, \dots, \emptyset)$. The only element admissible with respect to $C^1$ is 2, and so on. Thus the only $C$-permutation is $12\dots n$.

Similarly, if $C = (\emptyset, \dots, \emptyset, \{1, \dots, n\})$, then the only $C$-permutation is $n(n-1)\dots 1$.

**Example 2.3.** Suppose *C* is a division of *S* and |*C*| = (1, ..., 1). Then every element of *S* is admissible with respect to *C*. Moreover, for any element *s* ∈ *S*, *C*<sup>*s*</sup> satisfies |*C*<sup>*s*</sup>| = (1, ..., 1). So by induction, every permutation of *S* is a *C*-permutation.

**Example 2.4.** Let $C$ be a division of the form $C = (C_1, \emptyset, \dots, \emptyset, C_n)$. Then the only admissible elements with respect to $C$ are the first element of $C_1$ and the last element of $C_n$. Furthermore, when we delete either of these elements, the resulting sequence of sets is again of the form $(C'_1, \emptyset, \dots, \emptyset, C'_{n-1})$. So when we construct a $C$-permutation by successively deleting admissible elements, at each step we delete either the first element of the first set or the last element of the last set. Thus the $C$-permutations are the permutations where the elements of $C_1$ appear in ascending order and the elements of $C_n$ appear in descending order.

**Example 2.5.** We will see from Corollary 3.8 that if $1 \le k \le n$ and $C$ is the division of $\{1, \dots, n\}$ with $C_k = \{1, \dots, n\}$ and $C_i = \emptyset$ for all $i \ne k$, then a permutation $w \in S^n$ is a $C$-permutation if and only if it has $k-1$ descents.

We are now ready to state the main result.

**Theorem 2.6.** Let $C = (C_1, \dots, C_n)$ be a division with $|C| = (c_1, \dots, c_n)$. Then $A_{c_1, \dots, c_n}$ equals the number of $C$-permutations.

*Sketch of proof.* It suffices to show that the mixed Eulerian numbers satisfy the recursion

$$
A_{c_1, \dots, c_n} = \sum_{s \text{ admissible w.r.t. } C} A_{|C^s|}.
$$

Let

$$
\begin{align*}
f_n(\lambda_1, \dots, \lambda_n) &= \mathrm{Vol}(\lambda_1 \Delta_{1,n} + \lambda_2 \Delta_{2,n} + \dots + \lambda_n \Delta_{n,n}) \\
&= \sum_{c_1+\dots+c_n=n} \frac{1}{c_1! \dots c_n!} A_{c_1, \dots, c_n} \lambda_1^{c_1} \dots \lambda_n^{c_n}
\end{align*}
$$

so that

$$
A_{c_1, \dots, c_n} = \partial_1^{c_1} \cdots \partial_n^{c_n} f_n.
$$

The main idea is to write a recursive formula for $f_n$. To do this, we use the following:
**Proposition 2.7.** Let $\lambda_1, \dots, \lambda_n$ be nonnegative real numbers. Fix a real number $0 \le x \le \lambda_1 + \dots + \lambda_n$, and let $1 \le i \le n$ be such that $\lambda_{i+1} + \dots + \lambda_n \le x \le \lambda_i + \dots + \lambda_n$ (where $0 \le x \le \lambda_n$ if $i=n$). Set $t = \lambda_i + \dots + \lambda_n - x$. Consider the cross section of

$$ \lambda_1 \Delta_{1,n} + \lambda_2 \Delta_{2,n} + \dots + \lambda_n \Delta_{n,n} $$

with first coordinate equal to $x$. The projection of this cross section onto the last $n$ coordinates is congruent to the following polytopes in the following cases:

* If $i=1$,

$$ (t + \lambda_2) \Delta_{1,n-1} + \lambda_3 \Delta_{2,n-1} + \dots + \lambda_n \Delta_{n-1,n-1}. $$

* If $2 \le i \le n-1$,

$$ \lambda_1 \Delta_{1,n-1} + \dots + \lambda_{i-2} \Delta_{i-2,n-1} + (\lambda_{i-1} + \lambda_i - t) \Delta_{i-1,n-1} \\ + (t + \lambda_{i+1}) \Delta_{i,n-1} + \lambda_{i+2} \Delta_{i+1,n-1} + \dots + \lambda_n \Delta_{n-1,n-1}. $$

* If $i=n$,

$$ \lambda_1 \Delta_{1,n-1} + \dots + \lambda_{n-2} \Delta_{n-2,n-1} + (\lambda_{n-1} + \lambda_n - t) \Delta_{n-1,n-1}. $$

This gives the following formula for $f_n$:

**Proposition 2.8.** We have

$$ f_n(\lambda_1, \dots, \lambda_n) = \int_0^{\lambda_1} f_{n-1}(t + \lambda_2, \lambda_3, \dots, \lambda_n) dt \\ + \sum_{i=2}^{n-1} \int_0^{\lambda_i} f_{n-1}(\lambda_1, \dots, \lambda_{i-2}, \lambda_{i-1} + \lambda_i - t, t + \lambda_{i+1}, \lambda_{i+2}, \dots, \lambda_n) dt \\ + \int_0^{\lambda_n} f_{n-1}(\lambda_1, \dots, \lambda_{n-2}, \lambda_{n-1} + \lambda_n - t) dt. $$

Applying the operator $\partial_1^{c_1} \cdots \partial_n^{c_n}$ gives us the desired recursion. $\square$

<figure><img src="image_2.png" /></figure>

While C-permutations are defined recursively in general, there are certain cases where more explicit descriptions can be given. This allows us to calculate various formulas for mixed Eulerian numbers, as described in the next section.

# 3 Properties of mixed Eulerian numbers

Using algebraic and geometric techniques, Postnikov proved the following properties of mixed Eulerian numbers.

**Theorem 3.1** (Postnikov [6]). The mixed Eulerian numbers have the following properties:

(a) The numbers $A_{c_1, \dots, c_n}$ are positive integers defined for $c_1, \dots, c_n \ge 0$, $c_1 + \dots + c_n = n$.
(b) We have $A_{c_1,...,c_n} = A_{c_n,...,c_1}$.

(c) For $1 \le k \le n$, the number $A_{0^{k-1},n,0^{n-k}}$ equals the usual Eulerian number $A(n,k)$. Here, $0^l$ denotes a sequence of $l$ zeroes.

(d) We have $\sum \frac{1}{c_1!...c_n!} A_{c_1,...,c_n} = (n+1)^{n-1}$, where the sum is over nonnegative integer sequences $c_1, ..., c_n$ with $c_1 + ... + c_n = n$.

(e) We have $\sum A_{c_1,...,c_n} = n!C_n$, where the sum is over nonnegative integer sequences $c_1, ..., c_n$ with $c_1 + ... + c_n = n$, and $C_n = \frac{1}{n+1} \binom{2n}{n}$ is the n-th Catalan number.

(f) For $2 \le k \le n$ and $0 \le r \le n$, the number $A_{0^{k-2},r,n-r,0^{n-k}}$ is equal to the number of permutations $w \in S_{n+1}$ with $k-1$ descents and $w_1 = r+1$.

(g) We have $A_{1,...,1} = n!$.

(h) We have $A_{k,0,...,0,n-k} = \binom{n}{k}$.

(i) We have $A_{c_1,...,c_n} = 1^{c_1}2^{c_2}\dots n^{c_n}$ is $c_1 + \dots + c_i \ge i$ for all $i$.

**Theorem 3.2 (Postnikov [6].)** Let $\sim$ denote the equivalence relation on the set of nonnegative integer sequences $(c_1, ..., c_n)$ with $c_1 + \dots + c_n = n$ given by $(c_1, ..., c_n) \sim (c'_1, ..., c'_n)$ whenever $(c_1, ..., c_n, 0)$ is a cyclic shift of $(c'_1, ..., c'_n, 0)$. Then for a fixed $(c_1, ..., c_n)$, we have

$$ \sum_{(c'_1, \dots, c'_n) \sim (c_1, \dots, c_n)} A_{c'_1, \dots, c'_n} = n! $$

Note: There are exactly $C_n = \binom{2n}{n}$ equivalence classes.

We now sketch how these properties arise from the combinatorial interpretation of mixed Eulerian numbers given by Theorem 2.6. We also give the following four additional properties.

**Theorem 3.3.** We have $A_{c_1,...,c_n} \le 1^{c_1}2^{c_2}\dots n^{c_n}$, with equality if and only if $c_1 + \dots + c_i \ge 1$ for all $i$.

**Theorem 3.4.** Let $c_1, ..., c_n$ be nonnegative integers such that $c_1 + \dots + c_n = n$, and suppose there exists some $0 \le r \le n$ such that $c_1 + \dots + c_i \ge i$ for all $1 \le i \le r$ and $c_n + c_{n-1} + \dots + c_{n-i+1} \ge i$ for all $1 \le i \le n-r$. Then

$$ A_{c_1, \dots, c_n} = \binom{n}{c_1 + \dots + c_r} 1^{c_1} 2^{c_2} \dots r^{c_r} 1^{c_n} 2^{c_{n-1}} \dots (n-r)^{c_{r+1}} $$

To state the third property, we introduce some terminology. Say a sequence $a_1, a_2, ..., a_n$ is extreme if for each $1 \le i \le n$, either $a_i = \min(a_1, ..., a_i)$ or $a_i = \max(a_1, ..., a_i)$. Let $\text{des}(a_1, ..., a_n)$ denote the number of descents in the sequence $a_1, ..., a_n$.

**Theorem 3.5.** For $1 \le k \le n-2$, $0 \le r \le n$, and $0 \le s \le n$, the number $A_{0^{k-1},r,s,n-r-s,0^{n-k-2}}$ is equal to the number of permutations $w \in S_{n+2}$ such that $w_1 = r+1$, $w_2 = r+s+2$, and if $p$ is the largest integer such that $w_1, ..., w_p$ is extreme, then $\text{des}(w_1, ..., w_p) + \text{des}(w_{p+1}, ..., w_n) = k$.
**Theorem 3.6.** We have

$$A_{n-m,0^{k-2},m,0^{n-k}} = \sum_{i=0}^{n-m} \binom{m+i}{m} A(m, k-i)$$

where $A(n, k)$ is defined to be 0 if $k \le 0$ or $k > n$.

The numbers $A_{n-m,0^{k-2},m,0^{n-k}}$ appeared in [5], where the authors used the recursions of [2] to obtain the formula

$$A_{n-m,0^{k-2},m,0^{n-k}} = \sum_{i=0}^{n-k} (n-k+1-i) \binom{n-i}{n-m} k^i A(m-i-1, m-n+k-1).$$

when $m-n+k \ge 2$. (For other cases, $A_{n-m,0^{k-2},m,0^{n-k}} = k^m$ by Theorem 3.1(i).)

We do not have a combinatorial proof of Theorem 3.1(d), which was proven using the volume of the permutohedron.

## 3.1 Sketch of proof of Theorem 3.1

Property (a) is clear.

Property (b) follows from the fact that if $w$ is a $(C_1, \dots, C_n)$-permutation, then $w$ is also a $(C_n, \dots, C_1)$-permutation with the reverse ordering on $C_1 \cup \dots \cup C_n$.

Property (f), which is a generalization of property (c), follows from the following proposition, which is proved using induction.

**Proposition 3.7.** Let $2 \le k \le n$ and $0 \le r \le n$. Let $x_0 < x_1 < \dots < x_n < x_{n+1}$ be real numbers and let $S = \{x_1, \dots, x_n\}$. Let $C$ be the division of $S$ with $|C| = (0^{k-2}, r, n-r, 0^{n-k})$. Let $\lambda$ be a real number such that $x_r < \lambda < x_{r+1}$. Then a permutation $w = w_1 \dots w_n$ of $S$ is a C-permutation if and only if the sequence $\lambda, w_1, \dots, w_n$ has $k-1$ descents.

**Corollary 3.8.** Let $1 \le k \le n$ and let $C = (\emptyset^{k-1}, \{1, \dots, n\}, \emptyset^{n-k})$. Then a permutation $w \in S_n$ is a C-permutation if and only if it has $k-1$ descents.

*Proof.* Take $r=0$ or $n$ in the previous Proposition. $\square$

<figure><img src="image_3.png" /></figure>

Property (e) follows from Theorem 3.2 and the note afterwards.

Property (g) follows from Example (2.3).

Property (h) follows from Example (2.4).

Finally, we prove Theorem 3.3, which implies (i). We first introduce some terminology. Fix a division $C = (C_1, \dots, C_n)$ of a set $S$. Let $w = w_1 \dots w_n$ be a C-permutation. For each $1 \le i \le n$, the index of $w_i$ in $w$ with respect to $C$ is the $j$ such that $w_i \in ((C^{w_1})^{w_2} \dots)^{w_{i-1}}$. Let $I_w^C : S \to \mathbb{N}$ be the function which takes each $s \in S$ to its index in $w$ with respect to $C$. Note that if $s \in C_i$, then $I_w^C(s) \in \{1, \dots, i\}$. We will call any function $I : S \to \mathbb{N}$ which maps $C_i$ into $\{1, \dots, i\}$ and index function of $C$.

**Example 3.9.** Let $C = (\{1\}, \emptyset, \{2, 3\}, \{4\}, \{5\})$ and $w = 23154$ as in Example 2.1. Then $I_w^C(2) = 3$, $I_w^C(3) = 3$, $I_w^C(1) = 1$, $I_w^C(5) = 2$, and $I_w^C(4) = 1$.

Theorem 3.3 follows immediately from the next proposition.
**Proposition 3.10.** Fix a division $C = (C_1, \dots, C_n)$ of $S$. Then the map $w \mapsto I_w^C$ is an injection from the set of $C$-permutations to the set of index functions of $C$. This map is a bijection if and only if $|C_1| + \dots + |C_i| \ge i$ for all $i$.

Note that by Theorem 3.3 and Theorem 3.1(b), we also have

$$A_{c_1, \dots, c_n} \le 1^{c_n} 2^{c_{n-1}} \dots n^{c_1}$$

with equality if and only if $c_n + c_{n-1} + \dots + c_{n-i+1} \ge i$ for all $i$.

## 3.2 Proof of Theorem 3.2

Let $n$ be a positive integer and let $c_1, \dots, c_n$ be nonnegative integers with $c_1 + \dots + c_n = n$. Let $C = (C_1, \dots, C_n)$ be the division of $\{1, \dots, n\}$ with $|C| = (c_1, \dots, c_n)$. Set $C_{n+1} = \emptyset$.

We will describe a process which is a cyclic version of the construction of $C$-permutations. Arrange the numbers $1, \dots, n$ around a circle $C$ clockwise in that order. We will define $n+1$ “blocks” as follows: for each $1 \le i \le n+1$, block $B_i$ initially contains the elements of $C_i$. We view $B_1, \dots, B_{n+1}$ as being arranged around $C$ in that order, including the empty blocks; i.e. $B_i$ is viewed as being between $B_{i-1}$ and $B_{i+1}$ even if $B_i$ is empty. For any element $s \in \{1, \dots, n\}$, we define the deletion of $s$ from $C$ as follows. Suppose $s \in B_i$. Let $B_i^-$ be the set of elements in $B_i$ which are to the left of (counterclockwise from) $s$, and let $B_i^+$ be the set of elements in $B_i$ which are to the right of (clockwise from) $s$. To delete $s$, we remove $s$ and the block $B_i$ from $C$, put all the elements of $B_i^-$ into the block to the left of $B_i$, and put all the elements of $B_i^+$ into the block to the right of $B_i$. The order of the undeleted elements remains unchanged. We can then delete another element, and so on. After we delete all $n$ elements, we are left with only one block, which is empty. Since a nonempty block remains nonempty until it is deleted, this final empty block was originally empty and remained so throughout the process.

Let $w = w_1 \dots w_n \in S_n$ be a permutation. Let $r(w)$ be the $r$ such that $B_r$ is the final block that remains when we successively delete $w_1, \dots, w_n$ from $C$. It is not hard to see that for each $r$ with $C_r = \emptyset$, the set of $w$ such that $r(w) = r$ is precisely the set of $(C_{r+1}, C_{r+2}, \dots, C_{r-1})$-permutations, where the indices of the $C_i$ are taken modulo $n+1$ and the elements $\{1, \dots, n\}$ are ordered starting from the first element of $C_{r+1}$ and going cyclically to the last element of $C_{r-1}$. There are $A_{c_{r+1}, \dots, c_{r-1}}$ such permutations. Hence we have

$$n! = \sum_{c_r=0} A_{c_{r+1}, c_{r+2}, \dots, c_{r-1}}$$

which is exactly what we wanted to prove.

## 3.3 Sketch of proof of Theorem 3.6

Given a set $S$, define a $\star$-permutation of $S$ to be a finite sequence of elements of $S$ and $\star$ symbols such that every element of $S$ appears exactly once. A descent of a $\star$-permutation $s_1 s_2 \dots$ is a pair of elements $(s_i, s_j)$ such that $i < j$, $s_i > s_j$, and $s_k = \star$ for every $i < k < j$. Theorem 3.6 follows from the following.

**Proposition 3.11.** Let $C$ be a division with $|C| = (n-m, 0^{k-2}, m, 0^{n-k})$. Then the $C$-permutations are in bijection with $\star$-permutations of $C_k$ for which the number of $\star$'s is at most $n-m$ and the number of $\star$'s plus the number of descents is equal to $k-1$.
**Sketch of proof.** Assume $C$ is a division of $S$. Suppose $s = s_1s_2...$ is a $\star$-permutation of $C_k$ satisfying the above conditions. Let $i$ be the largest index such that $s_i$ is either a $\star$ or $(s_i, s_j)$ is a descent for some $j$. We obtain a $C$-permutation from $s$ as follows: Begin with the subsequence $s_1...s_i$, and replace the first $\star$ with the first element of $C_1$, the second $\star$ with the second element of $C_1$, and so on, until all $\star$'s are replaced. Call the new sequence $w' = w_1...w_i$. Append to the end of $w'$ the elements of $S \setminus \{w_1, ..., w_i\}$ in ascending order. The result is a $C$-permutation.

Now suppose $w = w_1...w_n$ is a $C$-permutation. Replace all $w_i$ for which $w_i \notin C_k$ with $\star$'s. Call the resulting $\star$-permutation $s' = s_1s_2...$. Now, call an index $i$ good if either $s_i = \star$ or $(s_i, s_j)$ is a descent of $s'$ for some $j$. Delete any $\star$'s in $s'$ which occur after the $(k-1)$-th good index. The result is a $\star$-permutation of $C_k$ satisfying the desired conditions. $\square$

In fact, the above argument extends easily to the following:

**Proposition 3.12.** Let $C$ be a division with $|C| = (n-m, 0^{k-3}, r, m-r, 0^{n-k})$, and let $\lambda$ be a number such that $\lambda > s$ for all $s \in C_{k-1}$ and $\lambda < s$ for all $s \in C_k$. Then the $C$-permutations are in bijection with $\star$-permutations $s_1s_2...$ of $C_{k-1} \cup \{\lambda\} \cup C_k$ for which $s_1 = \lambda$, the number of $\star$'s is at most $n-m$, and the number of $\star$'s plus the number of descents is equal to $k-1$.

# 4 Type B mixed Eulerian numbers

We now give an analogous combinatorial interpretation for the numbers $B_{c_1,...,c_n}$. Let $C = (C_1, ..., C_n)$ be a division of a set $S$. We say that an element $s \in S$ is type B admissible with respect to $0 \in C$ if either $s$ is the smallest element of $C_1$ or $s \in C_i$ for $i \neq 1$. Given a type B admissible element $s$, we now define the type B deletion of $s$ from $C$, which by abuse of notation we denote by $C^s$. Let $i$ be such that $s \in C_i$. If $i \neq n$, then we define $C^s$ to be the same as in the type A case. If $i = n$, then we define

$$C^s = (C_1, ..., C_{n-2}, C_{n-1} \cup (C_n \setminus \{s\})).$$

Given these definitions of admissibility and deletion, we define a type B $C$-permutation analogously as in the type A case.

**Theorem 4.1.** Let $C = (C_1, ..., C_n)$ be a division with $|C| = (c_1, ..., c_n)$. Then $B_{c_1,...,c_n}$ equals $2^n$ times the number of type B $C$-permutations.

Using Theorem 4.1, we obtain the following properties of type B mixed Eulerian numbers.

**Theorem 4.2.** The type B mixed Eulerian numbers have the following properties.

(a) We have $2^n A_{c_1,...,c_n} \le B_{c_1,...,c_n} \le 2^n 1^{c_1} 2^{c_2} ... n^{c_n}$. Each inequality is equality if and only if $c_1 + \dots + c_i \ge i$ for all $i$.

(b) For $1 \le k \le n$, the number $B_{0^{k-1},n,0^{n-k}}$ is equal to $2^n$ times the number of permutations in $S_n$ with at most $k-1$ descents.

(c) For $1 \le k \le n-1$ and $0 \le r \le n$, the number $B_{0^{k-1},r,n-r,0^{n-k-1}}$ is equal to $2^n$ times the number of permutations $w \in S_{n+1}$ with at most $k$ descents and $w_1 = r+1$.

(d) We have $B_{1,...,1} = 2^n n!$.

(e) We have $B_{k,0,...,0,n-k} = \binom{n}{k}(n-k)!$.
(f) We have $B_{c_1,...,c_n} = 2^n 1^{c_1} 2^{c_2} ... n^{c_n}$ if $c_1 + ... + c_i \ge i$ for all $i$.

(g) We have $B_{c_1,...,c_n} = 2^n n!$ if $c_n + c_{n-1} + ... + c_{n-i+1} \ge i$ for all $i$.

(h) We have

$$B_{c_1,...,c_n} = 2^n \binom{n}{c_1 + \dots + c_r} 1^{c_1} 2^{c_2} \dots r^{c_r} (c_{r+1} + \dots + c_n)$$

if there exists some $0 \le r \le n$ such that $c_1 + \dots + c_i \ge i$ for all $1 \le i \le r$ and $c_n + c_{n-1} + \dots + c_{n-i+1} \ge i$ for all $1 \le i \le n-r$.

(i) For $1 \le k \le n-2$, $0 \le r \le n$, and $0 \le s \le n$, the number $A_{0^{k-1},r,s,n-r-s,0^{n-k-2}}$ is equal to the number of permutations $w \in S_{n+2}$ such that $w_1 = r+1$, $w_2 = r+s+2$, and if $p$ is the largest integer such that $w_1, ..., w_p$ is extreme, then $\text{des}(w_1, ..., w_p) + \text{des}(w_{p+1}, ..., w_n) \le k$.

## Acknowledgments

The author would like to thank Alexander Postnikov for introducing this problem to him and for many useful discussions.

## References

[1] D. Bernstein, The number of roots of a system of equations, Functional Analysis and its Applications 9 (1975), 1-4.

[2] D. Croitoru, Mixed volumes of hypersimplices, root systems and shifted Young tableaux, Thesis, 2010.

[3] R. Ehrenborg, M. Readdy, E. Steingrímsson, Mixed volumes and slices of the cube, Journal of Combinatorial Theory, Series A 81 (1998), no. 1, 121-126.

[4] M. de Laplace, Oeuvres complètes, Vol. 7, réédité par Gauthier-Villars, Paris, 1886.

[5] M. Michałek, B. Sturmfels, C. Uhler, P. Zwiernik, Exponential varieties, arXiv:1412.6185, 2014.

[6] A. Postnikov, Permutohedra, associahedra, and beyond, International Mathematics Research Notices, 2009 (2009), no. 6, 1026-1106.