View Single Post
ghotra
#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
Experts defend operational earthquake forecasting, counter critiques
EU urged to convert TV frequencies to mobile broadband
Sierra Nevada freshwater runoff could drop 26 percent by 2100