Find an explicit formula for this n-sum problem

[bernd]

TL;DR Summary

Find simplified expression of multiple sums with almost same borders and depending on one given constant. Also nice looking equal-length pyramide if visualized.

Hello,
I am having trouble with deriving an explicit formula (if one exists) for S(a,n) such that for example
$$S(a,5) = \sum_{i5=a}^{49} \sum_{i4=i5}^{49} \sum_{i3=i4}^{49} \sum_{i2=i3}^{49} \sum_{i1=i2}^{49}(1)$$
or
$$S(a,4) = \sum_{i4=a}^{49} \sum_{i3=i4}^{49} \sum_{i2=i3}^{49} \sum_{i1=i2}^{49}(1)$$
so basically a is a given constant and I want a formula for this multi-sum-thingie here where the outermost border goes
a to 49 and each inner border goes from the next outer low border to 49.
well should be obvious what the pattern is if you just compare it.
And yeah, the actual part inside all the sums is literally just a 1. This whole thing comes in parts from a math lottery problem where I can draw 6 numbers from 1-49 (lottery 6 of 49, most popuplar one in germany) and I want to asign order numbers to all potential triples like (3,7,22) and such.

In the end, I would love a direct expression that just contains the number of sums in the expression. and the a which is the low border of the outmost sum.

I know, I can painstakingly try to solve this by hand.
but after simplifying the first 2 innermost sums, I would start to need some formulas for "the sum of the first n numbers ^3,^4,^5,etc.".
which to my knowledge, closed expressions for that exist only for ^2 and ^3 at most.

So I am at a loss here but hope that some smart people hear have some ideas.
On a sidenote try to mentally imagine this picture in the 3d realm:
we place a 1x1x1 unit long block right in the "corner" next to the origin.
3 of this cube's edges touch the 3 coordinate axis.
now along each of the 3 coordinate axis', place another 49-1 blocks in a straight line.
so that you have, including the startiung block, 49 blocks next to each other in eahc of the 3 axis directions.
now fill in blocks so the whole thing is like a 3 equally sided pyramide, tilted in a way so it's top is touching the origin and the 3 edges go along the coordinate axis.
and obviously we are in minecraft so the base of the pyramide due to the blocks sticking out isnt a flat surface but a spiky wasteland.
sorry if my explanation is... bad.

but jsut imagine each.
nyways for this weirdly rotated blocky pyramide the number of blocks in it actually are exactly S(1,3) from above, so the triple sum where the outermost sum goes from a=1 to 49.
if a=5, then the pyramide will have the (top touching) 3 sides of same length=49-5+1=45. so pyramide is simply smaller but same proportions.

if we had n=2 (instead of 3) we would be in 2d instead but the concept would be the same.
same for higher dimensional rooms (at least very likely) but obviously we cant visually imagine it.

but such nice symmetry, there must be some rule to it.

and literally while writing this , the "common denominator" hit me:
say we have a=1, so pyramide lengths=49 and have n=3, so 3d.
say we put a player inside the first (origin touching) block, right in the middle (at coordinates 0.5,0.5,0.5).
and the player can only move away from the origin, one blocks width per step.
a step can be done in any of the 3 directions parallel to the coordinate axis, lets call them up, right,forward.
so the player, by doing 0-48 steps, can reach a bunch of positions. how he gets there doesnt matter.
the total number of possible positions he can reach in a maximum of 48 steps (so including doing 0 steps and therefor also counting the start position), is exactly equal to the number of blocks and therefor also S(1,3).

staying in the 3d world for a=1 and n=3, we are basically asking:
if we write a "step sequence" like (steps up, steps right, steps forward) , how many different configurations can we find where the sum of all steps<=48?
so doing 0 steps: (0,0,0)
doing 1 step: (1,0,0) or (0,1,0) or (0,0,1)
doing 2 steps: ...

add them up and we got an answer for S(1,3).
if we change n from 3 to 4, we talk about 4-tupel instead.
and if a=5 instead of 1, the max step condition changes to
steps<=49-5=44

Now if only we can find some way to calculate the number of n-tuples where the sum of each tuple's components <=49-a, we have won.
cause that's precisely S(a,n).
If I am not completely wrong and this is all utter nonsense so far :-)

 

[jedishrfu]

Why not write a python program to compute it using a recursion function?

Factorials are done that way. fact(5) = 5* fact(4) = 5 * 4 * fact(3)

 

[andrewkirk]

1. You need another parameter for your numbers, which is the 49. So instead write S(a, n, m) where m is the number that goes where your 49s are. So all your formulas are for numbers of type S(a, n, 49)

2. You don't need a, because S(a, n, m) = S(1, n, m - a + 1), so that in your case your formulas will give the same result if you replace 49 by (50 - a) and then replace a by 1. Try it and see!
So we can simplify our notation to S(r, m) where n is still the number of nested summations, r is the upper limit of each summation and 1 goes where a was.

3. Having done that, we can now recognise S(r, n) as the r-th simplicial n-dimensional polytopic number, which you can read all about here.
And yes, it has an explicit formula for each one, which you can read at that link.

 

