1
$\begingroup$

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 Answers 1

0

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.

See this Wikipedia article.