2
$\begingroup$

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!

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Do you understand why there are $k^n$ ways of putting $n$ items into $k$ bags? Can you prove that? $\endgroup$
    – Raphael
    Commented Nov 2, 2016 at 9:34

1 Answer 1

Reset to default
2
$\begingroup$

You forgot the "1 outside" case.

[2][] 1 outside
[][2] 1 outside
Improve this answer
$\endgroup$
1
  • $\begingroup$ Alright well it looks like I need some sleep! Sorry everybody. $\endgroup$
    – washboardalex
    Commented Nov 2, 2016 at 10:34

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