Ordering Dozen Doughnuts: How Many Ways?

[coldcell]

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 doesn't 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 don't 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 couldn't figure it out :(

My last bet is 13^4... but that's a wild guess. Help is appreciated.

 

[Gokul43201]

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

 

[coldcell]

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!

 

[Gokul43201]

Okay, I'll make it smaller next time.