Find an explicit formula for this n-sum problem

In summary, In order to calculate the sum of a sequence of n numbers, you need to solve a math problem involving a lottery where you can choose six numbers from 1-49. Additionally, you need to know the low border of the outermost sum.
  • #1
bernd
16
0
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. :cool:
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 :-)
 
Mathematics news on Phys.org
  • #2
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)
 
  • #3
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.
 
  • Like
  • Informative
  • Love
Likes berkeman, DrClaude and PeroK
  • #4
andrewkirk said:
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 :-)
 
  • Sad
Likes PeroK
  • #5
bernd said:
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.
[tex]S(a,b;1):=\sum_{i=a}^b 1 = b-a+1[/tex]
[tex]S(a,b;2):=\sum_{i=a}^b S(i,b;1) = \sum_{i=a}^b (b-i+1) [/tex][tex]=(b+1)(b-a+1) - \sum_{i=1}^b i + \sum_{i=1}^{a-1} i [/tex][tex]= (b+1)(b-a+1) - \frac{b(b+1)}{2} + \frac{(a-1)a}{2} [/tex]
[tex]S(a,b;3):=\sum_{i=a}^b S(i,b;2)[/tex][tex]=(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 =...[/tex]
and so on.
Do I get you?
 
Last edited:
  • #6
anuttarasammyak said:
Let me know whether I get you properly.
[tex]S(a,b;1):=\sum_{i=a}^b 1 = b-a+1[/tex]
[tex]S(a,b;2):=\sum_{i=a}^b S(i,b;1) = \sum_{i=a}^b (b-i+1) [/tex][tex]=(b+1)(b-a+1) - \sum_{i=1}^b i + \sum_{i=1}^{a-1} i [/tex][tex]= (b+1)(b-a+1) - \frac{b(b+1)}{2} + \frac{(a-1)a}{2} [/tex]
[tex]S(a,b;3):=\sum_{i=a}^b S(i,b;2)[/tex][tex]=(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 =...[/tex]
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 :-/
 
  • #7
bernd said:
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"]
 
  • #8
bernd said:
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##
[tex]S(a,b;c)=\sum_{i=a}^{b}S (i,b;c-1)[/tex] for ##1 \leq c## and
[tex]S (i,b;0)=1[/tex]

The transformation
[tex]\sum_{i=a}^{b}=\sum_{i=1}^{b}-\sum_{i=1}^{a-1}[/tex] and the forlmula of sum,
1667602442617.png

would help you to get the result and check your method.
 
Last edited:
  • Like
Likes SammyS

FAQ: Find an explicit formula for this n-sum problem

1. What is an explicit formula for a n-sum problem?

An explicit formula for a n-sum problem is a mathematical expression that allows you to find the sum of a specific sequence of numbers up to a certain value of n. It is written in terms of n and can be used to find the sum for any value of n.

2. How do I find an explicit formula for a n-sum problem?

To find an explicit formula for a n-sum problem, you can use the formula for the sum of an arithmetic sequence: Sn = (n/2)(a1 + an), where Sn is the sum of the first n terms, a1 is the first term, and an is the nth term. You can then manipulate this formula to fit the specific n-sum problem you are trying to solve.

3. Can an explicit formula be used for any n-sum problem?

Yes, an explicit formula can be used for any n-sum problem as long as the sequence of numbers follows a pattern and can be represented by a mathematical expression. However, some n-sum problems may be more complex and require more advanced mathematical techniques to find an explicit formula.

4. Are there any limitations to using an explicit formula for a n-sum problem?

One limitation of using an explicit formula for a n-sum problem is that it may only work for a specific range of values of n. If the sequence of numbers does not follow a predictable pattern, it may be difficult to find an explicit formula that accurately represents the sum for all values of n.

5. How can I check if my explicit formula is correct for a n-sum problem?

To check if your explicit formula is correct for a n-sum problem, you can plug in different values of n and compare the results to the actual sum of the sequence. You can also use mathematical induction to prove that your formula holds true for all values of n.

Similar threads

Replies
7
Views
1K
Replies
3
Views
1K
Replies
8
Views
2K
Replies
2
Views
1K
Replies
2
Views
1K
Replies
25
Views
3K
2
Replies
69
Views
5K
Replies
2
Views
1K
Back
Top