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$$


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

  • $\begingroup$ If its asked not at least 1 but any numbers then or for at least 2 ?? $\endgroup$ – Aizen Sep 4 '12 at 6:38
  • $\begingroup$ @Aizen: If each box must contain at least two objects, an inclusion-exclusion argument 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. $\endgroup$ – Brian M. Scott Sep 4 '12 at 7:24
  • $\begingroup$ But inclusion-exclusion is valid when both are distinct. $\endgroup$ – Aizen Sep 4 '12 at 7:37
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Sep 4 '12 at 7:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.