Partitioning an IntegerDate: 11/14/98 at 06:25:51 From: Sam Huckin Subject: triples like (1,2,2), (3,1,1) = 5 I'm investigating how many different ways there are of making a number using different combinations of three numbers. For example, you can make a 5 by adding these triples: (1,2,2), (3,1,1). Does this have a formula? Thanks, Sam Date: 11/14/98 at 07:28:55 From: Doctor Anthony Subject: triples like (1,2,2), (3,1,1) = 5 This problem relates to the 'partition' of numbers. There is extensive literature on the subject, and it is algebraically quite demanding. For example the number of partitions of n into any number of parts but none exceeding q is the coefficient of x^n in the expansion of: (1-x)^-1 (1-x^2)^-2 (1-x^3)^-1 ..... (1-x^q)^-1. I will use the notation P(n,p) to represent the partition of n into p parts, for example P(50,10) is number of partitions of 50 into 10 parts. One example is (1,2,2,3,4,5,6,7,9,11). There is a recurrence relationship which allows you to fill in a table of values. So if you have the patience you can complete a table to get the answer you want. The recurrence relationship is P(n,p) = P(n-1,p-1) + P(n-p,p) And if this is applied continuously we get: P(n,p) = P(n-p,1) + P(n-p,2) + P(n-p,3) + .... + P(n-p,p) So for example: P(20,5) = P(15,1) + P(15,2) + P(15,3) + P(15,4) + P(15,5) = 1 + 7 + 19 + 27 + 30 = 84 Below is the start of such a table: n|1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 -+-------------------------------------------------------------------- p| 1|1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2| 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 3| 1 1 2 3 4 5 7 8 10 12 14 16 19 21 24 27 30 33 4| 1 1 2 3 5 6 9 11 15 18 23 27 34 39 47 54 64 5| 1 1 2 3 5 7 10 13 18 23 30 37 47 57 70 84 6| 1 1 2 3 5 7 11 14 20 26 35 44 58 71 90 7| 1 1 2 3 5 7 11 15 21 28 38 49 65 82 8| 1 1 2 3 5 7 11 15 22 29 40 52 70 9| 1 1 2 3 5 7 11 15 22 30 41 54 10| 1 1 2 3 5 7 11 15 22 30 42 If you require P(50,10) you should take the table as far as the n = 40 column, and then find: P(50,10) = P(40,1) + P(40,2) + P(40,3) + ..... + P(40,10) - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/