Question

A bagel shop has onion bagels, poppy seed bagels, egg bagels, salty bagels, pumpernickel bagels, sesame seed bagels, raisin bagels, and plain bagels. How many ways are there to choose

a) six bagels?

b) a dozen bagels?

c) two dozen bagels?

d) a dozen bagels with at least one of each kind?

e) a dozen bagels with at least three egg bagels and no more than two salty bagels?

Short answer

There are \(1716\) different ways to choose six bagels.

b) There are \(2,629,575\) different ways to choose two dozen bagels.

c) There are \(2,629,575\) different ways to choose two dozen bagels.

d) There are \(330\) different ways to choose a dozen bagels with at least one of each kind.

e) There are \(9724\) different ways to choose a dozen bagels with at least three egg bagels and no more than two salty bagels.

Step-by-step solution

Step 1(a): Definitions

Definition of Permutation (Order is important)

No repetition allowed:\(P(n,r) = \frac{{n!}}{{(n - r)!}}\)

Repetition allowed:\({n^r}\)

Definition of combination (order is important)

No repetition allowed:\(C(n,r) = \left( {\begin{array}{*{20}{c}}n\\r\end{array}} \right) = \frac{{n!}}{{r!(n - r)!}}\)

Repetition allowed:\(C(n + r - 1,r) = \left( {\begin{array}{*{20}{c}}{n + r - 1}\\r\end{array}} \right) = \frac{{(n + r - 1)!}}{{r!(n - 1)!}}\)

with\(n! = n(n - 1) \cdot ..... \cdot 2 \cdot 1\)

Step 2(a): Solution

The order of the elements does not matters (since you will select the same bagels when the order is different), thus we need to use the definition of combination.

The shop has eight types of bagels (onion, poppy seed, egg, salty, pumpernickel, sesame seed, raisin, plain) of which six have to be selected.

We are interested in selecting \(r = 6\)elements from a set with \(n = 8\)elements.

Repetition of elements is allowed

\(\begin{array}{l}C(n + r - 1,r) = C(8 + 6 - 1,6)\\C(13,6) = \frac{\begin{array}{l}\\13!\end{array}}{{6!(13 - 6)!}} = \frac{{13!}}{{6!7!}} = 1716\end{array}\)

Step 1(b): Definitions

Definition of Permutation (Order is important)

No repetition allowed:\(P(n,r) = \frac{{n!}}{{(n - r)!}}\)

Repetition allowed:\({n^r}\)

Definition of combination (order is important)

No repetition allowed:\(C(n,r) = \left( {\begin{array}{*{20}{c}}n\\r\end{array}} \right) = \frac{{n!}}{{r!(n - r)!}}\)

Repetition allowed:\(C(n + r - 1,r) = \left( {\begin{array}{*{20}{c}}{n + r - 1}\\r\end{array}} \right) = \frac{{(n + r - 1)!}}{{r!(n - 1)!}}\)

with\(n! = n(n - 1) \cdot ..... \cdot 2 \cdot 1\)

Step 2(b): Solution

The order of the elements does not matters (since you will select the same bagels when the order is different), thus we need to use the definition of combination.

The shop has eight types of bagels (onion, poppy seed, egg, salty, pumpernickel, sesame seed, raisin, plain) of which twelve(one dozen) have to be selected.

We are interested in selecting \(r = 12\)elements from a set with \(n = 8\)elements.

Repetition of elements is allowed

\(\begin{array}{l}C(n + r - 1,r) = C(8 + 12 - 1,12)\\C(19,12) = \frac{\begin{array}{l}\\19!\end{array}}{{12!(19 - 12)!}} = \frac{{19!}}{{12!7!}} = 50,388\end{array}\)

Step 1(c): Definitions

Definition of Permutation (Order is important)

No repetition allowed:\(P(n,r) = \frac{{n!}}{{(n - r)!}}\)

Repetition allowed:\({n^r}\)

Definition of combination (order is important)

No repetition allowed:\(C(n,r) = \left( {\begin{array}{*{20}{c}}n\\r\end{array}} \right) = \frac{{n!}}{{r!(n - r)!}}\)

Repetition allowed:\(C(n + r - 1,r) = \left( {\begin{array}{*{20}{c}}{n + r - 1}\\r\end{array}} \right) = \frac{{(n + r - 1)!}}{{r!(n - 1)!}}\)

with\(n! = n(n - 1) \cdot ..... \cdot 2 \cdot 1\)

Step 2(c): Solution

The order of the elements does not matters (since you will select the same bagels when the order is different), thus we need to use the definition of combination.

The shop has eight types of bagels (onion, poppy seed, egg, salty, pumpernickel, sesame seed, raisin, plain) of which twenty-four (two dozen) have to be selected.

We are interested in selecting \(r = 24\)elements from a set with \(n = 8\)elements.

Repetition of elements is allowed

\(\begin{array}{l}C(n + r - 1,r) = C(8 + 24 - 1,24)\\C(31,24) = \frac{\begin{array}{l}\\31!\end{array}}{{24!(31 - 24)!}} = \frac{{31!}}{{24!7!}} = 2,629,575\end{array}\)

