Ex: 7 coins, 7 players, players and coins are indistinguishable. There are 15 kinds of partitions:
(1, 1, 1, 1, 1, 1, 1)
(2, 1, 1, 1, 1, 1, 0)
(2, 2, 1, 1, 1, 0, 0)
(2, 2, 2, 1, 0, 0, 0)
(3, 1, 1, 1, 1, 0, 0)
(3, 2, 1, 1, 0, 0, 0)
(3, 2, 2, 0, 0, 0, 0)
(3, 3, 1, 0, 0, 0, 0)
(4, 1, 1, 1, 0, 0, 0)
(4, 2, 1, 0, 0, 0, 0)
(4, 3, 0, 0, 0, 0, 0)
(5, 1, 1, 0, 0, 0, 0)
(5, 2, 0, 0, 0, 0, 0)
(6, 1, 0, 0, 0, 0, 0)
(7, 0, 0, 0, 0, 0, 0)
They are generated by a simple recursive program. For large coins and players, it can only enumerate partitions one by one, rather than tell me the total size. Is there a way to directly compute how many kinds of partitions it has?
This is a well studied problem in combinatorics and the name is in fact partition.
There is no simple closed form, but there are some recurrence relations, and perhaps more interestingly a generating function as well as asymptotic estimates. We have:
\begin{align} \sum_{n\geq 0}\,p(n)\,x^n &= \prod_{k\geq 1}\,\left(\frac1{1-x^k}\right) \\&= (1+x+^2+x^3+\dots)\,(1+x^2+x^4+x^6+\dots)\,(1+x^3+x^6+x^9+\dots)\cdots \end{align}
and
$$\lim_{n\to\infty} \frac{\frac1{4n\sqrt3}\,\exp\left(\pi\sqrt{\frac{2n}3}\right)}{p(n)} = 1.$$