Theory Update 81

As Postnikov explains, the permutohedron polytope in dimension $n$ is expressed as a Minkowski sum of simplices

$(x_1 - x_2) \Delta_{1n} + (x_2 - x_3) \Delta_{2n} + \cdots + (x_{n} - x_{n+1}) \Delta_{nn}$

where the $n + 1$ letters $x_i$ define the permutations in $S_{n + 1}$. The simplex $\Delta_{kn}$ is defined by the permutations of the coordinate $(1,1, \cdots, 0,0)$ with $k$ ones at the start and then zeroes. The volume $V_n$ of the permutohedron is then given by a sum of terms

$V_n = \sum A_{c_1 c_2 \cdots c_n} \frac{(x_1 - x_2)^{c_1} \cdots (x_{n} - x_{n+1})^{c_n}}{(c_1)! \cdots (c_n)!}$

where the $A_{c_1 c_2 \cdots c_n}$ and $(c_i + 1)$ are positive integers, and the $c_i$ satisfy $\sum c_i = n$. For example, in dimension $4$ the sets of $(c_1, c_2, c_3, c_4)$ that are allowed are permutations of

$(2,2,0,0)$, $(1,1,1,1)$, $(3,1,0,0)$, $(4,0,0,0)$.

So the term $(2,0,0,2)$ contributes to $V_n$ a term

$\frac{6}{4} (x_1 - x_2)^{2} (x_4 - x_5)^2$

and $(c_1, c_2, c_3, c_4) = (1,1,1,1)$ gives

$24 (x_1 - x_2)(x_2 - x_3)(x_3 - x_4)(x_4 - x_5)$.

The coefficients $A_{c_1 c_2 \cdots c_n}$ are associated to planar binary trees. As it happens, the total volume $V_n$ of the permutohedron is just $(n+1)^{n-1}$, the parking function number. This highlights the simple fact that one can label binary trees on $n + 1$ leaves by permutations in $S_n$, where a permutation encodes the order that areas between adjacent branches hit a base node.