
Number Theory Number Theory Math Forum 
 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. 
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((N3*a)/2)+1 possibilities for b. So we get the closed formula: $\displaystyle \sum\limits_{k=0}^{floor(\frac{N}{3})}{(floor( \frac{N3k}{2})+1)}=floor(\frac{N}{3})+1+\sum\limits_{k=0} ^{floor(\frac{N}{3})}{(floor(\frac{N3k}{2})}$ Let's test this for N=10: $\displaystyle 3+1+\sum\limits_{k=0}^{3}{\frac{103k}{2}}=4+floor(\frac{100}{2})+floor(\frac{103}{2})+floor(\frac{106}{2})+floor(\frac{109}{2})=4+5+3+2+0=14$ Seems reasonable. 
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 
October 24th, 2016, 05:25 AM  #4 
Newbie Joined: Oct 2016 From: Europe Posts: 11 Thanks: 5  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?

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). Last edited by v8archie; October 24th, 2016 at 05:50 AM. 
October 24th, 2016, 05:55 AM  #6  
Newbie Joined: Oct 2016 From: Croatia Posts: 5 Thanks: 0  Quote:
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 ?  
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 N3. Last edited by Gregor Samsa; October 24th, 2016 at 06:29 AM. 
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 !! 

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 
closedform of integration  vanderpollator  Calculus  6  July 15th, 2011 07:43 PM 
a closedform formula for(1+1^2)*(1+2^2)*(1+3^2)*...*(1+n^2)  almahed  Number Theory  10  January 4th, 2008 09:57 AM 