3
$\begingroup$

Let $S_{n,m}$ be the number of ways to put $n$ distinct objects into $m$ non-distinct boxes.

Let $T_{n,m}$ be the number of ways to put $n$ distinct objects into $m$ distinct boxes.

I don't understand why $T_{n,m}$ and $S_{n,m}$ have different values. Please Explain this to me.

$\endgroup$
  • $\begingroup$ As it stands, your question does not have a direct relation with the title (i.e., with Stirling numbers). $\endgroup$ – Marc van Leeuwen Jan 9 '17 at 9:08
  • $\begingroup$ Yes Stirling numbers also require that no box should remain empty, but I suppose It will not change your explanation. $\endgroup$ – Shubhashish Jan 9 '17 at 9:10
3
$\begingroup$

The antonym of "distinct" is "equal", so strictly speaking "$m$ non-distinct boxes" means just one box. This is not what is meant though in this context. It means that among all configurations possible, we should consider equivalent those configurations that can be transformed into one another by permuting the boxes (but not their contents; you can think of it as identifying boxes by a label, which labels are then permuted). Or maybe (since it is hard to envision boxes that cannot be told apart for instance by their position) it is more natural to fix the places of the boxes, in which case one permutes their contents.

For instance, consider placing objects $a,b,c$ into distinct boxes labelled $1,2$; there are $2^3=8$ placements possible. But each placement maps to another one by permuting the labels $1\leftrightarrow2$, so with undistinguished boxes there are $4$ ways, given by the groupings $(\mid a,b,c)$, $(a\mid b,c)$, $(b\mid a,c)$ and $(c\mid a,b)$ (here interchanging left and right of the bar gives an equivalent grouping).

It might seem that $S_{n,m}=\frac{T_{n,m}}{m!}$ since there are $m!$ permutations of the boxes. However, this is not true, and $T_{n,m}=m^n$ is not even divisible by $m!$ in general. This is because not all permutations of boxes give distinct arrangements: permuting empty boxes among each other has no effect. But a similar formula does hold when we insist that each box be non-empty, which is maybe a condition you forgot to mention (as witnessed by your title; without the condition one does not get Stirling numbers of any kind either for $S_{n,m}$ or $T_{n,m}$).

$\endgroup$
2
$\begingroup$

Hint: shuffle the boxes. In which case do you obtain new combinations, and in which you don't?

$\endgroup$
1
$\begingroup$

For example, suppose that $n = 1$ and $m = 2$. Then, $T_{n,m} = 2$. Namely, you can put the ball in box one, or you can put the ball in box two. The boxes are distinct, so these are separate scenarios. However, $S_{n,m} = 1$: you always end up with one box with a ball in it, and one box without any balls. Because the boxes are non-distinct, the two scenarios that we counted for $T_{n,m}$ are considered to be the same, so we count it only once.

$\endgroup$
  • $\begingroup$ Note that OP does not require boxes to be non-empty, (even though the title mentions Stirling numbers). $\endgroup$ – Marc van Leeuwen Jan 9 '17 at 9:07

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.