Register to reply

Counting partitions with two givens

by ktoz
Tags: counting, givens, partitions
Share this thread:
ktoz
#1
Dec26-07, 12:23 AM
P: 145
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/
Phys.Org News Partner Science news on Phys.org
FIXD tells car drivers via smartphone what is wrong
Team pioneers strategy for creating new materials
Team defines new biodiversity metric
al-mahed
#2
Dec27-07, 03:59 PM
P: 258
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
#3
Dec27-07, 09:49 PM
Sci Advisor
HW Helper
P: 3,684
Quote Quote by al-mahed View Post
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 [itex]a_1+a_2+\cdots+a_k=s[/itex] and [itex]a_1<a_2<\cdots<a_k[/itex].

ktoz
#4
Dec27-07, 10:20 PM
P: 145
Counting partitions with two givens

Quote Quote by al-mahed View Post
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
#5
Dec27-07, 10:25 PM
P: 258
Quote Quote by CRGreathouse View Post
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 [itex]a_1+a_2+\cdots+a_k=s[/itex] and [itex]a_1<a_2<\cdots<a_k[/itex].
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 [itex]T = \frac{n(n+1)}{2}[/itex] 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/Partiti...mber_theory%29
CompuChip
#6
Dec28-07, 03:46 AM
Sci Advisor
HW Helper
P: 4,300
I think you can reduce this to an recursively inductive problem.
Let us call [itex]N(s, m)[/itex] the number of distinct partitions of s with highest value m. Then
[tex]N(s, m) = \sum_{k = 1}^{m-1} N(s - m, k)[/tex]
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
#7
Dec28-07, 03:52 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,091
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
#8
Dec28-07, 09:10 AM
Sci Advisor
HW Helper
P: 3,684
Dynamic programming sounds a bit grandiose when all this needs is a bit of memoization, yes?
ktoz
#9
Dec28-07, 11:53 AM
P: 145
Quote Quote by CRGreathouse View Post
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
#10
Dec28-07, 12:13 PM
Sci Advisor
HW Helper
P: 3,684
Quote Quote by ktoz View Post
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);
  add_base_case(s, m, L, sum);
  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
#11
Dec28-07, 12:44 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,091
Quote Quote by CRGreathouse View Post
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
#12
Dec28-07, 12:55 PM
Sci Advisor
HW Helper
P: 3,684
Quote Quote by Hurkyl View Post
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
#13
Dec28-07, 02:47 PM
P: 145
Quote Quote by CRGreathouse View Post
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 Ramanujan stuff :)
CompuChip
#14
Dec29-07, 05:00 AM
Sci Advisor
HW Helper
P: 4,300
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
#15
Dec30-07, 05:15 AM
P: 145
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.

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
#16
Dec30-07, 01:23 PM
Sci Advisor
HW Helper
P: 4,300
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.
ktoz
#17
Dec30-07, 01:46 PM
P: 145
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
#18
May1-09, 11:28 PM
P: 81
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)


Register to reply

Related Discussions
[101]Potential energy of mass on a spring with 2 givens Introductory Physics Homework 2
Urgent help with partitions Calculus & Beyond Homework 2
Sets and Partitions Calculus & Beyond Homework 14
Let X be a set. A partition of X is a subset Set Theory, Logic, Probability, Statistics 1
Is there yet a mystery about partitions? Linear & Abstract Algebra 2