# Counting partitions with two givens

by ktoz
Tags: counting, givens, partitions
 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/
 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?
HW Helper
P: 3,682
 Quote by 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?
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$.

P: 145
Counting partitions with two givens

 Quote by 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?
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.
P: 258
 Quote by 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 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}$ 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
 Sci Advisor HW Helper P: 4,300 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.
 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, 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!
 Sci Advisor HW Helper P: 3,682 Dynamic programming sounds a bit grandiose when all this needs is a bit of memoization, yes?
P: 145
 Quote by CRGreathouse 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).
HW Helper
P: 3,682
 Quote by 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.
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);
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.
Emeritus
PF Gold
P: 16,091
 Quote by CRGreathouse 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.
HW Helper
P: 3,682
 Quote by Hurkyl 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.
P: 145
 Quote by CRGreathouse 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 :)