The f-Vector of the Descent Polytope

For a positive integer n and a subset S⊆[n-1], the descent polytope DP _S is the set of points (x₁,...,x_n) in the n-dimensional unit cube [0,1]ⁿ such that x_i≥x_i+1 if i∈S and x_i≤x_i+1 otherwise. First, we express the f-vector as a sum over all subsets of [n-1]. Second, we use certain factorizations of the associated word over a two-letter alphabet to describe the f-vector. We show that the f-vector is maximized when the set S is the alternating set {1,3,5,...}∩[n-1]. We derive a generating function for F_S(t), written as a formal power series in two non-commuting variables with coefficients in ℤ[t]. We also obtain the generating function for the Ehrhart polynomials of the descent polytopes.