# How many natural multisets exist with a given sum?

Given natural number $n$, how many multisets are there which sum of their elements equals $n$?

There is a recursive function which can give the value in $O(n^2)$, but is there a formula for that?

$f(n,i)$ = answer where minimum elements of multisets are at least $i$.

$f(n,i) = 1$ for $n=0$

$f(n,i) = 0$ for $i>0$

$f(n,i) = f(n,i+1) + f(n-i,i)$ for $0 < i \le n$

-

## 1 Answer

If you're speaking only of positive integers, then you're talking about partitions of an integer. There is an extensive literature on this topic.

-