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/