# Combinatorics problem with repetition…

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?

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.

• 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. – David Jul 2 '14 at 3:59