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.

I was hoping I could receive some clarification into the the four cases:

  1. Placing labeled balls in unlabeled boxes with repetition.

  2. Placing labeled balls in unlabeled boxes without repetition.

  3. Placing unlabeled balls in unlabeled boxes with repetition.

  4. Placing unlabeled balls in unlabeled boxes without repetition.

I just want an intuitive understanding of the four cases. How many ways are there to arrange, say, 4 balls into 9 boxes or 9 balls into 4 boxes in each case above, and why?

share|improve this question
    
I think I saw a very similar question very recently, just with "ordered" instead of "labeled", but I can't find it now. Was that yours? –  joriki Dec 18 '12 at 23:50
    
@joriki: You did $-$ this one $-$ and it was. –  Brian M. Scott Dec 19 '12 at 2:14
add comment

1 Answer

up vote 2 down vote accepted

The number of ways of placing $n$ labelled balls in $k$ unlabelled boxes with repetition allowed is $\left\{n\atop k\right\}$, a Stirling number of the second kind. There is a rather ugly explicit formula for them:

$$\left\{n\atop k\right\}=\frac1{k!}\sum_i(-1)^{k-i}\binom{k}ii^n\;.$$

They also satisfy a rather nice Pascal-like recurrence:

$$\left\{n\atop k\right\}=k\left\{n-1\atop k\right\}+\left\{n-1\atop{k-1}\right\}\;,$$

with initial condition $$\left\{n\atop 0\right\}=\left\{0\atop n\right\}=[n=0]\;,$$

where $[n=0]$ is an Iverson bracket. The explanation here of the recurrence is concise but reasonably clear.

If the balls are also unlabelled, you are in effect looking at partitions of $n$ into $k$ parts. The number of such partitions is sometimes denoted by $P(n,k)$ and satisfies the recurrence

$$P(n,k)=P(n-1,k-1)+P(n-k,k)$$

with initial conditions $P(n,k)=0$ for $k>n$, $P(n,n)=1$, and $P(n,0)=[n=0]$. The triangle of these numbers is OEIS A008284, and you’ll find more information and references there.

If you don’t allow repetition, clearly you must have $n\le k$, and since you can’t tell one box from another, there is only one way to distribute the balls, whether they’re labelled or not: $n$ boxes each containing a ball, and $n-k$ empty boxes.

share|improve this answer
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.