# Counting partitions with two givens

1. Dec 26, 2007

### ktoz

Hi

Is there a relatively easy way to calculate the number of partitions of a number given the maximum term and the count of terms?

A couple of examples:

25 has four partitions with five terms where each term is unique and the largest term is 8
{8,6,5,4,2}
{8,7,5,3,2}
{8,7,5,4,1}
{8,7,6,3,1}

10 has two partitions with 3 terms where each term is unique and the largest term is 5
{5,3,2}
{5,4,1}

For small numbers, it's pretty easy to write a filter that just iterates through all the possibilities selecting partitions with the chosen properties, but iteration becomes unfeasible as the number gets larger. Is there a way to directly calculate these values?

Thanks for any help/

2. Dec 27, 2007

### al-mahed

I do not understand what you search for... do you want to know how many partitions in the partitions of a given n have complete different numbers?

3. Dec 27, 2007

### CRGreathouse

I think the OP wants a closed-form formula (ideally) or an algorithm for f(n, k, s), the number of k-tuples in {1, 2, ..., n}^k with $a_1+a_2+\cdots+a_k=s$ and $a_1<a_2<\cdots<a_k$.

4. Dec 27, 2007

### ktoz

After looking into the terminology a bit more, I believe what I'm looking for are called distinct partitions. With that in mind, the original question can be rephrased:

Is there a way to calculate the distinct partitions of n into k parts where the value of the largest part equals m.

5. Dec 27, 2007

### al-mahed

Ok !

Find a closed-form formula should be very tough, because the original formula to calculate the partitions is already complex.

But, infact, I think the triangular numbers $T = \frac{n(n+1)}{2}$ could be usefull as a start.

Ex: calculate partitions of 21 such that all numbers are different.

T = 21 ==> n = 6 ==> 1,2,3,4,5,6 is a partition with such restrictions

in fact 1,2,3,4,5,6 is the highest number of terms such that all terms are different

in fact, given a number n, the nearest triangular number < n must show the highest number of terms such that all terms are different on all partitions of n

agree CRG?

http://en.wikipedia.org/wiki/Partition_function_(number_theory)

Last edited: Dec 27, 2007
6. Dec 28, 2007

### CompuChip

I think you can reduce this to an recursively inductive problem.
Let us call $N(s, m)$ the number of distinct partitions of s with highest value m. Then
$$N(s, m) = \sum_{k = 1}^{m-1} N(s - m, k)$$
which contains more terms, but the arguments of the N occurring on the right hand side are smaller. If you continue this, you might end up with things all like N(1, 1) or something like it and then you have just reduced the problem to keeping track of all the nested sums.

7. Dec 28, 2007

### Hurkyl

Staff Emeritus
He has a fixed number of part too, so that's

N(s, m, L) = sum_{k < m} N(s - m, k, L-1)

Also, you have to use dynamic programming to compute this efficiently -- if you implement the recursion directly, all you've done is found a complicated method of iterating over all possible partitions!

Last edited: Dec 28, 2007
8. Dec 28, 2007

### CRGreathouse

Dynamic programming sounds a bit grandiose when all this needs is a bit of memoization, yes?

9. Dec 28, 2007

### ktoz

How do you memorize the partitions of 577 or 8631 or 23,765,488,962? I actually want to use these counts in a hashing algorithm I'm playing around with, so need an efficient way to get them.

After studying hand-selected partitions that satisfy the original criteria, I observed the following:

For any given width (k-tuple?) any change in value of one term, must be balanced with an opposite change in another term. For example:
Given the partition of 25 {8,6,5,4,2} if you increment the 6 term, you need decrement either the 4 or the 2 terms. You can't increment/decrement the 5 in the first iteration, because that would create a duplicate term.

So one possible relationship between "successive" partitions of width 5 would be

a1 + a2 + a3 + a4 + a5 = a1 + (a2 - 1) + a3 + (a4 + 1) + a5

The solution to the original problem seems to be coming up with a way to count the number of valid pair changes for any given width (k-tuple).

Last edited: Dec 28, 2007
10. Dec 28, 2007

### CRGreathouse

That's memoization: I'd never suggest that someone memorize all the partitions. I have enough trouble just memorizing my own address and phone numbers!

The memoization I'm suggesting is simply changing

Code (Text):
N (s, m, L) {
if (is_a_base_case (s, m, L))
return base_case (s, m, L);
sum = 0;
for (k = 1; k < m; k++)
sum += N (s - m, k, L-1);
return sum;
}
to

