In how many ways can we distribute $r$ distinct balls in $n$ identical
boxes so that none is empty?
Note that,
At once, a ball can only lie in exactly one box.
If at first, we consider boxes to be different, let the boxes be $\{b_1\ldots , b_n\}$ and let us call the action of putting balls in these boxes as $f$, then $f$ is a function since all balls must be put (domain must used completely), and a ball can be put in exactly one of the boxes (well defined)
Now note, that $f^{-1}(b_i)\neq \phi$ since $f$ is onto, i.e, all boxes should be non empty. Moreover,
$f^{-1}(b_i)\cap f^{-1}(b_j)= \phi \; \forall \; i\neq j$ as $f$ is well defined.
and $\cup_{i=1}^{n}f^{-1}(b_i ) = \text{the set of all r balls}$
So, we are basically partitioning the set of $r$ balls into $n$ non empty subsets.
But since our boxes are identical, we are looking for unordered partitions which is given by $S(r,n)$ where $S$ is Stirling's Number of $2nd$ kind.
Is my interpretation correct? Please correct me wherever I am going wrong. This is very important to me
Best Answer
Since the bins are undistinguishable, you can always arrange them in a non-decreasing (or v.v.) order wrt the number of balls contained.
Then, since the balls are instead distinguishable, you shall make clear if inside each bin the order of the balls is taken into account, or not. That leads to different computations.
In either case, you can sub-arrange the bins with equal number of balls, according to the first /lower index of the balls that each contains.
If the order of the balls is taken into account, that is if e.g. the bin $[1,4,5]$ is considered different from $[1,5,4]$, then you are computing the partitions of a $r$-tuple into $n$ parts (non empty).
In this case the computation is intricated. In fact it is not just $r!$ times the scheme "undist. - undist.", which would be the number of partitions of $r$ into exactly $n$ parts. Take in fact two bins containing $[1,2],[3,4]$. This configuration is considered the same as $[3,4],[1,2]$.
To my knowledge there is not a closed formula for this case.
If instead the order of the balls is not taken into consideration, so the bin $[1,4,5]$ is considered same as $[1,5,4]$, then for the re-arrangement told above, you are actually splitting the set $\{1,2, \cdots, r \}$ into a set of $n$ non empty subsets, and that is the Stirling N. of 2nd kind.