1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Is this a bound? from which side? $\endgroup$ – Fedor Petrov May 27 '18 at 6:15
  • $\begingroup$ Yes, it is bounded by the coordinate planes and the axes as well. $\endgroup$ – Shivin Srivastava May 27 '18 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$ – Brendan McKay May 27 '18 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$ – Shivin Srivastava May 27 '18 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$ – Max Alekseyev May 27 '18 at 8:35
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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