[Math] How many tetrahedrons in a tetrahedron

Question

Given a regular tetrahedron. All the edges were divided into N equal segments. How many non-degenerate ($|\text{volume}| > 0$) tetrahedrons with vertices at the points of division can be built inside this tetrahedron? Vertex of given tetrahedron can't be the point of division.

I'm looking for a formula.

Examples:
For $N=2$, answer is $12$.
For $N=37$, answer is $65561472$.

Answer 1

This is the partial result I have.

Let $m = N-1$, the number of non-degenerate tetrahedron $\mathcal{N}_N$ is given by:

$$\begin{align} \mathcal{N}_N &= 3\binom{m}{2}^2 + 48\binom{m}{2}m^2 + 15m^4 - 3\mathcal{O}_N\\ &= \frac34 m^2 (53m^2 - 34 m + 1) -3\mathcal{O}_N \end{align}$$ where $\mathcal{O}_N$ is something which I didn't have a close form expression.

$\mathcal{O}_N$ is the number of degenerate tetrahedra where the four vertices are taken from two pairs of opposite edges of original tetrahedron. The factor $3$ before $\mathcal{O}_N$ is there because there are 3 possible choices for the two pairs. It can be shown that $\mathcal{O}_N$ is the number of solutions for the following equation: $$\frac{u}{N-u}\frac{z}{N-z} = \frac{v}{N-v}\frac{w}{N-w}$$ where $u, v, w, z \in \{1,\ldots,m\}$. $\mathcal{O}_N$ is something of order $O(3N^2)$ and can be computed with following algorithm in $O(N^2 \log N)$ steps.

histogram = {};  
for( u = 1; u < N; u++){    
    U = u/(N-u);    
    for( z = 1; z < N; z++){
        Z = z/(N-z);
        histogram{U*Z}++;    
    } 
} 
number_degen = 0;
foreach fraction in histogram {
    number_degen += histogram{fraction}^2;
}
return number_degen;

For example, when $N = 37$, $\mathcal{O}_N = 4836$ and $\mathcal{N}_N = 65575980 - 3*4836 = 65561472$.

EDIT

Let me explain the logic behind the algorithm and why its complexity is $O(N^2 \log N)$.

Consider a simpler example where $f$ is a function which sends $1, 2, 3, 4, 5$ to $0, 0, 1, 1, 1$ respectively. To count the number of solutions for $f(x) = f(y)$, you don't need to loop over $x$ and $y$ twice. Instead, you loop over $x$ once to find $f(x) = 0$ twice and $f(x) = 1$ three times.

For $f(x) = f(y) = 0$, $(x, y)$ can be any one of the $2^2$ combinations: $$(1,1), (1,2), (2,1), (2,2)$$ For $f(x) = f(y) = 1$, $(x, y)$ can be any one of the $3^2$ combinations: $$(3,3), (3,4), (3,5), (4,3), (4,4), (4,5), (5,3), (5,4), (5,5)$$

So there are $13 = 2^2 + 3^2$ solution for this simpler problem. The key is once the histogram of the range of $f$ is known. One can compute the total number of solutions by summing the square of the counts.

If one apply this to count the solutions for $$\frac{u}{N-u}\frac{z}{N-z} = \frac{v}{N-v}\frac{w}{N-w}$$ you can construct the histogram in $O(N^2)$ steps.

On the surface, the complexity of the algorithm is $O(N^2)$ instead of $O(N^2\log N)$. But the truth is the possible values of fractions are not that uniform and not that direct to represent in computer. One need to use some higher-level data structure to hold the histogram for fast access and manipulation.

I use an associated hash in Perl to do the dirty work. In other language, you may need to implement the data structure yourself. In the worst case, you can always implement the histogram using a binary tree. During the lifetime of the loop, the histogram will be holding the counts of $O(N^2)$ fraction. So each access/modification of the binary tree itself contribute a $O(\log(N^2))$ factor. The final complexity is $\sum_{O(N^2)} O(\log N) \sim O( N^2 \log N)$.

EDIT2

For people requesting actual code, a Perl implementation is given below.

use Math::BigRat;
my $N   = 37;
my %histogram = ();
for( my $u = 1; $u < $N; $u++ ){
    my $fU = Math::BigRat->new(sprintf('%d/%d',$u,$N-$u));
    for( my $z = 1; $z < $N; $z++ ){
        my $fZ = Math::BigRat->new(sprintf('%d/%d',$z,$N-$z));
        $histogram{ ($fU*$fZ)->bstr() }++;
    }
}
my $number_degen = 0;
foreach my $count (values %histogram){
    $number_degen += $count*$count;
}
printf "number_degen = %d\n", $number_degen;