http://en.wikipedia.org/wiki/Integer_partition(adsbygoogle = window.adsbygoogle || []).push({});

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:

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

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?

**Physics Forums - The Fusion of Science and Community**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Restricted Partitions

Loading...

Similar Threads for Restricted Partitions | Date |
---|---|

I Partitioning a whole number in a particular way | Feb 14, 2018 |

I Stochastic Minimax partition problem card game | Sep 1, 2017 |

Number of Possible Outcomes w/ Restrictions (Coin Toss) | Aug 8, 2013 |

Universal restriction in description logic | Jan 19, 2012 |

Testing multiple linear restrictions | Sep 7, 2010 |

**Physics Forums - The Fusion of Science and Community**