%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%  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




.
