A "Christmas tree formula" //:-)

L published this in a free online platform. ~~~~~ Christmas three sequence ~~~~~ --A Recursive definition of the partition function-- p(n) = n M n = n M (n-1) + 1 whereas n M t = sigma (k=0 to n Q t), (n R t + t*k) M (t-1), and n M 1 = 1 whereas Q is the quotient function and R is the remainder function. a number, v, can be expressed as: V = Q*D + R. for example, 17 = 5*3 + 2. here, 17 is the Value, 3 is the Divider, 5 is the Quotient, and 2 is the Remainder. We denote, 5 = 17Q3, and 2 = 17R3, because 5 is the Quotient when we divide 17 by 3, and 2 is the Remainder when we divide 17 by 3. -------------------------history of partition function----------------- The partition function has been plaguing the top notch mathematicians for centuries. Leonard Euler, Hardy, Ramanujan, Rademacher, you name it. They strived to find a closed form formula for the partition functions, all these mathematical giants. The formula presented above is recursive, not closed. But we posit that it's brand new. So we decided to publish what we found here. it's a grass root effort to help out the mathematics community, a volunteerism so to speak. -------------------------- the partition function p(n), in plain English, is defined as this: express the number, n, in terms of summation of numbers less than or equal to n. how many ways are there? for instance, 3 = 3. 3 = 2+1. 3 = 1+1+1. there are three ways to express the number 3 in terms of summations of numbers, each of which is 3 or less. we are talking about non-negative integers, or natural numbers like 0, 1, 2, ... -------------------- Now. we can generalize the partition function p(n) like this: nMt = the number of ways to express n in terms of summation of numbers each of which is equal to or less than t. We call this function, a restricted partition function. the function M takes two input variables, n, and t, both of which are natural numbers. Its output is also a natural number, i.e., a non-negative integer. ----------------------- Now. nM1 is the number of ways to express n in terms of 1 or less. How many ways are there? ... 1. only 1. why? because: n = 1 + 1 + 1 + ... + 1. you add up 1's, n times. there is only one way to do so. ----- Next. nM2 means the number of ways to express n in terms of sum of numbers, each of which is 2 or less. For instance, 5 = 2+2+1 =2+1+1+1 =1+1+1+1+1. So there are 3 ways. that is, 5M2 = 3. We will have to come up with a new notation here. 5M2 = |5MM2| = |{(2,2,1), (2,1,1,1), (1,1,1,1}| = 3. 5MM2 is a set of vectors. What is a vector? It is an ordered set of numbers. A number is also known as a scalar. (2,2,1) is an ordered set of numbers. We call it, a vector in linear algebra community. ------------------- Ok. Now. In mathematics, we have a set. Like, A = {a, b, c}. The 'cardinality' of a set A is, n(A) = |A| = 3. It means the number of members in the set A. The size of A. For simplicity's sake, we will borrow the absolute value notation to denote the cardinality of a set. ------------------- So. 5MM2 is a set function, meaning, the output of the function is a set. A scalar function is a function whose output is a scalar. A vector function is a function whose output is a vector. We will follow that convention and generalize it as such: "A set function is a function whose output is a set." --------------------- ok. where are we? here. xMMy is a set function, whose inputs are two natural numbers, x and y. We could have written it as MM(x, y). But we want to be more efficient in notational convention. So we will write it as xMMy instead. ----------------------- so what is xMMy? it is a set of vectors. a vectors is an ordered set of numbers, aka, scalars. xMMy is a set of vectors, whose individual members sum up to x, given that each number is less than or equal to y. please, allow me to explain. I know it's not an easy concept to grasp. --------------------- 5MM2 = { (2,2,1), (2,1,1,1), (1,1,1,1,1) } it means, in plain English, there are three ways to express the number 5, in terms of the summation of numbers, each of which is equal to or less than 2. It's what we call, a restricted partition set. ----------------- What is a partition set, then? It's this: 5=5 =4+1 =3+2 =3+1+1 =2+2+1 =2+1+1+1 =1+1+1+1+1 there are 7 ways to express 5 in terms of natural numbers, each of which is less than or equal to 5. The partition function is just that: p(5)=7. Then, a restricted partition set is this: 5M3 = the number of ways to express 5 via the sum of numbers of 3 or less. 5MM3 = {(3,2), (3,1,1), (2,2,1), (2,1,1,1), (1,1,1,1,1)} 5M3=|5MM3|=5. -------------------------- Now. we are about to take it to the next level, next step. we found that already: nM1 = 1. because, n = 1+1+...+1. there is only one and only one way to express n in terms of sum of 1's. we got that. how about, nM2? ... can you guess? I'll give you 5 minutes. ... -------------------------- ok, time's up. comp are your answer with mine, please: nM2 = nQ2 + 1, whereas, nQ2 means the quotient of n resulting from the division of n by 2. For instance, 5 =2+2+1 =2+1+1+1 =1+1+1+1+1. There are 3 ways to express 5 in sum of 2 or less. Would it surprise you, if we say, 3 = 2+ 1 = 5Q2 + 1? divide 5 by 2. Quotient = 2, Remainder=1. Correct? --------------------- so the general formula is this: nM2 = nQ2 + 1. we are not gonna prove that this time. Though you are encouraged to prove it via perhaps mathematical induction. ok? ------------------------ Ok. next step: nM3=? to give you away the result, it's this: nM3 = sigma (k=0 to nQ3) (nR3+3k)M2. I didn't study how to use LaTex, so my apologies. I have no idea how to write mathematical equation with that and upload here. Sorry. --------------------- So we'll just do it the ole school way, k kiddo? //:-) now. what does that equation mean? nQ3 means, when you divide n by 3, it's the Quotient that we are after. nR3 means, when you divide n by 3, it's the Remainder that we are after. For example, 14Q3 = 4, 14R3 = 2, because, 14 = 4*3 + 2 = Q*3 + R. meaning, 14 is the Value, 3 is the Divider, 4 is the Quotient, and lastly, 2 is the Remainder, folks. ----------------------------- So let us plug in the numbers, to verify whether our equation is correct. shall we? nM3 = sigma (k=0 to nQ3) (nR3+3k)M2. 14M3 = sigma (k=0 to 14Q3) (14R3 + 3*k) M 2 = Sigma (k=0 to 4) (2 + 3k) M 2 = sigma (k=0 to 4) [ {(2+3k) Q 2} + 1] = 2Q2+1 + 5Q2+1 + 8Q2+1 + 11Q2+1 +14Q2+1 = 2+3+5+6+8 = 24 --------------------- is it that big? perhaps our formula is wrong, lol. no worries. if we are wrong, we can correct it later, refine it so to speak. let's see here. 14MM3={ 333 3 2, 333 3 11, 333 2 2 1, 333 2 11 1, 333 11 11 1, 33 2 2 2 2, 33 2 2 2 11, 33 2 2 11 11, 33 2 11 11 11, 33 11 11 11 11, 3 2 2 2 2 2 1, 3 2 2 2 2 11 1, 3 2 2 2 11 11 1, 3 2 2 11 11 11 1, 3 2 11 11 11 11 1, 3 11 11 11 11 11 1, 2 2 2 2 2 2 2, 2 2 2 2 2 2 11, 2 2 2 2 2 11 11, 2 2 2 2 11 11 11, 2 2 2 11 11 11 11, 2 2 11 11 11 11 11, 2 11 11 11 11 11 11, 11 11 11 11 11 11 11 }. 14 M 3 = | 14 MM 3 | = 24. looks like a Christmas tree, doesn't it? we may call this 2-dimensional sequence of numbers, the x-mas tree numbers. -------------------- So. if you have been so so kind enough to count the number of the rows up there, it's 24. Which nicely matches the result of our handy dandy formula up there. now. how did 'we' came up with the formula? ... a lot of leg work. a lot of additions by hand. a lot of examples. it took us about two weeks. we all have our day jobs. in our spare time, we devoted ourselves in discovering this one formula. it took us about two weeks, even a month. not too long, but it's been a long journey, it seems. we will share it with you, the experience- ------------------------- ok. where do we begin? the basics. 5=5 = 4+ 1 = 3+ 2 = 2+ 2+ 1 = 2+ 1+1+ 1 = 1+1+ 1+1+ 1 we gotta be very careful with spacing. the key is, organizing things well. we have to be diligent enough to space the numbers, align them in a tidy, neat fashion. then, we can start to see the patterns. that's how we can come up with a general math formula. -------------------------- So. up there, we got: p(5) = 6. that is to say, there are 6 ways to express 5 in terms of additions of numbers each of which is less than or equal to 5. capiche? ok. now. we are decomposing a number from upstairs. we are breaking down a number upstairs into smaller numbers downstairs, ok? but, we try to keep the numbers as big, high and mighty as possible, in each step, all the way. it's called, 'well-ordered system' of numbers. like, lexicographical ordering in linguistics, so to speak. ------------------------ in our example above, we had: 5=5 = 4+ 1 = 3+ 2 = 2+ 2+ 1 = 2+ 1+1+ 1 = 1+1+ 1+1+ 1 observe this. at the each row in the above triangle or trapezoidal figure, we got, "trailing" 2's and 1's. it's binary. that is the first clue in our pattern recognition project of this, x-mas tree numbers. -------------------- say, we have: 2 2 1 as a vector, which, I remind you, is an ordered set of numbers, or an ordered set of scalars. now. we can 'decompose' the one two into two ones, once, like so: 2 11 1 ok? so, to illustrate, we are splitting the second 2 into two 1's: 2 2 1 | v 2 1 1 1 it's.... ascii diagram, kinda ghetto way to draw a picture, lol. ------------------------ the next step is a further decomposition of one 2 into 2 ones: 2 11 1 11 11 1 ------------------ this is how we get the formula for nM2: nM2 = nQ2 + 1. what is nM2 again? it's the number of ways to express n in sum of 2 or less. for example, 5=2+ 2+ 1 = 2+ 1+1 +1 =1+1+ 1+1 +1 I hope you got the idea. first, we express 5 in sum of 2's or 1's. next step, we decompose the right-most 2 into two 1's. next, we decompose the next right-most 2 into two 1's. we do it that way, again and again, folks //:-) -------------------------- so. what is 5M2 again? ... it is the number of ways to express 5 in sum of 2 or less. how many ways are there? ... you divide 5 by 2: 5 = 2*2 + 1. so the quotient is 2, remainder is 1. right? how about 7? 7 = 3*2 + 1. the quotient is 3, remainder is 1. k? now, let us find, 7MM2, the set of vectors, whose elements are 2's or 1's, who collectively add up 7. shall we? here: 7MM2={ 2 2 2 1, 2 2 11 1, 2 11 11 1, 11 11 11 1}. and, 7M2 = | 7MM2 | = 4. how about 6? here: 6MM2={ 2 2 2 2 2 11 2 11 11 11 11 11}. 6M2 = | 6MM2 | = 4. ------------------- is it too hard? to understand? I understand. math is not easy, I get it. I feel ya //:-) but you see the pattern here, right? to express a number 'n', in sum of 2's and 1's, all you gotta do is div it up by 2, and find the quotient. 6 or 7, if you div it up by 2, you get 3 as quotient. do they not, hmm? lol. so yeah. you express 6 as 2+2+2, and 7 as 2+2+2+1. the trailing 1, whatever. right? lol. ---------------------- so yeah. we got the formula here: nM2 = nQ2 + 1. ---------------------- so why do we call the 'restricted partition function,' M? well, as I worked on this problem, I had to merge numbers. that's why I had to name it, 'M'. 'M' for Merger. Not 'M' for Murder as in Agatha Christie's novel. She's a fine writer, I guess. I never read her novel from cover to cover, by the way lol. ---------------------- alright. our next step is to find an algebraic expression for: nM3. ... ok. we will have to make some examples, folks. here: 10MM3 = { 3 3 3 1 3 3 2 2 3 3 2 11 3 3 11 11 3 2 2 2 1 3 2 2 11 1 3 2 11 11 1 3 11 11 11 1 2 2 2 2 2 2 2 2 2 11 2 2 2 11 11 2 2 11 11 11 2 11 11 11 11 11 11 11 11 11 }. ------------------- ok. a lot of numbers, right? I know lol. but it's beautiful. our of chaos, we find some cosmos. some orderliness. can you spot some pattern here? --------------- Basically, we need to group them into separate subsets. k? like so: 3 3 3 1 -------------- 3 3 2 2 3 3 2 11 3 3 11 11 -------------- 3 2 2 2 1 3 2 2 11 1 3 2 11 11 1 3 11 11 11 1 --------------- 2 2 2 2 2 2 2 2 2 11 2 2 2 11 11 2 2 11 11 11 2 11 11 11 11 11 11 11 11 11 --------------- the motivation of this particular kind of grouping is this: ignore the big guy, 3. we're underdogs, k? we'll just deal with 2's and 1's for now, lol. small guy helping out another small guy, so to speak, ok? --------------------- so if we take the 3's out of the picture, we have the trailing 2's and 1's: 1 ------------- 2 2 2 11 11 11 -------------- 2 2 2 1 2 2 11 1 2 11 11 1 11 11 11 1 --------------- 2 2 2 2 2 2 2 2 2 11 2 2 2 11 11 2 2 11 11 11 2 11 11 11 11 11 11 11 11 11 ---------------------------------------------------- what we got here up above, is this: 1MM2 4MM2 7MM2 10MM2 ------------------------------------------------ are you following all this? ------------------- to generalize, we basically can come up with the following formula, folks: nM3 = | nMM3 | = sigma (k=0 to nQ3) { (nR3 + 3k) M 2 }. ---------------------------------------- We will do just one more example and we will call it a day, ladies and gentlemen. --------------------------- 10MM4={ 4 4 2 4 4 11 4 3 3 4 3 21 4 3 111 4 2 2 2 4 2 2 11 4 2 11 11 4 11 11 11 3 3 3 1 3 3 2 2 3 3 2 11 3 3 11 11 3 2 2 2 1 3 2 2 11 1 3 2 11 11 1 3 11 11 11 1 2 2 2 2 2 2 2 2 2 11 2 2 2 11 11 2 2 11 11 11 2 11 11 11 11 11 11 11 11 11 }. looks like a Christmas tree, does it not? lol so yeah. we'll call it, this 2-dimensional sequence of numbers, the x-mas tree numbers //:-) ----------------------- ok. as usual, we will group this thang. but this time around, we will group it in terms of base 3, like so: 4 4 2 4 4 11 ---------- 4 3 3 4 3 21 4 3 111 4 2 2 2 4 2 2 11 4 2 11 11 4 11 11 11 ---------- 3 3 3 1 3 3 2 2 3 3 2 11 3 3 11 11 3 2 2 2 1 3 2 2 11 1 3 2 11 11 1 3 11 11 11 1 2 2 2 2 2 2 2 2 2 11 2 2 2 11 11 2 2 11 11 11 2 11 11 11 11 11 11 11 11 11 ---------- then, the Christmas tree of ours becomes, I mean, after we take 4 out of play: 2 11 ---------- 3 3 3 21 3 111 2 2 2 2 2 11 2 11 11 11 11 11 ---------- 3 3 3 1 3 3 2 2 3 3 2 11 3 3 11 11 3 2 2 2 1 3 2 2 11 1 3 2 11 11 1 3 11 11 11 1 2 2 2 2 2 2 2 2 2 11 2 2 2 11 11 2 2 11 11 11 2 11 11 11 11 11 11 11 11 11 ---------- which reduces to, dramatically so: 2MM3 6MM3 10MM3 ------------------------------- so, what we got here is this: 10M4 = 2M3 + 6 M3 + 10M3. it's increment of 4, in the head number of this, Merger function, i.e., the restricted partition function, as we named it some time before. ---------------------------- to generalize it, it's easy, right? lol. here: nM4 = sigma (k=0 to nQ4) {(nR4 + 4k) M 3}. --------------------------------------- so. you see the pattern. in general, nMt = sigma (k=0 to nQt) {(nRt + t*k) M (t-1) }. and, for that one special case when n is equal to t, we got the partition function, ladies and gentlemen: p(n) = nMn = sigma (k=0 to nQn) {(nRn + n*k) M (n-1)} = (k=0 to 1) {n*k M (n-1)} = 0 M (n-1) + n M (n-1) = n M (n-1) + 1 = 1 + sigma (k=0 to 1) ( 1 + (n-1)*k ) M (n-2) = 1 + 1M(n-2) + n M (n-2) = n M (n-2) + 2 e.g. p(5) = 7 = 5 M 3 + 2 = 5 + 2. 5MM3 = | 3 2 3 1 1 2 2 1 2 11 1 11 11 1 | = 5 ------------------------ so yeah. we got it. congratulations. you are witnessing the making of a brand new chapter of the history in mathematics, ladies and gentlemen. thank you //:-) ---------------------- as an epilogue, we encourage you to prove this formula, by using mathematical induction, or by calculus or geometry or whatsoever mathematical theory that you are familiar with. ... it's all about division of labor. I did my part by discovering this. perhaps it's a conjecture at best. this formula could be incorrect, I admit that possibility. but as far as I can see, this formula works. so yeah. challenge me, if you would. either prove it, or disprove it. take it or leave it. it is up to you. Merry Xmas- //:-) ~~~~~~~~~~Q.E.D.~~~~~~~~~