Math Help Forum - View Single Post

Soroban · #5 September 5th, 2007, 11:40 AM

Hello, ThePerfectHacker!

Drag your cursor between the asterisks.

Quote:

2. Given a positive integer $n$ , define a $k$ -partition
to be a sum of $k$ positive integers which sum to $n$ .

For example, $n=10$ .
The following are $4$ -partitions: $10 = 4+4+2+2,\; 10 = 2+2+4+4,\;10 = 1+1+1+7$ .
Notice that $2+2+4+4\mbox{ and }4+4+2+2$ are considered distinct. *

Say you are a given a specific $n$ and given a specific value of $k$ .
Can you find the total number of $k$ -partitions of this integer, with a formula?

* This is done to simplify this problem.
When these are not considered distinct, this forms a problem from number theory
called the "partition problem", a very complicated problem.
Yes, it is. I investigated it years ago.

*
Consider a board n inches long.
It is marked with n-1 inch-marks.

We will cut it (on the inch-marks) into k pieces.
So we will make k-1 cuts.

There are: C(n-1, k-1) ways to choose the cuts.

*

Quote:

Now try to see how many partitions (again not counting order)
exist for a given integer $n$ .

*
We have a board n units long with n-1 inch-marks.

For each of the n-1 inch-marks, there are two choices: cut or don't cut.

Therefore, there are: 2^{n-1} possible partitions.
(This includes an intact, uncut board.)

*