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
= 2 + 2
= 2 + 1 + 1
= 1 + 1 + 1 + 1
So, p(4) = 5. In mathematica, one can use PartitionsP.
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:
I have 2 indistinguishable balls and I want to give them to 3 indistinguishable children. There are just 2 unique ways of doing this:
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?