Number of Unordered PartitionsDate: 08/18/99 at 03:40:29 From: Nicolae Bonciocat Subject: Formula for the unordered partitions of n Dear Professor, I kindly ask you to inform me if there is any known formula for the number of unordered partitions of a positive integer p(n). Many thanks, Nicolae Bonciocat Date: 08/18/99 at 07:40:12 From: Doctor Anthony Subject: Re: Formula for the unordered partitions of n The generating function for the number of partitions of a number n is the coefficient of x^n in the expansion of 1 ----------------------------- (1-x)(1-x^2)(1-x^3)(1-x^4)... = (1-x)^(-1) * (1-x^2)^(-1) * (1-x^3)^(-1) * ... = [1+x+x^2+x^3...]*[1+x^2+x^4+x^6+...]*[1+x^3+x^6+x^9+...]*... Clearly this infinite product need not be continued beyond terms x^n. This generating function is not of much practical use unless you have a mathematics package like Mathcad or Mathematica to handle the heavy algebra. Fortunately there is a recursion formula which can be used without the heavy algebra. The recursion formula for p(n), the TOTAL number of partitions of n is given by: p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + p(n-15) - p(n-22) - ... Note that the signs follow the pattern ++ -- ++ -- ++ -- and so on. The numbers 1, 2, 5, 7, 12, 15, 22, 26, ... inside the brackets are of the form (m/2)(3m-1) and (m/2)(3m+1) It is useful to have a table showing how these values go. m 1 2 3 4 5 6 7 8 --------------------------------------------------------- (m/2)(3m-1) 1 5 12 22 35 51 70 92 (m/2)(3m+1) 2 7 15 26 40 57 77 100 Take p(0) = 1 and p(1) = 1 p(2) = p(1) + p(0) = 2 p(3) = p(2) + p(1) = 3 p(4) = p(3) + p(2) = 5 p(5) = p(4) + p(3) - p(0) = 3+5-1 = 7 p(6) = p(5) + p(4) - p(1) = 7+5-1 = 11 p(7) = p(6) + p(5) - p(2) - p(0) = 11+7-2-1 = 15 p(8) = p(7) + p(6) - p(3) - p(1) = 15+11-3-1 = 22 and so on. - 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- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/