View Single Post
ghotra
ghotra is offline
#1
Sep9-06, 12:16 AM
P: 53
http://en.wikipedia.org/wiki/Integer_partition

The above link should set the context.

Given an integer q, the total number of partitions is given by partition function p(q). For example,

4 = 4
= 3+1
= 2 + 2
= 2 + 1 + 1
= 1 + 1 + 1 + 1

So, p(4) = 5. In mathematica, one can use PartitionsP[4].

The number of partitions is unrestricted. An example problem might be: Suppose I have 2 indistinguishable balls and I want to give them to any number of indistinguishable children. What are the unique ways of distributing the balls?

I can give one child 4 balls.
I can give one child 3 balls and another child 1 ball.
I can give two children 2 balls each.
I can give one child 2 balls and two children 1 ball each.
I can give four children 1 ball each.

Notice, as the number of balls increases, it is necessary that there are at least as many indistinguishable children as there are balls to distribute.

Now, suppose I want to limit the number partitions (children) to some integer k. In the above example, suppose I limit the number of children to k=3. Then there are 4 partitions of size k=3 or less for the interger q=4. The disallowed partition is when I give 1 ball each to four children.

Is there a general formula for restricting the number of partitions. That is:

How many partitions of size k or fewer exist for the integer q?
Example usage:

I have 2 indistinguishable balls and I want to give them to 3 indistinguishable children. There are just 2 unique ways of doing this:

(2,0,0)
(1,1,0)

That is, I give 2 balls to one child and none to the other children.
That is, I give 1 ball to one child and 1 ball to another child.
So, the number I am looking for is 2.

This is related to a common combinatorics problem. If I care about the order, then the following options are available:

(2,0,0) (0,2,0) (0,0,2)
(1,1,0) (1,0,1) (0,1,1)

This total number is 6 and the formula that determines it is well-known:

[2 + (3-1)]! / (3-1)! / 2! = 6

Thus, I am looking for some way to remove the permutation degeneracy from the above formula.

Any help is appreciated. This seems like it should be a common question. Does anyone know of the closed form answer?
Phys.Org News Partner Science news on Phys.org
NASA's space station Robonaut finally getting legs
Free the seed: OSSI nurtures growing plants without patent barriers
Going nuts? Turkey looks to pistachios to heat new eco-city