Integer Partition Restriction: Solving for q When k is Limited

  • Thread starter ghotra
  • Start date
  • Tags
    partitions
In summary, the number of integer partitions is given by partition function p(q). The number of partitions is unrestricted. The number of partitions is restricted when k is an integer. There is no closed form solution to determining the number of integer partitions.
  • #1
ghotra
53
0
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?
 
Last edited:
Physics news on Phys.org
  • #2
Here is a much better statement of my question:

How many integer solutions exist to the following equation:

[tex]
\sum_{i=1}^k n_i = N
[/tex]

Let me call this number [itex]p(N,k)[/itex]. 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 [tex]k \geq N[/tex], then [tex]p(N,k) = p(N)[/tex] 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:

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

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:
  • #3
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:
  • #4
Thanks. A quick look did not reveal any information on restricting the partitions as I discussed. Any other ideas?
 
  • #5
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
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
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
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
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
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
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.
 

1. What is an integer partition?

An integer partition is a way of expressing a positive integer as the sum of other positive integers. For example, the integer partition of 5 can be expressed as 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, and 1+1+1+1+1.

2. What is the "Integer Partition Restriction" problem?

The "Integer Partition Restriction" problem involves finding the number of ways to partition a given integer q into smaller positive integers, with the additional restriction that the largest integer in the partition cannot exceed a certain value k. In other words, we are looking for the number of ways to write q as a sum of smaller positive integers, with the largest integer being no greater than k.

3. Why is solving for q when k is limited important?

Solving for q when k is limited is important because it allows us to understand the different ways in which a given integer can be partitioned with a specific restriction. This can have applications in various fields such as number theory, combinatorics, and computer science.

4. How is the "Integer Partition Restriction" problem solved?

The "Integer Partition Restriction" problem can be solved using various methods such as generating functions, recurrence relations, and dynamic programming. These methods involve breaking down the problem into smaller subproblems and using mathematical equations or algorithms to find the solution.

5. Can the "Integer Partition Restriction" problem be extended to higher dimensions?

Yes, the "Integer Partition Restriction" problem can be extended to higher dimensions, such as partitioning a given integer into a sum of smaller integers with restrictions on two or more dimensions. This can be visualized as partitioning a 3D cube or a higher-dimensional hypercube into smaller cubes with certain restrictions.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
13
Views
262
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
12
Views
913
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
1K
  • Set Theory, Logic, Probability, Statistics
5
Replies
174
Views
9K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
829
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
Replies
5
Views
2K
Back
Top