Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Discrete Math
High School Discrete Mathematics
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search