Register to reply 
Counting partitions with two givens 
Share this thread: 
#1
Dec2607, 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/ 


#2
Dec2707, 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?



#3
Dec2707, 09:49 PM

Sci Advisor
HW Helper
P: 3,684




#4
Dec2707, 10:20 PM

P: 145

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


#5
Dec2707, 10:25 PM

P: 258

Find a closedform 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 


#6
Dec2807, 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}^{m1} 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. 


#7
Dec2807, 03:52 AM

Emeritus
Sci Advisor
PF Gold
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, L1) 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! 


#8
Dec2807, 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?



#9
Dec2807, 11:53 AM

P: 145

After studying handselected partitions that satisfy the original criteria, I observed the following: For any given width (ktuple?) 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 (ktuple). 


#10
Dec2807, 12:13 PM

Sci Advisor
HW Helper
P: 3,684

The memoization I'm suggesting is simply changing



#11
Dec2807, 12:44 PM

Emeritus
Sci Advisor
PF Gold
P: 16,091




#12
Dec2807, 12:55 PM

Sci Advisor
HW Helper
P: 3,684




#13
Dec2807, 02:47 PM

P: 145




#14
Dec2907, 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



#15
Dec3007, 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.
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 abovementioned 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? 


#16
Dec3007, 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.



#17
Dec3007, 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
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... 


#18
May109, 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 (258)=17 with (51)=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 