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





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!

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

You forgot the "1 outside" case.

[2][] 1 outside
[][2] 1 outside
| cite | improve this answer | |
  • $\begingroup$ Alright well it looks like I need some sleep! Sorry everybody. $\endgroup$ – washboardalex Nov 2 '16 at 10:34

Not the answer you're looking for? Browse other questions tagged or ask your own question.