1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Expressions of integers

  1. Jan 19, 2008 #1
    [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. jcsd
  3. Jan 19, 2008 #2

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    How is n related to a?
     
  4. Jan 19, 2008 #3

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Assuming that 'a' is an 'n', then the OP should read up on the partition function.
     
  5. Jan 19, 2008 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  6. Jan 19, 2008 #5

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    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):

    [tex]\sum_{n \geq 0} f(n) x^n = \prod_{n \geq 1} \frac{1}{(1-x^n)}[/tex]
     
  7. Jan 19, 2008 #6
    No wonder I was having trouble with it.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?