In this case, the occupancy theorem gives me a result of ${7 \choose 2} = 21$, but working it out by hand gives me $56$. I think the difference is that the order of the bins matters in my case.
Following the same type of formula, I'm guessing that the general formula that would give a result of $56$ with $n=3$ and $p=5$ is $C(n+p,n)$, but I have no idea why that would be the case. It doesn't fit with any of the occupancy formulas. The one my textbook gives is $C(n+p-1,n-1)$, but this is clearly incorrect.
Any help would be greatly appreciated. This is not homework per se, but its a very minor part of a course project in heuristic search. I just need a formula to find the worst-case search time (i.e. when all combinations are tried) against my heuristic algorithm.
Edit: The difference, as I just figured out, is that I'm interested in all of the allocations with <= 5 balls, not just with all 5 balls allocated.
$\endgroup$ 41 Answer
$\begingroup$If you’re using at most $5$ balls, then you’re looking at
$$\sum_{n=0}^5\binom{n+2}2\;.$$
More generally, if you have $r$ bins and a maximum of $n$ balls, you’re looking at
$$\sum_{k=0}^n\binom{k+r-1}{r-1}$$
assignments. A handy identity, formula $(10)$ here, takes care of this sum:
$$\sum_{k=0}^n\binom{k+r-1}{r-1}=\binom{n+r}r\;.$$
In your case that’s $\dbinom{5+3}3=56$.
$\endgroup$ 2
