Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Counting question

  1. Jun 15, 2006 #1
    The doughnut shop has 5 kinds of doughnuts: a, b, c,d and e. There are unlimited supply of each kind. In how many ways can you order a dozen doughnuts?


    Well, my first instict is to simply 5^12. But then I realize aaaab is the same as baaaa... hence the order doesnt matter.

    I'm trying to do it by cases:

    Case 1: one daughnuts only.

    (5 C 1) x 1 = 5 ways

    Case 2: two daughnuts only.

    (5 C 2) x 13 = 130
    But this include one daughnuts, so its 130-5 = 125.

    The problem starts here. I dont know why the arrangements for 2 daughnuts is 13. I got it by simply listing out all the cases.

    Then I tried using simpler problems, like let's say you want to buy 5 daughnuts out of 3 different daughnuts. I can find out the number of ways for this one, but I see no relation if let's say you want to buy 6 daughnuts.

    I sat down for 2 hours and still couldnt figure it out :(

    My last bet is 13^4... but that's a wild guess. Help is appreciated.
     
  2. jcsd
  3. Jun 15, 2006 #2

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Here's a big hint:

    You've got 5 labeled boxes (call them boxes 1,2,3,4,5), one for each type of doughnut. You want to fill these 5 boxes with 12 doughnuts, any number per box.

    Here's how I'm going to represent the boxes:

    1 | 2 | 3 | 4 | 5

    We now have to distribute 12 doughnuts among these boxes. One such distribution might look like the following (I'm hiding the box numbers and representing doughnuts by circles) :

    oo|ooo|o|ooooo|o

    The answer we are looking for is hence nothing but the number of ways of arranging these 12 circles and 4 lines in different patterns. Can you think of a way to count these? Can you then generalize the problem to n doughnuts and k boxes (or k types)?
     
  4. Jun 16, 2006 #3
    Darn I should have thought about grouping the donuts together... how dumb am I :(

    So it's simply 16 C 4, or 16!/(4!12!) since there are 16 items, 4 alike, 12 alike.

    That hint is REALLY big. THANKS!!
     
  5. Jun 16, 2006 #4

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Okay, I'll make it smaller next time.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook