Number partition

  • Thread starter ziad1985
  • Start date
  • #1
236
0
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 ?
 

Answers and Replies

  • #2
CRGreathouse
Science Advisor
Homework Helper
2,820
0
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.
9 into 3 positive parts, is the same as 6 into 3 nonnegative parts, which is http://www.research.att.com/~njas/sequences/A038505 [Broken] (6) = 28. I don't know a term for this better than "partitioning".
 
Last edited by a moderator:
  • #3
236
0
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?
 
  • #4
mjsd
Homework Helper
726
3
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.
 
  • #5
236
0
where i can i find more info regarding this ?
 
  • #6
236
0
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
 
  • #7
61
0
I think it looks like qbasic
 

Related Threads on Number partition

Replies
11
Views
683
  • Last Post
Replies
10
Views
6K
  • Last Post
Replies
8
Views
2K
Replies
8
Views
276
Replies
2
Views
796
Replies
1
Views
683
Replies
2
Views
1K
  • Last Post
Replies
1
Views
2K
Replies
0
Views
952
Replies
5
Views
841
Top