Number of distinct points in an n-dimensional tetrahedron

Question

Consider an n-dimensional tetrahedron with $n+1$ vertices $\langle v_0, v_1, \dots,v_n\rangle$. $v_0$ is the origin while $v_i$ lies on $e_i$ (the $i^{th}$ coordinate axis) at a distance $D$ from the origin ie. $v_i = De_i$.

I want to find the set $S$ of all distinct points which lie inside and on the surface of the above tetrahedron such that no point in $S$ is a permutation of any other point.

A distinct point is defined as:-

• $(p_1, p_2, ..., p_n)$ such that $p_i \neq p_j$ for any $1 \leq i,j\leq n$ and $0\leq p_1 \leq n$ ie. no repetitions. All elements are distinct.

In one line both the conditions enforce this inequality $p_1<p_2<...<p_n$.

My first solution is $\frac{D^n}{n!} \times \frac{1}{n!}$. The first term is the volume of the tetrahedron while the second term is to remove circular duplicates. Is this right?

Does there exist a tighter bound?

[EDIT 1]: The above solution will give a lower bound as it just calculates the points inside the tetrahedron and not those which lie on the surface.

To include those points we need to either sum up the volume of all the faces (ie. all lower dimensional faces like line segments and number of points).

The other option is to shift $v_0$ from origin to the point $(1,1,...,1)$ and find a new tetrahedron which encloses the old one completely.

The new equation of the tetrahedron is

$(x_1-1)+(x_2-1)+...(x_n-1) = D$ ie. $x_1+x_2+...+x_n = D + n$

Now we can approximate the number of points within the enveloping tetrahedron. This will include all the boundary points of the inner one also.

The new tetrahedron must have intercept $>D+n$. So we can take it to be $D+n+1$ and the number of points within the enclosed tetrahedron are now bounded by $\frac{(D+n+1)^n}{n!}$

Problem 2: Having found the upper bound on the number of points, the second problem is to find those which satisfy the distinct point property. I can presently think only of removing permutations by dividing by $k!$.

How to proceed?

Thanks for help!

Answer 1

You wish to count solutions to $p_1+\dotsb + p_n \leq D$, under the condition that $0 \leq p_i<p_{i+1}$. This is the same as counting solutions to $$ (p_1+1-1) + (p_2+1-2) + \dotsb + (p_n+1-n) \leq D -\binom{n}{2} $$ under the condition that $$0\leq p_i < p_{i+1} \Longleftrightarrow (p_i+1-i) \leq (p_{i+1}+1-(i+1))$$ and $p_i \geq 0$. So by letting $u_i = p_i+1-i$, and $D'=D-\binom{n}{2}$ you seek solutions to $$ u_1+\dotsb + u_n \leq D' $$ with $0\leq u_1 \leq \dotsb \leq u_n$.

This is now the same as counting the number of integer partitions $D'$ (and smaller) into at most $n$ parts. This is equivalent to count integer partitions of $D'$ and smaller with parts of size at most $n$.

Let $$ f(x) = \prod_{j=1}^n (1-x^j)^{-1} $$ Then you seek $[x^0]f(x) + [x^1]f(x) + \dotsb + [x^{D'}]f(x)$ where $[x^j]f(x)$ means the coefficient of $x^j$ in $f(x)$.