1
$\begingroup$

Ten different people walk into a delicatessen to buy a sandwich. Four always order tuna fish, two always order chicken, two always order roast beef, and two order any of the three types of sandwich.

(a) How many different sequences of sandwiches are possible?

(b) How many different (unordered) collections of sandwiches are possible?

I wasn't quite sure how to answer (a), but here is my attempt at it:

ATTEMPT: We case on the sandwiches the last 2 customers buy:

Case 1: The last 2 customers both get Tuna sandwiches $\implies \frac{10!}{6!2!2!}$

Case 2: The last 2 customers both get chicken $\implies \frac{10!}{4!4!2!}$

Case 3: The last 2 customers both get roast beef $\implies \frac{10!}{4!4!2!}$

Case 4: 1 customer gets tuna, the other chicken $\implies \frac{10!}{5!3!2!}$

Case 5: 1 customer gets tuna, the other roast beef $\implies \frac{10!}{4!3!3!}$

Case 6: 1 customer gets chicken, the other roast beef $\implies \frac{10!}{4!3!3!}$

Adding up the results of our cases, we obtain our result.

I am not sure if this is correct, and am thinking the answer might actually just be $${10 \choose 4}{6 \choose 2}{4 \choose 2}{2 \choose 2}3^2$$ for (a) since the final two customers choose whichever one of the sandwiches they want and there and $3^2$ ways for this to happen.

For (b), I am thinking the answer is $${2+3-1 \choose 2}$$ since we have 2 people and there are 3 sandwiches that the 2 people than choose from.

My question: Remotely correct?

$\endgroup$
3
$\begingroup$

We assume that the people are lined up in a row. We record the sequence of sandwich orders. This will be a $10$-letter word, made up of the letters T, C, and R. But there are restrictions. There are at least $4$ T, at least $2$ C, and at least $2$ R. It seems reasonable to divide into cases, exactly as you did.

1) $6$ T, and $2$ each of the others: The location of the $6$ T can be chosen in $\binom{10}{6}$ ways, and for each the location of the $2$ C can be chosen in $\binom{4}{2}$ ways, for a total of $\binom{10}{6}\binom{4}{2}$.

2) $4$ T, $4$ C, $2$ R: The same reasoning gives $\binom{10}{4}\binom{6}{4}$.

3) $4$ T, $2$ C, $4$ R: Same as in 2).

4) $5$ T, $3$ C, $2$ R or $5$ T, $2$ C, $3$ R: Each makes a contribution of $\binom{10}{5}\binom{5}{3}$.

5) $4$ T, $3$ C, $3$ R: There are $\binom{10}{4}\binom{6}{3}$ sequences of this type.

Now add up.

As to the second problem, we have implicitly listed the possibilities in the solution of the first problem. Your calculation is correct.

$\endgroup$
  • $\begingroup$ Since $\binom{10}6\binom42=10!/6!2!2!$, this is essentially the same as the OP's solution, except that the OP made a slip in case 5. $\endgroup$ – David Jul 2 '14 at 3:59
  • $\begingroup$ Thank you. I have altered the wording to acknowledge that. $\endgroup$ – André Nicolas Jul 2 '14 at 4:14
  • $\begingroup$ Ah wonderful! It's nice to know my thinking was correct :D Probability has been kicking me square in the face lol. $\endgroup$ – user137087 Jul 2 '14 at 4:50
  • $\begingroup$ Yes, apart from a minor slip that has the character of a typo, you had it. At least in one case, it would have been a good idea to indicate why the answer was what you indicated it was. Combinatorics, and probability, can take a while for the intuition to develop. $\endgroup$ – André Nicolas Jul 2 '14 at 4:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.