Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
    
If its asked not at least 1 but any numbers then or for at least 2 ?? –  Aizen Sep 4 '12 at 6:38
    
@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. –  Brian M. Scott Sep 4 '12 at 7:24
    
But inclusion-exclusion is valid when both are distinct. –  Aizen Sep 4 '12 at 7:37
    
@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. –  Brian M. Scott Sep 4 '12 at 7:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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