Approximate Restricted Integer Partition With Exact Part Number

I'm interested in a certain type of mathematical structure this week: integer partitions. An integer partition, p(n), is the set of sets of integers that add up to n. For example,

• p(3) = 1 + 1 + 1, 1 + 2, 3
• p(4) = 1 + 1 + 1 + 1, 1 + 1 + 2, 2 + 2, ...

Each grouping of integers that add up to n is a partition. I'm interested in partitions where the number of integers is fixed, the order is fixed, and the integers are bounded. This makes more sense if you view it as a problem of putting numbers into boxes. Let's say you have four boxes:        . You want to partition 8. An example would be then: 2 3 1 2. Or perhaps 2 2 2 2.

The next restriction is on the bounds of each number. With the previous example, let's say I now restrict each integer to be less than 4. So 3 3 0 2 would work. I'll call this function b(n, m, k) where n is the sum to partition, m is the number of parts, and k is the maximum at each position. The range of b will 0 through infinity because I'm going to have it count the number of partitions, not be the set of partitions.

An algorithm to calculate b(n, m, k) is given below in python. It works exactly like you would expect: enumerating the exponential number of partitions. The only trick it does is know when a partition it is trying will fail. For example, if you're trying to do the previous example and you have 1 0    , there are no two other numbers that will cause the partition to sum to 8 (1 + 0 + 3 + 3 = 7). That helps reduce the number of partitions it attempts. Here's the code:

#Recursive restricted block partition. Each call reduces the sum, n,
# and m, the number of parts.
def blockpart(n, m, k):
    
    #Is the number of parts only 1?
    if(m == 1):
        #Trivial: to partition n into one part, we need to be able to use  n
        if(n < k):
            return 1
        else:
            return 0
    #what is the highest possible sum we may have
    #that will still be a valid partition
    smax = m * (k - 1)
    #This is the lowest term we can add to the partition (subtract from sum)
    start = n - k + 1

    #If the lowest is too high, then we aren't able to get a valid partition
    if( start > smax):
        return 0

    paths = 0

    #add up all possible other partitions after subtracting choices
    #to place in the current part (m)
    for i in range(max(0,start), 1 + min(smax, n)):
        paths += blockpart(i, m - 1, k)

    return paths

Anyway, it turns out that as n grows, it may be approximated by the equation:


 Who discovered that equation? Me. And I'm sure many other people. Here's the fit of the equation, where the dots are the results of the python program and the red lines are the approximation.

 


Find out next time on Crows and Cats how I derived that equation!