Permutohedron

In mathematics, the permutohedron of order n (also spelled permutahedron) is an (n − 1)-dimensional polytope embedded in an n-dimensional space, the vertices of which are formed by permuting the coordinates of the vector (1, 2, 3, ..., n).

According to Ziegler (1995), permutohedra were first studied by Schoute (1911). The name "permutohedron" (or rather its French version, "permutoèdre") was coined by Guilbaud & Rosenstiehl (1963). Regarding this coinage, they write that the word "permutohedron" is barbaric, but easy to remember, and that they submit it to the criticism of their readers.

The alternative spelling permutahedron is sometimes also used. Permutohedra are sometimes also called permutation polytopes, but this terminology is also used for a related polytope, the Birkhoff polytope, defined as the convex hull of permutation matrices. More generally, Bowman (1972) uses the phrase "permutation polytope" for any polytope whose vertices are in 1-1 correspondence with the permutations of some set.

The permutohedron of order n has n! vertices, each of which is adjacent to n − 1 others, so the total number of edges is (n − 1)n!/2. Each edge has length √2, and connects two vertices that differ by swapping two coordinates the values of which differ by one.

The permutohedron has one facet for each nonempty proper subset S of {1, 2, 3, ..., n}, consisting of the vertices in which all coordinates in positions in S are smaller than all coordinates in positions not in S. Thus, the total number of facets is 2ⁿ − 2. More generally, the faces of the permutohedron (including the permutohedron itself, but not including the empty set) are in 1-1 correspondence with the strict weak orderings on a set of n items: a face of dimension d corresponds to a strict weak ordering in which there are n − d equivalence classes. Because of this correspondence, the number of faces is given by the ordered Bell numbers.

...
Wikipedia