Proof of Ordered Partioning of Integers
Date: 07/31/2001 at 18:55:11 From: Dina Subject: Proving my formula for the Ordered Partioning of Integers I have been examining the different ways to partition an integer (where order does not matter) and, after coming up with a chart similar to the one below, I found that there are 2^(n-1) ways to partition an integer (where order matters and all positive integers are available). My problem, however, is coming up with a proof for this seemingly simple formula. Here is what I have done so far, and any help that you could provide to help me prove this formula would be greatly appreciated. =) Integer | # of Ordered Partitions ___________|____________________________ | 1 | 1 = 2^0 | 2 | 2 = 2^1 | 3 | 4 = 2^2 | 4 | 8 = 2^3 | 5 | 16 = 2^4 | 6 | 32 = 2^5 This chart makes me pretty confident that the formula works, but of course, providing numerous examples does not constitute a proof. I have tried proving it by induction but have not gotten very far with this approach: Starting with n = 1, it is clear that the formula works, since there is obviously only one way to partition the integer 1, as the formula also displays: 2^(1-1) = 2^0 = 1 Now, assuming that there are 2^(n-1) ways of to partition the integer n, we need to show that this is the case for the integer (n+1). This is where I am stuck, because I cannot find an alternate expression for 2^n (which is the number of ways to partition the integer n+1) that comes from what we have already proved or assumed true. Also, I have been trying to come up with an algorithm that will generate all the trains of length n, but not much luck there either. I have seen an algorithm called the "tree algorithm" that was used to build all the n-digit numbers that use only 1s and 2s, and believe that something along these lines may help me in generating my algorithm, but the problem is I don't really understand the "tree algorithm" itself, so its not of much use as of yet. Well, any help or suggestions you may have would definitely be appreciated lots! Thanks so much for your time, Dina
Date: 08/01/2001 at 08:50:09 From: Doctor Anthony Subject: Re: Proving my formula for the Ordered Partioning of Integers We can prove this by first finding the number of ordered partitions of n into exactly r parts and then summing over all r from 1 to n. For example 6 can be partitioned into exactly 4 ordered parts as follows: (3,1,1,1), (1,3,1,1), (1,1,3,1), (1,1,1,3), (2,2,1,1), (2,1,2,1) (2,1,1,2), (1,2,2,1), (1,2,1,2), (1,1,2,2). We require the number of solutions of x1 + x2 + x3 + x4 = 6 The generating function is (x+x^2+x^3+x^4+....)^4 and we must pick out the coefficient of x^6 x^4[1+x+x^2+x^3+...]^4 x^4 --------- (1-x)^4 x^4[1 + C(4,1)x + C(5,2)x^2 + C(6,3)x^3 + .....] and the term in x^6 is C(5,2) = 10 (as we found above) Extending this to the general case of exactly r partitions of n we have the generating function x^r -------- and we require the coefficient of x^n (1-x)^r x^r[1 + C(r,1)x + C(r+1,2)x^2 + C(r+2,3)x^3 + ... ...... + C(r+(n-r-1),n-r)x^(n-r) +......] Coefficient of x^n is C(r+n-r-1,n-r) = C(n-1,n-r) = C(n-1,r-1) This is the general expression for the ordered partition of n into EXACTLY r parts. To find all the ordered partitions we must evaluate n SUM[C(n-1,r-1)] r=1 C(n-1,0) + C(n-1,1) + C(n-1,2) + ...... + C(n-1,n-1) .....(1) And if you consider the binomial expansion of (1+x)^(n-1) we have C(n-1,0) + C(n-1,1)x + C(n-1,2)x^2 + .... + C(n-1,n-1) If we put x = 1 we get expression (1) above. And so (1+1)^(n-1) = required sum 2^(n-1) = required sum This completes the proof. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.