User Name Remember Me? Password

 Number Theory Number Theory Math Forum

 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((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 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

Quote:
 Originally Posted by miki 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? October 24th, 2016, 05:33 AM #5 Math Team   Joined: Dec 2013 From: Colombia Posts: 7,689 Thanks: 2669 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. October 24th, 2016, 05:55 AM   #6
Newbie

Joined: Oct 2016
From: Croatia

Posts: 5
Thanks: 0

Quote:
 Originally Posted by Gregor Samsa 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 ? 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. 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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post gelatine1 Algebra 3 September 1st, 2013 10:57 PM kriegor Applied Math 1 March 22nd, 2013 04:48 PM joatmon Real Analysis 2 January 24th, 2012 08:33 PM vanderpollator Calculus 6 July 15th, 2011 07:43 PM al-mahed Number Theory 10 January 4th, 2008 09:57 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top      