Wolfram Mathworld:
P(n, k) denotes the number of ways of writing n as a sum of exactly k
terms or, equivalently, the number of partitions into parts of which
the largest is exactly k. (Note that if "exactly k" is changed to "k
or fewer" and "largest is exactly k," is changed to "no element
greater than k," then the partition function q is obtained.) For
example, P(5, 3) = 2, since the partitions of 5 of length 3 are {3, 1, 1}
and {2, 2, 1}, and the partitions of 5 with maximum element 3 are {3, 2}
and {3, 1, 1}.
...
P(n, k) can be computed from the recurrence relation
P(n, k) = P(n-1, k-1) + P(n-k, k)
(Skiena 1990, p. 58; Ruskey) with P(n, k) = 0 for k > n, P(n, n) = 1, and
P(n, 0) = 0.
So if we want to calculate the number of ways of writing n as a sum, we should calculate-

Let's define P(n, k):
def p(n, k):
"""Gives the number of ways of writing n as a sum of exactly k terms or, equivalently,
the number of partitions into parts of which the largest is exactly k.
"""
if n < k:
return 0
if n == k:
return 1
if k == 0:
return 0
return p(n-1, k-1) + p(n-k, k)
Now we can calculate the number of ways of writing n
as a sum:
n = 6
partitions_count = 0
for k in range(n + 1):
partitions_count += p(n, k)
print(partitions_count)
# Output:
# 11
As p(n, k)
is a recursive function, you can boost the speed by saving values of each p(n, k)
in a dictionary (thanks to the fast hash-based search!) and check if we have calculated the value (check if the value is in the dictionary) before calculating:
dic = {}
def p(n, k):
"""Gives the number of ways of writing n as a sum of exactly k terms or, equivalently,
the number of partitions into parts of which the largest is exactly k.
"""
if n < k:
return 0
if n == k:
return 1
if k == 0:
return 0
key = str(n) + ',' + str(k)
try:
temp = dic[key]
except:
temp = p(n-1, k-1) + p(n-k, k)
dic[key] = temp
finally:
return temp
Full function:
def partitions_count(n):
"""Gives the number of ways of writing the integer n as a sum of positive integers,
where the order of addends is not considered significant.
"""
dic = {}
def p(n, k):
"""Gives the number of ways of writing n as a sum of exactly k terms or, equivalently,
the number of partitions into parts of which the largest is exactly k.
"""
if n < k:
return 0
if n == k:
return 1
if k == 0:
return 0
key = str(n) + ',' + str(k)
try:
temp = dic[key]
except:
temp = p(n-1, k-1) + p(n-k, k)
dic[key] = temp
finally:
return temp
partitions_count = 0
for k in range(n + 1):
partitions_count += p(n, k)
return partitions_count
Helpful links: