[Math] Distribute distinct objects in identical boxes

Question

Number of ways to distribute $6$ distinct objects to $3$ identical boxes such that each box should have atleast one?

$\mathbf {Is\ there\ any\ standard\ formula\ for\ these\ sums}$, as we have for $\langle identical\ object,\ distinct\ box\rangle$ pair as $$N+R-1\choose R-1$$

Answer 1

These numbers are the Stirling numbers of the second kind; the specific one that you mention is denoted by $\left\{6\atop 3\right\}$ or $S(6,3)$. These numbers satisfy a fairly simple recurrence relation that is reminiscent of the relation $\dbinom{n+1}k=\dbinom{n}k+\dbinom{n}{k-1}$ satisfied by the binomial coefficients:

$$\left\{n+1\atop k\right\}=k\left\{n\atop k\right\}+\left\{n\atop k-1\right\}\;,$$

with initial conditions $\left\{0\atop 0\right\}=1$ and $\left\{n\atop 0\right\}=\left\{0\atop n\right\}=0$ for $n>0$.

Added: This recurrence isn’t hard to prove. Consider the ways of partitioning the integers $1,\dots,n+1$ into $k$ non-empty sets. We can start with a partition of $\{1,\dots,n\}$ into $k-1$ non-empty sets and make $\{n+1\}$ the $k$-th set; there are $\left\{n\atop k-1\right\}$ ways to do this. Or we can partition $\{1,\dots,n\}$ into $k$ non-empty sets and add $n+1$ to one of those $k$ sets; there are $k\left\{n\atop k\right\}$ ways to do this. The total number of possibilities is therefore $k\left\{n\atop k\right\}+\left\{n\atop k-1\right\}$.

There is an explicit formula for $\left\{n\atop k\right\}$, but it’s rather ugly:

$$\left\{n\atop k\right\}=\frac1{k!}\sum_{i=0}^k(-1)^{k-i}\binom{k}ii^n\;.$$