Sum of Natural NumbersDate: 11/23/97 at 15:45:57 From: Helmut Lerche Subject: Combinatorics Hello, Is there a formula for counting all the possibilities for writing a natural number (1,2,3, etc.) as the sum of natural numbers (order is not important)? Example: The natural number 4 can be written as: 1+1+1+1 1+1+2 1+3 2+2 4 This means that for 4 there are 5 possibilities. Thank you very much for helping me. Yours sincerely, Helmut Lerche from Germany (Upper Bavaria near Munich) Date: 11/23/97 at 16:49:47 From: Doctor Anthony Subject: Re: Combinatorics 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. There is a recurrence relationship which allows you to fill in a table of values. 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 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 Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/