Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number partition

  1. Feb 4, 2007 #1
    I want to partition a number n into k parts
    for example 9 into 3 parts
    x+y+z=9
    and each element must be non zero , first look tells me it's combination with repetition.
    however C(n-1,n-k) doesn't give the same number of possibilities when trying all of them.
    x+y+z=9 C(8,6)=28
    while trying them give only 7 possibilities
    (7,1,1) (6,2,1) (5,2,2) (5,3,1) (4,4,1) (4,3,2) (3,3,3)
    (1,7,1) is the same as (1,1,7) and (7,1,1) this small condition is changing the outcome , what kind of problem is this called ?
     
  2. jcsd
  3. Feb 4, 2007 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    9 into 3 positive parts, is the same as 6 into 3 nonnegative parts, which is A038505 (6) = 28. I don't know a term for this better than "partitioning".
     
  4. Feb 4, 2007 #3
    first thing , i didn't quiet understand what this is , plus i already stated that the number actually is 7 not 28.
    any help with what i'm dealing with here?
     
  5. Feb 4, 2007 #4

    mjsd

    User Avatar
    Homework Helper

    if you really "partitioning" that I believe that (1,1,7), (1,7,1) and (7,1,1) are identical in this context. nCr doesn't work because you have an addition constraint namely, x+y+z=constant. There is also a generalised version of this problem where you partition a number into[tex]N[/tex] parts (not just 3) where [tex]N\geq 1[/tex]. more interesting properties will ensure there too.
     
  6. Feb 5, 2007 #5
    where i can i find more info regarding this ?
     
  7. Feb 5, 2007 #6
    already find some stuff , but one question , in what language is this program written in?
    INPUT m
    DIM a(m),p(m)
    FOR i = 0 TO m: p(i) = 1: NEXT i

    FOR u = 2 TO m
    FOR i = 0 TO m: a(i) = p(i): p(i) = 0: NEXT i
    FOR j = 0 TO m STEP u
    FOR k = j TO m
    p(k) = p(k) + a(k-j)
    NEXT k
    NEXT j
    NEXT u

    REM
     
  8. Feb 5, 2007 #7
    I think it looks like qbasic
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Number partition
  1. A number (Replies: 4)

  2. Restricted Partitions (Replies: 10)

Loading...