Combinatorics

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 dozen bagels with at least three egg bagels and no more than two salty bagels?

Answer 1

shop have 8 different type of bagels as y1, y2, y3, y4, y5, y6, y7, y8 where y1 is egg bagel (y1>=3) and y2 is salty bagel (y2<=2).

y1 + y2 + y3 + y4 + y5 + y6 + y7 + y8=12

By generating function : 

we have to choose coefficient of x¹² in following  eq.

(x³ + x⁴ +....x¹²) (1 + x + x² ) (1 + x + x²...x¹²) (1 + x + x²...x¹²) (1 + x + x²...x¹²) (1 + x + x²...x¹²) (1 + x + x²...x¹²) (1 + x + x²...x¹²) 

as we only need coefficient of x¹² adding variable having power greater than x¹² should not affect the solution. 

(x³ + x⁴ +....∞) (1 + x + x² ) (1 + x + x²...∞) (1 + x + x²...∞) (1 + x + x²...∞) (1 + x + x²...∞) (1 + x + x²...∞) (1 + x + x²...∞) 

 = x³ (1 + x + x²...∞) (1 + x + x² ) (1 + x + x²...∞)⁶

 = x³ (1 + x + x² ) (1 + x + x²...∞)⁷

now we choose coefficient of x⁹ in $\left ( \frac{1-x^{3}}{1-x} \right )\left ( \frac{1}{(1-x)^{7}} \right )$

 = $(1-x^{3})\left ( \frac{1}{(1-x)8} \right )$

General term of Binomial coefficient is $\binom{n+r-1}{r}$ for $\frac{1}{(1-x)^{8}}$

here we have to calculate x⁹ and x⁶

$\binom{8+9-1}{9}$ - $\binom{8+6-1}{6}$ = 11440 - 1716 = 9724

Answer 2

Here we have total 8 types of bagels,  now according to the question we want atleast 3 egg bagels and no more than 2 salty bagels:

So here we start with selecting 3 egg bagels and 0 salty bagels , now we did not want any salty bagels so we remove them

The remaining 9 bagels (12-3)  out of remaining 7 types (excluding salty bagels) can be selected in:

$\binom{15}{9}$ = 5005 ways ( it is the case of number of ways of putting or selecting n indinguishable objects in k distinguishable boxes , which is equal to $\binom{(n+k-1)}{n}$ )

now for 3 egg bagels and 1 salty bagel:

number of ways = $\binom{(8+7-1)}{8}$ = 3003

for 3 egg bagels and 2 salty bagels:

number of ways = $\binom{7+7-1}{7}$ = 1716

therefore total ways are = 5005+3003+1716 = 9724

hence the required answer is 9724...

Comments

aur nirmal...

what about the case when we select more than 3 egg bagels, why you havent included it

---

bcz question says " at least three egg bagels"