Some geometric probability problems involving the Eulerian numbers

Frank Schmidt Rodica Simion† Department of Mathematics The George Washington University Washington, DC 20052 simion@math.gwu.edu

Dedicated to Herb Wilf on the occasion of his sixty-fifth birthday

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.

0. Introduction

Consider the following general type of problem: From a convex polytope P ⊂ R^{n}, select a point x = (x_{1}, x_{2}, …, x_{n}) at random according to a certain fixed distribution. Given a function f: P → R and a sequence of functions ρ_{0}, ρ_{1}, …, ρ_{m} : P → R, satisfying ρ_{0}(x) ≤ ρ_{1}(x) ≤ … ≤ ρ_{m}(x) and ρ_{0}(x) ≤ f(x) ≤ ρ_{m}(x), what is the probability that ρ_{i−1}(x) ≤ f(x) ≤ ρ_{i}(x)?

For example, what is the probability that the average of the coordinates of x is at most \frac{1}{2}, if x is selected uniformly at random from P = [0, 1]^{n}, the n-dimensional unit cube? This arises upon choosing f(x) = \frac{x_{1}+x_{2}+...+x_{n}}{n}, and the constant functions ρ_{0}(x) = 0, ρ_{1}(x) = \frac{1}{2}, and ρ_{2}(x) = 1.

† Partially supported through NSF grant DMS–9108749.

Here we present several problems of this type, in which the selection of x is done uniformly at random, and the functions f, ρ_{0}, ρ_{1}, …, ρ_{m} are linear. Hence, the problems can be reformulated geometrically as follows. Let H_{1}, H_{2}, …, H_{m} be a sequence of affine hyperplanes in R^{n}. For each i, let H_{i}^{+} and H_{i}^{−} be the two closed half-spaces in R^{n} determined by H_{i}. In terms of the original formulation of the problem, the hyperplane H_{i} has equation f(x) = ρ_{i}(x), and H_{i}^{+} = {x ∈ R^{n} : f(x) ≤ ρ_{i}(x)}. If a point x is selected uniformly at random from the polytope P, what is the probability that x lies in P ∩ H_{i−1}^{−} ∩ H_{i}^{+}?

Since the selection of x is done uniformly at random, this geometric probability can be expressed in terms of the (n-dimensional) volume of the region P ∩ H_{i−1}^{−} ∩ 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 x uniformly at random corresponds to the selection of x_{1}, x_{2}, …, 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 x = (x_{1}, x_{2}, …, x_{n}) as above, first reorder its coordinates in weakly increasing order, and then apply the functions f and ρ_{i} to the increasingly ordered n-tuple x^{≤} ∈ R^{n} thus obtained. Clearly, x^{≤} lies in the n-dimensional simplex Δ^{n} : = {(x_{1}, x_{2}, …, x_{n}) ∈ R^{n} : 0 ≤ x_{1} ≤ x_{2} ≤ … ≤ x_{n} ≤ 1}. If the selection is according to the uniform distribution, then the desired probability can be obtained by selecting x uniformly directly from the simplex Δ^{n}. This leads to the question of finding the volumes of the regions into which the simplex Δ^{n} is divided by a family of hyperplanes.

The specific problems described here pertain to the cube [0, 1]^{n} and the simplex Δ^{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} ∩ H_{i} or Δ^{n} ∩ H_{i} turn out to have closely related expressions as well.

As an initial example, consider the simplex Δ^{n} and the functions f(x) = 0, ρ_{0}(x) = −α, and ρ_{i}(x) = x_{i} −α, for some real number α ∈ (0, 1) and 1 ≤ i ≤ n. If x is chosen uniformly at random from Δ^{n}, then the probability Pr[ρ_{i−1}(x) ≤ f(x) ≤ ρ_{i}(x)] equals Pr[x_{i−1} ≤ α ≤ x_{i}] (where x_{0} = 0). The values of the first i−1 coordinates, selected from [0, 1], are all from [0, α] with probability α^{i−1}. Similarly, the values of the ith through nth coordinates are from [α, 1] with probability (1 − α)^{n−i+1}. Finally, upon ordering the coordinates in increasing order, we obtain the probability \frac{n!}{(i−1)!(n−i+1)!}α^{i−1}(1 − α)^{n−i+1}. Equivalently, the hyperplanes H_{i} with equations x_{i} = α, for 1 ≤ i ≤ n, dissect Δ^{n} into n + 1 regions with volumes given by V^{(n)}(R_{i}^{(n)}) = \frac{1}{n!} \binom{n}{i−1}α^{i−1}(1 − α)^{n−i+1}, for 1 ≤ i ≤ n + 1. When α = \frac{1}{2}, the volumes have especially simple expressions proportional to binomial coefficients: V^{(n)}(R_{i}^{(n)}) = \frac{1}{n!2^{n}} \binom{n}{i−1}. (This corresponds to the case of a fair coin if the problem is phrased in terms of tossing a coin having probability α for heads.) The sections S_{i}^{(n)}: = Δ^{n} ∩ H_{i} have (n − 1)-dimensional volumes proportional to binomial coefficients as well (for a given i, we have x_{i} = α, and the probability that x_{1}, …, x_{i−1} ≤ α and x_{i+1}, …, x_{n} ≥ α can be computed similarly to the previous calculation).

