1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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


    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) :


    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


    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