[bernd]

1. You need another parameter for your numbers, which is the 49. So instead write S(a, n, m) where m is the number that goes where your 49s are. So all your formulas are for numbers of type S(a, n, 49)

2. You don't need a, because S(a, n, m) = S(1, n, m - a + 1), so that in your case your formulas will give the same result if you replace 49 by (50 - a) and then replace a by 1. Try it and see!
So we can simplify our notation to S(r, m) where n is still the number of nested summations, r is the upper limit of each summation and 1 goes where a was.

3. Having done that, we can now recognise S(r, n) as the r-th simplicial n-dimensional polytopic number, which you can read all about here.
And yes, it has an explicit formula for each one, which you can read at that link.

1. I can follow.
2. I will jsut accept it even though it "seems sus" to me that youc an basically let the outermost border go from 1 to (50-a) insted of a to 49 like before. But I'll just accept it for the moment.
after that, I am kind of lost.
S(r,m) still depends on n even though you havent listed it as a parameter anymore?
"r is the upper limit of each summation"
not sure what you mean there?
like, the outermost sum now goes from 1 to 50-a. and the inner ones from (outer variable) to a.
or did you mean to transform all sum borders?
3. I don't need to mention that I havent even remotely ever heard of this type of numbers, right? :-)
will look through the link and try not to totally fail at understanding anything there :-)

 

[anuttarasammyak]

TL;DR Summary: Find simplified expression of multiple sums with almost same borders and depending on one given constant. Also nice looking equal-length pyramide if visualized.

Hello,
I am having trouble with deriving an explicit formula (if one exists) for S(a,n) such that for example
S(a,5)=∑i5=a49∑i4=i549∑i3=i449∑i2=i349∑i1=i249(1)
or
S(a,4)=∑i4=a49∑i3=i449∑i2=i349∑i1=i249(1)
so basically a is a given constant and I want a formula for this multi-sum-thingie here where the outermost border goes

Let me know whether I get you properly.
$$S(a,b;1):=\sum_{i=a}^b 1 = b-a+1$$
$$S(a,b;2):=\sum_{i=a}^b S(i,b;1) = \sum_{i=a}^b (b-i+1)$$$$=(b+1)(b-a+1) - \sum_{i=1}^b i + \sum_{i=1}^{a-1} i$$$$= (b+1)(b-a+1) - \frac{b(b+1)}{2} + \frac{(a-1)a}{2}$$
$$S(a,b;3):=\sum_{i=a}^b S(i,b;2)$$$$=(b+1)(\frac{b}{2}+1)\sum_{i=a}^b 1 -(b+\frac{3}{2})\sum_{i=a}^b i +\frac{1}{2}\sum_{i=a}^b i^2 =...$$
and so on.
Do I get you?

 

[bernd]

Let me know whether I get you properly.
$$S(a,b;1):=\sum_{i=a}^b 1 = b-a+1$$
$$S(a,b;2):=\sum_{i=a}^b S(i,b;1) = \sum_{i=a}^b (b-i+1)$$$$=(b+1)(b-a+1) - \sum_{i=1}^b i + \sum_{i=1}^{a-1} i$$$$= (b+1)(b-a+1) - \frac{b(b+1)}{2} + \frac{(a-1)a}{2}$$
$$S(a,b;3):=\sum_{i=a}^b S(i,b;2)$$$$=(b+1)(\frac{b}{2}+1)\sum_{i=a}^b 1 -(b+\frac{3}{2})\sum_{i=a}^b i +\frac{1}{2}\sum_{i=a}^b i^2 =...$$
and so on.
Do I get you?

Basically, yeah. Except in my case here, b is always 49.
but otherwise, you got the idea.
Haven't really checked your calculation there, just checked the basically recursive formula for S(a,b,n) that you described there.

Cant exactly followed how you did those calculations there.
but yeah, as you might have guessed, for like S(a,,n) with n=4 or bigger, you will inevitably coem face to face with having to solve a sum of cubed or higher potency numbers.
so 1^4+2^4+...+n^4 and such.
which might or might not even have an explicit formula.

not to mention that calculating each recursive step by hand until you reach S(a,b,n) is a huge PITA and super easy to make tiny mistakes that ruin everything :-/

 

[berkeman]

3. I don't need to mention that I havent even remotely ever heard of this type of numbers, right? :-)
will look through the link and try not to totally fail at understanding anything there :-)

[Thread prefix level changed "A"-->"I"]

 

[anuttarasammyak]

Basically, yeah. Except in my case here, b is always 49.
but otherwise, you got the idea.
Haven't really checked your calculation there, just checked the basically recursive formula for S(a,b,n) that you described there.

I am glad to know that I have gotten you.

For integers $0 <a \leq b, 0 \leq c$
$$S(a,b;c)=\sum_{i=a}^{b}S (i,b;c-1)$$ for $1 \leq c$ and
$$S (i,b;0)=1$$

The transformation
$$\sum_{i=a}^{b}=\sum_{i=1}^{b}-\sum_{i=1}^{a-1}$$ and the forlmula of sum,

would help you to get the result and check your method.