The preceding example involves a pencil of n hyperplanes passing through the point (α, α, …, α) ∈ R^{n}, which are parallel to the coordinate hyperplanes, and the volumes of the resulting regions and sections of Δ^{n} involve binomial coefficients. In Section 2 we consider the simplex and a different pencil of n hyperplanes passing through (\frac{1}{2}, \frac{1}{2}, …, \frac{1}{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.

1. Eulerian numbers and the simplex

Suppose that a point x is selected uniformly at random from the simplex Δ^{n} = {x = (x_{1}, x_{2}, …, x_{n}) ∈ R^{n} : 0 ≤ x_{1} ≤ x_{2} ≤ … ≤ x_{n} ≤ 1}. What is the probability that the average of 0, 1, and the coordinates of x falls between the (i − 1)st and ith coordinates of x? Note that Pr[x_{i−1} < \frac{x_{1}+...+x_{n+2}}{n+2} ≤ x_{i}] with x selected from Δ^{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(x) = \frac{x_{1}+x_{2}+...+x_{n}+1}{n+2}, ρ_{0}(x) = 0, and ρ_{i}(x) = x_{i} for i = 1, 2, …, n. Thus, we consider the hyperplanes H_{i} ⊂ R^{n} with equations

x_{1} + x_{2} + … + x_{n} + 1 = (n + 2)x_{i},

for i = 1, 2, …, n. These form a pencil of hyperplanes through the point (\frac{1}{2}, \frac{1}{2}, …, \frac{1}{2}) ∈ R^{n}, and they determine n + 1 regions, R_{1}^{(n)}, R_{2}^{(n)}, …, R_{n+1}^{(n)} in the simplex Δ^{n}: R_{1}^{(n)} = {x ∈ Δ^{n} : ∑_{k=1}^{n} x_{k} +1 ≤ (n+2)x_{1}}, R_{i}^{(n)} = {x ∈ Δ^{n} : (n+2)x_{i−1} ≤ ∑_{k=1}^{n} x_{k} +1 ≤ (n + 2)x_{i}} for 2 ≤ i ≤ n, and R_{n+1}^{(n)} = {x ∈ Δ^{n} : (n + 2)x_{n} ≤ ∑_{k=1}^{n} x_{k} + 1}. The question of finding

Pr[x_{i−1} < \frac{0 + x_{1} + x_{2} + … + x_{n} + 1}{n + 2} ≤ x_{i}]

is answered then by determining the sequence of volumes (V^{(n)}(R_{i}^{(n)}))_{i=1}^{n+1} of these regions.

For example, in dimensions n = 1, 2, 3, the volumes of the regions are:

( V^{(1)}(R_{1}^{(1)}), V^{(1)}(R_{2}^{(1)}) ) = (\frac{1}{2}, \frac{1}{2}),

( V^{(2)}(R_{1}^{(2)}), V^{(2)}(R_{2}^{(2)}), V^{(2)}(R_{3}^{(2)}) ) = (\frac{1}{12}, \frac{4}{12}, \frac{1}{12}),

( V^{(3)}(R_{1}^{(3)}), V^{(3)}(R_{2}^{(3)}), V^{(3)}(R_{3}^{(3)}), V^{(3)}(R_{4}^{(3)}) ) = (\frac{1}{144}, \frac{11}{144}, \frac{11}{144}, \frac{1}{144}). These low-dimensional cases suggest that the volumes are proportional to the Eulerian numbers (see, e.g., [Co], [St1]). A permutation σ ∈ S_{n} has a descent in position i (where 1 ≤ i ≤ n − 1) if σ(i) > σ(i + 1), and the Eulerian numbers count permutations according to their number of descents.

Theorem 1.1.

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 ∑_{k=1}^{n} x_{k} +1 = (n + 2)x_{i}, for 1 ≤ i ≤ n, dissect the simplex Δ^{n} into regions R_{i}^{(n)} whose volumes are given by

V^{(n)}(R_{i}^{(n)}) = \frac{A(n + 1, i − 1)}{n!(n + 1)!},

and the (n − 1)-dimensional volumes of the sections S_{i}^{(n)} = Δ^{n} ∩ H_{i} for 1 ≤ i ≤ n are given by

V^{(n−1)}(S_{i}^{(n)}) = c(n) · \frac{A(n, i − 1)}{(n − 1)!n!},

where c(n) = \sqrt{n^{2} + 3n}/(n + 1).

For ease of exposition, we postpone the proof of the theorem until after three preliminary results.

Lemma 1.2.

For each i = 1, 2, …, n, the section S_{i}^{(n)} has i(n − i + 1) vertices x whose coordinates are

x_{1} = x_{2} = … = x_{s} = 0,

x_{s+1} = … = x_{i} = … = x_{r} = \frac{n − r + 1}{n − r + s + 2},

x_{r+1} = … = x_{n} = 1,

where 0 ≤ s < i ≤ r ≤ n. In particular, the point (\frac{1}{2}, \frac{1}{2}, …, \frac{1}{2}) belongs in the intersection of Δ^{n} with every hyperplane H_{i}.

Proof. The vertices of Δ^{n} have coordinates of the form (0, 0, …, 0, 1, 1, …, 1), with the number of 0’s ranging between zero and n. Hence, an edge of Δ^{n} consists of points having a certain number, s ≥ 0, of initial coordinates equal to 0, followed by a number, r − s ≥ 0, of equal coordinates whose common value lies in (0, 1), followed in turn by n−r ≥ 0 coordinates equal to 1. To determine such a point x which lies in H_{i}, observe that if x_{r+1} = … = x_{n} = 1 for some r +1 ≤ i, then the equation of H_{i} requires s·0+(r −s)x_{r} +(n−r)·1+1 = (n+2)·1, implying x_{r} = \frac{r+1}{r−s} > 1. Since such a point x is not in Δ^{n}, we must have i ≤ r.

Similarly, if s ≥ i, then the equation of H_{i} requires (r −s)x_{r} +(n−r)·1+1 = 0, implying that x_{r} < 0, so again x ∉ Δ^{n}.

Therefore we must have 0 ≤ s < i ≤ r ≤ n, and it follows from the equation of H_{i} that x_{s+1} = … = x_{r} = \frac{n−r+1}{n−r+s+2}, and x ∈ Δ^{n} ∩ H_{i}.

In the sequel, we will write H_{i}^{(d)} to indicate the dimension d of the ambient Euclidean space in which we view the hyperplane H_{i}.

Lemma 1.3.

For each i such that 1 ≤ i ≤ n, the region R_{i}^{(n−1)} of Δ^{n−1} is a projection of the section S_{i}^{(n)} of Δ^{n}.

Proof. First, we describe the vertices of R_{i}^{(n−1)} when i satisfies 2 ≤ i ≤ n − 1. These vertices fall into three classes: those of the section S_{i}^{(n−1)}, those of the section S_{i−1}^{(n−1)}, and vertices of Δ^{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 Δ^{n−1} ∩ H_{i}^{(n−1)} ∩ H_{i−1}^{(n−1)}. There are (i − 1)(n − i) vertices in this intersection, namely, for each choice of s, r such that 0 ≤ s < i − 1 < i ≤ r ≤ n − 1, we obtain a vertex x ∈ Δ^{n−1} ∩ H_{i}^{(n−1)} ∩ H_{i−1}^{(n−1)} whose coordinates are x_{1} = x_{2} = … = x_{s} = 0, x_{s+1} = … = x_{i−1} = x_{i} = … = x_{r} = \frac{n−r}{n−r+s+1}, x_{r+1} = … = x_{n−1} = 1.

Only one vertex of Δ^{n−1} appears in R_{i}^{(n−1)}. This is the vertex whose coordinates are x_{1} = x_{2} = … = x_{i−1} = 0, x_{i} = x_{i+1} = … = x_{n−1} = 1, and we denote it by v_{i}^{(n−1)}.

In particular, for 2 ≤ i ≤ n − 1, the total number of vertices of R_{i}^{(n−1)} 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_{i}^{(n)}.

The regions R_{1}^{(n−1)} and R_{n}^{(n−1)} are (n − 1)-dimensional simplices. Indeed, the vertices of R_{1}^{(n−1)} are v_{1}^{(n−1)} = (1, 1, …, 1) and the n − 1 vertices of S_{1}^{(n−1)} as in Lemma 1.2. Similarly, R_{n}^{(n−1)} has n affinely independent vertices (the origin v_{n}^{(n−1)} = (0, 0, …, 0) and the n − 1 vertices of S_{n−1}^{(n−1)}).

By comparing the above description of the vertices of R_{i}^{(n−1)} with the earlier description of the vertices of S_{i}^{(n)} (Lemma 1.2), we see that the projection (x_{1}, x_{2}, …, x_{n}) → (x_{1}, …, x_{i−1}, x_{i+1}, …, x_{n}) is a bijection between the vertices of S_{i}^{(n)} and R_{i}^{(n−1)}, which maps S_{i}^{(n)} onto R_{i}^{(n−1)}.

Corollary 1.4.

The (n − 1)-dimensional volumes of S_{i}^{(n)} and R_{i}^{(n−1)} are related by

V^{(n−1)}(S_{i}^{(n)}) = \frac{\sqrt{n^{2} + 3n}}{n + 1} · V^{(n−1)}(R_{i}^{(n−1)}).

Proof. Since the hyperplane H_{i}^{(n)} containing S_{i}^{(n)} has unit normal vector N_{i}^{(n)} = \frac{(1,1,...,1,−(n+1),1,...,1)}{\sqrt{n^{2}+3n}} (the non-unit coordinate is the i^{th} one), the desired relation follows from Lemma 1.3.

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_{2}^{(1)} are segments of length \frac{1}{2}.

Consider n ≥ 2. For i = 2, 3, …, n, the region R_{i}^{(n)} is the union of two pyramids with apex v_{i}^{(n)} = (0, …, 0, 1, …, 1) (the first unit coordinate is the i^{th} one). One pyramid is pyr(v_{i}^{(n)}, S_{i}^{(n)}) over the section S_{i}^{(n)} and the other is pyr(v_{i}^{(n)}, S_{i−1}^{(n)}) over the section S_{i−1}^{(n)}. Their intersection is the (n − 1)-dimensional pyramid with apex v_{i}^{(n)} over the (n − 2)-dimensional intersection of S_{i}^{(n)} and S_{i−1}^{(n)}. The distance d_{i} from v_{i}^{(n)} to H_{i}^{(n)} is easily calculated as

\frac{| − 1 − (N_{i}^{(n)}, v_{i}^{(n)})|}{||N_{i}^{(n)}||,}

and is equal to

d_{i} = \frac{i}{\sqrt{n^{2} + 3n}}.

Similarly, the distance d_{i−1} between v_{i}^{(n)} and H_{i−1}^{(n)} is

d_{i−1} = \frac{n − i + 2}{\sqrt{n^{2} + 3n}}.

Together with Corollary 1.4, this implies that for 2 ≤ i ≤ n,

V^{(n)}(R_{i}^{(n)}) = \frac{1}{n} · d_{i} · V^{(n−1)}(S_{i}^{(n)}) + \frac{1}{n} · d_{i−1} · V^{(n−1)}(S_{i−1}^{(n)})

= \frac{1}{n(n + 1)}[i · V^{(n−1)}(R_{i}^{(n−1)}) + (n − i + 2) · V^{(n−1)}(R_{i−1}^{(n−1)})].

By induction, we obtain

V^{(n)}(R_{i}^{(n)}) = \frac{1}{n!(n + 1)!}[iA(n, i − 1) + (n − i + 2)A(n, i − 2)]

= \frac{1}{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_{1}^{(n)} can be computed directly via a determinant evaluation or, using the notation established above,

V^{(n)}(R_{1}^{(n)}) = \frac{1}{n} · d_{1} · V^{(n−1)}(S_{1}^{(n)}),

in which we have d_{1} = \frac{1}{\sqrt{n^{2}+3n}} and, by Corollary 1.4, V^{(n−1)}(S_{1}^{(n)}) = \frac{\sqrt{n^{2}+3n}}{n+1}V^{(n−1)}(R_{1}^{(n−1)}). Again, inductively we have V^{(n−1)}(R_{1}^{(n−1)}) = \frac{A(n,0)}{(n−1)!n!} = \frac{1}{(n−1)!n!}, and it follows that V^{(n)}(R_{1}^{(n)}) = \frac{A(n+1,0)}{n!(n+1)!}. We omit the calculation of V^{(n)}(R_{n+1}^{(n)}) which follows through a similar direct computation, or simply by symmetry.

Using Theorem 1.1 we derive an expression for the partial sums of the Eulerian numbers. As before, let x = (x_{1}, …, x_{n}) denote a random point in the simplex Δ^{n}. Successive differences x_{j} − x_{j−1} are called spacings. We may model the spacings as follows (see [Py]): x_{j} −x_{j−1} = \frac{y_{j}}{y_{1}+y_{2}+...+y_{n+1}} , for 1 ≤ j ≤ 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 ≤ j ≤ n:

Pr[\frac{x_{1} + x_{2} + … + x_{n} + 1}{n + 2} ≤ x_{j}]

= Pr[(n − j + 1)y_{j+1} + … + 3y_{n−1} + 2y_{n} + y_{n+1} ≤ y_{1} + 2y_{2} + 3y_{3} + … + jy_{j}]. (∗)

Each y_{j} has probability density function (p.d.f.)

g(t) = \{ \begin{matrix}e^{−t} & if t ≥ 0, \\ 0 & if t < 0. \end{matrix}

For distinct, positive values c_{j} (1 ≤ j ≤ k), the p.d.f. for Y = c_{1}y_{1} + c_{2}y_{2} + … + c_{k}y_{k} is (see [JK], p.222)

g_{Y} (t) = ∑_{i=1}^{k} \frac{c_{i}^{k−2}}{∏_{j≠i} (c_{i} − c_{j})}e^{−t/c_{i}}, for t ≥ 0.

Let Y_{1} = (n − j + 1)y_{j+1} + … + 3y_{n−1} + 2y_{n} + y_{n+1} and Y_{2} = y_{1} + 2y_{2} + 3y_{3} + … + jy_{j}. With this notation, (∗) is given by

∫_{0}^{∞} g_{Y_{2}}(t) dt ∫_{0}^{t} g_{Y_{1}}(s) ds,

where

g_{Y_{1}}(s) = ∑_{a=1}^{n−j+1} \frac{(−1)^{n+j+1−a}a^{n−j−1}}{(a − 1)!(n − j + 1 − a)!}e^{−s/a}

and

g_{Y_{2}}(t) = ∑_{i=1}^{j} \frac{(−1)^{j−i}i^{j−2}}{(i − 1)!(j − i)!}e^{−t/i}.

Performing the integration gives

Pr[\frac{x_{1} + x_{2} + … + x_{n} + 1}{n + 2} ≤ x_{j}] = ∑_{i=1}^{j} ∑_{a=1}^{n−j+1} \frac{(−1)^{n+1−i+a}a^{n−j}i^{j}}{(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:

∑_{k=0}^{j−1} A(n + 1, k) = (n + 1)n\binom{n − 1}{j − 1} ∑_{i=1}^{j} ∑_{a=1}^{n−j+1} \frac{(−1)^{n+1−i−a}}{i + a} \binom{j − 1}{i − 1}\binom{n − j}{a − 1}a^{n−j}i^{j},

for 1 ≤ j ≤ n.

2. Eulerian numbers and the cube

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(x) = x_{1} + x_{2} + … + x_{n}, ρ_{0}(x) = 0 and ρ_{i}(x) = i for 1 ≤ i ≤ n − 1. Thus, this problem concerns the volumes of the n regions of [0, 1]^{n} determined by the n − 1 hyperplanes H_{i} : x_{1} + x_{2} + … + x_{n} = i, for 1 ≤ i ≤ n − 1. We denote the regions as R_{i}^{(n)} = {x ∈ [0, 1]^{n} : i − 1 ≤ ∑_{k=1}^{n} x_{k} ≤ i}, for 1 ≤ i ≤ 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_{i}^{(n)}) = \frac{1}{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_{i}^{(n)}) suggests that (up to a set of measure zero) the region R_{i}^{(n)} may be partitioned by the images, under a measure-preserving transformation, of A(n, i − 1) n-dimensional simplices, each of volume \frac{1}{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 φ 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 ≤ i < j ≤ n, into n! simplices, each having volume \frac{1}{n!}. For each such simplex, there exists a permutation σ ∈ S_{n} which permutes in increasing order the coordinates of every point in the interior of the simplex. Denote the simplex by Δ_{σ}. Now, the desired map φ on [0, 1]^{n} less the measure zero set of points having any equal consecutive coordinates, is defined by φ(x) = y ∈ [0, 1]^{n}, where

y_{n} = 1 − x_{n},

and

y_{i} = \{ \begin{matrix}x_{i+1} − x_{i} & if x_{i} < x_{i+1}, \\ 1 + x_{i+1} − x_{i} & if x_{i} > x_{i+1}, \end{matrix}

for i = 1, 2, …, n − 1. Note that if x ∈ Δ_{σ}, then f(y) = ∑_{k=1}^{n} y_{k} = des(σ) + 1 − x_{1}, where des(σ) denotes as usual the number of descents of σ. Thus, φ(Δ_{σ}) ⊂ R_{des(σ)+1}^{(n)}. Note also that φ 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, …, n − 1, and that the determinant of the transformation is equal to (−1)^{n}. Therefore φ is measure-preserving. The inverse of φ is defined on [0, 1]^{n} less the set of measure zero {y ∈ [0, 1]^{n} : ∑_{k=i}^{n} y_{k} ∈ Z, for some i}, and is given by φ^{−1}(y) = x, where x_{i} = 1 + ⌊∑_{k=i}^{n} y_{k}⌋ − ∑_{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(x) = x_{1} + x_{2} + … + x_{n}, and ρ_{0}(x) = 0, and consider the functions ρ_{i}(x) = i − \frac{1}{2}, for 1 ≤ i ≤ n. These give rise to n parallel hyperplanes, H_{i} : x_{1} + x_{2} + … + x_{n} = i − \frac{1}{2}, for 1 ≤ i ≤ 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_{i+1}^{(n)} = \{x ∈ [0, 1]^{n} : i − \frac{1}{2} ≤ ∑_{k=1}^{n} x_{k} ≤ i + \frac{1}{2}\}, for 0 ≤ i ≤ n.

Proposition 2.1. ([ChLo])

For i = 0, 1, …, n, let S(i, n − i) = 2^{n}n!V^{(n)}(R_{i+1}^{(n)}). 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.

It turns out that this recurrence implies that the volumes are proportional to the Eulerian numbers for signed permutations. A signed permutation on n letters is a permutation of {1, 2, …, 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 descent for signed permutations is based on the linear ordering 1 < 2 < … < n < \overline{n} < \overline{n − 1} < … < \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 ≤ i ≤ 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.

Corollary 2.2.

Let \overline{A}(n, m) denote the Eulerian numbers for the hyperoctahedral group on n letters. Then the hyperplanes with equations ∑_{k=1}^{n} x_{k} = i − \frac{1}{2}, for 1 ≤ i ≤ n, dissect the unit cube [0, 1]^{n} into regions R_{i}^{(n)} whose volumes are given by

V^{(n)}(R_{i}^{(n)}) = \frac{\overline{A}(n, i − 1)}{2^{n}n!}, 1 ≤ i ≤ n + 1.

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 ≤ i ≤ 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{τ} on \{2, 3, …, n\}. Clearly, if 1 is inserted into \overline{τ}, then it will be the absolute minimum of the resulting signed permutation, while if \overline{1} is inserted into \overline{τ}, then it will be the absolute maximum. Therefore, if des(\overline{τ}) = 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{τ}; (ii) insert 1 at the front of \overline{τ}. This gives the first term on the right-hand-side. The second term is obtained similarly: if des(\overline{τ}) = 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{τ}; (ii) insert 1 at the front of \overline{τ}. The initial conditions are obvious and the desired conclusion follows.

Next, observe that the hyperplanes x_{i} = \frac{1}{2}, x_{i} = x_{j}, and x_{i} + x_{j} = 1 for 1 ≤ i, j ≤ n dissect the cube [0, 1]^{n} into 2^{n}n! simplices, each of volume \frac{1}{2^{n}n!}. Now let x be any point from the interior of such a simplex. Let x′ = (x′_{1}, x′_{2}, …, x′_{n}), where

x′_{i} = \{ \begin{matrix}x_{i} & if x_{i} < 1/2, \\ 1 − x_{i} & if x_{i} > 1/2. \end{matrix}

Clearly, x′ has distinct coordinates. Let σ be the (ordinary) permutation which orders the coordinates of x′ increasingly. Finally, we obtain a signed permutation \overline{σ} by placing a bar over σ(i) if x_{i} > \frac{1}{2}. For example, if x = (0.4, 0.8) ∈ [0, 1]^{2}, then x′ = (0.4, 0.2), leading to σ(1)σ(2) = 21 and, finally, to \overline{σ} = 2\overline{1}. All points from the interior of a simplex give rise to the same signed permutation, and we denote by Δ\overline{σ} the simplex corresponding to \overline{σ}. An adaptation of the map found by Stanley for the previous problem plays the analogous role here, mapping the simplex Δ\overline{σ} to the region R_{des(\overline{σ})+1}^{(n)}.

Proposition 2.3.

The map \overline{φ} given by \overline{φ}(x) = y where

y_{n} = \{ \begin{matrix}1/2 − x_{n} & if x_{n} < 1/2, \\ 3/2 − x_{n} & if x_{n} > 1/2, \end{matrix}

and, for i = 1, 2, …, n − 1,

y_{i} = \{ \begin{matrix}x_{i+1} − x_{i} & if x_{i} < x_{i+1}, \\ 1 + x_{i+1} − x_{i} & if x_{i} > x_{i+1}, \end{matrix}

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, …, n, the region R_{j+1}^{(n)} of [0, 1]^{n} is partitioned, up to a set of measure zero, by the images of the interiors of the simplices Δ\overline{σ} for those signed permutations satisfying des(\overline{σ}) = j.

Proof. The former part of the conclusion follows from arguments as in [St2]. For the latter part, using the description of x′, it is easy to check that the second case in the definition of y_{i}, for all 1 ≤ i ≤ n, corresponds precisely to a descent in position i for the signed permutation \overline{σ} corresponding to x. Thus, ∑_{k=1}^{n} y_{k} = des(\overline{σ}) + \frac{1}{2} − x_{1} lies in the interval (des(\overline{σ}) − \frac{1}{2}, des(\overline{σ}) + \frac{1}{2}), and \overline{φ} maps each Δ\overline{σ} as claimed.

3. Remarks and open questions.

a) For dimensions n = 1, 2, 3, the sections S_{i}^{(n)} 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_{i}^{(n)} from Section 1 is, informally put, a “folded”

(n − 1)-dimensional simplex, with the folds occurring along the intersections S_{i}^{(n)} ∩ S_{i+1}^{(n)}, for 1 ≤ i ≤ 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 ρ_{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?

Acknowledgment The authors thank the anonymous referee for the careful reading of the manuscript.

References

[ChLo] D. Chakerian and D. Logothetti, Cube slices, pictorial triangles, and probability, Math. Mag. 64 (1991) 219-241.

[Co] L. Comtet, “Advanced Combinatorics,” D. Reidel, Dordrecht, 1974.

[E] E. Ehrhart, “Polynômes Arithmétiques et Méthode des Polyèdres en Combinatoire,” Birkhäuser, Basel and Stuttgart, 1977.

[Fo] D. Foata, Distributions eulériennes 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.

[Hi] T. Hibi, “Algebraic Combinatorics on Convex Polytopes,” Carslaw Publications, Glebe, Australia, 1992.

[JK] N. Johnson and S. Kotz, “Continuous Univariate Distributions - 1,” Houghton-Mifflin, Boston, 1970.

[Lag] J. Lagarias, Point lattices, in “Handbook of Combinatorics” (R. Graham, M. Grötschel and L. Lovász, eds.), MIT Press, Cambridge, 1995, p. 919-966.

[Lap] Marquis de Laplace, “Oeuvres complètes,” vol. 7, 1820; reprinted by Gauthiers-Villars, Paris, 1886, p. 257 ff.

[Py] R. Pyke, Spacings, Royal Stat. Soc. (B) 27 (1965) 395-436.

[St1] R. Stanley, “Enumerative Combinatorics,” vol. 1, Wadsworth & Brooks/Cole, Monterey, 1986; second edition, Cambridge Univ. Press, to appear.

[St2] R. Stanley, 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.