1
$\begingroup$

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$

1 Answers 1

4

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\;.$

  • 0
    @Aizen: I don’t understand what you’re trying to say. Inclusion-exclusion is a general technique that is applicable in a wide variety of situations.2012-09-04