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
    If its asked not at least 1 but any numbers then or for at least 2 ??2012-09-04
  • 0
    @Aizen: If each box must contain at least two objects, an [inclusion-exclusion argument](http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle) shows that the number of arrangements is $$\sum_{i=1}^{k-1}(-1)^{k-1}\binom{n}i\left\{n-i\atop k-i\right\}\;.$$ It’s entirely possible that this can be simplified, but I don’t immediately see anything nice. After the ‘at least $2$’ case it looks to be getting really messy; I’d probably try to work with generating functions at that point.2012-09-04
  • 0
    But inclusion-exclusion is valid when both are distinct.2012-09-04
  • 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