A polytope related to empirical distributions, plane trees, parking functions, and the associahedron (Q1611066): Difference between revisions

In this paper, the polytopes \[ \Pi_n(x)=\{y\in\mathbb R^n : y\geq 0,\;y_1+\dots+y_i\leq x_1+\dots+x_i\text{ for all }i\} \] (for all \(x\in\mathbb R^n\) with \(x\geq 0\)) are studied, in particular, their \(n\)-dimensional volumes \(V_n(x)\) and the numbers \(N_n(x)\) of integer points contained in them. The authors derive descriptions of \(V_n(x)\) and \(N_n(x)\) (as functions of \(x=(x_1,\dots,x_n)\in\mathbb R_{\geq 0}^n\)) as polynomials in \(x_1,\dots,x_n\). In fact, the terms of highest degree of the polynomial \(N_n(x)\) yield \(V_n(x)\). The result on \(N_n(x)\) is a special case of a much more general result on the number of integer points in sections of order cones, proved in the paper. From this theory, a decomposition of \(\Pi_n(x)\) into \(C_n\) \(n\)-dimensional products of simplices is obtained (\(C_n\) being the \(n\)th Catalan number), whose \(n\)-dimensional volumes equal the coefficients of the polynomial \(V_n(x)\). A different such polyhedral decomposition of \(\Pi_n(x)\) is derived by associating to every \(y\in\Pi_n(x)\) a plane binary tree with edge lengths. The complex of interior faces of the latter decomposition is combinatorially equivalent to an associahedron. Furthermore, the authors derive several results concerning empirical distribution functions and parking functions via the polynomial \(V_n(x)\).