Countil problem

naturewild · 2006-06-15 12:10:16

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.

John E. Franklin · 2006-06-15 14:59:23

1820 possible dozens. Solved in one hour with a TV going!!

John E. Franklin · 2006-06-15 15:00:38

91 + 156 + 198 + 220 + 225 + 216 + 196 + 168 + 135 + 100 + 66 + 36 + 13

John E. Franklin · 2006-06-15 15:05:28

∑ 1..13 + 2 ∑ 1..12 + 3 ∑ 1..11 + 4 ∑ 1..10 + 5 ∑ 1..9 + 6 ∑ 1..8 + 7 ∑ 1..7 + 8 ∑ 1..6 +
+ 9 ∑ 1..5 + 10 ∑ 1..4 + 11 ∑ 1..3 + 12 ∑ 1..2 + 13

John E. Franklin · 2006-06-15 15:11:05

How I did it was to go through first what is the answer if the donut shop only makes one kind of donut.
Then what if donut shop makes 2 kinds of donuts (13 ways).
Then if donut shop makes 3 kinds of donuts ( ∑ 1..13 ways, which is 13 x 7 )
Then if the donut shop makes 4 kinds of donuts.
( ∑ 1..13 + ∑ 1..12 + ∑ 1..11 + ∑ 1..10 + ∑ 1..9 etc etc to ∑ 1..3 + ∑ 1..2 + 1 ways to make a dozen with four kinds of donuts)

Pi Man · 2006-06-16 09:21:39

Naturewild - I started doing this the same way you did. Your Case 1 is correct. Where the whole dozen is made up of the same type of donut, there are 5 differents way. Case 2 is almost correct. There are (5 C 2) ways to pick your 2 donuts but only 11 arrangements for those donuts - 11+1, 10+2, ... ,1+11. (There are 13 ways only if you allow 0 donuts of either type but you already counted those in case 1.) So there are (5 C 2) * 11 = 110 ways for Case 2.

Case 3 - Choose your dozen but only use 3 of the 5 types of donuts. There are (5 C 3) ways to choose your 3 donuts which is 10 ways. Now, how many arrangements (no zeros!) ?

a b c
10 1 1

9 2 1
9 1 2

8 3 1
8 2 2
8 1 3
....
You can see a pattern developing. It's going to be the 1 + 2 + 3 + .... + 10 =55.
So for Case 3, you have 10 * 55 = 550

Case 4: (5 C 4) = 5. How many arrangements?

a b c d
9 1 1 1

8 2 1 1
8 1 2 1
8 1 1 2

7 3 1 1
7 2 2 1
7 2 1 2
7 1 3 1
7 1 2 2
7 1 1 3
....
Another pattern, just not as easy to see. For a=9, you have 1 possibility. For a = 8, you have 3 possibilities (1+2). For a = 7, you have 6 (1+2+3). If you crank through it, you going to have 1+3+6+10+15+21+28+36+45=165. Case 4 total: 5 * 165 = 825

Case5: Only 1 way to pick 5 donut types. Bunch of different arrangements. The pattern is:
1 + (1 + (1+2)) + (1+ (1+2) + (1+2+3)) .... Comes out to 329. So that's the answer for case 5.

Add your 5 cases together and the answer is.... 5 + 110 + 550 + 825 + 329 = 1819. So close to John's answer!!! Probably a simple math error somewhere on my part but I'm going to let you find it!

Pi Man · 2006-06-16 17:36:25

Found my mistake. In case 5, the number of arrangements is 330, not 329.

1 + (1 + (1+2)) + (1+ (1+2) + (1+2+3)) +...
= 1 + 4 + 10 + 20 + 35 + 56 + 84 + 120 = 330

Add your 5 cases together and the answer is.... 5 + 110 + 550 + 825 + 330 = 1820!

Math Is Fun Forum

#1 2006-06-15 12:10:16

Countil problem

#2 2006-06-15 14:59:23

Re: Countil problem

#3 2006-06-15 15:00:38

Re: Countil problem

#4 2006-06-15 15:05:28

Re: Countil problem

#5 2006-06-15 15:11:05

Re: Countil problem

#6 2006-06-16 09:21:39

Re: Countil problem

#7 2006-06-16 17:36:25

Re: Countil problem

Board footer