Faces of the Permutahedron We define the Permutahedron as the convex hull of all permutations of the vector $(1,2,\dots,n)\in\mathbb R^n$. I am having trouble seeing why the number of $n-k$ dimensional faces of this polytope is given by $k!S(n,k)$, where $S(n,k)$ is the Stirling number of the second kind. More generally, why is the face lattice of the Permutahedron given by the partition lattice?
 A: The vertices of the $n$-permutahedron are all the permutations of $(1,\dotsc,n)$ in $\mathbb{R}^n$.
For instance, the 3-permutahedron has the 6 vertices $(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2)$, and $(3,2,1)$.
Notice that all of these lie in the plane $x + y + z = 6$,
so the 3-permutahedron is actually a 2-dimensional polytope (a hexagon.)
In general, all the permutations of $(1, \dotsc, n)$ lie in the hyperplane $\sum_{i=1}^n x_i = \frac{n^2 + n}{2}$, so the $n$-permutahedron is an $(n-1)$-dimensional polytope.
Each edge at a vertex $v$ connects it to another vertex whose coordinates are the same as $v$, except that two values differing by one are transposed.
For instance, in the 3-permutahedron, $(2,1,3)$ is adjacent to $(1,2,3)$ and $(3,1,2)$.
With $n$ coordinates, there are $n-1$ pairs of adjacent values.
So every vertex of the $n$-permutahedron is in $n-1$ edges.
The reason why all this matters is that a $d$-dimensional polytope where every vertex is incident to $d$ edges is called simple, so permutahedra are simple. And in a simple polytope, every nonempty intersection of $k$ distinct facets is an $(d-k)$-face, and vice versa.
In general, any nonempty intersection of two distinct facets (i.e. $(d-1)$-faces of a $d$-dimensional polytope) has dimension $(d-2)$ or lower,
and any nonempty intersection of 3 distinct facets has dimension $(d-3)$ or lower.
But a nonempty intersection of 4 distinct facets could be a $(d-4)$-face, or a $(d-3)$-face; a nonempty intersection of 5 distinct facets could be a $(d-5)$-face or $(d-4)$-face or $(d-3)$-face. This doesn't happen in a simple polytope.
Now, each facet $F$ of a permutahedron is determined by a nonempty proper subset $S$ of the coordinate positions; the vertices of $F$ are all the points where all the coordinates in $S$ are smaller than all the coordinates not in $S$. There is one facet for each nonempty proper subset of $\{1,\dotsc,n\}$, so $2^n - 2$ in total.
Consider a nonempty intersection of two facets, corresponding to subsets $S$ and $S'$ of $\{1,\dotsc,n\}$, of sizes $j$ and $k$, where $j \leq k$.
Since the numbers $1, \dotsc, j$ must occur in the positions $S$,
and $1, \dotsc, j, \dotsc, k$ must occur in the positions $S'$,
we must have $S \subset S'$. If $S = S'$, then the two facets are identical.
So every nonempty intersection of two distinct facets
is determined by two nested nonempty proper subsets,
$\emptyset \subsetneq S \subsetneq S' \subsetneq \{1,\dotsc,n\}$.
(The vertices in the intersection are all the points where the first $j$ numbers appear in the positions in $S$,
the next $k - j$ numbers appear in $S' \setminus S$,
and the rest are outside of $S'$.)
Similarly, a nonempty intersection of $k$ facets
corresponds to $k$ nested proper subsets,
$\emptyset \subsetneq S_1 \subsetneq \dotsb \subsetneq S_k \subsetneq \{1,\dotsc,n\}$.
So, the number of $(d-k)$-faces is the number of sequences of $k$ nonempty nested proper subsets. (Here, $d = n - 1$ is the dimension of the $n$-permutahedron.)
The Stirling number of the second kind $S(n,k)$ counts the partitions of $\{1,\dotsc,n\}$ into $k$ nonempty subsets.
So $k!\, S(n,k)$ counts the partitions into $k$ nonempty subsets, counting the order of the subsets.
Given a partition of $\{1,\dotsc,n\}$ into $k+1$ nonempty subsets
$K_1, \dotsc, K_{k+1}$, you can construct a sequence of $k$ nonempty nested proper subsets
$$
\emptyset \; \subsetneq \; K_1 \; \subsetneq \; K_1 \cup K_2 \; 
\subsetneq \; K_1 \cup K_2 \cup K_3 \; 
\subsetneq \dotsb
\subsetneq \; K_1 \cup \dotsb \cup K_{k+1}.
$$
The last entry in that list is the whole set $\{1,\dotsc,n\}$,
so there are only $k$ proper nonempty subsets.
You can also go backwards from a sequence of $k$ nonempty nested proper subsets to make a partition into $k+1$ nonempty subsets;
so this is a bijection.
Hence, $(k+1)!\,S(n,k+1)$ counts the number of $(n-1-k)$-faces of the $n$-permutahedron.
So the number of $(n-k)$-faces is $k!\, S(n,k)$.
