Can you solve this recurrence relation?

69 Views Asked by At

The function $M(n,s)$ represents the number of ways to distribute n indistinguishable objects into s different containers/sets. It adheres to the following recurrence relation:

$M(n,s+1) = \sum^{n}_{k = 0} M(k,s)$

If anyone could find a closed form expression of $M(n,z)$ or tell me why it's not possible to find it i would greatly appreciate it.

Note: $M(1,s) = s$ and $M(n,1) = 1$

1

There are 1 best solutions below

2
On BEST ANSWER

its actually a question about Combinatorics, the number of ways to distribute n indistinguishable objects into s different containers/sets equals to ${n+s-1 \choose n}$. in the equation you wrote, its can be represent as recursive call cause the sigma is for all the ways to put the rest of the objects (the $n-k$) in the $(s+1)$'s container/set, and to distribute the $k$ into the other $s$ baskets.