Code (Text):
N (s, m, L) {
if (is_a_base_case (s, m, L))
return base_case (s, m, L);
sum = 0;
for (k = 1; k < m; k++)
sum += N (s - m, k, L-1);
return sum;
}
Actually the problem is more complicated in calculation than I first thought, and full-fledged dynamic programming might not be a bad idea after all.

Last edited: Dec 28, 2007
11. Dec 28, 2007

### Hurkyl

Staff Emeritus
Interestingly enough, I also thought of "dynamic programming" as only referring to the bottom-up approach -- I had originally written "store intermedaite values in a lazy array so they can be reused later" as an option. But then I checked wikipedia, and noticed that the term covers both the bottom-up and the top-down approach.

12. Dec 28, 2007

### CRGreathouse

I do think of lazy evaluation as a kind of dynamic programming, just a simple one. But I'm not sure now if naive memoization is the best way to solve this problem, as I wrote above. There seems to be enough structure to support something else... let me think.

13. Dec 28, 2007

### ktoz

Whew! I already know I'm out of my league posting here, but am glad to hear that you guys can't just memorize partitions of arbitrary numbers. That's spooky Ramanujan stuff :)

14. Dec 29, 2007

### CompuChip

I used kotz idea to draw up an algorithm that will generate all possibilities. I am not sure how efficient it is though...

First, start by finding the partition with the highest possible numbers,e.g. {8, 7, 6, 3, 1}).
We cannot touch the highest one.
Now one by one, try to vary the numbers.
- We can lower the 7 by one, then we must lower the 6 by one (continue until all numbers are again unique -- if you get a zero somewhere we are done). We now have the sequence {8, 6, 5, 3, 1} but we have lowered the total by 2, so we must add it again. We cannot touch the 8, 6 and 5 because we have worked them already, so we must distribute this over the 3 and 1.
Note that we can add at most 1 to the 3.
-- Add the maximum to 3. Then the remaining 1 must be added to the 1, giving {8, 6, 5, 4, 2}
-- Loop all the possibilities...
-- In this case, only one is left: add nothing to 3. Then 2 would have to be added to the 1, but that gives {8, 6, 5, 3, 3} which is not a valid partition.
- Now lower the 6 by 1, 2 and 3 (6 - 3 gives the first overlap with the next lowest number):
-- Lowering by one produces {8, 7, 5, 3, 1} and reduces the total by one. We can add this to either the 3 or the 1, both produce valid partitions {8, 7, 5, 4, 1} and {8, 7, 5, 3, 2}.
-- Lowering by two produces {8, 7, 4, 3, 1} and reduces the total by two.
--- The three can be raised maximally by 0 (adding one would yield an invalid partition). Then the one can be raised maximally by 1. We cannot add two and get a valid partition.
-- Lowering the 6 by 3 and shifting to get a unique partition gives {8, 7, 3, 2, 1} with two short in the total. We can add maximally 0 to the 2 and 0 to the 1 in order not to get double digits, so we must add 2 but can only add 0 -- no valid partitions.
- Lowering the 3 by 1 and 2 (3 - 2 gives the next lowest number):
-- Lowering 3 by 1 gives {8, 7, 6, 2, 1}. We can add no more than 0 to the 1, but we must add 1 to get the total right, so no valid sequence.
-- Lowering 3 by 2 and shifting the rest to get unique numbers gives {8, 7, 6, 1, 0} which is not valid to begin with.

So basically it comes down to this
Code (Text):

P = {partition with highest numbers} = { P(1), P(2), ..., P(L) };
for i = 2 to length(p) {
let p = P;
for each k such that p(i) >= p(i) - k >= p(i + 1) {
p(i) -> p(i) - k
for j = i + 1 to L {
if p(j) = p(j - 1) then p(j) -> p(j) - 1
}
if p(L) = 0 then sequence ends in zero => break;
diff = sum(P) - sum(p) = difference in wanted total and current total;
for each n1 such that p(i+1) + n1 < p(i)
for each n2 such that p(i+2) + n2 < p(i+1)
...
for each n.. such that p(L-1) + n.. < p(L)
{
check if {p(1), p(2), ..., p(i), p(i+1)+n1, p(i+2)+n2, ..., p(L-1)+n.., p(L) + (diff - n1 - n2 - ... - n..) } is a valid sequence
}
}
}

Last edited: Dec 29, 2007
15. Dec 30, 2007

### ktoz

Thanks CompuChip

