My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree4Thanks
  • 1 Post By Gregor Samsa
  • 1 Post By Gregor Samsa
  • 1 Post By v8archie
  • 1 Post By Gregor Samsa
Reply
 
LinkBack Thread Tools Display Modes
October 22nd, 2016, 07:07 AM   #1
Newbie
 
Joined: Oct 2016
From: Croatia

Posts: 5
Thanks: 0

Closed form formula required

Is there a closed form formula for calculating the number of partially ordered sets of integers that sum up to N? Let N be 10, then the question is in how many ways can this number be reached, given that if one starts with 3 the numbers in the ordered set cannot be larger than 3.

so
3+3+3+1 =10
3+3+2+2 = 10
3+3+2+1+1 = 10
etc...

so how many calculations can I perform in this way? Keep in mind that no number can be larger than 3 and they have to be partially ordered from left to right.

miki

Last edited by skipjack; October 22nd, 2016 at 12:34 PM.
miki is offline  
 
October 23rd, 2016, 12:44 PM   #2
Newbie
 
Joined: Oct 2016
From: Europe

Posts: 11
Thanks: 5

Well, if I've understood you correctly, the numbers have to come from the set {1,2,3}. Then your question is equivalent to asking how many triples (a,b,c) there are that solve
3*a+2*b+c=N.
a can be anything from 0 to floor(N/3). For each of these floor(N/3)+1 possibilities, there are another floor((N-3*a)/2)+1 possibilities for b. So we get the closed formula:
$\displaystyle \sum\limits_{k=0}^{floor(\frac{N}{3})}{(floor( \frac{N-3k}{2})+1)}=floor(\frac{N}{3})+1+\sum\limits_{k=0} ^{floor(\frac{N}{3})}{(floor(\frac{N-3k}{2})}$
Let's test this for N=10:
$\displaystyle 3+1+\sum\limits_{k=0}^{3}{\frac{10-3k}{2}}=4+floor(\frac{10-0}{2})+floor(\frac{10-3}{2})+floor(\frac{10-6}{2})+floor(\frac{10-9}{2})=4+5+3+2+0=14$
Seems reasonable.
Thanks from miki
Gregor Samsa is offline  
October 24th, 2016, 05:00 AM   #3
Newbie
 
Joined: Oct 2016
From: Croatia

Posts: 5
Thanks: 0

Thank you for the help. But I think you neglected the ordering (as I did on many attempts till now) so the numbers in the summation have to be partially ordered. In that case we can only have 8 summations:

3+3+3+1 =10
3+3+2+2 = 10
3+2+2+2+1 = 10
3+2+2+1+1+1 = 10
3+3+2+1+1 = 10
3+3+1+1+1+1 = 10
3+2+1+1+1+1+1 = 10
3+1+1+1+1+1+1+1 = 10


The best I managed to come up with is to make a tree algorithm and then recursively travers it and sum up things as a go along. but that just equals to counting the possibilities.

Thank you. If you have any ideas regarding it please do let me know! Thank you once again

miki
miki is offline  
October 24th, 2016, 05:25 AM   #4
Newbie
 
Joined: Oct 2016
From: Europe

Posts: 11
Thanks: 5

Quote:
Originally Posted by miki View Post
Thank you for the help. But I think you neglected the ordering (as I did on many attempts till now) so the numbers in the summation have to be partially ordered. [...]
What do you mean by "partially ordered"? If I recall correctly, any set that has reflexivity, transitivity and antisymmetry under some relation (≤ in this case) is a poset. So if a set only contains {1,2,3} it's always partially ordered, or is it not?
Thanks from miki
Gregor Samsa is offline  
October 24th, 2016, 05:33 AM   #5
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 7,671
Thanks: 2651

Math Focus: Mainly analysis and algebra
Here's a paper on a more advanced problem. I post it because it refers to simpler results that may provide the exact answer that you seek, or perhaps just start you on a path to get there.

Note that, in this case, partitions are unique if and only if the elements of the partitions are different (which I believe is what you are seeking).
Thanks from miki

Last edited by v8archie; October 24th, 2016 at 05:50 AM.
v8archie is offline  
October 24th, 2016, 05:55 AM   #6
Newbie
 
Joined: Oct 2016
From: Croatia

Posts: 5
Thanks: 0

Quote:
Originally Posted by Gregor Samsa View Post
What do you mean by "partially ordered"? If I recall correctly, any set that has reflexivity, transitivity and antisymmetry under some relation (≤ in this case) is a poset. So if a set only contains {1,2,3} it's always partially ordered, or is it not?
Yes that is true but the ordering has to be on a partition. so given a set {1,2,3} partition (3,2,1,2,2,2) is not ordered and therefore

3+2+1+2+2= 10

does not belong to a result I am looking for.

However 3+2+2+2+1= 10 does since partition (3,2,2,2,1) is properly ordered.

Do I make any sense ?
miki is offline  
October 24th, 2016, 06:14 AM   #7
Newbie
 
Joined: Oct 2016
From: Europe

Posts: 11
Thanks: 5

Mmh, I think I still don't quite understand you. Here's a list I made. These are all partially ordered, I believe:

3+3+3+1

3+3+2+2
3+3+2+1+1
3+3+1+1+1+1

3+2+2+2+1
3+2+2+1+1+1
3+2+1+1+1+1+1
3+1+1+1+1+1+1+1

2+2+2+2+2
2+2+2+2+1+1
2+2+2+1+1+1+1
2+2+1+1+1+1+1+1
2+1+1+1+1+1+1+1+1

1+1+1+1+1+1+1+1+1+1

--> 14

EDIT: Ah, I didn't read you required it to start with 3. That explains it.

EDIT: I think you can still use my formula. Just plug in N-3.
Thanks from miki

Last edited by Gregor Samsa; October 24th, 2016 at 06:29 AM.
Gregor Samsa is offline  
October 25th, 2016, 05:09 AM   #8
Newbie
 
Joined: Oct 2016
From: Croatia

Posts: 5
Thanks: 0

thank you both, this was more that helpful

thank you !!
miki is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
close, closed, form, formula, order, required



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
closed form expression gelatine1 Algebra 3 September 1st, 2013 10:57 PM
Finding closed form formula for sequence kriegor Applied Math 1 March 22nd, 2013 04:48 PM
Closed Form joatmon Real Analysis 2 January 24th, 2012 08:33 PM
closed-form of integration vanderpollator Calculus 6 July 15th, 2011 07:43 PM
a closed-form formula for(1+1^2)*(1+2^2)*(1+3^2)*...*(1+n^2) al-mahed Number Theory 10 January 4th, 2008 09:57 AM





Copyright © 2019 My Math Forum. All rights reserved.