# Homework Help: Expressions of integers

1. Jan 19, 2008

### ehrenfest

[SOLVED] expressions of integers

1. The problem statement, all variables and given/known data
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
2. Relevant equations

3. 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...

Last edited: Jan 19, 2008
2. Jan 19, 2008

### EnumaElish

How is n related to a?

3. Jan 19, 2008

### morphism

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

4. Jan 19, 2008

### 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.

5. Jan 19, 2008

### 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)}$$

6. Jan 19, 2008

### ehrenfest

No wonder I was having trouble with it.