  We compute the expansion of the cohomology class of the permutahedral variety
in the basis of Schubert classes. The resulting structure constants $a_w$ are
expressed as a sum of \emph{normalized} mixed Eulerian numbers indexed
naturally by reduced words of $w$. The description implies that the $a_w$ are
positive for all permutations $w\in S_n$ of length $n-1$, thereby answering a
question of Harada, Horiguchi, Masuda and Park. We use the same expression to
establish the invariance of $a_w$ under taking inverses and conjugation by the
longest word, and subsequently establish an intriguing cyclic sum rule for the
numbers. We then move toward a deeper combinatorial understanding for the $a_w$
by exploiting in addition the relation to Postnikov's divided symmetrization.
Finally, we are able to give a combinatorial interpretation for $a_w$ when $w$
is vexillary, in terms of certain tableau descents. It is based in part on a
relation between the numbers $a_w$ and principal specializations of Schubert
polynomials. Along the way, we prove results and raise questions of independent
interest about the combinatorics of permutations, Schubert polynomials and
related objects. We also sketch how to extend our approach to other Lie types,
highlighting in particular an identity of Klyachko.
