Integer partitioning under constraints on number of parts and maximum elements I have an use case which requires storing and then looking up the integer partitions of numbers. So before I go and actually store all the integer partitions, I am actually trying to check if they are feasible.I have 3 questions associated with it.
Question 1
I am not actually storing all the partitions of the number rather I am storing only those which have 16 parts and maximum element used is 128 . Hence 2048 has 1 partition and everything greater than that has 0 partitions satisfying the constraints. So is there an upper bound or an approximation to find number of such partitions i.e p(n,k,m) which is number of partitions of n into k partitions with maximum partition element used being m?
Question 2
I found out that
p(16,16,128) = 1 which is 1+1+...+1(16 times)
p(2048,16,128) = 1 which is 128+128+...+128(16 times)
p(17,16,128) = 1 which is 1+1+...+2
p(2047,16,128) = 1 which is 128+128+...+127
And I checked for few more and they were similar. As in p(n,k,m) = p(2048-(n-16),k,m) and we could derive the other partition with the one I had. Is this actually true?
Question 3
What is the best algorithm that can be used to generate such integer partitions under constraints? I had seen some code on the internet which does fairly well but it doesn't eliminate the possibilities fast enough i.e for p(2048.16,128) it takes a lot of time even though there is only one such partition.
 A: You may be interested in the following (infinite) (binary) tree:

It contains all partitions of any integer $n$ at its $n$-th level, and also as a sub-tree with same root. In the picture, for instance, the partitions of $7$ are in the dotted areas.
Notice that partitions of given length are arranged in specific sub-trees, as well as partition with given maximum part.
This make this tree very convenient for fast listing of (specific kinds of) integer partitions (Question 3); it is also helpful to derive expressions to count them (Question 1).
More details are available in: The Lattice of integer partitions and its infinite extension. See in particular Algorithm 1 and Corollary 2.
A: I think you are actually defining $p(n,k,m)$ to be the number of partitions of $n$ into $k$ parts of size at most $m$.  One way to compute this is recursively by conditioning on the value $j$ of the largest part:
$$p(n,k,m)=
\begin{cases}
[n = 0] &\text{if $k=0$} \\
[1 \le n \le m] &\text{if $k=1$}\\
\sum_{j=1}^{\min(n,m)} p(n-j,k-1,j) &\text{otherwise}
\end{cases}
$$
