Combinatorics problem with repetition...

Question

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?

(This happens to be Problem $8$ in Section $5.3$ of Alan Tucker's Applied Combinatorics textbook.)

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?

Answer 1

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.

Answer 2

The answer given is correct, as is that of André Nicolas, but I'd like to enumerate one that (while functionally identical) might feel nicer to some people.

This focuses primarily on the first problem.

---

Multinomial Coefficient Overview:

For this, we define a "multinomial coefficient." It is analogous to the binomial coefficient, but now we have $m$ different indices on bottom:

$$\binom{n!}{k_1 , k_2 , \cdots , k_m} := \frac{n!}{k_1! \cdot k_2! \cdot \ldots \cdot k_m!}$$

We also have the $k_1+k_2 + \cdots + k_m = n$ by convention. Note an equality with the ordinary binomial coefficient:

$$\binom{n}{k} \equiv \binom{n}{k,n-k}$$

Where does this multinomial coefficient come from?

Suppose we have a group of $n$ objects, divided into $m$ groups. There are $k_i$ objects in the $i$th group, all functionally identical. Now let's try to find the number of ways to permute these $n$ objects, as a sequence.

There are $n!$ overall arrangements, but there is double-counting amongst each of the $m$ groups. Specifically, given a permutation, the objects in group $i$ can be permuted themselves in $k_i!$-many ways, giving us (for our purposes) the same overall permutation. Hence, we divide $n!$ by $k_i!$ for each $i$, giving the answer.

The multinomial coefficient also arises in the multinomial theorem, analagous to the binomial expansion and binomial theorem, but those details I'll leave for the reader to investigate on their own.

---

Example: Suppose we have $4$ red balls, $5$ blue balls, $6$ green balls, and $7$ yellow balls. We arrange them in a line. How many arrangements are possible?

In this case, there are $22$ objects in all, with groups of sizes $k_1 = 4$, $k_2 = 5$, $k_3 = 6$, and $k_4 = 7$. Then the number of arrangements is

$$\binom{22}{4,5,6,7} = 107,550,162,720$$

For what it's worth, in WolframAlpha, we have

$$\texttt{multinomial(k_1,k_2,...,k_m)} \equiv \binom{k_1+k_2+\ldots+k_m}{k_1,k_2,\ldots,k_m}$$

to make calculations easier, but obviously this is doable by hand, if tedious.

---

Onto the Given Problem:

In this case, we are - for all intents and purposes - wondering how many rearrangements there are to

$$TTTTCCRRxy$$

where $x,y \in \{T,C,R\}$ represent the latter two people in the problem statement. Working over each distinct $\{x,y\} \subseteq \{T,C,R\}$, we can find the number of arrangements. Given some $x,y$, the arrangements for that given case are

$$\binom{10}{ k_T,k_C,k_R }$$

for $k_T$ the number of $T$'s present, $k_C$ the number of $C$'s, and $k_R$ the number of $R$'s.

The end result ends up boiling down to precisely the same casework and calculations as in the OP, giving $16,800$ as the final answer.

Of course, the casework also leads immediately to the answer to the second part, as already commented upon.