1
$\begingroup$

If there are $15$ distinguishable objects; all will be placed into $2$ boxes. There needs to be at least one object in each box. How many ways can you place these objects into the $2$ boxes?

Tried solution

I learned about the stars and bars, however, this method does not work because the objects in question are distinguishable. I'm thinking of it this way:

For each book, there's a choice, it will be placed in box $1$ or box $2$. With two choices on $n$ objects, there are $2^n$ (permutations?). There needs to be at least $1$ object in each box. However there are two combinations where there's not at least $1$ object in each box, so the combination amounts to:

$$2^{15} - 2 = 32768 - 2 = 32766$$

I'm not sure if my solution is right, can anyone verify? Maybe direct me to where I can learn more about the common types of combination and permutation problems?

$\endgroup$
2
$\begingroup$

You are looking for Stirling numbers of the second kind. Specifically, the number of ways to partition $n$ distinct objects into $k$ identical, non-empty groups is given by $S(n,k)$, where $S(n, k)$ are the Stirling numbers of the second kind.

You are right that the stars and bars approach won't work, because the objects are now distinct. However, it is crucial to take into consideration whether the groups (boxes) are distinct or identical. If the boxes are identical, then there are $S(n, k)$ ways; if they are distinct, there are $S(n,k)k!$ ways.

Applying specifically to the context you provided: There are indeed $S(15, 2)2! = 2^{15} - 2$ ways to distribute $15$ distinct objects into $2$ distinct, non-empty boxes. In fact, one can easily generalize this to the result: $S(n, 2) = 2^{n-1} - 1$ for all $n \in \mathbb{Z^+}, n \ge 2$.

$\endgroup$
  • $\begingroup$ In the Wikipedia entry they claimed $S(n,1) = S(n,n) = 1$ which doesn't make sense to me. If I have $15$ objects in one box, they can be permutated $15!$ times. Any explanation to this scenario? $\endgroup$ – B. Lee Sep 29 '14 at 12:56
  • $\begingroup$ Consider a smaller case: $S(2, 1)$. Putting the first object into the box followed by the second object is the same as putting the second object first followed by the first, because in both cases the box ends up with both the objects. $\endgroup$ – Yiyuan Lee Sep 29 '14 at 12:59
  • $\begingroup$ Well, in my case I did care about order. So $\{1,2\}$ differs from $\{2,1\}$, both sets contain $1$ and $2$, but they're in different order, and so the ways to put $2$ objects in $1$ box would be $2$. $\endgroup$ – B. Lee Sep 29 '14 at 13:01
  • 1
    $\begingroup$ If ordering within a group matters then the problem changes completely. For the case of $15$ distinct objects into $2$ identical boxes, there are $\frac{15!\cdot14}{2!}$ ways. First line up the objects in a line ($15!$ permutations), then cut the line into two ($14$ possible positions to cut), then divide by $2!$ since the boxes are identical. $\endgroup$ – Yiyuan Lee Sep 29 '14 at 13:09

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.