How many ways can you express n as the sum of positive integers?

[ehrenfest]

[SOLVED] expressions of integers

Homework Statement

Let n be a positive integer. How many ways can you express a as the sum of positive integers? Order of addition does not matter.

EDIT: change "a" to "n" in the second sentence

Homework Equations

The Attempt at a Solution

Let f(x) be the function that gives the number of ways you can express x as the sum of positive integers? Order of addition does not matter.
f(1)=1
f(2)=2
f(3)=3
f(4)=5
f(5)=7

I do not see the pattern. I was hoping for Fibonacci numbers...

 

[EnumaElish]

Homework Statement

Let n be a positive integer. How many ways can you express a as the sum of positive integers? Order of addition does not matter.

How is n related to a?

 

[morphism]

Assuming that 'a' is an 'n', then the OP should read up on the partition function.

 

[HallsofIvy]

looks to me like a recursive formula. "2" can be written as a sum of integers just one way: 1+ 1. Obviously 3 can be written 2+ 1 or 1+ 2 and then the 2 in that can be written in one way: 2+ 2(1)= 4. 3 can be written is 3+ 1 and 1+ 3 and, in addition to that 3 can be written if 4 ways: 2+ 2(4)= 10. In general, if k can be written in n(k) ways, then k+ 1 can be written as (k)+ 1 or 1+ (k), which is 2 ways and then the (k) can be written in n(k) ways: n(k+1)= 2+ 2n(k). Once you found the formula from that you can prove it by induction.

 

[morphism]

That misses some of the partitions, e.g. 4=2+2 cannot be obtained from the partitions of 3. Also, judging by the OP's calculations, I don't think he's paying attention to the order of the terms in the partition, i.e. 1+(k) and (k)+1 count as one.

As far as I'm aware, there is no nice closed form for the partition function in general, although there are formulas for particular types of partitions. A good way to work with partitions is via generating series (a good book on these matters is Generatingfunctionology, available for free online). For example, here's an expression due to Euler (IIRC):

$$\sum_{n \geq 0} f(n) x^n = \prod_{n \geq 1} \frac{1}{(1-x^n)}$$

 

[ehrenfest]

As far as I'm aware, there is no nice closed form for the partition function in general,

No wonder I was having trouble with it.