I'm having a little trouble following all the loop nesting so I think I'll try to rewrite it using recursive functions to eliminate some of that.

After studying the problem some more, I think the counts might be calculable using a normal distribution.

The partition with the smallest maximum for any number v can be found by solving v = w(w + 1) / 2 for w which I packaged up into the following C function.

Code (Text):

int pmax(int inNum)
{
int width = (pow(8 * inNum + 1, .5) - 1) / 2;

return (width * (width + 1) / 2 == inNum) ? width : ++ width ;
}

The partition with the largest maximum will be the number itself so the partition "families" (ie: all possible max values for a given number v) will lie in the range v - pmax(v). The mid point of this range ( (v - pmax(v)) / 2 ) has the highest number of partitions with the same max value.

I plotted out the distinct partitions for a few numbers and they definitely follow a distribution curve of some sort. I don't really understand the formula for distribution curves so don't know if there's enough info with the min, max, mid and number of steps to enable calculating the count for specified widths and max value.

Are the above-mentioned variables enough to generate a distribution curve? If so, how? And c an the curve be used to calculate the number of partitions with a specific max value?

Last edited: Dec 30, 2007
16. Dec 30, 2007

### CompuChip

Don't know if it will help you at all, but I found this article just now. Probably nothing, but maybe you will find an idea there.

17. Dec 30, 2007

### ktoz

Further plugging revealed that the minimum distinct partition of number n with width w can often be expressed as the partition of a smaller number m whose values are shifted by s

For example: The smallest partition of 37 with width 6 = the smallest partition of 25 with width 6 where each value is shifted by 2. Using the C shift operator, it can be expressed like this:

pmin(37, 6) = pmin(25, 6) << 2 = 1 + 2 + 4 + 5 + 6 + 7 << 2 = 3 + 4 + 6 + 7 + 8 + 9 = 37
pmin(42, 6) = pmin(24, 6) << 3 = 1 + 2 + 3 + 5 + 6 + 7 << 3 = 4 + 5 + 6 + 8 + 9 + 10 = 42

pmin(23, 4) = pmin(11, 4) << 3 = 1 + 2 + 3 + 5 << 3 = 4 + 5 + 6 + 8 = 23
pmin(32, 4) = pmin(12, 4) << 5 = 1 + 2 + 4 + 5 << 5 = 6 + 7 + 9 + 10 = 32

pmin(13, 3) = pmin(7, 3) << 2 = 1 + 2 + 4 << 2 = 3 + 4 + 6 = 13
pmin(29, 3) = pmin(8, 3) << 7 = 1 + 3 + 4 << 7 = 8 + 10 + 11 = 29

etc...

The minimum and maximum distinct partitions for a given number and width can be generated with these functions

Code (Text):

int* pmin(int inNum, int inWidth)
{
int wsum        = psum(inWidth),
*result     = NULL;

// make sure number can support partitions of inWidth
if (wsum <= inNum)
{
// allocate result
result      = malloc(inWidth * sizeof(int));
if (result != NULL)
{
int dif = psum(inWidth + 1) - (inNum - wsum) % inWidth - wsum,
shift   = (inNum - wsum) / inWidth,
*s  = result,
*e  = s + inWidth,
i   = 1;

// fill in partition values
while (s < e)
{
if (i != dif)
{
*(s++)  = i + shift;
}

i++;
}
}
}

return result;
}

int* pmax(int inNum, int inWidth)
{
int wsum    = psum(inWidth),
*result = NULL;

// make sure number can support partitions of inWidth
if (wsum <= inNum)
{
// allocate result
result      = malloc(inWidth * sizeof(int));
if (result != NULL)
{
int max = inNum - psum(inWidth - 1),
w   = 1,
*s  = result;

// set the low values
while (w < inWidth)
{
*(s++)  = w++;
}

// set the max value
*s  = max;
}
}

return result;
}

inline
int psum(int inNum)
{
return inNum * (inNum + 1) / 2;
}

This shifting trick brings up the possibly interesting/useful point that, for any choice of width, w, there are exactly w distinct "families" of partitions. That is, all partitions of width w are in some way expressible as a shift and increment of the base partitions for w.

Now, on to the pinc (partition increment) functions...

Last edited: Dec 30, 2007
18. May 1, 2009

### alphachapmtl

If you want to count the partitions of 25 with 5 terms where each term is unique and the largest term is 8,
then you need to count the partitions of (25-8)=17 with (5-1)=4 terms where each term is unique and smaller than 8.
(that's not a final answer but it could help)