# Number of ways $n$ distinct objects can be put into two identical boxes

The number of ways in $n$ distinct objects can be put into two identical boxes, so that neither box remains empty.

My Try:: If the question is the numbers of ways in $n$ distinct objects can be put into two Distinct boxes so that no box remains empty, then I can solve easily; this can be done in $2^n-2$ ways

But I do not Understand how can I solve the original Question.

• Your try is correct, since the number of subsets of $n$ distinct objects is $2^n$, and the empty set and the full set are members, and you can put any other member of the powerset in box $A$ and put the complement within the powerset into box $B$. Is there some other original question? – abiessu Oct 8 '13 at 14:57
• Thanks abiessu, My original question is The number of ways in $n$ distinct objects can be put into two identical boxes, so that neither box remains empty. – juantheron Oct 8 '13 at 15:00

The only change needed if the two boxes are identical is to divide the number of ways by two, since swapping boxes produces two different cases when the boxes (as well as the objects) are distinct.

So $2^{n-1} -1$ ways to fill the two identical boxes, subject to having neither empty.

Since there are two boxes, the $n$ objects can be placed in $2^{n}$ ways. And the boxes themselves can be arranged in $2!$ different ways. Dividing by $2!$, we get $2^{n-1}$. But this includes the possibilty that each object is put into only one box. So we must subtract one (because neither box can remain empty), leaving us with $2^{n-1}-1$.

You can split $n$ distinct objects by $n-1$ ways to two parts. Each split can be arranged by two ways: 1) first group to first box and second group to second box or 2) first group to second box and second group to first box. So total arrangments equals:$$2(n-1)$$. For example $3$ distinct objects $A,B,C$ can be arranged to two boxes by $2\cdot 2=4$ ways:

1. $(A)_1$$(BC)_2, 2. (A)_2$$(BC)_1$,
3. $(AB)_1$$(C)_2, 4. (AB)_2$$(C)_1$
where in parenthesis are objects of corresponding split, and the index indicates the box (1 or 2).
For $n=4$, the total arrangements equals: $2\cdot 3 = 6$:
5. $(A)_1(BCD)_2$,
6. $(A)_2(BCD)_1$,
7. $(AB)_1(CD)_2$,
8. $(AB)_2(CD)_1$,
9. $(ABC)_1(D)_2$,
10. $(ABC)_2(D)_1$.