Combinatorics - Removing Double Counted Cases

Question

Here's my solutions: $$1.)\,(2)(4!)=48$$ $$2.)\,(4)(3)(3!)=72$$ $$3.)\,48+48+3!=102$$

It's the last one I get wrong. The correct answer is 42. The solutions manual of the textbook says the following:

Someone mind explaining what exactly are the double counted cases. Also, what is wrong with my way of doing 1c? I think it is just a simple OR problem, as in an application of the addition principle.

Thank you very much.

Answer 1

Let $A$ be the event that Anya is at the left end of the line; let $B$ be the event that Elena is at the right end of the line. Then the event that Anya is on the left or Elena is on the right or both is $A \cup B$.

We want to find $|A \cup B|$, the number of elements that are in the union of $A$ and $B$. Notice that if we simply add the number of elements in $A$, $|A|$, to the number of elements in $B$, $|B|$, we will have added those elements in the intersection twice. We only want to count them once. Hence, we must subtract them from the total. Therefore, $$|A \cup B| = |A| + |B| - |A \cap B|$$

$|A|$: Anya is at the left end of the line. There is one way to place Anya and $4!$ ways to place the remaining four people in the remaining four positions. Hence, there are $4!$ arrangements in which Anya is at the left end of the line.

$|B|$: Elena is at the right end of the line. There is one way to place Elena and $4!$ ways to place the remaining four people in the remaining four positions. Hence, there are $4!$ arrangements in which Elena is at the right end of the line.

$|A \cap B|$: Anya is at the left end of the line and Elena is at the right end of the line. Anya can be placed in one way, Elena can be placed in one way, and the remaining three people can be arranged in the remaining three positions in $3!$ ways.

Hence, $$|A \cup B| = |A| + |B| - |A \cap B| = 4! + 4! - 3!$$

Answer 2

There are $4!=24$ possible permutations such that Anya is at the left ($3!=6$ or these permutations are that Elena is at the right).

There are $4!=24$ possible permutations such that Elena is at the right ($3!=6$ or these permutations are that Anya is at the left).

The $6$ cases that Anya is at the left and Elena is at the right are counted twice.

So, the number of permutations is $24+24-6=42$.

Answer 3

Consider the three events:

When $Anya$ stands on the left end of the line, there are $4!$ ways to arrange the rest four people (including the cases when $Elena$ stands on the right end of the line): $$A \ \times \ \times \ \times \ \times $$ When $Elena$ stands on the right end of the line, there are $4!$ ways to arrange the rest four people (including the cases when $Anya$ stands on the left end of the line): $$ \times \ \times \ \times \ \times \ E$$ When $Anya$ stands on the left end and $Elena$ stands on the right end of the line, there are $3!$ ways to arrange the rest three people: $$ A \ \times \ \times \ \times \ E$$ Notice that the first event also counted the outcomes of $Elena$ on the right end of the line and the second event also counted the outcomes of $Anya$ on the left end of the line, so when the first two events are added, the outcomes of $Anya$ first and $Elena$ last are double counted, hence must be subtracted once: $$4!+4!-3!=42.$$

Answer 4

For question 3, you've counted a number of combinations twice.

3*3! is the number of ways Anya is on the left and Elena isn't on the right. This is the same number when Elena is on the right and Anya isn't on the left.

When they are both on the right and left, that number is 3!.

So, 3*3! + 3*3! + 3! = 42