2
$\begingroup$

It's my second try to solve the question I posted here Combinatorics question - How many different ways to change sitting order

I got some really good advice, but no one said the answer, I solved it, and before I rush into the exam, I'd like to have it verified. I solved it using inclusion exclusion.

The question:

Six children (a through f) are playing on a carousel with 6 seats (numbered one to six) such that a is sitting in front of d, b is sitting in front of e, and c is sitting in front of f.

How many ways are there to change the sitting order, such that no child is sitting in front of the child they are sitting in front of now?

My answer

First, let us count the total number of combinations. There are 6 seats and 6 children, therefore there are $6!$ different combinations (note that it's $6!$ and not $5!$ since the seats are numbered, and rotating right or left is a totally different order).

let $A$ be the set of sitting arrangements such that $a$ sits infront of $d$.

let $B$ be the set of sitting arrangements such that $b$ sits infront of $e$.

let $C$ be the set of sitting arrangements such that $c$ sits infront of $f$.

Let's count $|A|$. First we need to choose a seat for child $a$. he has $6$ options to choose from. As soon as he chose, child $d$ has no option but to sit infront of him. and now we are left with $4$ seats and $4$ children, there are $4!$ options for this, so $|A|=6*4! = 144$.

Due to symmetry, $|B|=|C|=144$ as well.

let's count $|A\cap B|$. First we choose a seat for $a$, that's $6$ options, $d$ sits infront him of immediatly. then choose a place for $b$, we have $4$ options, $e$ sits infront of him immediately. then we are left with $2$ seats and $2$ children, that's $2!$ options, so overall $|A\cap B|=6*4*2!=48$.

Due to symmetry, $|A\cap C|=|B\cap C|=48$ as well.

it is clear to see that $|A\cap B\cap C|=1$.

Using inclusion-exclusion:

$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|=3*144-3*48+1=289$.

There are $289$ bad arrangements, and there are $6!=720$ arrangements in total, so there are $720-289=431$ good arrangements and that is my final answer.

Is this correct?

$\endgroup$
1
$\begingroup$

Your answer is not quite correct. You set up the inclusion-exclusion correctly, but there are two modifications you need to make to your counting:

  1. In the calculation of $|A \cap B|$, you say there are 4 options for $b$. In fact, there are only $3$ options -- the seat behind $b$ has to be empty so that there is a place left for $e$. So $|A \cap B| = 6 \cdot 3 \cdot 2! = 36$.

  2. You also have the wrong value for $|A \cap B \cap C|$. There are $6$ choices for $a$, and then $d$ has to sit right behind him. Then, there are four remaining seats

    d  a  _  _  _  _
    

    The only way we can fill these seats is with $e, b, f, c$ or $f, c, e, b$. So in fact, $|A \cap B \cap C| = 6 \cdot 2 = 12$.

Your final calculation will be \begin{align*} |A \cup B \cup C| &= |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| \\ &= 3(144) - 3(36) + (12) \\ &= 336 \\ \end{align*}

So the answer, $720 - 336 = \boxed{384}$.

$\endgroup$
  • $\begingroup$ I think $|A\cap B|=5\times 3\times2!$ since $A$ has exactly $5$ options, since the seat behind $a$ has to be empty. $\endgroup$ – Hai Minh Jul 20 '14 at 4:08
  • $\begingroup$ @HaiMinh The carousel is round, i.e. they are sitting around in a circle. Otherwise you would be correct. $\endgroup$ – 6005 Jul 22 '14 at 4:07

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.