Volumes and Permutations

The factorial function n! = n \cdot (n-1) \ldots 3 \cdot 2 \cdot 1 is traditionally introduced as the number of permutations of n items.

It also crops up as the reciprocal of the n-dimensional volume of the n-dimensional simplex defined by

x_1 \textgreater 0, x_2 \textgreater 0, \ldots x_n \textgreater 0, x_1 + x_2 + \ldots + x_n \textless 1

There’s a routine proof by induction that the volume of an n-simplex is 1/n!, but it leaves the connection with the number of permutations of n items a little mysterious.

Here’s one way to see why they’re related.

Start by considering the n-dimensional cube of volume one, namely

0 \textless x_1 \textless 1 , 0 \textless x_2 \textless 1 , \ldots , 0  \textless x_n  \textless  1

Now consider the subset

0  \textless  x_1  \textless x_2  \textless  \ldots  \textless x_n  \textless  1

It has volume 1/n!.

This is because there are n! subsets of the form 0 \textless x_{i_1} \textless x_{i_2} \textless \ldots \textless x_{i_n} \textless 1 where ( i_1 , i_2 , \ldots , i_n) is a permutation of ( 1 , 2, \ldots , n). They all have the same volume (permuting axes doesn’t change volume). And, finally, their disjoint union is the hypercube (modulo subsets of the hyperplanes x_i = x_j where i \ne j, which doesn’t change anything because they have zero volume)

All that’s left is to show that the above subset of the hypercube has the same volume as the n-simplex. One way to do that is to find a volume preserving linear transformation (i.e. with determinant one) that changes one to the other. And there is such a transformation, namely:
x_1\prime = x_1
x_2\prime = x_1 + x_2
\ldots
x_n\prime = x_1 + x_2 + \ldots + x_n

Author: Walter Vannini

Hi, I'm Walter Vannini. I'm a computer programmer and I'm based in the San Francisco Bay Area. Before I wrote software, I was a mathematics professor. I think about math, computer science, and related fields all the time, and this blog is one of my outlets. I can be reached via walterv at gbbservices dot com.