CODEWITHSUNDEEP
integercombinatoricsnumber-theory
klocey
klocey

Reputation: 334

Finding the number of integer partitions given a total, a number of parts, and a maximum summand

I'm looking for the number of integer partitions for a total N, with a number of parts S, having a maximum part that is exactly X, without enumerating all of them.

For example: all partitions of 100 that have 10 parts and 42 as the largest part.

I've found no theorems or partitioning identities that address this question and I suspect that is a non-trivial problem that is not easily derived from known theorems (e.g. Nijenhuis and Wilf 1978, Andrews et al. 2004, Bona 2006):

For example: The number of partitions of N with exactly S parts equals the number of partitions of N with exactly S as the largest part.

This question is related to my research, which is far-outside pure math.

Update: This question is answered below but I wanted to post the Python script I used to implement it. I'll probably push it through Cython to get some speed.

n = 100 # the total
s = 10  # number of parts
x = 20  # largest part
print Partitions(n,length=s,max_part=x).cardinality() # Sage is very slow at this

def parts_nsx(n,s,x):
    if n==0 and s==0:return 1
    if n<=0 or s<=0 or x<=0:return 0
    if n>0 and s>0 and x>0:
        _sum = 0
        for i in range(0,s+1):
            _sum += parts_nsx(n-i*x, s-i, x-1)
        return _sum    
print parts_nsx(n,s,x)

Upvotes: 3

Views: 2023

Answers (1)

Ante
Ante

Reputation: 5448

For this number of partitions recursion P(n,s,x) holds:

P(n,s,x) = sum P(n-i*x, s-i, x-1), for i=0,...,s 
P(0,0,x) = 1
P(n,s,x) = 0, if n <= 0 or s <= 0 or x <= 0

Calculation is not efficient, maybe in your examples it will be fast enough.

It is the best to implement using memoization.

Edit:

Python implementation with memoization:

D = {}
def P(n,s,x):
  if n > s*x or x <= 0: return 0
  if n == s*x: return 1
  if (n,s,x) not in D:
    D[(n,s,x)] = sum(P(n-i*x, s-i, x-1) for i in xrange(s))
  return D[(n,s,x)]

P(100, 10, 42)
2685871

Update:

Partition that satisfy parameters n,s,x can have i partitions of maximal size x. By removing these i parts with size x we get same problem with parameters n-i*x, s-i, x-1. E.g. partition of 100 that have 10 parts and 42 as the largest part, can have 0, 1 or 2 parts of size 42.

P(0,0,x) = 1 means that we already have partition in previous iterations.

P(n,s,x) = 0, if n>s*x means that we can't partition n with all partitions of maximal size, so it is not possible combination of parameters. Boundary conditions are

Upvotes: 1

Related Questions