# Restricted Partitions

1. Sep 9, 2006

### ghotra

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:

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?

Last edited: Sep 9, 2006
2. Sep 9, 2006

### ghotra

Here is a much better statement of my question:

How many integer solutions exist to the following equation:

$$\sum_{i=1}^k n_i = N$$

Let me call this number $p(N,k)$. It is the number of partitions for N such that the partitions are restricted to be of order k or less.

Example:

N = 5
k = 3
p(5,3) = 5

The solutions are:

(5,0,0)
(4,1,0)
(3,2,0)
(3,1,1)
(2,2,1)

Notice, if $$k \geq N$$, then $$p(N,k) = p(N)$$ where p(N) is the number of integer partitions of N.
http://en.wikipedia.org/wiki/Integer_partition

Notice, we do not care about the ordering. If we did care about the ordering, then there woudl be 21 solutions.

3!/2! of (5,0,0)
3! of (4,1,0)
3! of (3,2,0)
3!/2! of (3,1,1)
3!/2! of (2,2,1)
====
21

This number is:

$$\binom{5+(3-1)}{(3-1)} = \frac{[5+(3-1)]!}{(3-1)!5!}$$

Again, I would like to remove the degneracy due to permutations. So I want 21 -> 5, in this example. What is the general solution? The is no closed for solution for p(N)...so I am not expecting a closed-form solution. Any thoughts?

Last edited: Sep 9, 2006
3. Sep 10, 2006

### CRGreathouse

Sloane's http://www.research.att.com/~njas/sequences/A000041 [Broken] has some information on this: asymptotics, upper bounds, precalculated numbers, and various generating functions.

Last edited by a moderator: May 2, 2017
4. Sep 10, 2006

### ghotra

Thanks. A quick look did not reveal any information on restricting the partitions as I discussed. Any other ideas?

5. Sep 11, 2006

### CRGreathouse

I shomewhat misread the queston, so there isn't all I said there was there. It does have this:

a(n)=sum(i=0, n-1, P(i, n-i)), where P(x, y) is the number of partitions of x into at most y parts, and P(0, y)=1. - Jon Perry (perry(AT)globalnet.co.uk), Jun 16 2003

at least. A000012, A004526, and A001399 are the partition numbers for at most/exactly (1, 2, 3) partitions, modulo a shift in the offsets. Euler's table, A026820, has the general result (see also A008284 for "exactly" rather than "at least").

http://www.users.globalnet.co.uk/~perry/maths/morepartitionfunction/morepartitionfunction.htm
has a general result that may be useful.

6. Sep 12, 2006

### ghotra

Wonderful! So, it doesn't appear that there is a closed form solution to this. However, the recurrence relation is quite nice, along with the Euler triangle.

Thanks!

7. Jul 9, 2010

### jleach

I just ran across this thread, and it looks as if I'm a few years too late. But, if anyone is interested, I have some expertise on this topic. Not to brag, but several years ago, I independently discovered partitions and an approach to solve them, before I finally learned that I had been beaten to the glory by about 200 years. I've also discovered a way to determine the number of integer partitions that contain no repeated numbers. In other words, 2,2 would not be counted as a partition of 4. I'm just a mathematician by hobby, so I don't get published and a lot of times I reinvent the wheel. I don't find the time that I used to have, but I am sitting on a lot of past work that I'd like to share, just in case it would do someone some good.

8. Oct 7, 2010

### jleach

Before I leave for the weekend, I'll give you a preview of what I can remember. Let's first assign the function F(n) to be the procedure for generating the number of partitions for the number n. Let k be a number equal to or less than n. The number of partitions that contain the value k at least one time is F(n-k). But, that is old news. If S is a set of values, we can also let k be the sum of those values within the set. F(n-k) will tell me how many partitions of n contain the set at least once. Now for the number of partitions of n that contain no repeated values, I must double check my notes to be certain, but I know that k is calculated from the sum of natural numbers. I'll try to confirm and give you details next week.

9. Oct 11, 2010

### jleach

I'm back and I've reviewed my notes. Restricted partitions is a little more complex than I described above, but not bad. The first thing that you'll need is a partition table like the one that I posted on Wikipedia (Search for "Integer Partitions" or "Partition (Number Theory)", then look under the section "See also". My table is the link called "Leibniz's distribution table for integer partitions". Leibniz is the one who beat me to the discovery. This table is actually two overlapping tables. One is for partitioning finite integers and the other is for partitioning infinity. You'll want to use the column for finite integers. From what I've read, everyone should already know the pattern to recreate this table. The stage values tell you how many ways you are going to divide the integer, but the stage values run opposite the number of divisions. For example, stage 1 will always be a set of all ones, but there will be N one's within that set.

As I said before, this is a fractal pattern that can only be described in terms of the repeating pattern within the table. Therefore, my solutions are in terms of the table coordinates. The next thing to remember is that the table coordinate (Column 0 Row 0) = 1.

Here's the solution:
Let N = The integer to be partitioned
Let S = The number of spaces or divisions of that number
Let E = Summation of i as i goes from 1 to S
Let L = Greatest integer function of (-1+sqrt(1+8*N))/2
The number of partition sequences without repeated values at S divisions is the coordinate (Column N-E+1, Row N-E+S).
Therefore, the total number of partitions sequences without repeated values is:
Summation of S from 1 to L of (Column N-E+1, Row N-E+S).

To check a practice run, let N=14. The answer should be 1 + 6 + 10 + 5 = 22

10. Oct 11, 2010

### jleach

P.S. If by chance you get a table coordinate with negative numbers, the table value is zero. Example: Column 4 Row -3 = 0

11. Oct 12, 2010

### jleach

FYI, You can generate a new table for partitions without repeats and it is also a fractal, but with a slightly different rule. I thought that I'd mention this, because if you are only interested in partition sequences without repeated values, then this approach may be a faster computing method.