Multi-dimensional triangular numbers (triangular powers?)

[MartinB]

I am trying to write an algorithm in C for calculating the required number of iterations needed for carry out the same task on several different data sets and I've figured out so far that I need to use triangle numbers in order to achieve the result. Finding the way to figure out standard 2D triangle numbers via Google ((N/2)*(N+1)) was easy enough, but unfortunetly, this isn't enough, and it's proving very difficult to find what I need and I'm not good at math. :p

What I need to be able to do is to calculate multi-dimensional triangle numbers, so for example, just like a 2D triangle of 5, you would add the 1D lines together (i.e. 5 + 4 + 3 + 2 + 1 = 15), in a 3D triangle of 5, you would add the 2D triangles together (i.e. 15 + 10 + 6 + 3 + 1 = 35) and for a 4D triangle of 5, you would add the 3D triangles (i.e. 35 + 20 + 10 + 4 + 1 = 70), and so on.

So it's kind of like how you have "n to the power of x" for multi-dimensional square numbers, where x is the number of dimension, only I need to be able to do "n to the triangular power of x" (If that makes any sense).

[Pafnoutios]

This looks like recursion.
If 'T' were our triangle operator, such that 1T1 = 1, 2T1 = 1 + 2 = 3, nT1 = n + n-1 + ... + 1, then nT2 = nT1 + (n-1)T1 + ... + 1T1, nTx = nT(x-1) + (n-1)T(x-1) + ... + 1T(x-1).

You're function would look like:


triangle(int n, int x)
{
int result;
//add error checking to ensure n and x are positive
result = 0;
if(x == 1)
for(int i = 1; i<=n; i++)
result += i;
else //x > 1
for(int i = 1; i<=n; i++)
result += triangle(i, x-1);
return result;
}

<note>I removed the semicolon after the else.</note>

[MartinB]

Cheers,

I'll give that a try... Just before I read your post I managed to figure out a non-recursive method, which works, but I'll try to get yours working as I expect that it would be more efficient than mine. :)

[bwkaz]

If your version works, it may be slightly more efficient than recursion. The overhead of a function call isn't huge, but it can be noticeable.

If the amount of work done in Pafnoutios' function is about equal to the amount of work done in each iteration of your method, and Pafnoutios' function gets called about the same number of times that your loop(s) iterate(s), then your non-recursive method will be slightly faster.

[Pafnoutios]

Yeah, I don't think recursion is ever more efficient than iteration, but can be the way to think through a problem, especially this one. If you were really worried about efficiency, you would create a 2-dimentional array to hold the values of all the previously calculated nTx's, that way you would never have to recalculate the smaller triangular numbers, which would otherwise have been calculated many different times in the recursive calculation of one large triangular number. Assuming we're working in c (because you haven't told us otherwise) the array indices start at 0, so we can define 0Tx=0 and nT0=n. We're even lucky enough that 0T0 is defined (as opposed to 0^0). You'll either have to make your array global (eeeeeek!) or pass down through your recursion a pointer to it (more proper). Don't forget to save the array to a file so it can be reloaded next time you run the program.

[Pafnoutios]

Originally posted by MartinB
Cheers,

I'll give that a try... Just before I read your post I managed to figure out a non-recursive method, which works, but I'll try to get yours working as I expect that it would be more efficient than mine. :)

I can't see this problem any way but recursively. Can you post your non-recursive code so I can see it?

[lagdawg]

All you really need is is a 2 dimensional array for 3d triangles.



i 2D 3D
-------------------------------
1 1 1
2 3 4
3 6 10
4 10 20

i 2D(i-1) + i 3D(i-1) + 2D(i)



So one trip through the array and you can calculate the number needed.

[lagdawg]

so for i = 5 and d = 3 (d is the dimension wanted ie. d= 3 is 3D).


int i = 5;
int d = 3;

int triangle [i+1][d-1];

//initialize array for
for(int x = 0; x < (d-1); x++) {
triangle [1][x] = 1;
}

for(int y = 2; y <= i; y++) {
for(int x = 0; x < (d-1); x++) {
if(x == 0) {
traingle[i][x] = triangle[i-1][x] + i;
} else {
triangle[i][x] = triangle[i-1][x] + triangle[i][x-1];
}
}
}



This requires i * (d-1) steps to complete. I don't think you will get any more efficient with recursion.

[Pafnoutios]

Of course! My array! Just iterate through it! I don't know how I didn't see that.

