# Number of combinations to put n items into 2 bags [closed]

I’m currently working on a finger exercise for mit6.00.2x, a MOOC in computaional thinking, and was having some issues.

First of all: don’t worry, I don’t need you to do my homework for me, I just want to clarify an aspect of the question.

So, the original question asked us to program the computer to find all subsets of a list of items to go into a bag. It said that "The number of possible combinations to put n items into one bag is $2^n$."

So far, so good.

However, the extension of the question is to program the computer to output the amount of combinations possible to put n items into 2 bags: an item must be in either bag or neither.

Now we arrive at my question: At this point it is said that there are $3^n$ possible combinations for this, as each item has three possibilities instead of two.

This makes sense, but I actually did the problem with two items and only found seven combinations:

[][1], 2 outside

[1][], 2 outside

[][], 1 and 2 outside

[][1,2]

[2][1]

[1,2][]

[1][2]

So, there are 2 items, there should be $3^2=9$ combinations, but there are only 7.

I'm sure I'm missing something....help!

• Do you understand why there are $k^n$ ways of putting $n$ items into $k$ bags? Can you prove that? – Raphael Nov 2 '16 at 9:34

[2][] 1 outside