Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫  π  -¹ ² ³ °

You are not logged in.

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

naturewild
Member
Registered: 2005-12-04
Posts: 30

### Countil problem

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.

Offline

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

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,588

### Re: Countil problem

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

igloo myrtilles fourmis

Offline

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

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,588

### Re: Countil problem

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

igloo myrtilles fourmis

Offline

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

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,588

### Re: Countil problem

∑ 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

igloo myrtilles fourmis

Offline

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

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,588

### Re: Countil problem

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)

igloo myrtilles fourmis

Offline

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

Pi Man
Guest

### Re: Countil problem

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!

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

Pi Man
Guest

### Re: Countil problem

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!