Originally posted by lagdawg
I don't think you will get any more efficient with recursion.

Of course not. My recursive method with the array would have a bunch of comparisons to see if each value had been calculated yet. That would take much longer than this.

[MartinB]

This was my method - I have three loops going here, which is why I didn't really think that it was very efficient (d is number of dimensions).

long long unsigned int triangulate(int d, int n)
{
int t1, t2, t3;
long long unsigned int triangles[200];
n ++;
for(t1 = 0; t1 < n; t1 ++)
triangles[t1] = 1;
for(t1 = 0; t1 < d; t1 ++)
for(t2 = n; t2 > 0; t2 --)
for(t3 = 0; t3 < t2; t3 ++)
triangles[t2] += triangles[t3];
return triangles[n - 1];
}

[lagdawg]

Actually for 3d array numbers you only need to do i calcluations.



int i = 5;
int 3d = 0;
for(int x = 1; x <= i; x++) {
3d += (x * (x+1))/2;
}



This modification can be implemented in my original piece of code to make the efficiency of the program actually i * (d-2) instead of i * (d-1) I will try and figure something out for the rest of the dimensions as well.


***EDIT****
4D sum of i calculated in i calculations


int i = 5;
int 4d = 0;
for(int x = 1; x <= i; x++) {
4d += (x*(x+1))/2 * (i - x + 1);
}

[Pafnoutios]

Screw calculations.

The d-dimentional triangle of size n equals:

(The product of n+x-1 as x goes from 1 to d) / d! (factorial)
Triangle(int n, int d)
{
int result = 1;
for(int i = 1; i <= d; i++)
result = result * (n + i - 1) / i;
return result;
}

How's that for efficient!

[Pafnoutios]

Here's a table of values.
n\d 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1
2 2 3 4 5 6 7 8 9
3 3 6 10 15 21 28 36 45
4 4 10 20 35 56 84 120 165
5 5 15 35 70 126 210 330 495
6 6 21 56 126 252 462 792 1287
7 7 28 84 210 462 924 1716 3003
8 8 36 120 330 792 1716 3432 6435
9 9 45 165 495 1287 3003 6435 12870
10 10 55 220 715 2002 5005 11440 24310
11 11 66 286 1001 3003 8008 19448 43758
12 12 78 364 1365 4368 12376 31824 75582
13 13 91 455 1820 6188 18564 50388 125970
14 14 105 560 2380 8568 27132 77520 203490
15 15 120 680 3060 11628 38760 116280 319770
16 16 136 816 3876 15504 54264 170544 490314
17 17 153 969 4845 20349 74613 245157 735471

[lagdawg]

(The product of n+x-1 as x goes from 1 to d) / d! (factorial)

Where did you get this formula?



Screw calculations.

You are still performing i calcutions.

I was close to getting this same formula, just hadn't worked out all the details yet. I was trying to find the relationship between my equations for the 3d and 4d solutions.

Good job.

[Pafnoutios]

Originally posted by lagdawg
Where did you get this formula?
Well, to start, the 1-dimentional numbers are trivial, 1, 2, 3, 4, in other words, n.
The 2-dimentional numbers are high school algebra.
The Sum of x as x goes from 1 to n = (n)(n+1)/2
The 3-D numbers are the sum of the 2-D numbers from 1 to n. If you're comfortable working in Sigma notiation and know the sum of x^2 from 1 to n, or have a calculator that can find it, you get (n)(n+1)(n+2)/6.
4-D is (n)(n+1)(n+2)(n+3)/24.
I haven't proved this formula yet. It would be a classic induction problem, just a little more complex than proving a summation formula. I'll work on the proof and present it later.

Originally posted by lagdawg
You are still performing i calcutions.
I only gave code to show the algorithm in case someone didn't understand what I meant by 'The product of ___ as x goes from __ to __'. Once we know the formula we don't need computer program. You are still performing calculations, but the computer doesn't have to.

[lagdawg]

Yes you are correct. I guess once I got out of school for the year I decided to forget everything I knew. I also hate calculus, which is kind of funny since I'm a CS major. Any way that was simple enough I should have been able to figure it out just took a wrong look at it to begin with. Thank you for the insight.

[Pafnoutios]

Here's a proof. It took me a little work to get used to OpenOffice's formula editor. The part where the upperbound on the leftmost product changes from d-1 back to d is the easiest part to get confused at. Look at it for a while and break out a couple small examples so you can see I didn't fudge anything there.