1

I try to do part b of the question below in a manner similar to part a, but still get stuck. Any hints?

enter image description here

My attempt:

enter image description here enter image description here

ensbana
  • 2,277

1 Answers1

1

Picture three bins and start throwing your elements in them however you like. There is a specific number of ways to do so. However, that also counts the cases that some bin is left empty! You're going to need to subtract those. Then you should promptly add all the ways that left two bins empty, since you counted each twice at the previous step. Finally, the order of the bins doesn't really matter, does it?

Edit your progress if you need extra help.

George K
  • 492
  • "Picture three bins and start throwing your elements in them however you like. There is a specific number of ways to do so." - this should be $3^n$ – ensbana May 13 '18 at 11:46
  • "However, that also counts the cases that some bin is left empty! You're going to need to subtract those." - this should be ${{3} \choose {2}} \times 2^n$ + ${{3} \choose {3}} \times 1$ (i.e. the number of ways to leave 1 bin empty plus the number of ways to leave 2 bins empty). – ensbana May 13 '18 at 11:49
  • "Then you should promptly add all the ways that left two bins empty, since you counted each twice at the previous step." - I think this is where I got stuck in my original attempt. How do I relate this to the numbers in my previous comment? – ensbana May 13 '18 at 11:50
  • 1
    You got $3^n$ correctly. However, when some bin is left empty, that's just (less than) $3\choose 2$ *2^n cases, since these also include the cases when 2 bins are left empty (2 out of the $2^n$ cases leave one of your "chosen bins" empty - do you see that?). To understand why this counts the ways that two bins are left empty twice, a Venn diagram should help you - draw three disks with an empty intersection (why?) and intersecting per two, each representing the case that their respective bin is left empty. Go ahead and color each - see how you colored the intersections twice? – George K May 14 '18 at 14:44
  • 1
    Finally, recall that the order of the bins doesn't matter, and translate that into math. – George K May 14 '18 at 14:44
  • I see! The part that actually tripped me up was that ${{3} \choose {2}}\times 2^n$ + ${{3} \choose {3}} \times 1$ bit. I was a bit hasty when analysing that ${{3} \choose {2}}\times 2^n$ number. Thanks so much for your contribution! – ensbana May 14 '18 at 18:10