Counting partitions with two givens

[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/

 

[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?

 

[CRGreathouse]

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?

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$.

 

[ktoz]

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?

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.

 

[al-mahed]

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$.

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)

 

[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.

 

[Hurkyl]

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!

 

[CRGreathouse]

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

 

[ktoz]

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

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).

 

[CRGreathouse]

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.

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

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

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);
  [color=blue]add_base_case(s, m, L, sum);[/color]
  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.

 

[Hurkyl]

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

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.

 

[CRGreathouse]

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.

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.

 

[ktoz]

I have enough trouble just memorizing my own address and phone numbers!

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 http://en.wikipedia.org/wiki/Ramanujan" stuff :)

 

[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

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
          }
  }
}

 

[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 http://en.wikipedia.org/wiki/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.

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?

 

[CompuChip]

Don't know if it will help you at all, but I found http://www.artofproblemsolving.com/Resources/Papers/LaurendiPartitions.pdf just now. Probably nothing, but maybe you will find an idea there.

 

[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

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...

 

[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)