# Formula for the number of "addition constructions" of a positive integer

I was working on a cool maths problem and got inspired from one of the mini lemmas I had to make up in order to solve the problem. From then on, I have been trying to find a formula which for any positive integer, gives the number of ways it can be "built" as a sum of smaller positive integers. Example: for 5, you can have: 1+1+3, 2+3, 1+4, 1+1+1+1+1, etc.

Finding a formula that regards (example) 1+1+3, 3+1+1 and 1+3+1 as unique "constructions" proved to be not too hard (in fact I re-discovered ;P 2 formulas) but finding a formula for my original aim is proving exceedingly difficult for me.

Please (I don't wan't to spoil the fun and look the answers up on wikipedia or something), given a high school education in maths, could one potentially attain the formula (as I have been trying for very long now) or am I wasting my time and should I look up the answer (as it is far too advanced???)? Thank you.

• IMHO you get what mathematics is all about: playing with stuff like this. Keep at it! I did peek around a bit and you'll want to look at partitions. It gets really messy really fast.
– John
Jan 3, 2014 at 22:07

## 1 Answer

What's important is that you've stumbled onto an entire field of mathematics!

A method to write an integer $n$ as a sum of lesser integers, e.g. $5$ as $4+1$, is called an partition. We consider integer partitions such as $1+4$ and $4+1$ to be equivalent --- for integer partitions, order doesn't matter!

If you say that order matters, then we call that a composition. For example, for any integer $n$, we have $2^n-1$ distinct compositions. Unfortunately, the formula for the number of distinct partitions is a lot more difficult, likely requiring tools you currently don't have.

• haha oh my god how did pi get in there :O.. thanks for the link. Seems like this question is too hard but very cool nevertheless. Jan 3, 2014 at 22:21
• How pi got in there? It's math, it all fits together ;)
– Newb
Jan 3, 2014 at 22:22