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$

1 Answer 1

3
$\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$
4
  • $\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, 2014 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, 2014 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, 2014 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, 2014 at 13:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .