Count integer partions with k parts, each below some threshold m

Question

I want to count the number of ways we can partition the number n, into k distinct parts where each part is not larger than m.

For k := 2 i have following algorithm:

public int calcIntegerPartition(int n, int k, int m) {

  int cnt=0;
  for(int i=1; i <= m;i++){
    for(int j=i+1; j <= m; j++){
      if(i+j == n){
        cnt++;
        break;
      }
    }
  }
  return cnt;
}

But how can i count integer partitions with k > 2? Usually I have n > 100000, k := 40, m < 10000.

Thank you in advance.

Answer 1

Let's start by choosing the k largest legal numbers: m, m-1, m-2, ..., m-(k-1). This adds up to k*m - k(k-1)/2. If m < k, there are no solutions because the smallest partition would be <= 0. Let's assume m >= k.

Let's say p = (km - k(k-1)/2) - n.

If p < 0, there are no solutions because the largest number we can make is less than n. Let's assume p >= 0. Note that if p = 0 there is exactly one solution, so let's assume p > 0.

Now, imagine we start by choosing the k largest distinct legal integers, and we then correct this to get a solution. Our correction involves moving values to the left (on the number line) 1 slot, into empty slots, exactly p times. How many ways can we do this?

The smallest value to start with is m-(k-1), and it can move as far down as 1, so up to m-k times. After this, each successive value can move up to its predecessor's move.

Now the problem is, how many nonincreasing integer sequences with a max value of m-k sum to p? This is the partition problem. I.e., how many ways can we partition p (into at most k partitions). This is no closed-form solution to this.

Someone has already written up a nice answer of this problem here (which will need slight modification to meet your restrictions):

Is there an efficient algorithm for integer partitioning with restricted number of parts?

Answer 2

As @Dave alludes to, there is already a really nice answer to the simple restricted integer case (found here (same link as @Dave): Is there an efficient algorithm for integer partitioning with restricted number of parts?).

Below is a variant in C++ which takes into account the maximum value of each restricted part. First, here is the workhorse:

#include <vector>
#include <algorithm>
#include <iostream>

int width;
int blockSize;
static std::vector<double> memoize;

double pStdCap(int n, int m, int myMax) {
    
    if (myMax * m < n || n < m) return 0;
    if (myMax * m == n || n <= m + 1) return 1;
    if (m < 2) return m;
    
    const int block = myMax * blockSize + (n - m) * width + m - 2;
    if (memoize[block]) return memoize[block];
    
    int niter = n / m;
    
    if (m == 2) {
        if (myMax * 2 >= n) {
            myMax = std::min(myMax, n - 1);
            return niter - (n - 1 - myMax);
        } else {
            return 0;
        }
    }
    
    double count = 0;
    
    for (; niter--; n -= m, --myMax) {
        count += (memoize[myMax * blockSize + (n - m) * width + m - 3] = pStdCap(n - 1, m - 1, myMax));
    }
    
    return count;
}

As you can see pStdCap is very similar to the linked solution. The one noticeable difference are the 2 additional checks at the top:

if (myMax * m < n || n < m) return 0;
if (myMax * m == n || n <= m + 1) return 1;

And here is the function that sets up the recursion:

double CountPartLenCap(int n, int m, int myMax) {
    
    if (myMax * m < n || n < m) return 0;
    if (myMax * m == n || n <= m + 1) return 1;
    if (m < 2) return m;
    
    if (m == 2) {
        if (myMax * 2 >= n) {
            myMax = std::min(myMax, n - 1);
            return n / m - (n - 1 - myMax);
        } else {
            return 0;
        }
    }
    
    width = m;
    blockSize = m * (n - m + 1);
    memoize = std::vector<double>((myMax + 1) * blockSize, 0.0);
    
    return pStdCap(n, m, myMax);
}

Explanation of the parameters:

1. n is the integer that you are partitioning
2. m is the length of each partition
3. myMax is the maximum value that can appear in a given partition. (the OP refers to this as the threshold)

Here is a live demonstration https://ideone.com/c3WohV

And here is a non memoized version of pStdCap which is a bit easier to understand. This is originally found in this answer to Is there an efficient way to generate N random integers in a range that have a given sum or average?

int pNonMemoStdCap(int n, int m, int myMax) {
    
    if (myMax * m < n) return 0;
    if (myMax * m == n) return 1;
    
    if (m < 2) return m;
    if (n < m) return 0;
    if (n <= m + 1) return 1;
    
    int niter = n / m;
    int count = 0;
    
    for (; niter--; n -= m, --myMax) {
        count += pNonMemoStdCap(n - 1, m - 1, myMax);
    }
    
    return count;
}

If you actually intend to calculate the number of partitions for numbers as large as 10000, you are going to need a big int library as CountPartLenCap(10000, 40, 300) > 3.2e37 (Based off the OP's requirement).