Vincenzo's Delicious Deli

There are $4!$ ways to arrange the meats. After the meats have been arranged, there are 5 different spaces between the meats or before or after the meats. The two types of cheese can be inserted into these spaces in $5 \times 4$ different ways. Thus, there are $20\times 4!$ total ways to arrange the meat and cheese, for a total of 480 ways.

Rather than trying to figure out the number of ways the 6 food items (4 meat and 2 cheese) can be arranged with the two types of cheese not next to each other directly , it is better to subtract the number of ways of arrangement in which they are together from the total number of possible ways of arranging the 6 food items. The 6 food items can be arranged in $6!$ ways, while if we consider the two types of cheese always next to each other the number of cases are $5! \times 2!$ (we consider the two types of cheese as a single item, so we effectively have 5 items which can be arranged in $5!$ ways, on the top of which the provolone and asiago can interchange places, so multiply by $2!$ ). So, the number of cases in which they are not next to each other are $6! - (5!\times2!) = 480$ .

total number of arrangements without restrictions= 6!

arrangements with the two cheese next to each other= 5! x 2!

arrangements with the two cheese not next to each other= 6! - (5! x 2!)= 480

Consider the sandwich s A s B s C s D s Let A, B, C, D be the 4 types of meat and 5s represent the spaces three in between and one each at the ends.. There 5P2 ways to insert the cheese in the spaces occupy by s, so that they are not together and 4! arrangements for the meats. Number of arrangements = (5P2)(4!) = 420

We can imagine Vincenzo's sandwich as a column of 6 slots, in which we have 6 elements to place: 4 different layers of meat $+$ 2 different layers of cheese. We shall call these m1, m2, m3, m4, c1 and c2 respectively.

No matter how the cheese will be placed, the meat layers will follow a certain hierarchy. For example, the solutions (c1, m3, c2, m2, m1, m4) and (c1, m3, m2, m1, m4, c2) both follow the same meat hierarchy: (m3, m2, m1, m4). Since we can rearrange this particular example and we are dealing with 4 different elements, we come across P(4) different hierarchies, where P(4) is the number of permutations of 4 distinct elements. P(n), when n is a natural number, equals n! or $1 \times 2 \times ... \times (n-1) \times n$ . Therefore, P(4) equals $1 \times 2 \times 3 \times 4=24$ .

Let's now take a look at the cheese layers. We have 6 slots and 2 layers of cheese. We will start off by placing c1 and c2 in the virtual sandwich and we will mark the empty slots with 'x'. Firstly, let's place c1 in the first slot. The sandwich will look like this: (c1, x, x, x, x, x). Then, we must place c2. We know that c2 must not touch c1, so we cannot place it in the second slot. Since the first one is taken by c1, we are left with slots 3, 4, 5 and 6. That means 4 ways we can assign a sandwich slot to c2, knowing that c1 already takes up slot 1. In each of these 4 ways, we replace a certain 'x' in the above structure with 'c1' and we are left with 4 'x'-es to be replaced with m1, m2, m3 and m4, in any order. We can decide which m gets to replace which x in 24 ways, by using one of the meat hierarchies. so we have 4 x 24 ways to place m1, m2, m3, m4 and c2, given that c1 takes up slot 1. We use the same logic when placing c1 in slot 6, since c2 cannot take up slot 5, so we are left with 4 options for c2 and, given any position of c2, P(4) options for the meat layers. There is a difference when placing c1 in a non-marginal slot, because these have 2 adjacent slots, so we only have $6-3=3$ options for placing c2 (for example, if c1 goes in slot 3, c2 can occupy slots 1, 5 or 6). We still have P(4) hierarchies for the meat, though.

To conclude with the answer, we have to count the ways in which we can place all of the 6 elements in the slots. We will add up the number of options we have when placing c1 in a marginal or a non-marginal slot, respectively. There are $4 \times 24$ ways for either slot 1 or 6 and $3 \times 24$ for either slot 2, 3, 4 or 5. So the answer is $24 ( 4+4+3+3+3+3)=24 \times 20=480$ .

First, place the meats in order. Because the cheese must be ordered in a special way (neither cheese can be next to the other), we will save the ordering of the cheese until the end. Since there are four types of meat, and we must order all four of them (per the statement of the problem, order matters), there are $4!=24$ ways to place the meats in order on the sandwich.

We now place the cheeses onto the sandwich. Since the cheeses cannot be next to one another, we must have at least one meat between them. Holding the ordering of the meat as a constant, the number of ways to place the cheeses with one meat between them can be verified by iteration and exhaustion as $8$ . The number of ways to place the cheeses with two meats between them is (using the same method) $6$ . The number of ways to place the cheeses with three meats between them is $4$ , and placing the cheeses at either side of the stack of meat gives $2$ possibilities for ordering. In all, for each placement of meats, there are $8+6+4+2=20$ placements for the cheeses.

Therefore, the number of arrangements for the sandwich is $24\cdot 20=480$ .

There are $6! = 720$ ways to arrange the items on the sandwich with no restriction. If we consider the two cheeses as being a single item (which will make them adjacent to each other), there are $5! = 120$ ways of arranging the combined cheese and four meats on the sandwich. There are also 2 possible ways of ordering the cheese within the stack so there are $240$ ways to make the sandwich with the cheeses adjacent. Thus there are $720 - 240 = 480$ ways for Vincenzo to make his sandwich.