%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% Plain TeX file - 13 pages paper %%%% \magnification = 1095 \vsize = 8.0 true in \hsize = 6.1 true in \hoffset = 0.3 true in \voffset = 0.2 true in \baselineskip = 1.1 pc \parskip = .5 pc \parindent = 1.5 pc \def\qed{{\hfill \offinterlineskip \vbox { \hrule \hbox{\vrule \phantom{i$\!$} \vrule } \hrule} }} \font\smcp=cmcsc8 \headline={\ifnum\pageno>1 {\smcp the electronic journal of combinatorics 4 (no. 2) (1997), \#R18\hfill\folio} \fi} \ \vskip 1 true in \centerline{\bf Some geometric probability problems} \centerline{\bf involving the Eulerian numbers} \centerline{} \centerline{Frank Schmidt} \centerline{Rodica Simion\footnote\dag{Partially supported through NSF grant DMS--9108749.}} \centerline{Department of Mathematics} \centerline{The George Washington University} \centerline{Washington, DC 20052} \centerline{simion@math.gwu.edu} \bigskip \bigskip \centerline{} \centerline{\it Dedicated to Herb Wilf on the occasion of his sixty-fifth birthday} \centerline{} \bigskip \bigskip \centerline{\bf Abstract} We present several problems involving geometric probability. Each is related to the division of a simplex or cube by a family of hyperplanes. Both the classical Eulerian numbers and their analogue for the hyperoctahedral group arise in the solutions. \bigskip \bigskip \noindent {\bf 0. Introduction} Consider the following general type of problem: From a convex polytope $P \subset {\bf R}^n$, select a point ${\bf x} = (x_1, x_2, \dots, x_n)$ at random according to a certain fixed distribution. Given a function $f \colon P \to {\bf R}$ and a sequence of functions $\rho_0, \rho_1, \dots, \rho_m \ \colon \ P \to {\bf R}$, satisfying $\rho_0({\bf x}) \leq \rho_1({\bf x}) \leq \dots \leq \rho_m({\bf x})$ and $\rho_0({\bf x}) \leq f({\bf x}) \leq \rho_m({\bf x})$, what is the probability that $\rho_{i-1} ({\bf x}) \leq f({\bf x}) \leq \rho_i ({\bf x})$? For example, what is the probability that the average of the coordinates of $\bf x$ is at most $1 \over 2$, if ${\bf x}$ is selected uniformly at random from $P = [0,1]^n$, the $n$-dimensional unit cube? This arises upon choosing $f({\bf x}) = { { x_1 + x_2 + \dots + x_n } \over {n} }$, and the constant functions $\rho_0 ({\bf x}) = 0$, $\rho_1 ({\bf x}) = {1 \over 2}$, and $\rho_2 ({\bf x}) = 1$. Here we present several problems of this type, in which the selection of ${\bf x}$ is done uniformly at random, and the functions $f, \rho_0, \rho_1, \dots, \rho_m$ are linear. Hence, the problems can be reformulated geometrically as follows. Let $H_1, H_2, \dots, H_m$ be a sequence of affine hyperplanes in ${\bf R}^n$. For each $i$, let $H_i^+$ and $H_i^-$ be the two closed half-spaces in ${\bf R}^n$ determined by $H_i$. In terms of the original formulation of the problem, the hyperplane $H_i$ has equation $f({\bf x}) = \rho_i({\bf x})$, and $H_i^+ = \{ {\bf x} \in {\bf R}^n \ \colon \ f({\bf x}) \leq \rho_i({\bf x}) \}$. If a point ${\bf x}$ is selected uniformly at random from the polytope $P$, what is the probability that $\bf x$ lies in $P \cap H_{i-1}^- \cap H_i^+$? Since the selection of $\bf x$ is done uniformly at random, this geometric probability can be expressed in terms of the ($n$-dimensional) volume of the region $P \cap H_{i-1}^- \cap H_i^+$. Thus, we are led to consider problems in which the goal is to find the volumes of the regions into which a polytope is divided by a family of hyperplanes. When the choice of polytope is $P= [0,1]^n$, the selection of a point ${\bf x}$ uniformly at random corresponds to the selection of $x_1, x_2, \dots, x_n$ from $[0,1]$ independently at random, according to the uniform distribution. A related probabilistic question is to consider order statistics. That is, after selecting ${\bf x} = (x_1, x_2, \dots, x_n)$ as above, first reorder its coordinates in weakly increasing order, and then apply the functions $f$ and $\rho_i$ to the increasingly ordered $n$-tuple ${\bf x}^{\leq} \in {\bf R}^n$ thus obtained. Clearly, ${\bf x}^{\leq}$ lies in the $n$-dimensional simplex $\Delta^n \ \colon = \ \{ (x_1, x_2, \dots, x_n) \in {\bf R}^n \ \colon \ 0 \leq x_1 \leq x_2 \leq \dots \leq x_n \leq 1 \}$. If the selection is according to the uniform distribution, then the desired probability can be obtained by selecting $\bf x$ uniformly directly from the simplex $\Delta^n$. This leads to the question of finding the volumes of the regions into which the simplex $\Delta^n$ is divided by a family of hyperplanes. The specific problems described here pertain to the cube $[0,1]^n$ and the simplex $\Delta^n$, and the answers turn out to involve well-known sequences from combinatorial enumeration. The $(n-1)$-dimensional volumes of the sections $[0,1]^n \cap H_i$ or $\Delta^n \cap H_i$ turn out to have closely related expressions as well. As an initial example, consider the simplex $\Delta^n$ and the functions $f({\bf x}) = 0$, $\rho_0({\bf x}) = - \alpha $, and $\rho_i({\bf x}) = x_i - \alpha$, for some real number $\alpha \in (0, 1)$ and $1 \leq i \leq n$. If ${\bf x}$ is chosen uniformly at random from $\Delta^n$, then the probability ${\rm Pr} [\rho_{i-1}({\bf x}) \leq f({\bf x}) \leq \rho_i({\bf x}) ]$ equals ${\rm Pr} [ x_{i-1} \leq \alpha \leq x_i ]$ (where $x_0 = 0$). The values of the first $i-1$ coordinates, selected from $[0,1]$, are all from $[0, \alpha]$ with probability $\alpha^{i-1}$. Similarly, the values of the $i$th through $n$th coordinates are from $[\alpha, 1]$ with probability $(1-\alpha)^{n-i+1}$. Finally, upon ordering the coordinates in increasing order, we obtain the probability ${{n!} \over {(i-1)! (n-i+1)!}}\alpha^{i-1} (1-\alpha)^{n -i+1}$. Equivalently, the hyperplanes $H_i$ with equations $x_i = \alpha$, for $1 \leq i \leq n$, dissect $\Delta^n$ into $n+1$ regions with volumes given by $V^{(n)}(R^{(n)}_i) = {1 \over {n!}} {n \choose {i-1}} \alpha^{i-1} (1-\alpha)^{n -i+1}$, for $ 1 \leq i \leq n+1$. When $\alpha = {1 \over 2}$, the volumes have especially simple expressions proportional to binomial coefficients: $V^{(n)}(R^{(n)}_i) = {1 \over {{n!} 2^n} } {n \choose {i-1}}$. (This corresponds to the case of a fair coin if the problem is phrased in terms of tossing a coin having probability $\alpha$ for heads.) The sections $S^{(n)}_i \colon = \Delta^n \cap H_i$ have $(n-1)$-dimensional volumes proportional to binomial coefficients as well (for a given $i$, we have $x_i = \alpha$, and the probability that $x_1, \dots, x_{i-1} \leq \alpha$ and $x_{i+1}, \dots, x_n \ge \alpha$ can be computed similarly to the previous calculation). The preceding example involves a pencil of $n$ hyperplanes passing through the point $(\alpha, \alpha, \dots, \alpha) \in {\bf R}^n$, which are parallel to the coordinate hyperplanes, and the volumes of the resulting regions and sections of $\Delta^n$ involve binomial coefficients. In Section 2 we consider the simplex and a different pencil of $n$ hyperplanes passing through $({1\over 2}, {1\over 2}, \dots, {1\over 2})$. The volumes of the resulting regions and sections of the simplex turn out to be related to the Eulerian numbers. These numbers are well-known in permutation enumeration. First we solve the problem of finding the volumes of the regions through a direct geometric and inductive argument. Then we sketch a second approach, using tools from probability theory. The Eulerian numbers arise again in Section 3, in a problem dating back to Laplace, concerning the cube and a certain family of parallel hyperplanes. Similar results are derived for a different family of parallel hyperplanes and the cube, which give rise to the analogue of Eulerian numbers for the hyperoctahedral group. This follows readily from recurrence relations given in [ChLo], where the volumes of regions and sections are discussed. We provide an explanation for this connection between geometry and the enumeration of signed permutations, by adapting to the hyperoctahedral case a result for the symmetric group (the previous problem) found by Stanley [St2] in response to a question posed by Foata [Fo]. The final section includes several open problems. \bigskip \bigskip \noindent {\bf 1. Eulerian numbers and the simplex} Suppose that a point $\bf x$ is selected uniformly at random from the simplex $\Delta^n = \{ {\bf x} = (x_1, x_2, \dots , x_n) \in {\bf R}^n \ \colon \ 0 \leq x_1 \leq x_2 \leq \dots \leq x_n \leq 1 \}$. What is the probability that the average of $0, 1$, and the coordinates of $\bf x$ falls between the $(i-1)$st and $i$th coordinates of $\bf x$? Note that ${\rm Pr}[ x_{i-1} < { {x_1 + \dots + x_{n+2}}\over {n+2}} \leq x_i ]$ with ${\bf x}$ selected from $\Delta^{n+2}$ gives the same distribution, as can be seen by conditioning on the values of $x_1$ and $x_{n+2}$. This geometric probability question arises from choosing $f({\bf x}) = { {x_1 + x_2 + \dots + x_n + 1}\over{n+2} }$, $\rho_0({\bf x})=0$, and $\rho_i({\bf x}) = x_i$ for $i = 1, 2, \dots, n$. Thus, we consider the hyperplanes $H_i \subset {\bf R}^n$ with equations $$x_1 + x_2 + \dots + x_n + 1 = (n+2) x_i,$$ for $i = 1, 2, \dots, n$. These form a pencil of hyperplanes through the point $({1 \over 2}, {1 \over 2}, \dots , {1 \over 2}) \in {\bf R}^n$, and they determine $n+1$ regions, $R^{(n)}_1, R^{(n)}_2, \dots, R^{(n)}_{n+1}$ in the simplex $\Delta^n$: \hfil\break $R^{(n)}_1 \ = \{ {\bf x} \in \Delta^n \ \colon \ \sum_{k=1}^{n}{x_k} \ + 1 \leq (n+2)x_1 \}$, $R^{(n)}_i \ = \{ {\bf x} \in \Delta^n \ \colon \ (n+2)x_{i-1} \leq \sum_{k=1}^{n}{x_k} \ + 1 \leq (n+2)x_i \}$ for $2 \leq i \leq n$, and $R^{(n)}_{n+1} \ = \{ {\bf x} \in \Delta^n \ \colon \ (n+2) x_n \leq \sum_{k=1}^{n}{x_k} \ + 1 \}$. The question of finding $${\rm Pr} \bigl[ x_{i-1} < { { 0 + x_1 + x_2 + \dots + x_n + 1} \over {n+2} } \leq x_i \bigr]$$ is answered then by determining the sequence of volumes $\bigl( V^{(n)}(R^{(n)}_i) \bigr)_{i=1}^{n+1}$ of these regions. For example, in dimensions $n = 1, 2, 3$, the volumes of the regions are: \hfil\break\indent $\bigl( \ V^{(1)}(R^{(1)}_1), \ V^{(1)}(R^{(1)}_2) \ \bigr) \ = \ \bigl( {1 \over 2}, {1 \over 2} \bigr)$, \hfil\break\indent $\bigl( \ V^{(2)}(R^{(2)}_1), \ V^{(2)}(R^{(2)}_2), \ V^{(2)}(R^{(2)}_3) \ \bigr) \ = \ \bigl( {1 \over {12}}, {4 \over {12}}, {1 \over {12}} \bigr)$, \hfil\break\indent $\bigl( \ V^{(3)}(R^{(3)}_1), \ V^{(3)}(R^{(3)}_2), \ V^{(3)}(R^{(3)}_3), \ V^{(3)}(R^{(3)}_4) \ \bigr) \ = \ \bigl( {1\over{144}}, {{11}\over{144}}, {{11}\over{144}}, {1\over{144}} \bigr)$. \hfil\break These low-dimensional cases suggest that the volumes are proportional to the Eulerian numbers (see, e.g., [Co], [St1]). A permutation $\sigma \in S_n$ has a {\it descent} in position $i$ (where $1 \leq i \leq n-1$) if $\sigma(i) > \sigma(i+1)$, and the Eulerian numbers count permutations according to their number of descents. \bigskip \noindent {\bf Theorem 1.1.} \hfil\break\indent {\it Let $A(m,j)$ denote the Eulerian numbers, i.e., the number of permutations in the symmetric group $S_m$ having exactly $j$ descents. Then, the hyperplanes with equations $\sum_{k=1}^{n}{x_k} \ + 1 = (n+2) x_i$, for $1 \leq i \leq n$, dissect the simplex $\Delta^n$ into regions $R^{(n)}_i$ whose volumes are given by $$V^{(n)}(R^{(n)}_i) = { {A(n+1, i-1)} \over {n! (n+1)!} },$$ and the $(n-1)$-dimensional volumes of the sections $S^{(n)}_i \ = \Delta^n \cap H_i$ for $ 1 \leq i \leq n$ are given by $$V^{(n-1)}(S^{(n)}_i) = c(n) \cdot { {A(n, i-1)} \over {(n-1)! n!} },$$ where $c(n) = {\sqrt{n^2 + 3n}}/(n+1)$. } %%% end italics \bigskip For ease of exposition, we postpone the proof of the theorem until after three preliminary results. \bigskip \noindent{\bf Lemma 1.2.} \hfil\break\indent {\it For each $i = 1, 2, \dots, n$, the section $S^{(n)}_i$ has $i(n-i+1)$ vertices ${\bf x}$ whose coordinates are $$x_1 = x_2 = \dots = x_s = 0,$$ $$x_{s+1} = \dots = x_i = \dots = x_r = {{n-r+1}\over{n-r+s+2}},$$ $$x_{r+1} = \dots = x_n = 1,$$ where $0 \leq s < i \leq r \leq n$. In particular, the point $({1\over 2}, {1\over 2}, \dots , {1\over 2})$ belongs in the intersection of $\Delta^n$ with every hyperplane $H_i$. } %%%%%%%%% end ital \noindent {\it Proof.} The vertices of $\Delta^n$ have coordinates of the form $(0,0, \dots, 0,1,1,\dots,1)$, with the number of $0$'s ranging between zero and $n$. Hence, an edge of $\Delta^n$ consists of points having a certain number, $s \ge 0$, of initial coordinates equal to $0$, followed by a number, $r-s \ge 0$, of equal coordinates whose common value lies in $(0,1)$, followed in turn by $n-r \ge 0$ coordinates equal to $1$. To determine such a point ${\bf x}$ which lies in $H_i$, observe that if $x_{r+1} = \dots = x_n = 1$ for some $r+1 \leq i$, then the equation of $H_i$ requires $s \cdot 0 + (r-s) x_r + (n-r)\cdot 1 + 1 = (n+2) \cdot 1$, implying $x_r = {{r+1}\over{r-s}} > 1$. Since such a point ${\bf x}$ is not in $\Delta^n$, we must have $i \leq r$. Similarly, if $s \ge i$, then the equation of $H_i$ requires $(r-s) x_r + (n-r)\cdot 1 + 1 = 0$, implying that $x_r < 0$, so again ${\bf x} \not\in \Delta^n$. Therefore we must have $0 \leq s < i \leq r \leq n$, and it follows from the equation of $H_i$ that $x_{s+1} = \dots = x_r = {{n-r+1}\over{n-r+s+2}}$, and ${\bf x} \in \Delta^n \cap H_i$. \qed In the sequel, we will write $H^{(d)}_i$ to indicate the dimension $d$ of the ambient Euclidean space in which we view the hyperplane $H_i$. \bigskip \noindent{\bf Lemma 1.3.} \hfil\break\indent {\it For each $i$ such that $1 \leq i \leq n$, the region $R^{(n-1)}_i$ of $\Delta^{n-1}$ is a projection of the section $S^{(n)}_i$ of $\Delta^n$. } %%%%%%%%%% end ital \noindent {\it Proof.} First, we describe the vertices of $R^{(n-1)}_i$ when $i$ satisfies $2 \leq i \leq n-1$. These vertices fall into three classes: those of the section $S^{(n-1)}_i$, those of the section $S^{(n-1)}_{i-1}$, and vertices of $\Delta^{n-1}$. In the first two types we have vertices as described in Lemma 1.2 (shifting the dimension down to $n-1$). These overlap in the vertices of $\Delta^{n-1} \cap H^{(n-1)}_i \cap H^{(n-1)}_{i-1}$. There are $(i-1)(n-i)$ vertices in this intersection, namely, for each choice of $s,r$ such that $0 \leq s < i-1 < i \leq r \leq n-1$, we obtain a vertex ${\bf x} \in \Delta^{n-1} \cap H^{(n-1)}_i \cap H^{(n-1)}_{i-1}$ whose coordinates are $x_1 = x_2 = \dots = x_s = 0$, $x_{s+1} = \dots = x_{i-1} = x_i = \dots = x_r = {{n-r}\over{n-r+s+1}}$, $x_{r+1} = \dots = x_{n-1} = 1$. Only one vertex of $\Delta^{n-1}$ appears in $R^{(n-1)}_i$. This is the vertex whose coordinates are $x_1=x_2=\dots = x_{i-1} = 0$, $x_i = x_{i+1} = \dots = x_{n-1}=1$, and we denote it by $v^{(n-1)}_i$. In particular, for $2 \leq i \leq n-1$, the total number of vertices of $R^{(n-1)}_i$ is $i(n-i) + (i-1)(n-i+1) - (i-1)(n-i) + 1 = i(n-i+1)$, the same (by Lemma 1.2) as the number of vertices of $S^{(n)}_i$. The regions $R^{(n-1)}_1$ and $R^{(n-1)}_n$ are $(n-1)$-dimensional simplices. Indeed, the vertices of $R^{(n-1)}_1$ are $v^{(n-1)}_1 = (1, 1, \dots, 1)$ and the $n-1$ vertices of $S^{(n-1)}_1$ as in Lemma 1.2. Similarly, $R^{(n-1)}_n$ has $n$ affinely independent vertices (the origin $v^{(n-1)}_n = (0, 0, \dots, 0)$ and the $n-1$ vertices of $S^{(n-1)}_{n-1}$). By comparing the above description of the vertices of $R^{(n-1)}_i$ with the earlier description of the vertices of $S^{(n)}_i$ (Lemma 1.2), we see that the projection \hfil\break $(x_1, x_2, \dots , x_n) \to (x_1, \dots, x_{i-1}, x_{i+1}, \dots, x_n)$ is a bijection between the vertices of $S^{(n)}_i$ and $R^{(n-1)}_i$, which maps $S^{(n)}_i$ onto $R^{(n-1)}_i$. \qed \bigskip \noindent{\bf Corollary 1.4.} \hfil\break\indent {\it The $(n-1)$-dimensional volumes of $S^{(n)}_i$ and $R^{(n-1)}_i$ are related by $$V^{(n-1)}(S^{(n)}_i) = {{\sqrt{n^2 + 3n}}\over{n+1}} \cdot V^{(n-1)}(R^{(n-1)}_i).$$ } \noindent {\it Proof.} Since the hyperplane $H^{(n)}_i$ containing $S^{(n)}_i$ has unit normal vector \hfil\break $N^{(n)}_i = { {(1, 1, \dots, 1, -(n+1), 1, \dots, 1)}\over{\sqrt{n^2+3n}} }$ (the non-unit coordinate is the $i^{\rm th}$ one), the desired relation follows from Lemma 1.3. \qed \bigskip \noindent {\it Proof of Theorem 1.1.} The proof is by induction on the dimension $n$. The result is obviously true for $n=1$, where $R^{(1)}_1$ and $R^{(1)}_2$ are segments of length $1\over 2$. Consider $n \ge 2$. For $i = 2, 3, \dots, n$, the region $R^{(n)}_i$ is the union of two pyramids with apex $v^{(n)}_i = (0, \dots, 0, 1, \dots, 1)$ (the first unit coordinate is the $i^{\rm th}$ one). One pyramid is ${\rm pyr} (v^{(n)}_i, S^{(n)}_i)$ over the section $S^{(n)}_i$ and the other is ${\rm pyr} (v^{(n)}_i, S^{(n)}_{i-1})$ over the section $S^{(n)}_{i-1}$. Their intersection is the $(n-1)$-dimensional pyramid with apex $v^{(n)}_i$ over the $(n-2)$-dimensional intersection of $S^{(n)}_i$ and $S^{(n)}_{i-1}$. The distance $d_i$ from $v^{(n)}_i$ to $H^{(n)}_i$ is easily calculated as $${| -1 - (N^{(n)}_i , v^{(n)}_i) |}\over{|| N^{(n)}_i ||},$$ and is equal to $$d_i = {i \over {\sqrt{n^2 + 3n}}}.$$ Similarly, the distance $d_{i-1}$ between $v^{(n)}_i$ and $H^{(n)}_{i-1}$ is $$d_{i-1} = { {n-i+2}\over {\sqrt{n^2 + 3n}}}.$$ Together with Corollary 1.4, this implies that for $2 \leq i \leq n$, $$V^{(n)}(R^{(n)}_i) = {1\over n} \cdot d_i \cdot V^{(n-1)}(S^{(n)}_i) + {1\over n} \cdot d_{i-1} \cdot V^{(n-1)}(S^{(n)}_{i-1})$$ $$= {1\over {n(n+1)}} [i \cdot V^{(n-1)}(R^{(n-1)}_i) + (n-i+2) \cdot V^{(n-1)}(R^{(n-1)}_{i-1})].$$ By induction, we obtain $$V^{(n)}(R^{(n)}_i) = {1\over{n! (n+1)!}} [ i A(n, i-1)+ (n-i+2) A(n,i-2)]$$ $$ = {1\over{n! (n+1)!}} A(n+1, i-1).$$ The last equality follows from the standard recurrence relation satisfied by the Eulerian numbers (see, e.g., [Co]). For $i=1$, the volume of the simplex $R^{(n)}_1$ can be computed directly via a determinant evaluation or, using the notation established above, $$V^{(n)}(R^{(n)}_1) = {1 \over n} \cdot d_1 \cdot V^{(n-1)}(S^{(n)}_1),$$ in which we have $d_1 = {1\over {\sqrt{n^2 + 3n}}}$ and, by Corollary 1.4, $V^{(n-1)}(S^{(n)}_1) = {{\sqrt{n^2+3n}}\over{n+1}} V^{(n-1)}(R^{(n-1)}_1)$. Again, inductively we have $V^{(n-1)}(R^{(n-1)}_1) = {{A(n, 0)}\over{(n-1)! n!}} = {1 \over {(n-1)! n!}}$, and it follows that \hfil\break $V^{(n)}(R^{(n)}_1) = { {A(n+1, 0)}\over{n! (n+1)!}}$. We omit the calculation of $V^{(n)}(R^{(n)}_{n+1})$ which follows through a similar direct computation, or simply by symmetry. \qed \bigskip Using Theorem 1.1 we derive an expression for the partial sums of the Eulerian numbers. As before, let ${\bf x} = (x_1, \dots, x_n)$ denote a random point in the simplex $\Delta^n$. Successive differences $x_j - x_{j-1}$ are called {\it spacings}. We may model the spacings as follows (see [Py]): $x_j - x_{j-1} = { {y_j} \over {y_1 + y_2 + \dots + y_{n+1}} }$, for $1 \leq j \leq n+1$, where each $y_j$ is a standard exponential random variable and where we define $x_0 = 0$ and $x_{n+1} = 1$. Next, rewriting the probability in terms of the $y$'s, we get for $1 \leq j \leq n$: $${\rm Pr} \bigl[ { { x_1 + x_2 + \dots + x_n + 1 } \over {n+2} } \leq x_j \bigr] $$ $$ = \ {\rm Pr} \bigl[ (n-j+1) y_{j+1} + \dots + 3 y_{n-1} + 2 y_n + y_{n+1} \leq y_1 + 2 y_2 + 3 y_3 + \dots + j y_j \bigr]. \hskip 2 pc (*) $$ Each $y_j$ has probability density function (p.d.f.) $$g(t) = \cases{ e^{-t} &if $t \ge 0$, \cr 0 &if $t < 0$. \cr } $$ For distinct, positive values $c_j$ ($1 \leq j \leq k$), the p.d.f. for $Y = c_1 y_1 + c_2 y_2 + \dots + c_k y_k$ is (see [JK], p. $\!\!$222) $$ g_Y(t) = \sum_{i=1}^{k}{ { {c_i^{k-2} } \over { \prod_{j\neq i}{(c_i - c_j)} } } } e^{-t / {c_i} }, {\rm \ \ \ for \ } t \ge 0. $$ Let $Y_1 = (n-j+1) y_{j+1} + \dots + 3 y_{n-1} + 2 y_n + y_{n+1}$ and $Y_2 = y_1 + 2 y_2 + 3 y_3 + \dots + j y_j$. With this notation, $(*)$ is given by $$\int_{0}^{\infty} {g_{Y_2}(t)\ dt \int_{0}^{t}{ g_{Y_1}(s)\ ds }},$$ where $$ g_{Y_1}(s) = \sum_{a=1}^{n-j+1} { { {(-1)^{n+j+1-a} a^{n-j-1} } \over {(a-1)! (n-j+1-a)! } } e^{- s / a} }$$ and $$ g_{Y_2}(t) = \sum_{i=1}^{j} { { {(-1)^{j-i} i^{j-2} } \over {(i-1)! (j-i)!} } e^{-t / i} }.$$ Performing the integration gives $${\rm Pr} \bigl[ { { x_1 + x_2 + \dots + x_n + 1 } \over {n+2} } \leq x_j \bigr] \ = \ \sum_{i=1}^{j}{ \sum_{a=1}^{n-j+1} { { {(-1)^{n+1-i+a} a^{n-j} i^j } \over {(i+a) (i-1)! (j-1)! (a-1)! (n-j+1-a)!} } } }.$$ Equivalently, we get the following expression for the partial sums of the Eulerian numbers: $$ \sum_{k=0}^{j-1}{ A(n+1, k) } \ = \ (n+1) n {{n-1} \choose {j-1}} \sum_{i=1}^{j}{ \sum_{a=1}^{n-j+1} { { {(-1)^{n+1-i-a} } \over {i + a} } {{j-1} \choose {i-1}} {{n-j} \choose {a-1}} a^{n-j} i^j }},$$ for $1 \leq j \leq n$. \bigskip \bigskip \noindent {\bf 2. Eulerian numbers and the cube} %% 3. cube - Laplace, Foata, RPS Turning to a cube as the choice of polytope $P$, we will consider two problems. The first one corresponds to the choice of functions $f({\bf x}) = x_1 + x_2 + \dots + x_n$, $\rho_0({\bf x}) = 0$ and $\rho_i({\bf x}) = i$ for $1 \leq i \leq n-1$. Thus, this problem concerns the volumes of the $n$ regions of $[0,1]^n$ determined by the $n-1$ hyperplanes $H_i \ \colon \ \ x_1 + x_2 + \dots + x_n = i$, for $1 \leq i \leq n-1$. We denote the regions as $R^{(n)}_i = \{ {\bf x} \in [0,1]^n \ \colon \ i-1 \leq \sum_{k=1}^{n}{x_k} \leq i \}$, for $1 \leq i \leq n$. The solution to this problem is implicit in the work of Laplace [Lap] and it appears in [Fo], in the context of results about combinatorial statistics on permutations. The Eulerian numbers arise again: the volumes of the regions are given by $$V^{(n)}(R^{(n)}_i) = {1 \over {n!}} A(n, i-1),$$ and the $(n-1)$-dimensional volumes of the sections are also proportional to Eulerian numbers. The expression for the volume $V^{(n)}(R^{(n)}_i)$ suggests that (up to a set of measure zero) the region $R^{(n)}_i$ may be partitioned by the images, under a measure-preserving transformation, of $A(n,i-1)$ $n$-dimensional simplices, each of volume ${1 \over {n!}}$. Moreover, these simplices may be in natural correspondence with the permutations in $S_n$ which have $i-1$ descents. The existence of such a map would provide an alternative proof of the volume formulas for the regions, reflecting the combinatorial nature of the formulas. In reponse to a question asked by Foata, Stanley [St2] exhibited such a map. The map $\varphi$ whose description follows is essentially that given in [St2]. First, it is well-known that the unit cube, $[0,1]^n$, is dissected by the hyperplanes $x_i = x_j$, $1 \leq i < j \leq n$, into $n!$ simplices, each having volume $1 \over {n!}$. For each such simplex, there exists a permutation $\sigma \in S_n$ which permutes in increasing order the coordinates of every point in the interior of the simplex. Denote the simplex by $\Delta_{\sigma}$. Now, the desired map $\varphi$ on $[0,1]^n$ less the measure zero set of points having any equal consecutive coordinates, is defined by $\varphi({\bf x}) = {\bf y} \in [0,1]^n$, where $$y_n = 1 - x_n,$$ and $$y_i = \cases{x_{i+1} - x_i &if $x_{i} < x_{i+1}$,\cr 1 + x_{i+1} - x_i &if $x_{i} > x_{i+1}$,\cr }$$ for $i=1, 2, \dots, n-1$. Note that if ${\bf x} \in \Delta_{\sigma}$, then $f({\bf y}) = \sum_{k=1}^{n}{y_k} = {\rm des}(\sigma) + 1 - x_1$, where ${\rm des}(\sigma)$ denotes as usual the number of descents of $\sigma$. Thus, $\varphi(\Delta_{\sigma}) \subset R^{(n)}_{{\rm des}(\sigma) + 1}$. Note also that $\varphi$ is an affine transformation on each of the $2^{n-1}$ regions determined by a choice of $x_{i+1} > x_{i}$ or $x_{i+1} < x_{i}$ for each $i= 1, 2, \dots, n-1$, and that the determinant of the transformation is equal to $(-1)^n$. Therefore $\varphi$ is measure-preserving. The inverse of $\varphi$ is defined on $[0,1]^n$ less the set of measure zero $\{ {\bf y} \in [0,1]^n \ : \ \sum_{k=i}^{n}{y_k} \in {\bf Z}, {\rm \ for \ some \ } i \}$, and is given by $\varphi^{-1}({\bf y}) = {\bf x}$, where $x_i = 1 + \lfloor \sum_{k=i}^{n}{y_k} \rfloor - \sum_{k=i}^{n}{y_k}$ for each $i$. The remainder of this section is devoted to analogous results for a second problem involving the cube. Let again $P = [0,1]^n$, $f({\bf x}) = x_1 + x_2 + \dots + x_n$, and $\rho_0({\bf x}) = 0$, and consider the functions $\rho_i({\bf x}) = i - {1 \over 2}$, for $1 \leq i \leq n$. These give rise to $n$ parallel hyperplanes, $H_i \ \colon \ \ x_1 + x_2 + \dots + x_n = i-{1\over 2}$, for $1 \leq i \leq n$. The volumes of the resulting $n+1$ regions and $n$ sections were investigated by Chakerian and Logothetti [ChLo], who established recurrence relations satisfied by the sequence of volumes. We denote the regions by $R^{(n)}_{i+1} \ = \ \{ {\bf x} \in [0,1]^n \ \colon \ {i - {1 \over 2}} \leq \sum_{k=1}^{n}{x_k} \leq {i + {1 \over 2}} \}$, for $0 \leq i \leq n$. \bigskip \noindent{\bf Proposition 2.1.} ([ChLo]) \hfil\break\indent {\it For $i=0, 1, \dots, n$, let $S(i,n-i) = 2^n n! V^{(n)}(R^{(n)}_{i+1})$. Then $$ S(i,n-i) = (2i +1) S(i, n-i-1) + (2n - 2i + 1) S(i-1, n-i),$$ with $S(0,0) = 1$. } %%%%%%%%%% end ital \bigskip It turns out that this recurrence implies that the volumes are proportional to the Eulerian numbers for signed permutations. A {\it signed permutation} on $n$ letters is a permutation of $\{ 1, 2, \dots, n \}$ in which each letter may bear a minus sign. The signed permutations on $n$ letters form the hyperoctahedral group of order $2^n n!$. For notational convenience, we will write ${\overline{m}}$ instead of $-m$. The notion of {\it descent} for signed permutations is based on the linear ordering $1 < 2 < \dots < n < {\overline{n}} < {\overline{n-1}} < \dots < {\overline{2}} < {\overline{1}}$ of the symbols, together with the fact that if the last letter in the permutation is negative (``barred''), then the last position contributes a descent. For example, the signed permutation ${\overline{2}} \ 4 \ 5 \ 1 \ 6 \ {\overline{3}}$ has $3$ descents (occurring in positions 1, 3, and 6). For $0 \leq i \leq n$, let ${\overline{A}}(n,i)$ denote the number of signed permutations on $n$ letters, having exactly $i$ descents. For example, when for $n=2$, we have ${\overline{A}}(2,0) = 1$, ${\overline{A}}(2,1) = 6$, and ${\overline{A}}(2,2) = 1$. \bigskip \noindent{\bf Corollary 2.2.} \hfil\break\indent {\it Let ${\overline{A}}(n,m)$ denote the Eulerian numbers for the hyperoctahedral group on $n$ letters. Then the hyperplanes with equations $\sum_{k=1}^{n}{x_k} = i - {1 \over 2}$, for $1 \leq i \leq n$, dissect the unit cube $[0,1]^n$ into regions $R^{(n)}_i$ whose volumes are given by $$V^{(n)}(R^{(n)}_i) = { { {\overline{A}}(n,i-1) } \over { 2^n n!} }, \ \ \ \ 1 \leq i \leq n+1.$$ } \bigskip \noindent {\it Proof.} In Proposition 2.1 one recognizes, as explained below, the recurrence relation for the hyperoctahedral Eulerian numbers, leading to the conclusion $S(i,n-i) = {\overline{A}}(n,i)$ for all $0 \leq i \leq n$. Indeed, it can easily be checked that $${\overline{A}}(n,i) = (2i+1) \ {\overline{A}}(n-1,i) + (2n - 2i + 1) \ {\overline{A}}(n-1,i-1),$$ by examining how a signed permutation counted by the left-hand-side can arise from the insertion of either $1$ or ${\overline{1}}$ into a signed permutation ${\overline{\tau}}$ on $\{ 2, 3, \dots, n \}$. Clearly, if $1$ is inserted into ${\overline{\tau}}$, then it will be the absolute minimum of the resulting signed permutation, while if ${\overline{1}}$ is inserted into $\overline{\tau}$, then it will be the absolute maximum. Therefore, if ${\rm des}({\overline{\tau}}) = i$, then one of $1$ or ${\overline{1}}$ should be inserted so that the number of descents will be preserved. There are precisely $2i+1$ such insertions, of which $2i$ are of type (i) and one is of type (ii), as follows: (i) insert either $1$ or ${\overline{1}}$ after the larger element of one of the $i$ descents of ${\overline{\tau}}$; (ii) insert $1$ at the front of ${\overline{\tau}}$. This gives the first term on the right-hand-side. The second term is obtained similarly: if ${\rm des}({\overline{\tau}}) = i-1$, then the number of descents must be increased by one. This is achieved through each of precisely the following $2(n-i)+1$ insertions: (i) insert either $1$ or ${\overline{1}}$ after the smaller element of one of the ascents of ${\overline{\tau}}$; (ii) insert $1$ at the front of ${\overline{\tau}}$. The initial conditions are obvious and the desired conclusion follows. \qed Next, observe that the hyperplanes $x_i = {1\over 2}$, $x_i = x_j$, and $x_i + x_j = 1$ for $1 \leq i, j \leq n$ dissect the cube $[0,1]^n$ into $2^n n!$ simplices, each of volume $1 \over {2^n n!}$. Now let ${\bf x}$ be any point from the interior of such a simplex. Let ${\bf x'} = ({x'}_1, {x'}_2, \dots, {x'}_n )$, where $${x'}_i = \cases{x_i &if $x_i < 1/2$,\cr 1 - x_i &if $x_i > 1/2$.\cr } $$ Clearly, ${\bf x'}$ has distinct coordinates. Let $\sigma$ be the (ordinary) permutation which orders the coordinates of ${\bf x'}$ increasingly. Finally, we obtain a signed permutation ${\overline{\sigma}}$ by placing a bar over $\sigma(i)$ if $x_i > {1\over 2}$. For example, if ${\bf x} = (0.4, 0.8) \in [0,1]^2$, then ${\bf x'} = (0.4, 0.2)$, leading to $\sigma(1) \sigma(2) = 2 1$ and, finally, to ${\overline{\sigma}} = 2 {\overline{1}}$. All points from the interior of a simplex give rise to the same signed permutation, and we denote by $\Delta_{\overline{\sigma}}$ the simplex corresponding to ${\overline{\sigma}}$. An adaptation of the map found by Stanley for the previous problem plays the analogous role here, mapping the simplex $\Delta_{\overline{\sigma}}$ to the region $R^{(n)}_{{\rm des}({\overline{\sigma}}) + 1}$. \bigskip \noindent{\bf Proposition 2.3.} \hfil\break\indent {\it The map ${\overline{\varphi}}$ given by ${\overline{\varphi}}({\bf x}) = {\bf y}$ where $$y_n = \cases{{1 / 2} - x_n &if $x_n < {1 / 2}$,\cr {3 / 2} - x_n &if $x_n > {1 / 2}$,\cr } $$ and, for $i = 1, 2, \dots, n-1$, $$y_i = \cases{x_{i+1} - x_i &if $x_{i} < x_{i+1}$,\cr 1 + x_{i+1} - x_i &if $x_{i} > x_{i+1}$,\cr } $$ is defined on $[0,1]^n$, measure-preserving, and invertible on $[0,1]^n$, up to measure-zero sets. Moreover, for each $j=0, 1, \dots, n$, the region $R^{(n)}_{j+1}$ of $[0,1]^n$ is partitioned, up to a set of measure zero, by the images of the interiors of the simplices $\Delta_{\overline{\sigma}}$ for those signed permutations satisfying ${\rm des}({\overline{\sigma}}) = j$. } %%%%%%%%%%%% end ital \noindent {\it Proof.} The former part of the conclusion follows from arguments as in [St2]. For the latter part, using the description of ${\bf x'}$, it is easy to check that the second case in the definition of $y_i$, for all $1 \leq i \leq n$, corresponds precisely to a descent in position $i$ for the signed permutation ${\overline{\sigma}}$ corresponding to ${\bf x}$. Thus, $\sum_{k=1}^{n}{y_k} = {\rm des}({\overline{\sigma}}) + {1\over 2} - x_1$ lies in the interval $({\rm des}({\overline{\sigma}}) - {1 \over 2}, {\rm des}({\overline{\sigma}}) + {1 \over 2} )$, and ${\overline{\varphi}}$ maps each $\Delta_{\overline{\sigma}}$ as claimed. \qed \bigskip \bigskip \noindent {\bf 3. Remarks and open questions.} a) For dimensions $n=1, 2, 3$, the sections $S^{(n)}_i$ exhibit the following property: they form a dissection of an $(n-1)$-dimensional simplex (Section 1) or parellelipiped (Section 2). In particular, the union of the sections $S^{(n)}_i$ from Section 1 is, informally put, a ``folded'' $(n-1)$-dimensional simplex, with the folds occurring along the intersections $S^{(n)}_i \cap S^{(n)}_{i+1}$, for $1 \leq i \leq n-1$. Does this property hold in every dimension, and under what conditions does it hold for more general choices of the polytope $P$ and the functions $f$ and $\rho_i$'s? Arguments based on tiling may prove fruitful in this regard. b) In each of the problems discussed here, the sequence of the volumes of regions turns out to be symmetric and unimodal; in fact, even logarithmically concave. Is there a connection between these sequences and mixed volumes (see, e.g., [Lag, p. $\!\!$946]), also known to be logarithmically concave? c) The regions arising from the dissections considered here are themselves convex polytopes, and their vertices have rational coordinates. Upon scaling, they can be transformed into integral polytopes, and thus, the information about the volumes of the regions corresponds to the leading coefficients of the Ehrhart polynomials of the regions (expositions on the Ehrhart polynomial appear, e.g., in [St1], [Hi], in addition to the original treatment [E]). Do the sequences of coefficients of lower-order terms of the Ehrhart polynomial admit enumerative interpretations as well? d) The symmetric group and the group of signed permutations are, in fact, the Weyl groups for the root systems $A_{n-1}$ and $B_n$, respectively. In both cases, the notion of a descent is motivated by the geometric context of reflection groups. Is there a unified approach to the results presented here, in the framework of Coxeter systems? e) A direct combinatorial proof of Theorem 1.1 would be desirable. f) What other combinatorial sequences arise naturally as volumes of regions and sections of polytopes? \bigskip \noindent{\bf Acknowledgment} The authors thank the anonymous referee for the careful reading of the manuscript. \bigskip \bigskip %\vfil\eject \noindent {\bf References} \item{[ChLo]} D. Chakerian and D. Logothetti, {\it Cube slices, pictorial triangles, and probability}, Math. Mag. {\bf 64} (1991) 219-241. \item{[Co]} L. Comtet, ``Advanced Combinatorics,'' D. Reidel, Dordrecht, 1974. \item{[E]} E. Ehrhart, ``Polyn\^omes Arithm\'etiques et M\'ethode des Poly\`edres en Combinatoire,'' \hfil\break Birkh\"auser, Basel and Stuttgart, 1977. \item{[Fo]} D. Foata, {\it Distributions eul\'eriennes et mahoniennes sur le groupe de permutations}, in ``Higher Combinatorics'' (M. Aigner, ed.), NATO Adv. Study Inst. Series, Series C: Mat. and Phys. Sci., D. Reidel, Dordrecht, 1977, p. 27-48. \item{[Hi]} T. Hibi, ``Algebraic Combinatorics on Convex Polytopes,'' Carslaw Publications, Glebe, Australia, 1992. \item{[JK]} N. Johnson and S. Kotz, ``Continuous Univariate Distributions - 1,'' Houghton-Mifflin, Boston, 1970. \item{[Lag]} J. Lagarias, {\it Point lattices}, in ``Handbook of Combinatorics'' (R. Graham, M. Gr\"otschel and L. Lov\'asz, eds.), MIT Press, Cambridge, 1995, p. 919-966. \item{[Lap]} Marquis de Laplace, ``Oeuvres compl\`etes,'' vol. 7, 1820; reprinted by Gauthiers-Villars, Paris, 1886, p. 257 ff. \item{[Py]} R. Pyke, {\it Spacings}, Royal Stat. Soc. (B) {\bf 27} (1965) 395-436. \item{[St1]} R. Stanley, ``Enumerative Combinatorics,'' vol. 1, Wadsworth \& Brooks/Cole, Monterey, 1986; second edition, Cambridge Univ. Press, to appear. \item{[St2]} R. Stanley, {\it Eulerian partitions of a unit hypercube}, in ``Higher Combinatorics'' (M. Aigner, ed.), NATO Adv. Study Inst. Series, Series C: Mat. and Phys. Sci., D. Reidel, Dordrecht, 1977, p. 49. \vfil\eject \bye