Step 1(d): Definitions

Definition of Permutation (Order is important)

No repetition allowed:\(P(n,r) = \frac{{n!}}{{(n - r)!}}\)

Repetition allowed:\({n^r}\)

Definition of combination (order is important)

No repetition allowed:\(C(n,r) = \left( {\begin{array}{*{20}{c}}n\\r\end{array}} \right) = \frac{{n!}}{{r!(n - r)!}}\)

Repetition allowed:\(C(n + r - 1,r) = \left( {\begin{array}{*{20}{c}}{n + r - 1}\\r\end{array}} \right) = \frac{{(n + r - 1)!}}{{r!(n - 1)!}}\)

with\(n! = n(n - 1) \cdot ..... \cdot 2 \cdot 1\)

Step 2(d): Solution

The order of the elements does not matters (since you will select the same bagels when the order is different), thus we need to use the definition of combination.

The shop has eight types of bagels (onion, poppy seed, egg, salty, pumpernickel, sesame seed, raisin, plain) of which twelve(one dozen) have to be selected.

We need at least one of each kind. Thus eight of the twelve selected have to be of each type of bagel. Then there are four selections.

We are interested in selecting \(r = 4\)elements from a set with \(n = 8\)elements.

Repetition of elements is allowed

\(\begin{array}{l}C(n + r - 1,r) = C(8 + 4 - 1,4)\\C(11,4) = \frac{\begin{array}{l}\\11!\end{array}}{{4!(11 - 4)!}} = \frac{{11!}}{{4!7!}} = 330\end{array}\)

Step 1(e): Definitions

Definition of Permutation (Order is important)

No repetition allowed:\(P(n,r) = \frac{{n!}}{{(n - r)!}}\)

Repetition allowed:\({n^r}\)

Definition of combination (order is important)

No repetition allowed:\(C(n,r) = \left( {\begin{array}{*{20}{c}}n\\r\end{array}} \right) = \frac{{n!}}{{r!(n - r)!}}\)

Repetition allowed:\(C(n + r - 1,r) = \left( {\begin{array}{*{20}{c}}{n + r - 1}\\r\end{array}} \right) = \frac{{(n + r - 1)!}}{{r!(n - 1)!}}\)

with\(n! = n(n - 1) \cdot ..... \cdot 2 \cdot 1\)

Step 2(e): At least three egg bagels and no salty bagels

The order of the elements does not matters (since you will select the same bagels when the order is different), thus we need to use the definition of combination.

The shop has eight types of bagels (onion, poppy seed, egg, salty, pumpernickel, sesame seed, raisin, plain) of which twelve(one dozen) have to be selected.

we first select three egg bagels, then we still need to select 9 bagels. There are seven possible types of bagels (since we have no salty bagels)

We are interested in selecting \(r = 9\)elements from a set with \(n = 7\)elements.

Repetition of elements is allowed

\(\begin{array}{l}C(n + r - 1,r) = C(7 + 9 - 1,9)\\C(15,9) = \frac{\begin{array}{l}\\15!\end{array}}{{9!(15 - 9)!}} = \frac{{15!}}{{9!6!}} = 5005\end{array}\)

Step 3(d): At least three egg bagels and one salty bagels

The order of the elements does not matters (since you will select the same bagels when the order is different), thus we need to use the definition of combination.

The shop has eight types of bagels (onion, poppy seed, egg, salty, pumpernickel, sesame seed, raisin, plain) of which twelve(one dozen) have to be selected.

we first select three egg bagels, then we still need to select eight bagels. There are seven possible types of bagels (since we have no salty bagels)

We are interested in selecting \(r = 8\)elements from a set with \(n = 7\)elements.

Repetition of elements is allowed

\(\begin{array}{l}C(n + r - 1,r) = C(7 + 8 - 1,8)\\C(14,8) = \frac{\begin{array}{l}\\14!\end{array}}{{8!(14 - 8)!}} = \frac{{14!}}{{8!6!}} = 3003\end{array}\)

Step 4(d): At least three egg bagels and two salty bagels

The order of the elements does not matters (since you will select the same bagels when the order is different), thus we need to use the definition of combination.

The shop has eight types of bagels (onion, poppy seed, egg, salty, pumpernickel, sesame seed, raisin, plain) of which twelve(one dozen) have to be selected.

we first select three egg bagels, then we still need to select seven bagels. There are seven possible types of bagels (since we have no salty bagels)

We are interested in selecting \(r = 7\)elements from a set with \(n = 7\)elements.

Repetition of elements is allowed

\(\begin{array}{l}C(n + r - 1,r) = C(7 + 7 - 1,7)\\C(13,7) = \frac{\begin{array}{l}\\13!\end{array}}{{7!(13 - 7)!}} = \frac{{13!}}{{7!6!}} = 1716\end{array}\)

So for at least three egg bagels and no more than two salty bagels we get the answer from the sum rule.

Use the sum rule (from the conclusions of step two three and four we get):

\(5005 + 3003 + 1716 = 9724\)

There are \(9724\) different ways to choose a dozen bagels with at least three egg bagels and no more than two salty bagels.