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!

  • $\begingroup$ Is this a bound? from which side? $\endgroup$ May 27, 2018 at 6:15
  • $\begingroup$ Yes, it is bounded by the coordinate planes and the axes as well. $\endgroup$ May 27, 2018 at 6:46
  • $\begingroup$ Your question is very unclear. I'll guess that you want the number of integer sequences $0\le p_1\lt\cdots\lt p_n$ such that $p_1+\cdots+p_n=D$ — is it right? $\endgroup$ May 27, 2018 at 6:58
  • $\begingroup$ Yes its quite unclear. I have edited it. No I don't want their sum to be exactly equal to $D$. That is the partition problem. This problem is similar but not that exactly. $\endgroup$ May 27, 2018 at 7:51
  • 1
    $\begingroup$ So, do you want to enumerate tuples $(p_1,\dots,p_n)$ with $0\le p_1 < \dots < p_n$ and $p_1 + \dots + p_n \le D$ ? $\endgroup$ May 27, 2018 at 8:35

1 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)$.

  • 1
    $\begingroup$ It's also $$[x^{D'}]\ \frac{f(x)}{1-x}.$$ $\endgroup$ May 27, 2018 at 14:04
  • $\begingroup$ Can you provide an asymptotic bound on this term or maybe the leading term of the power series solution? $\endgroup$ May 28, 2018 at 3:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.